Click here to Skip to main content
15,123,029 members
Home / Discussions / Algorithms
   

Algorithms

 
GeneralRe: Lock free algorithms Pin
Joe Woodbury6-Sep-14 12:49
professionalJoe Woodbury6-Sep-14 12:49 
GeneralRe: Lock free algorithms Pin
SledgeHammer016-Sep-14 13:55
MemberSledgeHammer016-Sep-14 13:55 
GeneralRe: Lock free algorithms Pin
Joe Woodbury6-Sep-14 14:11
professionalJoe Woodbury6-Sep-14 14:11 
GeneralRe: Lock free algorithms Pin
SledgeHammer016-Sep-14 14:37
MemberSledgeHammer016-Sep-14 14:37 
GeneralRe: Lock free algorithms Pin
Joe Woodbury6-Sep-14 14:44
professionalJoe Woodbury6-Sep-14 14:44 
QuestionAlgorithm for comparing word with randomly distributed substring Pin
asdf232111-Jul-14 0:06
Memberasdf232111-Jul-14 0:06 
AnswerRe: Algorithm for comparing word with randomly distributed substring Pin
Sanmayce3-Jul-14 8:15
MemberSanmayce3-Jul-14 8:15 
AnswerRe: Algorithm for comparing word with randomly distributed substring Pin
Sanmayce5-Jul-14 8:19
MemberSanmayce5-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:
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/
QuestionCubesort Pin
Gregorius van den Hoven22-Jun-14 5:09
MemberGregorius van den Hoven22-Jun-14 5:09 
AnswerRe: Cubesort Pin
Sanmayce28-Jun-14 9:02
MemberSanmayce28-Jun-14 9:02 
GeneralRe: Cubesort Pin
Gregorius van den Hoven29-Jun-14 10:58
MemberGregorius van den Hoven29-Jun-14 10:58 
AnswerRe: Cubesort Pin
Sanmayce30-Jun-14 7:48
MemberSanmayce30-Jun-14 7:48 
GeneralRe: Cubesort Pin
Gregorius van den Hoven12-Jul-14 5:01
MemberGregorius van den Hoven12-Jul-14 5:01 
AnswerRe: Cubesort Pin
Sanmayce3-Jul-14 5:30
MemberSanmayce3-Jul-14 5:30 
QuestionReduce a Q2SAT formula Pin
Apurvgupta15-Jun-14 21:48
MemberApurvgupta15-Jun-14 21:48 
QuestionFastest textual decompression in C Pin
Sanmayce10-May-14 9:54
MemberSanmayce10-May-14 9:54 
AnswerRe: Fastest textual decompression in C Pin
Richard MacCutchan10-May-14 22:46
mveRichard MacCutchan10-May-14 22:46 
GeneralRe: Fastest textual decompression in C Pin
Sanmayce12-May-14 1:18
MemberSanmayce12-May-14 1:18 
GeneralRe: Fastest textual decompression in C Pin
Richard MacCutchan12-May-14 2:24
mveRichard MacCutchan12-May-14 2:24 
GeneralRe: Fastest textual decompression in C Pin
Chris Losinger23-May-14 4:12
professionalChris Losinger23-May-14 4:12 
GeneralRe: Fastest textual decompression in C Pin
Sanmayce24-May-14 8:17
MemberSanmayce24-May-14 8:17 
QuestionThe Bessel-Overhauser Spline interpolation - suitable values for the weight function Pin
Kenneth Haugland4-Apr-14 0:34
professionalKenneth Haugland4-Apr-14 0:34 
AnswerRe: The Bessel-Overhauser Spline interpolation - suitable values for the weight function Pin
Kenneth Haugland6-Apr-14 1:30
professionalKenneth Haugland6-Apr-14 1:30 
QuestionFactoring algorithm Pin
Member 41945931-Apr-14 5:46
MemberMember 41945931-Apr-14 5:46 
AnswerRe: Factoring algorithm Pin
Bernhard Hiller1-Apr-14 21:44
MemberBernhard Hiller1-Apr-14 21:44 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.