4 ms·
Array is an appropriate datastructure for this algorithm. String is not. var dest = 'apple'.split(''); var j = dest.length; var start = new Date();
by mraleph 15y ago
Array is an appropriate datastructure for this algorithm. String is not.
var dest = 'apple'.split('');
var j = dest.length;
var start = new Date();
while (j < 100000) {
var offs = j - 5;
for (var i = offs; i < offs + 10; ++i)
dest[j++] = dest[i];
}
dest = dest.join('');
=> 7-10ms in the latest Chrome.
- mjs 15y agoArrays do seem to be the way to make Chrome happy, although unfortunately they're slower for everything else: http://jsperf.com/backreference-copy http://jsperf.com/backreference-copy I don't see why you say an array is a more appropriate datastructure for the algorithm, though--that seems very much implementation dependent. And at the JS level, arrays support operations such as splice that strings do not, suggesting that they'd typically be implemented with a more sophisticated datastructure, and hence slower at primitive operations like index access. (Perhaps V8 notices that these expensive operations aren't actually used, and creates a fast, basic version instead.)
- mraleph 15y agoArray is intended to be a mutable storage with a fast random access and optimistic preallocation of backing store. String is intended to be an immutable storage. At least that's how I see these types. I also would not expect that VM will use representation optimized for splicing --- you should _always_ expect that splicing will take O(arr.length) and use appropriate data structure when you want better time bounds. There is a limit to how VM can optimize use of data structures. It can't magically guess that you wanted list or binary tree instead of an Array. Introducing many special cases/heuristics also leads to complexity and as a result to bugs.