Benchmark: array vs hashmap vs array-polling vs find

Script Preparation code:

const array = [];

for (let i = 0; i < 100; i++) {
    array.push({
        key: i,
        "status": "Published",
          "npoId": 37,
          "directionId": 1,
          "title": "QWERTYU QWERTYU QWERTY",
          "subtitle": null,
          "description": "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer cursus fermentum commodo. Nullam hendrerit lectus quis tincidunt scelerisque. Suspendisse turpis augue, dignissim non molestie id, tempus tristique diam. Donec semper augue purus, et fermentum nibh laoreet ac. Pellentesque ac libero ac mauris bibendum pretium. Duis convallis vulputate dolor vitae semper. In eget ante dictum, vulputate nunc sit amet, consequat tortor. Vivamus et lorem tortor. Mauris venenatis risus et lobortis convallis. Vestibulum eros lectus, rhoncus id tincidunt non, faucibus dapibus sapien. Ut risus massa, pellentesque ac aliquam vitae, lobortis vel magna. Mauris in consectetur lorem.\nDonec imperdiet non sem at fermentum. Proin faucibus quis dui vestibulum hendrerit. Aenean pharetra sed quam vel egestas. Maecenas mattis nec quam consequat blandit. Aliquam viverra, velit vitae condimentum porttitor, dolor neque pretium dolor, a molestie urna risus vel neque. Nullam vitae erat a magna porttitor elementum. Aenean egestas auctor magna, eu rhoncus nisl blandit sed. Phasellus malesuada tempor auctor. Pellentesque non odio vel lectus rutrum condimentum.\nDonec porta vitae velit nec pellentesque. Duis tristique molestie ante, nec accumsan nibh. Aliquam consectetur ullamcorper nunc eu egestas. Vivamus luctus nulla et diam porta, in efficitur mi sagittis. Mauris eu sapien imperdiet, ultricies arcu quis, placerat justo. Integer vel mi in enim congue semper sit amet non purus. Pellentesque varius felis eu sem semper lobortis. Maecenas finibus congue felis quis tristique. Donec sit amet massa at sem vehicula luctus eu et massa. Nam id tortor sed magna volutpat dictum in id orci. Proin ac nulla id turpis maximus posuere.\nInteger vel arcu lacinia, malesuada enim vel, iaculis nisi. Nullam consectetur, elit eget varius auctor, arcu mi aliquet nisl, non pellentesque justo leo et ante. Aenean eu commodo quam, sed iaculis orci. Donec auctor odio nec sapien fringilla dignissim. Maecenas facilisis sit amet ipsum tincidunt tempor. Morbi dapibus ipsum et leo iaculis, a hendrerit arcu cursus. Sed in auctor risus, vitae ultricies mauris. Nunc ultricies maximus turpis, in malesuada leo posuere ac. Maecenas cursus elit et augue porta auctor. In consequat purus sit amet cursus rutrum. Integer ut purus aliquet, semper justo mollis, tincidunt tellus. Vivamus tortor neque, vulputate facilisis aliquet tempus, tempor at sapien. Aliquam et purus tincidunt magna vulputate aliquam viverra sit amet ex. In hac dui.",
          "customization": "QWERTYUQWERTYU2021",
          "avatar": "https://QQWERTYUIOIUYTRE/uploads/stories/story_avatar_1525702925760.jpeg",
          "customImage": null,
          "sharingImage": null,
          "requiredAmount": 120000000,
          "collectedAmount": 0,
          "donatorsCount": 0,
          "expiresAt": "2018-12-15T20:59:59.000Z",
          "promotion": null,
          "city": { "name": "Москва", "__typename": "City" },
          "metaInformation": {
            "description": "Благотворительный фонд QWERTY QWERTY",
            "__typename": "MetaInformation"
          },
          "npo": {
            "title": "QWERTYUI",
            "imgUrl": "https://dev.bllablaca.ru/entities/entity-1493723743044_app.png",
            "__typename": "ShortNpo"
          },
          "__typename": "Story"
    })
}

function hashmap () { return array.reduce((mapper, next) => ({
    ...mapper,
    [next.key]: next
}), {});}

let hashmap1;

function findInArray (key) {
    const index = bs(array, key, function(element, needle) {
        return element.key - needle;
    });
    return index > 0 ? array[index] : undefined;
}

function findArrayFind (key) {
  return array.find(elem=>elem.key===key);
}

function findInHashMap (key) {
  if (!hashmap1) {
    hashmap1 = hashmap();
  }
    return hashmap1[key] || undefined;
}

function findInArrayByPolling (key) {
    for (let i = 0, len = array.length ; i < len; i++) {
        if (array[i].key === key) {
            return array[i]
        }
    }
}



function bs(haystack, needle, comparator, low, high) {
    var mid, cmp;
  
    if(low === undefined)
      low = 0;
  
    else {
      low = low|0;
      if(low < 0 || low >= haystack.length)
        throw new RangeError("invalid lower bound");
    }
  
    if(high === undefined)
      high = haystack.length - 1;
  
    else {
      high = high|0;
      if(high < low || high >= haystack.length)
        throw new RangeError("invalid upper bound");
    }
  
    while(low <= high) {
      // The naive `low + high >>> 1` could fail for array lengths > 2**31
      // because `>>>` converts its operands to int32. `low + (high - low >>> 1)`
      // works for array lengths <= 2**32-1 which is also Javascript's max array
      // length.
      mid = low + ((high - low) >>> 1);
      cmp = +comparator(haystack[mid], needle, mid, haystack);
  
      // Too low.
      if(cmp < 0.0)
        low  = mid + 1;
  
      // Too high.
      else if(cmp > 0.0)
        high = mid - 1;
  
      // Key found.
      else
        return mid;
    }
  
    // Key not found.
    return ~low;
}

Tests:

find by binary search array
const target = Math.floor(Math.random() * 100); findInArray(target);
find by array polling
const target = Math.floor(Math.random() * 100); findInArrayByPolling(target);
find by hashmap
const target = Math.floor(Math.random() * 100); findInHashMap(target);
find by func find
const target = Math.floor(Math.random() * 100); findArrayFind(target)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
find by binary search array
find by array polling
find by hashmap
find by func find

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 3 years ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_3) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.114 Safari/537.36

Browser/OS: Chrome 91 on Mac OS X 10.15.3

View result in a separate tab

Test name	Executions per second
find by binary search array	1204063.1 Ops/sec
find by array polling	2185668.2 Ops/sec
find by hashmap	2559142.8 Ops/sec
find by func find	2298626.2 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 2 months ago):

LLMs can make mistakes. Check important info.

Related benchmarks:

array vs hashmap vs array-polling vs find (version: 0)

Comparing performance of: find by binary search array vs find by array polling vs find by hashmap vs find by func find

Created: 3 years ago by: Guest

Jump to the latest result

find by binary search array

find by array polling

find by hashmap

find by func find

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 2 months ago):