В 2014 уже писали про обыск массива, но вряд ли кто понял.
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 сек, вывод списков с сортировкой и фильтрами и многих других вещей где стандартные приемы, либы и фреймворки делают это все слишком медленно, хотя конечно они удобны и разработку ускоряют.
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 сек, вывод списков с сортировкой и фильтрами и многих других вещей где стандартные приемы, либы и фреймворки делают это все слишком медленно, хотя конечно они удобны и разработку ускоряют.
