Pattern Matcher

JavaScript performance comparison

Test case created by Nathan Hammond and last updated

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
  // RegEx version.
  function matcherRegEx(pattern, teststring) {
  	if (pattern.length > teststring.length) { return false; }
  
  	// Convert pattern to an array.
  	pattern = [].slice.call(pattern);
  
  	var patterninfo = Object.create(null);
  	var norepeat = true;
  
  	var backrefcount = 1;
  	var regex = "";
  
  	pattern.forEach(function(patternkey, index) {
  		if (patterninfo[patternkey] !== undefined) {
  			norepeat = false;
  			regex += "\\" + patterninfo[patternkey];
  		} else {
  			patterninfo[patternkey] = backrefcount++;
  			regex += "(.+)"
  		}
  	});
  
  	if (norepeat) { return true; }
  
  	return new RegExp(regex).test(teststring);
  }
  
  // Space delimited pattern matching.
  function matcherString(pattern, teststring) {
  	if (pattern.length > teststring.length) { return false; }
  
  	// Convert pattern and teststring to an array.
  	pattern = [].slice.call(pattern);
  	var testarray = teststring.split(' ');
  
  	var identified = Object.create(null);
  
  	return pattern.every(function(patternkey, index) {
  		if (identified[patternkey] !== undefined && identified[patternkey] !== testarray[index]) {
  			return false;
  		}
  
  		identified[patternkey] = testarray[index];
  		return true;
  	});
  }
  
  // Non-delimited pattern matching without regex.
  function matcherCustom(pattern, teststring) {
  	var teststringlength = teststring.length;
  	var patternlength = pattern.length;
  	if (patternlength > teststringlength) { return false; }
  
  	// Convert pattern to an array.
  	pattern = [].slice.call(pattern);
  
  	var patterninfo = Object.create(null);
  	var patterninfokeys = []; // Exists because Object.keys isn't available for dicts.
  
  	pattern.forEach(function(patternkey, index) {
  		if (patterninfo[patternkey] !== undefined) {
  			var occurrences = patterninfo[patternkey].indices.push(index);
  			patterninfo[patternkey].max = Math.floor((teststringlength - (patternlength - occurrences))/occurrences);
  		} else {
  			patterninfokeys.push(patternkey);
  			patterninfo[patternkey] = {
  				indices: [index],
  				min: 1,
  				max: teststringlength - (pattern.length - 1)
  			}
  		}
  	});
  
  	// Not repeating means it will default match everything.
  	if (patterninfokeys.length === patternlength) { return true; }
  
  	// "Even" patterns will only match "even" test strings.
  	// Eliminates 1/4 of the problem space.
  	var even = patterninfokeys.every(function(patternkey) {
  		return patterninfo[patternkey].length % 2 === 0;
  	});
  	if (even && teststringlength % 2 !== 0) { return false; }
  
  	// Adjacent single pattern keys can be coalesced.
  	// NOTE: this raises the minimum matching pattern length.
  	// NOTE: They're guaranteed to be adjacent in the data structure due to how they're added.
  	var previouspatternkey;
  	var offset = 0;
  	patterninfokeys = patterninfokeys.filter(function(patternkey) {
  		// First time through we need to simply skip.
  		if (!previouspatternkey) {
  			previouspatternkey = patternkey;
  			return true;
  		}
  
  		var occurrences = patterninfo[patternkey].indices.length;
  		var previousoccurrences = patterninfo[previouspatternkey].indices.length;
  
  		if (occurrences === 1 && previousoccurrences === 1) {
  			// Update the previous element.
  			patterninfo[previouspatternkey].min++;
  			patterninfo[previouspatternkey].max = Math.floor((teststringlength - (patternlength - patterninfo[previouspatternkey].min))/occurrences);
  
  			// Splice the pattern key out of the pattern array.
  			// Count how many we've removed, that will be our offset for future iterations.
  			// (Each removal results in the index being off by one more.)
  			pattern.splice(patterninfo[patternkey].indices[0]-offset++,1);
  
  			// This patternkey will be filtered out.
  			return false;
  		} else {
  			// We can move on to the next pattern.
  			previouspatternkey = patternkey;
  			return true;
  		}
  	});
  
  	// Now we check to see what the possible remaining solutions look like.
  	var stack = [];
  	var answer = permute(patterninfokeys);
  
  	// Unused, could be done instead of maintaining the offset.
  	function reduceIndices(compareIndex) {
  		patterninfokeys.forEach(function(patternkey) {
  			patterninfo[patternkey].indices = patterninfo[patternkey].indices.map(function(index) {
  				return index > compareIndex ? --index : index;
  			});
  		});
  	}
  
  	function permute(patterninfokeys) {
  		var answer = false;
  		var patternkey = patterninfokeys[0];
  
  		for (var value = patterninfo[patternkey].min; value <= patterninfo[patternkey].max; value++) {
  			// Add the current value.
  			stack.push(value);
  
  			// Check to see if that pushed us over the limit.
  			// If so, bail out. The rest of this tree is dead to us.
  			var patternlength = calcpatternlength(stack);
  			if (patternlength > teststringlength) {
  				stack.pop();
  				break;
  			}
  
  			if (patterninfokeys.length > 1) {
  				// We've not made it all the way to the leaf node.
  				answer = permute(patterninfokeys.slice(1));
  			} else if (patternlength === teststringlength) {
  				answer = check(stack, teststring);
  			}
  
  			if (answer) {
  				// We're matched, we're done.
  				break;
  			} else {
  				// No good, try again.
  				stack.pop();
  			}
  		}
  
  		return answer;
  	}
  
  	function calcpatternlength(lengths) {
  		var tocheck = patterninfokeys.slice(0, lengths.length);
  
  		return tocheck.reduce(function(previous, patternkey, index) {
  			return previous + patterninfo[patternkey].indices.length * lengths[index];
  		}, 0);
  	}
  
  	function check(lengths, teststring) {
  		// Look up length using the patternkey.
  		var lengthsbypatternkey = Object.create(null);
  		var samplesbypatternkey = Object.create(null);
  
  		patterninfokeys.forEach(function(patternkey, index) {
  			lengthsbypatternkey[patternkey] = lengths[index];
  		});
  		return pattern.every(function(patternkey) {
  			var sample = teststring.substr(0, lengthsbypatternkey[patternkey]);
  			teststring = teststring.substr(lengthsbypatternkey[patternkey]);
  
  			// Force the pattern to match.
  			if (samplesbypatternkey[patternkey] && samplesbypatternkey[patternkey] !== sample) {
  				return false;
  			}
  
  			// Force unique.
  			for (var x in samplesbypatternkey) {
  				if (patternkey == x) { continue; }
  				if (samplesbypatternkey[x] == sample) { return false; }
  			}
  
  			// Save our sample.
  			samplesbypatternkey[patternkey] = sample;
  
  			// Continue to the next piece of the pattern.
  			return true;
  		});
  	}
  
  	return answer;
  }
  

};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
RegEx.
/(.+)?(.+)?([.]{3,})?\2\1/.test("abcdeba")
pending…
Non-delimited pattern matching without RegEx.
matcherCustom("abcdeba", "abcdeba");
pending…
Space delimited pattern matching.
matcherString("abcdeba", "a b c d e b a")
pending…
RegEx builder.
matcherRegEx("abcdeba", "abcdeba");
pending…

You can edit these tests or add even more tests to this page by appending /edit to the URL.

Compare results of other browsers

0 Comments