15,123,029 members
Home / Discussions / Algorithms

# Algorithms

 Re: Lock free algorithms Joe Woodbury6-Sep-14 12:49 Joe Woodbury 6-Sep-14 12:49
 Re: Lock free algorithms SledgeHammer016-Sep-14 13:55 SledgeHammer01 6-Sep-14 13:55
 Re: Lock free algorithms Joe Woodbury6-Sep-14 14:11 Joe Woodbury 6-Sep-14 14:11
 Re: Lock free algorithms SledgeHammer016-Sep-14 14:37 SledgeHammer01 6-Sep-14 14:37
 Re: Lock free algorithms Joe Woodbury6-Sep-14 14:44 Joe Woodbury 6-Sep-14 14:44
 Algorithm for comparing word with randomly distributed substring asdf232111-Jul-14 0:06 asdf23211 1-Jul-14 0:06
 Re: Algorithm for comparing word with randomly distributed substring Sanmayce3-Jul-14 8:15 Sanmayce 3-Jul-14 8:15
 Re: Algorithm for comparing word with randomly distributed substring Sanmayce5-Jul-14 8:19 Sanmayce 5-Jul-14 8:19
 Okay, this is more serious, 31 patterns are needed to exhaust your request. 0 internal '*': Step01: *ABCDE* 1 internal '*': Step02: *ABCD*E* Step03: *ABC*DE* Step04: *AB*CDE* Step05: *A*BCDE* 2 internal '*': Step06: *A*B*CDE* Step07: *A*BC*DE* Step08: *A*BCD*E* Step09: *AB*C*DE* Step10: *AB*CD*E* Step11: *ABC*D*E* 3 internal '*': Step12: *A*B*C*DE* Step13: *A*B*CD*E* Step14: *A*BC*D*E* Step15: *AB*C*D*E* Above 15 patterns are optional, they would yield hits with 'high' rank earlier than all the 31 ones below. Finding all substrings (without elision): Step01+15: *A*B*C*D*E* Finding all substrings (with elision): C(5,4) equals number of wildcard patterns, 5 choose 4 = 5!/(4!*(5-4)!) = 5*4*3*2*1/(4*3*2*1*1) = 5 Step02+15: *B*C*D*E* Step03+15: *A*C*D*E* Step04+15: *A*B*D*E* Step05+15: *A*B*C*E* Step06+15: *A*B*C*D* C(5,3) equals number of wildcard patterns, 5 choose 3 = 5!/(3!*(5-3)!) = 5*4*3*2*1/(3*2*1*2*1) = 10 Step07+15: *A*B*C* Step08+15: *A*B*D* Step09+15: *A*B*E* Step10+15: *A*C*D* Step11+15: *A*C*E* Step12+15: *A*D*E* Step13+15: *B*C*D* Step14+15: *B*C*E* Step15+15: *B*D*E* Step16+15: *C*D*E* C(5,2) equals number of wildcard patterns, 5 choose 2 = 5!/(2!*(5-2)!) = 5*4*3*2*1/(2*1*3*2*1) = 10 Step17+15: *A*B* Step18+15: *A*C* Step19+15: *A*D* Step20+15: *A*E* Step21+15: *B*C* Step22+15: *B*D* Step23+15: *B*E* Step24+15: *C*D* Step25+15: *C*E* Step26+15: *D*E* C(5,1) equals number of wildcard patterns, 5 choose 1 = 5!/(1!*(5-1)!) = 5*4*3*2*1/(1*4*3*2*1) = 5 Step27+15: *A* Step28+15: *B* Step29+15: *C* Step30+15: *D* Step31+15: *E* In essence the number e.g. C(5,4) equals all ways to order any four of five elements, which is 5!/(5-4)! divided by all ways to order any group of 4, which is 4!. Thus, the number of distinct ways to choose 4 out of 5 is 120 divided by 24. By chance I wrote the fastest wildcard search function (iterative) so these 31 patterns won't be much of a problem: Copy Code ```int WildcardMatch_Iterative_Kaze(const char* mask, const char* name) { // Revision 1: /* const char* maskSTACK; const char* nameSTACK; int BacktrackFlag = 0; Backtrack: for (nameSTACK = name, maskSTACK = mask; *nameSTACK; ++nameSTACK, ++maskSTACK) { if (*maskSTACK == '&') { mask = maskSTACK+1; if (!*mask) return 1; name = nameSTACK; BacktrackFlag = -1; goto Backtrack; } //else if (*maskSTACK == '+') { //} else { else if (*maskSTACK != '+') { //if (tolower(*nameSTACK) != tolower(*maskSTACK)) { // These 'tolower's are outrageous, they hurt speed BADLY, in real-world usage both should have been lowercased outwith the 'for'. if (*nameSTACK != *maskSTACK) { if (!BacktrackFlag) return 0; name++; goto Backtrack; } } } while (*maskSTACK == '&') ++maskSTACK; return (!*maskSTACK); */ // Revision 2, 2013-Nov-30: const char* maskSTACK; const char* nameSTACK; //int BacktrackFlag = 0; // No need of it in rev.2 /* // Simplest heuristic with SUPEROVERHEAD enforced: trying to skip the whole wildcard section by comparing the two arrays order 1 of mask&name. int i; unsigned char maskOrder1[256]; unsigned char nameOrder1[256]; for (i='a'; i <= 'z'; i++) { maskOrder1[i]=0; nameOrder1[i]=0;} for (i=0; i < strlen(mask); i++) maskOrder1[mask[i]]=1; for (i=0; i < strlen(name); i++) nameOrder1[name[i]]=1; // Assuming the incoming strings are already lowercased (as it should for speed) and if we don't have matching alphabet parts (from mask side) means we don't need to compare any further i.e. the match fails. for (i='a'; i <= 'z'; i++) if ( maskOrder1[i] == 1 && nameOrder1[i] == 0 ) return 0; */ /* int i; for (i=0; i < strlen(mask); i++) { if ( mask[i] != '&' && mask[i] != '+' ) if ( !memchr(name,mask[i],strlen(name)) ) return 0; } */ /* Backtrack: for (nameSTACK = name, maskSTACK = mask; *nameSTACK; ++nameSTACK, ++maskSTACK) { if (*maskSTACK == '&') { mask = maskSTACK+1; if (!*mask) return 1; name = nameSTACK; BacktrackFlag = -1; goto Backtrack; } //else if (*maskSTACK == '+') { //} else { else if (*maskSTACK != '+') { //if (tolower(*nameSTACK) != tolower(*maskSTACK)) { // These 'tolower's are outrageous, they hurt speed BADLY, in real-world usage both should have been lowercased outwith the 'for'. if (*nameSTACK != *maskSTACK) { if (!BacktrackFlag) return 0; // Stupid branching, SLOW! name++; goto Backtrack; } } } */ // Here, outside the main/second 'for', in order to avoid branching we need to set the old/obsolete BacktrackFlag i.e. we need first occurrence of '&': for (name, mask; *name; ++name, ++mask) { if (*mask == '&') { goto Backtrack; } //else if (*mask == '+') { //} else { else if (*mask != '+') { if (*name != *mask) { return 0; } } } // We are entering the main/second 'for' with mask pointing to '&' as if BacktrackFlag is already set in the very first iteration at first condition: Backtrack: for (nameSTACK = name, maskSTACK = mask; *nameSTACK; ++nameSTACK, ++maskSTACK) { if (*maskSTACK == '&') { mask = maskSTACK+1; if (!*mask) return 1; name = nameSTACK; //BacktrackFlag = -1; goto Backtrack; } //else if (*maskSTACK == '+') { //} else { else if (*maskSTACK != '+') { //if (tolower(*nameSTACK) != tolower(*maskSTACK)) { // These 'tolower's are outrageous, they hurt speed BADLY, in real-world usage both should have been lowercased outwith the 'for'. if (*nameSTACK != *maskSTACK) { //if (!BacktrackFlag) return 0; // Stupid branching, SLOW! name++; goto Backtrack; } } } while (*maskSTACK == '&') ++maskSTACK; return (!*maskSTACK); }``` If you can write code generating, in particular, those 31+15 patterns you by all means could name the algorithm after your name, vanity is the strangest teachers of all, one Japanese aikidoka said that. In case of you being stronger than pride my proposal is to call the whole process 'bunyipping', SOED defines 'bunyip' as: bunyip, noun. Austral. M19. [Aboriginal.] A fabulous monster of swamps and lagoons. A ringy word, yes? Quite as 'troll' but not burdened with negativity of internetish jargon. troll v. tr. Slang: To patrol (an area) in search for someone or something: "[Criminals] troll bus stations for young runaways" (Pete Axthelm). n. A supernatural creature of Scandinavian folklore, variously portrayed as a friendly or mischievous dwarf or as a giant, that lives in caves, in the hills, or under bridges. /HERITAGE/
 Cubesort Gregorius van den Hoven22-Jun-14 5:09 Gregorius van den Hoven 22-Jun-14 5:09
 Re: Cubesort Sanmayce28-Jun-14 9:02 Sanmayce 28-Jun-14 9:02
 Re: Cubesort Gregorius van den Hoven29-Jun-14 10:58 Gregorius van den Hoven 29-Jun-14 10:58
 Re: Cubesort Sanmayce30-Jun-14 7:48 Sanmayce 30-Jun-14 7:48
 Re: Cubesort Gregorius van den Hoven12-Jul-14 5:01 Gregorius van den Hoven 12-Jul-14 5:01
 Re: Cubesort Sanmayce3-Jul-14 5:30 Sanmayce 3-Jul-14 5:30
 Reduce a Q2SAT formula Apurvgupta15-Jun-14 21:48 Apurvgupta 15-Jun-14 21:48
 Fastest textual decompression in C Sanmayce10-May-14 9:54 Sanmayce 10-May-14 9:54
 Re: Fastest textual decompression in C Richard MacCutchan10-May-14 22:46 Richard MacCutchan 10-May-14 22:46
 Re: Fastest textual decompression in C Sanmayce12-May-14 1:18 Sanmayce 12-May-14 1:18
 Re: Fastest textual decompression in C Richard MacCutchan12-May-14 2:24 Richard MacCutchan 12-May-14 2:24
 Re: Fastest textual decompression in C Chris Losinger23-May-14 4:12 Chris Losinger 23-May-14 4:12
 Re: Fastest textual decompression in C Sanmayce24-May-14 8:17 Sanmayce 24-May-14 8:17
 The Bessel-Overhauser Spline interpolation - suitable values for the weight function Kenneth Haugland4-Apr-14 0:34 Kenneth Haugland 4-Apr-14 0:34
 Re: The Bessel-Overhauser Spline interpolation - suitable values for the weight function Kenneth Haugland6-Apr-14 1:30 Kenneth Haugland 6-Apr-14 1:30
 Factoring algorithm Member 41945931-Apr-14 5:46 Member 4194593 1-Apr-14 5:46
 Re: Factoring algorithm Bernhard Hiller1-Apr-14 21:44 Bernhard Hiller 1-Apr-14 21:44
 Last Visit: 31-Dec-99 19:00     Last Update: 6-Dec-21 1:48 Refresh ᐊ Prev1...47484950515253545556 Next ᐅ