В последнее время у меня возникла проблема с массивом, который содержал сотни тысяч значений, и единственное, что я хотел сделать, это проверить, было ли значение уже присутствующим. В моем случае это были IP-адреса из журнала веб-сервера. Так что в основном что-то вроде:
in_array(ip2long(ip),$myarray) выполнила задание
Однако время поиска резко увеличилось, и 10 тыс. поисковых запросов заняли около 17 секунд.
Так что в этом случае мне было все равно, есть ли у меня дубликаты или нет, мне просто нужно проверить существование. Поэтому я мог хранить IP-адреса в индексе следующим образом:
isset($myarray[ip2long($ip)])
И стрела, время поиска уменьшилось с 17 секунд (и более) до статического времени 0,8 секунды для поиска 10k. В качестве значения для записи массива я просто использовал int 1.
Я думаю, что индекс массива, вероятно, основан на некотором b-дереве, который должен иметь время поиска log (n) и индекс на хэш-карте.
В моем случае использование индекса работало нормально, но есть ли какие-либо структуры данных, где я могу использовать hashmaps в качестве индекса значений, где могут также присутствовать несколько значений (я понимаю, что это имеет смысл только в том случае, если у него не слишком много дубликатов и Я не могу эффективно использовать запросы диапазона/поиска, что является основным преимуществом древовидных структур)?
Однако я подозреваю, что вы могли бы сделать свою логику намного более эффективной, если перевернул ваш массив, что позволит вам выполнить поиск по ключу (используя array_key_exists()) вместо поиска значения. Индекс массива представляет собой хеш, а не btree, что обеспечивает очень быстрый прямой доступ через ключ.
Однако, если вы работаете с 10k-элементами в массиве, вероятно, вам лучше воспользоваться базой данных, где вы можете определить свои собственные индексы.
У вас также есть расширение chdb (постоянная хэш-база) - это идеально подходит для этого.
Массивы имеют последовательный порядок и быстро получают доступ к определенным элементам, потому что вам не нужно пересекать дерево или работать через структуру последовательного списка.
Множество, конечно, здесь быстрее, потому что вы проверяете только уникальные элементы, а не все элементы (в массиве).
Дерево отлично подходит для отсортированных структур. Вы могли бы реализовать дерево с IP-адресами, отсортированными по их диапазонам, тогда вы могли бы решить быстрее, если этот IP существует или нет. Я не уверен, что PHP предоставляет такие настраиваемые древовидные структуры. Думаю, вам нужно будет реализовать это самостоятельно, но это займет около получаса.
Вы найдете примеры кода в Интернете для таких древовидных структур.
как уже было сказано, вы можете использовать совершенно новые классы, предоставляемые spl http://www.php.net/spl
НО, видимо, они не так быстро, как думают люди. вероятно, они не реализованы, как мы ожидаем. я считаю, что splfixedarray, например, не является реальным массивом, а хэш-таблицей как классическими массивами php
НО также у вас есть несколько альтернативных решений
сначала вы можете сохранить результат в базе данных. запросы быстрые, потому что индексы db могут быть лучше оптимизированы, чем файловая структура данных
вы можете использовать http://www.php.net/sqlite3 и хранить результаты во временной базе данных (файл или в памяти)
Я предлагаю временный файл, потому что вам не нужно загружать все в память, а в плюс вы можете добавить каждую строку отдельно (используя http://www.php.net/fgets например)
НТН!
не стесняйтесь исправить мой английский