jsPerf.app is an online JavaScript performance benchmark test runner & jsperf.com mirror. It is a complete rewrite in homage to the once excellent jsperf.com now with hopefully a more modern & maintainable codebase.
jsperf.com URLs are mirrored at the same path, e.g:
https://jsperf.com/negative-modulo/2
Can be accessed at:
https://jsperf.app/negative-modulo/2
*** Reupload of Revision 4, Updated by TheSpanishInquisition ***
Accidentally forgot to add functional optimisation. Its about 5 times faster than prototype optimisation. I cannot figure out why.
*** Fork of Revision 2, Updated by TheSpanishInquisition ***
Changed test data. Each test is now executed against exactly the same data set in the name of fairness. Added fully optimised adaptations of James Westgate's implementation. Removed old Damerau–Levenshtein Distance test CompareLD2 (see this jsPerf for comparison of Damerau–Levenshtein Distance, this is for Levenshtein Distance only).
*** Original ***
Prompted by a Stack Overflow question, this will compare implementations of the Levenshtein distance algorithm.
By adding a limit and optimising comparison operators, I hope to further increase the performance of the Westgate implementation.
Math.randomInt = function(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
};
// Generate random strings.
window.dataSet = [];
window.dataSetLength = 50;
for (var i = 0; i < dataSetLength; i++) {
dataSet[i] = Math.randomInt(999, 999999).toString();
}
// Original.
window.CompareLD1 = function(min, split) {
try {
split = !("0")[0];
} catch (i) {
split = true;
}
return function(a, b) {
if (a == b) return 0;
if (!a.length || !b.length) return b.length || a.length;
if (split) {
a = a.split("");
b = b.split("");
}
var len1 = a.length + 1,
len2 = b.length + 1,
I = 0,
i = 0,
d = [
[0]
],
c, j, J;
while (++i < len2) d[0][i] = i;
i = 0;
while (++i < len1) {
J = j = 0;
c = a[I];
d[i] = [i];
while (++j < len2) {
d[i][j] = min(d[I][j] + 1, d[i][J] + 1, d[I][J] + (c != b[J]));
++J;
}++I;
}
return d[len1 - 1][len2 - 1];
}
}(Math.min, false);
function minn(a, b, c) {
if (a > b) a = b;
if (a < c) return a;
return c;
}
// Stoianovici's.
window.CompareLD3 = function(S1, S2, limit) {
if (S1 == null || S2 == null || typeof(S1) != "string" || typeof(S2) != "string") return 9999999;
if (limit == null) limit = 9999999;
if (Math.abs(S1.length - S2.length) > limit) return 9999999;
S1 = S1.toLowerCase();
S2 = S2.toLowerCase();
if (S1 == S2) return 0;
var n = S1.length;
var m = S2.length;
dist = new Array(new Array(m + 2), new Array(m + 2));
current = 0;
for (i = 0; i <= m + 1; i++) {
dist[1][i] = i;
}
for (i = 1; i <= n; i++) {
ok = 0;
dist[current][0] = i;
if (i - limit >= 1) dist[current][i - limit - 1] = 9999999;
for (j = Math.max(i - limit, 1); j <= Math.min(i + limit, m); j++) {
if (S1.substr(i - 1, 1) == S2.substr(j - 1, 1)) dist[current][j] = dist[1 - current][j - 1];
else dist[current][j] = minn(dist[1 - current][j - 1], dist[1 - current][j], dist[current][j - 1]) + 1;
if (dist[current][j] <= limit) ok = 1;
}
if (i + limit <= m) {
dist[current][i + limit + 1] = 9999999;
}
if (!ok) return 9999999;
current = 1 - current;
}
if (dist[1 - current][m] > limit) return 9999999;
return dist[1 - current][m];
};
// Westgate's.
window.CompareLD6 = function(s, t, lim) {
if (!lim) lim = 20;
if (Math.abs(s.length - t.length) > lim) return lim;
var d = []; //2d matrix
// Step 1
var n = s.length,
m = t.length;
if (n === 0) return m;
if (m === 0) return n;
var i = n + 1;
do {
d[i] = [];
} while (i--);
// Step 2
i = n + 1, j = m + 1;
do {
d[i][0] = i;
} while (i--);
do {
d[0][j] = j;
} while (j--);
// Step 3
for (var i = 1; i <= n; i++) {
var s_i = s.charAt(i - 1);
// Step 4
for (var j = 1; j <= m; j++) {
//Check the jagged ld total so far
if (i === j && d[i][j] > 4) return n;
var t_j = t.charAt(j - 1);
var cost = (s_i === t_j) ? 0 : 1; // Step 5
//Calculate the minimum
var mi = d[i - 1][j] + 1;
var b = d[i][j - 1] + 1;
var c = d[i - 1][j - 1] + cost;
if (b < mi) mi = b;
if (c < mi) mi = c;
d[i][j] = mi; // Step 6
}
}
// Step 7
return d[n][m];
}
// TheSpanishInquisition
// Cache the matrix. Note this implementation is limited to
// strings of 64 char or less. This could be altered to update
// dynamically, or a larger value could be used.
var matrix = [];
for (var i = 0; i < 64; i++) {
matrix[i] = [i];
matrix[i].length = 64;
}
for (var i = 0; i < 64; i++) {
matrix[0][i] = i;
}
// Functional implementation of Levenshtein Distance.
String.levenshteinDistance = function(__this, that, limit) {
var thisLength = __this.length, thatLength = that.length;
if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32;
if (thisLength === 0) return thatLength;
if (thatLength === 0) return thisLength;
// Calculate matrix.
var this_i, that_j, cost, min, t;
for (i = 1; i <= thisLength; ++i) {
this_i = __this[i-1];
// Step 4
for (j = 1; j <= thatLength; ++j) {
// Check the jagged ld total so far
if (i === j && matrix[i][j] > 4) return thisLength;
that_j = that[j-1];
cost = (this_i === that_j) ? 0 : 1; // Step 5
// Calculate the minimum (much faster than Math.min(...)).
min = matrix[i - 1][j ] + 1; // Deletion.
if ((t = matrix[i ][j - 1] + 1 ) < min) min = t; // Insertion.
if ((t = matrix[i - 1][j - 1] + cost) < min) min = t; // Substitution.
matrix[i][j] = min; // Update matrix.
}
}
return matrix[thisLength][thatLength];
};
// Prototype implementation of Levenshtein Distance.
String.prototype.levenshteinDistance = function(that, limit) {
var thisLength = this.length, thatLength = that.length;
if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32;
if (thisLength === 0) return thatLength;
if (thatLength === 0) return thisLength;
// Calculate matrix.
var this_i, that_j, cost, min, t;
for (i = 1; i <= thisLength; ++i) {
this_i = this[i-1];
// Step 4
for (j = 1; j <= thatLength; ++j) {
// Check the jagged ld total so far
if (i === j && matrix[i][j] > 4) return thisLength;
that_j = that[j-1];
cost = (this_i === that_j) ? 0 : 1; // Step 5
// Calculate the minimum (much faster than Math.min(...)).
min = matrix[i - 1][j ] + 1; // Deletion.
if ((t = matrix[i ][j - 1] + 1 ) < min) min = t; // Insertion.
if ((t = matrix[i - 1][j - 1] + cost) < min) min = t; // Substitution.
matrix[i][j] = min; // Update matrix.
}
}
return matrix[thisLength][thatLength];
};
var levDist = (function () {
var _d, _i = 0, _j = 0;
function allocate(i, j) {
if (i > _i || j > _j) {
_d = new Array((i > j) ? i : j);
_i = i;
_j = j;
for (; i >= 0; i--) _d[i] = [i];
for (; j >= 0; j--) _d[0][j] = j;
}
return _d;
};
allocate (64, 64);
return function(s, t, damerau) {
// Step 1
var n = s.length;
var m = t.length;
if (n == 0) return m;
if (m == 0) return n;
if (s == t) return 0;
//Create an array of arrays in javascript (a descending loop is quicker)
var i = n, j = m; //, d = new Array(n + 1);
// Step 2
var d = allocate(i, j);
// for (; i >= 0; i--) d[i] = [i];
// for (; j >= 0; j--) d[0][j] = j;
var s_i, t_j, cost, mi, b, c, r, x1, x2, y1, y2;
// Step 3
for (i = 1, x1 = 0, x2 = -1; i <= n; i++, x1++, x2++) {
s_i = s[x1];
// Step 4
for (j = 1, y1 = 0, y2 = -1; j <= m; j++, y1++, y2++) {
//Check the jagged ld total so far
if (i == j && d[i][j] > 4) return n;
t_j = t[y1];
cost = (s_i === t_j) ? 0 : 1; // Step 5
//Calculate the minimum
mi = d[x1][j ] + 1;
if ((r = d[i ][y1] + 1) < mi) mi = r;
if ((r = d[x1][y1] + cost) < mi) mi = r;
// b = d[i][j - 1] + 1;
// c = d[i - 1][j - 1] + cost;
// if (b < mi) mi = b;
// if (c < mi) mi = c;
//Damerau transposition
if (damerau && i > 1 && j > 1 && s_i == t[y2] && s[x2] == t_j) {
if ((r = d[x2][y2] + cost) < mi) mi = r;
}
d[i][j] = mi; // Step 6
}
}
// Step 7
return d[n][m];
};
})();
function levenshtein_kitho(s, t, damerau) {
// Step 1
var n = s.length;
var m = t.length;
if (n == 0) return m;
if (m == 0) return n;
if (s == t) return 0;
//Create an array of arrays in javascript (a descending loop is quicker)
var d = new Array(n + 1);
// Step 2
for (var i = n; i >= 0; i--) d[i] = [i];
for (var j = m; j >= 0; j--) d[0][j] = j;
// Step 3
for (var i = 1; i <= n; i++) {
var s_i = s[i - 1];
// Step 4
for (var j = 1; j <= m; j++) {
//Check the jagged ld total so far
if (i == j && d[i][j] > 4) return n;
var t_j = t[j - 1];
var cost = (s_i === t_j) ? 0 : 1; // Step 5
//Calculate the minimum
var mi = d[i - 1][j] + 1;
var b = d[i][j - 1] + 1;
var c = d[i - 1][j - 1] + cost;
if (b < mi) mi = b;
if (c < mi) mi = c;
//Damerau transposition
if (i > 1 && j > 1 && s_i == t[j - 2] && s[i - 2] == t_j) {
var r = d[i - 2][j - 2] + cost;
if (r < mi) mi = r;
}
d[i][j] = mi; // Step 6
}
}
// Step 7
return d[n][m];
}
// Functional implementation of Levenshtein Distance.
var _levenshteinDistance = function(__this, that) {
var thisLength = __this.length, thatLength = that.length;
// if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32;
if (thisLength === 0) return thatLength;
if (thatLength === 0) return thisLength;
if (thisLength == thatLength) return 0;
var matrix = new Array(thisLength + 1), i = thisLength, j = thatLength;
for (; i >= 0; i--) matrix[i] = [i];
for (; j >= 0; j--) matrix[0][j] = j;
// Calculate matrix.
var this_i, that_j, cost, min, t, x, y;
for (i = 1, x = 0; i <= thisLength; ++i, ++x) {
// x = i - 1;
this_i = __this[x];
// Step 4
for (j = 1, y = 0; j <= thatLength; ++j, ++y) {
// Check the jagged ld total so far
if (i === j && matrix[i][j] > 4) return thisLength;
// y = j - 1;
that_j = that[y];
cost = (this_i === that_j) ? 0 : 1; // Step 5
// Calculate the minimum (much faster than Math.min(...)).
min = matrix[x][j] + 1; // Deletion.
if ((t = matrix[i][y] + 1 ) < min) min = t; // Insertion.
if ((t = matrix[x][y] + cost) < min) min = t; // Substitution.
matrix[i][j] = min; // Update matrix.
}
}
return matrix[thisLength][thatLength];
};
var levenshteinMdW = (function() {
var row2 = new Uint16Array(1e6);
return function(s1, s2) {
var s1_len = s1.length, s2_len = s2.length;
if (s1_len && s2_len) {
var i1 = 0, i2 = 0, a, b, c, c2, row = row2;
while (i1 < s1_len)
row[i1] = ++i1;
while (i2 < s2_len) {
c2 = s2.charCodeAt(i2);
a = i2;
++i2;
b = i2;
for (i1 = 0; i1 < s1_len; ++i1) {
c = a + (s1.charCodeAt(i1) !== c2);
a = row[i1];
b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
row[i1] = b;
}
}
return b;
} else {
return s1_len + s2_len;
}
};
})();Ready to run.
| Test | Ops/sec | |
|---|---|---|
| Original [ no limit ] | | ready |
| Westgate's [ no limit ] | | ready |
| Stoianovici's [ no limit ] | | ready |
| TheSpanishInquisition's [ no limit ] | | ready |
| TheSpanishInquisition's [ prototype ] [ no limit ] | | ready |
| kitho | | ready |
| kitho2 | | ready |
| kitho3 | | ready |
| Marco de Wit's Levenshtein | | ready |
You can edit these tests or add more tests to this page by appending /edit to the URL.