mkevac May 12 2017 at 11:37

Какой map быстрее, и есть ли альтернатива Judy

8 min

16K

Badoo corporate blogC*Algorithms*High performance*Programming*

+43

Comments 10

DaylightIsBurning May 12 2017 at 11:58

а что с insert?

mkevac May 12 2017 at 12:07

Привет. judy быстрее чем spp. Первая тройка выглядит так:

dense -> judy -> spp

Результаты есть в репозитории. Я не стал рисовать эти графики и добавлять в статью, т.к. скорость добавления нам в данном случае не критична.

graphican May 12 2017 at 12:06

Поиск среди десяти миллионов сколько раз в тесте был сделан?

mkevac May 12 2017 at 12:08

Три раза и взят лучший результат.
В коде "запускатора" бенчмарка можно эту цифру изменить.

alexeykuzmin0 May 12 2017 at 12:10

У вас текст противоречит картинке:

Самым быстрым ассоциативным массивом оказался dense hash от Google. Следом идёт spp, и затем – Judy.

Но на картинке сразу под этими словами на третьем месте std, разве нет?

mkevac May 12 2017 at 12:13

Вы правы, спасибо. В тексте ошибка. Исправил!

bfDeveloper May 12 2017 at 12:33

А как же сравнение с недавним лидером: https://habrahabr.ru/company/mailru/blog/323242/

mkevac May 12 2017 at 13:01

Спасибо за ссылку. Я взгляну на эту реализацию!

gresolio May 12 2017 at 18:58

Поддерживаю) Очень интересны результаты с применением flat_hash_map от Malte Skarupke:
I Wrote The Fastest Hashtable (оригинал англ.)

robert_ayrapetyan May 14 2017 at 21:16

Не забываем, что с тех пор эту реализацию довольно больно побили на гитхабе (например https://github.com/skarupke/flat_hash_map/issues/3 и https://github.com/skarupke/flat_hash_map/issues/4)