Comments 19
Фактически, это множество.
Тип
Тип
Map<T, Boolean> изоморфен типу Set<T> (и, например, в Java множество HashSet построено как тонкая обёртка над HashMap). В языках, где нет эффективной поддержки дженериков, множества частно эмулируются через ассоциативные массивы непосредственно. Например, общепринятым в Go способом создания множества (упоминается даже в официальной документации) является использование map[<something>]bool.
Краткое содержание: не реализуйте множество через массивы.
В данной теме может быть полезной функция array_flip(), естественно, где-нибудь однократно.
Я обычно использовал array_combine($badWordList, $badWordList), но array_filp() — это даже лучше, спасибо!
автор, сделай пожалуйста тест с array_flip, потому что все-таки удобнее массив составлять без ключей
Тест тут какой написать? Если запихнуть array_flip в цикл, то выигрыша естественно не будет, даже наоборот, т. к. каждый раз будет пересоздаваться массив. Если же вынести из цикла, то выигрыш существенный:
код
define('TEST_ITER', 100000);
$data = array('арбуз', 'дыня', 'вишня', 'слива', 'яблоко', 'груша', 'смородина', 'персик', 'абрикос', 'банан', 'виноград', 'киви');
$t = microtime(true);
for($i=0; $i<TEST_ITER; $i++)
$tmp = in_array('картофель', $data);
var_dump(microtime(true)-$t); // float(0.082980155944824)
$t = microtime(true);
$data = array_flip($data);
for($i=0; $i<TEST_ITER; $i++)
$tmp = isset($data['картофель']);
var_dump(microtime(true)-$t); // float(0.0057001113891602)
В следующем примере список запрещённых слов будет состоять из 10 000 элементов.
Вы только что запретили общаться одной из европейских стран.
Очень конечно весело видеть десятикратный прирост. Однако в реальных приложениях разницы между 0.000023 и 0.000123 вы никогда не заметите ибо все одеяло на себя утащат запросы к бд, парсинг больших xml и проч.
Ну да, алгоритм довольно-таки «тепличный». Хотя, мне всё равно чем-то идея понравилась, поэтому я и решил перевести эту статью.
Вот подумайте, у вас есть сервис, который крутится на 10 серверных стойках, а вы с помощью замены алгоритма понизили нагрузку на процессор на 10 процентов, то это значит, что одна из стоек безболезненно может быть отдана под другую задачу.
Или же вы сможете сэкономить 10% электроэнергии вот просто на замене 10 строчек кода.
Или же вы сможете сэкономить 10% электроэнергии вот просто на замене 10 строчек кода.
Поддержу, размера массива и кол-во обращений играют роль.
Помится, в Delphi, по крайней мере, до 7 версии было так.
Есть класс TDataSet для наборов данных, в него загружались данные из БД. Данный класс содержит в себе коллекцию полей (Fields), которые предоставляли доступ к значениям полей текущей записи. Доступ к объектам полей по имени, либо через метод FieldByName() либо более простой вариант типа dataset['fieldname']. Вся фишка в том, что эта коллекция построена на основе одного из базовых классов Delpgi — TList, по сути, массив.
Когда, по событию нужно прочитать/изменить поля одной записи, это не проблема. Но, например, если нужно обработать большой набор данных, данная особенность вылазила боком.
Решение, конечно, есть — получить объекты полей один раз перед циклом. Но сам этот факт вызывал искреннее удивление. В виду того, что в Delphi не было встроенных контейнеров типа хэш и множество, ситуация была не единична.
Помится, в Delphi, по крайней мере, до 7 версии было так.
Есть класс TDataSet для наборов данных, в него загружались данные из БД. Данный класс содержит в себе коллекцию полей (Fields), которые предоставляли доступ к значениям полей текущей записи. Доступ к объектам полей по имени, либо через метод FieldByName() либо более простой вариант типа dataset['fieldname']. Вся фишка в том, что эта коллекция построена на основе одного из базовых классов Delpgi — TList, по сути, массив.
Когда, по событию нужно прочитать/изменить поля одной записи, это не проблема. Но, например, если нужно обработать большой набор данных, данная особенность вылазила боком.
Решение, конечно, есть — получить объекты полей один раз перед циклом. Но сам этот факт вызывал искреннее удивление. В виду того, что в Delphi не было встроенных контейнеров типа хэш и множество, ситуация была не единична.
Я думаю что на массивах в несколько десятков и сотен тысяч элементов разница между O(1) и O(n) будет в разы очевиднее.
люто
Стоит сказать, что преимущества поиска по ключам массива довольно очевидны, если знать внутренне устройство ассоциативных массивов в PHP. Вот тут подробно всё и разъяснено.
Осмелюсь предположить что через stristr можно аналогично пройтись по тексту, добавив маркер начала/окончания слова. А так же через пересечение масивов array_intersect* (хотя на смотрел как оно в php реализовано в коде, может тупо как в первом варианте перебирает).
PS: для получения уникального массива (когда данные идут по очереди) можно все элементы вставлять в массив как ключи (если это возможно), а потом сделать array_keys — отпадает нужна в in_array. Да и много где такое подход крайне удобно использовать.
PS: для получения уникального массива (когда данные идут по очереди) можно все элементы вставлять в массив как ключи (если это возможно), а потом сделать array_keys — отпадает нужна в in_array. Да и много где такое подход крайне удобно использовать.
Вообще-то для данной задачи существует алгоритм Ахо-Карасик.
Sign up to leave a comment.
Используйте поиск по хешу, а не обыск массива