Существуют ли в PHP альтернативные структуры данных, кроме массива, где я могу использовать различные методы индексации?

Question

В последнее время у меня возникла проблема с массивом, содержащим несколько сотен тысяч значений, и единственное, что я хотел сделать, - это проверить, присутствует ли уже значение.В моем случае это были IP-адреса из журнала веб-сервера.В общем, что-то вроде:

in_array(ip2long(ip),$myarray) выполнил задание

Однако время поиска значительно увеличилось, и 10 тысяч просмотров заняли около 17 секунд или около того.

Так что в этом случаеМне было все равно, есть ли у меня дубликаты или нет, мне просто нужно было проверить существование.Таким образом, я мог хранить IP-адреса в индексе следующим образом:

isset($myarray[ip2long($ip)])

И время поиска уменьшилось с 17 секунд (и более) до статического времени 0,8 секунды при поиске 10 тыс.В качестве значения для записи массива я только что использовал int 1.

Я думаю, что индекс массива, вероятно, основан на некотором b-дереве, которое должно иметь время поиска log (n) и индекс на хэш-карте.

В моем случае использование индекса работало нормально, но есть ли какие-либо структуры данных, в которых я могу использовать хеш-карты в качестве индекса значений, где также могут возникать множественные значения (я понимаю, что это имеет смысл только в том случае, если не слишком многодублирует, и я не могу эффективно использовать запросы диапазона / поиска, что является основным преимуществом древовидных структур)?

Answer 1

Существует целый ряд альтернативных структур данных, кроме простых массивов в библиотеке SPL , связанных с PHP, включая связанные списки, стеки, кучи, очереди и т. Д.

Тем не менее, я подозреваю, что вы могли бы сделать свою логику намного более эффективной, если бы вы перевернули свой массив, что позволит вам выполнить поиск ключа (используя array_key_exists () функция), а не искать значение. Индекс массива является хешем, а не btree, что обеспечивает очень быстрый прямой доступ через ключ.

Однако, если вы работаете с 10 тыс. Записей в массиве, вам, вероятно, лучше воспользоваться базой данных, в которой вы можете определить свои собственные индексы.

Answer 2

У вас также есть расширение chdb (база данных с постоянным хэшем), которое идеально подходит для этого.

Answer 3

как уже ответили, вы можете использовать совершенно новые классы, предоставляемые spl http://www.php.net/spl

НО, очевидно, они не так быстры, как думают люди. вероятно, они не реализованы, как мы ожидаем. по моему мнению, splfixedarray, например, не является реальным массивом, а является хеш-таблицей как классические массивы php

НО также у вас есть альтернативные решения

сначала вы можете сохранить свой результат в базе данных. запросы выполняются быстро, потому что индексы БД могут быть лучше оптимизированы, чем структура данных php

Вы можете использовать http://www.php.net/sqlite3 и сохранять результаты во временной базе данных (файл или в памяти)

Я предлагаю временный файл, потому что вам не нужно загружать все в память, и в плюс вы можете добавить каждую строку отдельно (например, используя http://www.php.net/fgets)

НТН!

Не стесняйтесь исправлять мой английский

Answer 4

Массивы имеют последовательный порядок и быстрый доступ к определенным элементам, потому что вам не нужно обходить дерево или работать через структуру последовательного списка.

Набор здесь, конечно, быстрее, потому что вы проверяете только уникальные элементы, а не все элементы (в массиве).

Деревья хороши для, например, отсортированных структур. Вы можете реализовать дерево с IP-адресами, отсортированными по их диапазонам, и тогда вы сможете быстрее решить, существует этот IP или нет. Я не уверен, что PHP предоставляет такие настраиваемые древовидные структуры. Я думаю, вам нужно реализовать это самостоятельно, но это займет около получаса.

В Интернете вы найдете примеры кодов для таких древовидных структур.