LaVOZs

The World’s Largest Online Community for Developers

'; javascript - binary search in typescript vs indexOf - how to get performance properly - LavOzs.Com

I wrote wrote binary search algorithm with some typescript and i wanted to get its performance against array.indexOf. My result show that typescript version is slower. I tried to measure performance in available benchmarks on web and they show that binary search is much faster (as it should be). Whats wrong with this code / typescript / the way im trying to get performance of functions?

I tried benchmarks and results look completely different. http://jsben.ch/VBjt0

My code below.

function binarySearch(
  sortedArray: number[],
  seekElement: number,
): number {
  let startIndex = 0;
  let endIndex: number = sortedArray.length - 1;
  while (startIndex <= endIndex) {
    const mid = startIndex + Math.floor((endIndex - startIndex) / 2);
    const guess = sortedArray[mid];
    if (guess === seekElement) {
      return mid;
    } else if (guess > seekElement) {
      endIndex = mid - 1;
    } else {
      startIndex = mid + 1;
    }
  }

  return -1;
}

const indexOfSearch = function(arr, element) {
  return arr.indexOf(element);
};

const testArray = [...Array(100000).keys()].map(x => x + 1);


console.time('binarySearch');
binarySearch(testArray, 4400) // binarySearch: 0.134ms
console.timeEnd('binarySearch');

console.time('indexOfSearch');
indexOfSearch(testArray, 4400) // indexOfSearch: 0.029ms
console.timeEnd('indexOfSearch');

I also tried to use performance.now with this util function:

import { performance } from 'perf_hooks';

export const getPerformance = (func: Function, ...params) => {
  const start = performance.now();

  func(params);

  const end = performance.now();

  console.log(`${func.name} took ${end - start} milliseconds to execute`);
}

but results are even worse. With the same testing array binary search using getPerformance function took 11ms while indexOf took 0.003ms. Its weird and i don't know what im doing wrong. Thanks for any help

For an array of length 𝑛, the binary search should need to check π—…π—ˆπ—€β‚‚π‘› entries at the worst case, while the linear scan would take 𝑛 entries at the worst case. For 𝑛 = 100,000 as in your example, that means in the worst case you'd expect to be checking 100,000 / π—…π—ˆπ—€β‚‚ 100,000 β‰ˆ 6,000 as many entries in your linear scan as you would in your binary search. Obviously the implementation details can change things by some numeric factor, but I'd be very surprised if you don't see some large difference between the two.

As the comments mention, you should really be doing the search many many times before you can get a sense of the average performance. A single run of any small bit of code is likely to have a bunch of overhead that can dwarf any differences. Here's one possible way to do this:

const N = 10000;
const seekElements = [...Array(N)].map(k => Math.floor(Math.random() * len * 1.1));

console.time('binarySearch');
for (let el of seekElements) {
    binarySearch(testArray, el)
}
console.timeEnd('binarySearch'); // 6 ms / N = 0.6 microseconds per search

console.time('indexOfSearch');
for (let el of seekElements) {
    indexOfSearch(testArray, el)
}
console.timeEnd('indexOfSearch'); // 3215 ms / N = 320 microseconds per search

Here I've set up an array of 10,000 random elements to find, about 10% of which are not in the array. The particular distribution of elements to seek will have an impact on the search time, since values not present in the array will be the worst-case performance in both search strategies. By testing 10,000 searches instead of 1, we can divide the timer's result by 10,000 to get an average time per search.

Anyway, in the my tests on my browser, I see that the indexOf() search on average is taking 320 microseconds while the binary search is taking 0.5 microseconds. There's at least a 500-fold improvement with the binary search. It's not 6,000, but it's definitely an improvement. You could try speeding up the implementation a bit by using x>>1 instead of Math.floor(x/2), but I'm not sure how important that is to you.

Okay, hope that helps.

Playground link to code

indexOf()

is written in binary, it is call, to "hard coded" function, which has soft interface of JavaScript.

probably it's also binary search

developers of JavaScript aren't stupid. The way you're accessing variables, trough OP codes and tokens and all virtual sandbox, you never reach the speed of light(C).

If you benchmark good in plain JavaScript, you should implement in real program of browser or node, not just sandbox.

JavaScript been about performance, when avg. laptops haven't shipped with 8GB ram. It's more about the simplicity of doing things, that computer gets done. Computers are cheaper than human nowadays.

If you want to benchmark really good, write it in WebAssembly or compile to it with C. Or write Node.js extensions. But while spending time, consider the following: ability to do a task, is far much more than few miliseconds.

Related
How can I get jQuery to perform a synchronous, rather than asynchronous, Ajax request?
How do you get a timestamp in JavaScript?
How to get the children of the $(this) selector?
How can I get query string values in JavaScript?
How to get the value from the GET parameters?
How do I get the current date in JavaScript?
How to do case insensitive search in Vim
How do you explicitly set a new property on `window` in TypeScript?
get and set in TypeScript