C тех пор вышло много версий PHP и не исправили значит обратная связь плохая и об этом мало кто знает. На питоне так же, и в 3* хуже чем в 2.7.
Иногда нужно найти строку в массиве строк — очень частая операция в разных алгоритмах и если массив небольшой и искать немного и не в цикле, то in_array нормально, на общую скорость не влияет, но если big data и искать надо массиве из миллиарда строк и миллиард раз, то это уже критично: лучше час вместо недели.
Простой тест показывает:
in_array ищет за 6-9 сек ideone.com/Yb1mDa 6600ms
а array_key_exists ищет тоже самое, но быстрее в 250(php5.6/py3.*) в 400+ раз (php7.3/py2.7) ideone.com/gwSmFc (цикл увеличен в 100 раз) 12ms (6600/12=550раз +-10% разброс из-за нагрузки и кеша)
Почему же такое происходит? Рассмотрим подробно:
1) Поиск строк на чистом ассемблере/си это сортировка массива строк (быстрая или пузырьковая), затем бинарный поиск.
Число шагов в бинарном поиске log(n) раз и зависит от размера массива, и намного меньше чем простой перебор.
Отсортировать массив строк можно заранее, один раз и закешировать, а потом делать миллиард поисков. Но это не помогает.
По умолчанию сортировка происходит каждый раз снова, хотя писали что улучшили в 7.2 in_array через хеш, но немного.
2) Поиск индекса/key(как строки) в ассоц. массиве/словаре происходит по хешу строк и обработкой коллизий.(ошибок поиска по хешу). Хеш это числовой индекс массива и выборка из него как (адрес нулевого элемента) + смещение * размер указателя на массив строк с этим хешем) в 2 шага. +перебор коллизий, шагов в среднем меньше бинарного поиска.
Хеш индекса делается автоматически заранее один раз при создании элемента словаря $m[key]=val и кешируется.
Размер хеша, алгоритм хеширования зашит в движок пхп и его не поменять, хотя исходники открыты- можно скачать изменить и скомпилировать если сервер свой.
Дальше можно не читать, меняйте in_array на array_combine + array_key_exists и всё.
Число шагов при поиске по хешу зависит от количества коллизий и кол-ва строк с одинаковым хешем. Их нужно перебирать или также сортировать и бинарный поиск.
Для уменьшения коллизий можно выделить больше памяти, если возможно, что сейчас не такая проблема, как 50 лет назад когда 1 кб памяти на магн.катушках стоил как самолет. А именно тогда были придуманы все основные алгоритмы: sort/zip/gif/jpg/итд — им не надо много памяти, но они плохие, сейчас есть намного лучше, но им надо много памяти 1-16 Мб. Да, есть серверы с 256 Мб и на каждого отдельный поток и 16 Мб уже много, но на девайсе среднего юзера 1 Гб как минимум и 16 Мб это капля в море.
Еще больший эффект можно получить если заменить вызов функции array_key_exists на конструкцию isset($m[key]), она не чистит очередь команд и кеш, не использует стек и быстрее где-то на 20%.
Так же можно еще ускорить если создать массив 2х первых букв- 4*16кб и искать сначала по смещению (индекс=код 1го символа + 2го*256) указатель на массив хешей для остальной части строки, затем ищем уже среди маленького массива «хвостов» строк и коллизий на порядок меньше.
Это требует еще больше памяти и алгоритм сложнее, но поиск быстрее в 30+ раз. Но в пхп это не реализовано, можно написать свою библиотеку so/dll и вызывать, или попросить разработчиков добавить в 7.5.
Можно искать через mySQL, но надо группировать запросы и это будет все равно медленней.
P.S.: Этот способ нашел случайно методом тыка, интуиции и опыта когда ускорял один большой медленный сайт, таких тонкостей и приемов очень много, удалось добиться выгрузки данных в ексель с 40 сек до 0,8 сек, вывод списков с сортировкой и фильтрами и многих других вещей где стандартные приемы, либы и фреймворки делают это все слишком медленно, хотя конечно они удобны и разработку ускоряют.
lair
А вы время
array_combine
учитываете?(но вообще, конечно, удивительно, что кому-то надо рассказывать про уместность применения хэш-таблиц...)
xing2020 Автор
В статье код теста есть и видно что array_combine или array_flip делается один раз! чтобы значения превратить в ключи и сделать массив уникальным это 0,1мс- (можно там же проверить). а дальше поиск 10000 раз -он для подсчета скорости алгоритма и в реальной жизни поможет если искать много, а если мало то без разницы. В массиве 100 строк через in_array искать удобней.
А насчет хеш, некоторые даже не знают что это такое, разработчики PHP/Python видимо не в курсе что текущий алгоритм слабоват, а здесь мы превращаем большой массив строк в маленький массив их хешей как чисел 8,16,24,32 битных и число сравнений строк уменьшается в 256, 16к, итд раз. Алгоритм хеширования тоже влияет. Например надо в массиве из 2048 строк сделать 256 хешей- тогда в среднем надо не 1024 сравнения а 2048/256=8. перебор это 4 шага если равномерно, меньше если наиболее частые поместить в начало, или отсортировать 1 раз, а затем бинарный поиск, для массива 8 строк это 3 шага. Но если хеширование плохое — например КС % 256 то будет не 8, а где-то 2 где-то 16. А если будет сложное, то его считать долго. Но хеш считается один раз в длинном цикле и это намного меньше чем пузырьковая сортировка — там цикл n*n/2 и бинарный поиск требует больше шагов чем по индексу найти и сделать поиск в массиве который меньше в 256^n раз. где n-кол-во байт на хеш.
lair
… и это неправильно, потому что это делает заголовок бессмысленным. Без сравнения времени
array_combine
вы сравниваете поиск перебором в массиве с поиском в хэш-таблице, и это простая и известная вещь: O(n) против O(1). Собственно, весь ваш заголовок к этому сводится: поиск в хэш-таблице (точный) быстрее, чем в массиве. Ну… да? Это, типа, азы алгоритмов, и именно с точки зрения отличия структур это и надо обсуждать.… какой "текущий алгоритм" в Питоне слабоват?
И это операция O(n).
Если поиск надо делать много раз по одному и тому же массиву, сделать хэш-таблицу выгодно. Если поиск надо сделать один раз — невыгодно.
xing2020 Автор
1. идем сюда ideone.com/Yb1mDa — общее время 0.68s, только поиск 0.66s
2. идем сюда ideone.com/gwSmFc — общее время 0.14s, только поиск 0.12s
во втором поисков больше в 100 раз. считаем. 6800/14=? в каком месте неправильно? за что там +6, а мне -5? Вы хоть в школе учились? или это боты?
Заголовок про поиск в массиве через in_array() — это проверка есть/нет а не позиции в массиве. Это очень сложно понять?
Про текущий алгоритм отвечу когда мне +100 поставят, за попытку поделится с адекватными думающими людьми рабочим способом-костылем, исправляющим косяки разрабов, а не ерундой никому не нужной.
lair
В том, где вы делаете
array_combine
один раз. Повторюсь еще раз: если у вас есть на входе произвольный массив (именно массив, не ассоциативный массив), и вам надо найти в нем значение, один раз, поиск перебором (in_array
) должен быть быстрее, чем сворачивание в хэш-таблицу и поиск на вхождение в ней (array_combine
+array_key_exists
).Да вот за это, в общем-то:
.
А при чем тут вообще позиция в массиве?
Ну то есть никогда. Дело ваше, но до тех пор ваше утверждение "текущий алгоритм в Python слабоват" безосновательно.