Комментарии 50
Дальше можно не читать, меняйте in_array на array_combine + array_key_exists и всё.
А вы время array_combine учитываете?
(но вообще, конечно, удивительно, что кому-то надо рассказывать про уместность применения хэш-таблиц...)
В статье код теста есть и видно что 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-кол-во байт на хеш.
А насчет хеш, некоторые даже не знают что это такое, разработчики 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-кол-во байт на хеш.
В статье код теста есть и видно что array_combine или array_flip делается один раз!
… и это неправильно, потому что это делает заголовок бессмысленным. Без сравнения времени array_combine вы сравниваете поиск перебором в массиве с поиском в хэш-таблице, и это простая и известная вещь: O(n) против O(1). Собственно, весь ваш заголовок к этому сводится: поиск в хэш-таблице (точный) быстрее, чем в массиве. Ну… да? Это, типа, азы алгоритмов, и именно с точки зрения отличия структур это и надо обсуждать.
разработчики PHP/Python видимо не в курсе что текущий алгоритм слабоват
… какой "текущий алгоритм" в Питоне слабоват?
а здесь мы превращаем большой массив строк в маленький массив их хешей
И это операция O(n).
Если поиск надо делать много раз по одному и тому же массиву, сделать хэш-таблицу выгодно. Если поиск надо сделать один раз — невыгодно.
1. идем сюда ideone.com/Yb1mDa — общее время 0.68s, только поиск 0.66s
2. идем сюда ideone.com/gwSmFc — общее время 0.14s, только поиск 0.12s
во втором поисков больше в 100 раз. считаем. 6800/14=? в каком месте неправильно? за что там +6, а мне -5? Вы хоть в школе учились? или это боты?
Заголовок про поиск в массиве через in_array() — это проверка есть/нет а не позиции в массиве. Это очень сложно понять?
Про текущий алгоритм отвечу когда мне +100 поставят, за попытку поделится с адекватными думающими людьми рабочим способом-костылем, исправляющим косяки разрабов, а не ерундой никому не нужной.
2. идем сюда ideone.com/gwSmFc — общее время 0.14s, только поиск 0.12s
во втором поисков больше в 100 раз. считаем. 6800/14=? в каком месте неправильно? за что там +6, а мне -5? Вы хоть в школе учились? или это боты?
Заголовок про поиск в массиве через in_array() — это проверка есть/нет а не позиции в массиве. Это очень сложно понять?
Про текущий алгоритм отвечу когда мне +100 поставят, за попытку поделится с адекватными думающими людьми рабочим способом-костылем, исправляющим косяки разрабов, а не ерундой никому не нужной.
во втором поисков больше в 100 раз. считаем. 6800/14=? в каком месте неправильно?
В том, где вы делаете array_combine один раз. Повторюсь еще раз: если у вас есть на входе произвольный массив (именно массив, не ассоциативный массив), и вам надо найти в нем значение, один раз, поиск перебором (in_array) должен быть быстрее, чем сворачивание в хэш-таблицу и поиск на вхождение в ней (array_combine + array_key_exists).
а что там +6, а мне -5?
Да вот за это, в общем-то:
Вы хоть в школе учились?
.
Заголовок про поиск в массиве через in_array() — это проверка есть/нет а не позиции в массиве. Это очень сложно понять?
А при чем тут вообще позиция в массиве?
Про текущий алгоритм отвечу когда мне +100 поставят,
Ну то есть никогда. Дело ваше, но до тех пор ваше утверждение "текущий алгоритм в Python слабоват" безосновательно.
https://github.com/php/php-src/pull/3360
информация про isset/array_key_exists cскорее сего устаревшая (лень проверять).
Не надо сравнивать поиск в массиве по значению и по ключу. Нет никакого сюрприза в том, что поиск по значению (который последовательно перебирает все значения) оказывается медленнее чем поиск по ключу (который оказывается хеш таблицей). Соответственно «500 раз» будет тем больше, чем больше элементов в массиве.
Да, все правильно, в небольших массивах разницы почти нет, а в очень больших есть, но надо больше памяти на хеш и массив хешей, я думал если в in_array бинарный поиск, то сортировка заранее может поможет и сделать уникальным массив — нет, не помогает, так же долго. Видимо сортирует каждый раз или хеш считает. А с ключами-индексами один раз и кешируется всё. Можно код посмотреть, он открыт. А почему это не сделано в in_array и в питоне. Вот вопрос. Поиск в массиве очень частая и нужная операция. Но все юзают медленный способ, так как быстрый не знают и не узнают. Статья ушла в минус. Наверно люди думают что это ерунда и бред. Кстати за за статью об «обыске массиве» 6 лет назад, ни одного минуса, а там про тоже самое почти но менее подробно, а заголовок неудачный — я бы даже читать не стал.
Почему-почему… Да потому что если это сделать — это нужно будет поддерживать при каждом изменении массива. А это уже приведет к замедлению в других местах.
Это ваша задача как программиста — помнить о времени работы разных функций и выбирать правильные.
Не надо ля-ля, добавить значение в индекс не дольше чем в массив, а исправить можно так — делаем копию массива и хешей в первый раз и кешируем.
in_array это как раз та самая «правильная» ф-я которую надо использовать при поиске, а за костыль этот могут уволить или минусов наставить, людям не надо быстро — им надо понятно. А этот способ он не для всех, а кто шарит.
in_array это как раз та самая «правильная» ф-я которую надо использовать при поиске, а за костыль этот могут уволить или минусов наставить, людям не надо быстро — им надо понятно. А этот способ он не для всех, а кто шарит.
Поиск в массиве очень частая и нужная операция. Но все юзают медленный способ, так как быстрый не знают и не узнают.
Потому что самый быстрый способ искать в массиве (в общем случае) — это перебор. O(n).
А вот то, что кто-то не знает, что иногда надо использовать не массив, а другую структуру данных — это печально, да.
перебор? смешно, ну так и ищете перебором месяц, а мы будем за час искать через хеш или бинарный поиск — зависит от размера и памяти. Выше объяснил, кто не понял — гугл в помощь.
перебор? смешно
Очень смешно, да. Приведите способ, который будет быстрее в общем случае (то есть для любого массива), учитывая, что
через хеш
Требует создания хэш-таблицы, а это само по себе O(n).
бинарный поиск
Требует сортированного массива, а это O(n) в лучшем случае и O(n log n) в среднем. Плюс O(log n) на сам поиск, конечно.
А почему это не сделано в in_array и в питоне. Вот вопрос.
Потому что не нужно это. Ну то есть в Питоне точно не нужно.
Комбинация «array_combine + array_key_exists» ломается сразу как только в массиве появляются одинаковые значения. Причем об этом говориться в первом же комментарии официальной документации array_combine.
Это не помешает определить есть ли строка в массиве, но вот найти её индекс или количество строк уже проблема.
И почему не использовать array_flip вместо array_combine? Подозреваю быстрей будет.
Такое себе решение, вы сравниваете две совершенно разные функции.
Это не помешает определить есть ли строка в массиве, но вот найти её индекс или количество строк уже проблема.
И почему не использовать array_flip вместо array_combine? Подозреваю быстрей будет.
Такое себе решение, вы сравниваете две совершенно разные функции.
$m=array_combine($m,$m) делает массив уникальным без лишних вопросов.
array_flip меняет местами ключи и значения. на повторы и пусто не проверял. Да можно в простом цикле это сделать. $r=[];foreach($m as $v)if($v)$r[$v]=0;
На время почти не влияет если искать очень много: это делается один раз до поиска.
array_flip меняет местами ключи и значения. на повторы и пусто не проверял. Да можно в простом цикле это сделать. $r=[];foreach($m as $v)if($v)$r[$v]=0;
На время почти не влияет если искать очень много: это делается один раз до поиска.
$m=array_combine($m,$m) делает массив уникальным без лишних вопросов.А это важно, что там в значениях, если у вас ключ уже искомая строка?! Вы туда можете хоть null подставить, памяти сэкономите.
array_flip меняет местами ключи и значения.
Да можно в простом цикле это сделать. $r=[];foreach($m as $v)if($v)$r[$v]=0;Код с ошибкой и отличается от работы array_combine или array_flip, вы потеряете все пустые строки.
$m = [''];
var_dump(array_flip($m));
var_dump(array_combine($m,$m));
$r=[];foreach($m as $v)if($v)$r[$v]=0;
var_dump($r);
array(1) {
[""]=>
int(0)
}
array(1) {
[""]=>
string(0) ""
}
array(0) {
}
Что-то вы путаете тёплое с мягким.
in_array() ищет значение в массиве, а array_key_exist() наличие ключа, а это две огромные разницы.
Это тот же поиск строки в массиве строк, из тестов видно же, никаких фокусов и обмана. Возьмите массив миллиард строк и 10к строк для поиска. Надо узнать какие строки есть в этом массиве, а каких нет.
in_array() — это обычная ф-я, она для этого сделана. Но можно этот же массив превратить в массив индексов-строк для словаря(ассоц.массива) и тогда проверка есть ли такой ключ будет аналогом поиска в массиве, но здесь идет поиск по другому алгоритму (а именно через таблицу хешей, но об этом мало кто знает) и одинаковые и пустые значения запрещены. Но для поиска они обычно не нужны. Если надо, то на пусто можно проверять отдельно — это быстро.
Еще in_array() может искать 0, null,'' как пусто и значением может быть пустая строка, в индексах — не может, но '0', 0 — можно.
in_array() — это обычная ф-я, она для этого сделана. Но можно этот же массив превратить в массив индексов-строк для словаря(ассоц.массива) и тогда проверка есть ли такой ключ будет аналогом поиска в массиве, но здесь идет поиск по другому алгоритму (а именно через таблицу хешей, но об этом мало кто знает) и одинаковые и пустые значения запрещены. Но для поиска они обычно не нужны. Если надо, то на пусто можно проверять отдельно — это быстро.
Еще in_array() может искать 0, null,'' как пусто и значением может быть пустая строка, в индексах — не может, но '0', 0 — можно.
Нет, вы путаете теплое с мягким. Это две разные операции, которые вы патаетесь взаимозаменить.
И проблема все же останется. На маленьких массивах вы не заметите разницы (разве что вы правда делаете млн операций на массиве из 10 строк, но это маразм). А вот массивы в миллиард реальных строк вас сильно удивят выделением памяти.
Массив на млрд. уникальных строк будет отжирать память довольно существенно. Когда вы сделаете array_flip (ну или ваш аналог) — память по сути увеличится в два раза, т.к. массива у вас уже два. Это короткий промежуток времени и там не совсем уж х2, но все же в реальном мире вы только проиграете.
С другой стороны, если для вас эта память не играет роли, то не совсем понятно какой поиск вы пытаетесь так оптимизировать. Будет выигрыш в копейки.
Говорю это из собственного опыта на массивах до 1 млн значений (ссылки). Проще сразу хранить их как ключи => bool, чтобы и isset() работал и не приходилось его флипать.
И проблема все же останется. На маленьких массивах вы не заметите разницы (разве что вы правда делаете млн операций на массиве из 10 строк, но это маразм). А вот массивы в миллиард реальных строк вас сильно удивят выделением памяти.
Массив на млрд. уникальных строк будет отжирать память довольно существенно. Когда вы сделаете array_flip (ну или ваш аналог) — память по сути увеличится в два раза, т.к. массива у вас уже два. Это короткий промежуток времени и там не совсем уж х2, но все же в реальном мире вы только проиграете.
С другой стороны, если для вас эта память не играет роли, то не совсем понятно какой поиск вы пытаетесь так оптимизировать. Будет выигрыш в копейки.
Говорю это из собственного опыта на массивах до 1 млн значений (ссылки). Проще сразу хранить их как ключи => bool, чтобы и isset() работал и не приходилось его флипать.
Мне это реально помогло, вот и написал, может другим поможет тоже, памяти надо больше, сразу сказал. Надо экономить- искать частями, выгружать, загружать. Выигрыш есть, и не копейки, массив может прийти из вне, или из файла, пока что надо флипать его заранее или переделывать сам in_array() или писать на др. языке свой оптимальный поиск, выбирать размер хеш и алгоритм хеширования и считать по шагам что лучше, через хеш можно в нес-ко потоков искать, а бинарный поиск только в одном. тут 1байт-и делать хеш, там сортировка и сравнения. В разных случаях — наилучший свой.
Писали что в 7.2 улучшили этот поиск через обратный массив и хеш, но я сравнил — разница не заметна, сейчас через индекс быстрее и намного.
Писали что в 7.2 улучшили этот поиск через обратный массив и хеш, но я сравнил — разница не заметна, сейчас через индекс быстрее и намного.
У меня получше тема для разговора: полезно ли программистам читать Кнута в 2020?
Хм, странно… это же принципиально разные вещи — поиск по хешу или по значению. Это все равно, что повесить индекс к столбцу в базе данных и удивляться, что стало быстрее… Или не делить на два, а битовый сдвиг вправо, или проверить на четность как a & 1, а еще можно использовать как битовые флаги.
Притянутая за уши ситуация, когда сделал для себя «открытие».
Притянутая за уши ситуация, когда сделал для себя «открытие».
И ваше же решение для вашей же задачи не подходит:
Вы не находите строку, а просто говорите о наличии — есть она там или нет. Чтобы найти строку есть array_search (для поиска первого вхождения) и array_keys для поиска всех вхождений — на выходе получаете ключ/массив ключей, которые содержат искомую строку.
Иногда нужно найти строку в массиве строк
Вы не находите строку, а просто говорите о наличии — есть она там или нет. Чтобы найти строку есть array_search (для поиска первого вхождения) и array_keys для поиска всех вхождений — на выходе получаете ключ/массив ключей, которые содержат искомую строку.
Вот когда тебе дадут реальное задание — есть миллион строк — слова/фразы/итд. биг дата, накопили за 10 лет. что то, и надо написать экспертную систему — которая в том числе и ищет в словарях — есть/нет и делает что-то, вот попробуй это сделать. Там не в 100 строках искать надо и времени надо очень много, тогда будешь писать это на си или можно найти способ попроще, ведь одну задачу можно решить разными путями, только затраты на разработку и время работы разное. Наличие строки это тоже поиск.
Вот когда тебе дадут реальное задание — есть миллион строк — слова/фразы/итд. биг дата, накопили за 10 лет. что то, и надо написать экспертную систему — которая в том числе и ищет в словарях — есть/нет и делает что-то, вот попробуй это сделать.
Попробуйте это, сделать, да, учитывая, что это биг дата — то есть в память не влезает.
А так-то да, это типовая задача, еще в MMDS разобранная.
Если два вас бигдата — это то, что можно поднять в оперативу — то советую ознакомиться с машиной Тьюринга и его бесконечной лентой (читай — данные). Ну есть у меня в одном проекте база больше 500 Гб — ну так мускул с ней справляется без проблем — на сервере 32 ГБ оперативы. И это еще ни разу не бигдата, да, там есть пару-тройку тяжелых таблиц (гигов по 100 и миллиардами записей), которые нужно джойнить и фильтровать… Но это ладно.
Вы используете массивы как множество — это разные понятия, и пытаетесь притянуть за уши свой пример для «решения» задачи — хештаблицы и просто массив разные понятия. Если вы случайно сделали для себя открытие — поздравляю, мир об этом уже знает сто лет!
Вы используете массивы как множество — это разные понятия, и пытаетесь притянуть за уши свой пример для «решения» задачи — хештаблицы и просто массив разные понятия. Если вы случайно сделали для себя открытие — поздравляю, мир об этом уже знает сто лет!
Поиск строк на чистом ассемблере/си это сортировка массива строк (быстрая или пузырьковая), затем бинарный поиск.
Число шагов в бинарном поиске log(n) раз и зависит от размера массива, и намного меньше чем простой перебор.
Вы же, кстати, помните, что сортировка — это O(n log n)?
И с чего вы решили, что в in_array сделано так, а не простым перебором? Я, конечно, сварщик ненастоящий, но я никакой сортировки в исходниках не вижу.
А где я писал какой алгоритм там? Вам опять показалось. Я написал какие алгоритмы поиска есть и как можно еще улучшить, то что есть сейчас, но здесь большинству даже просто проверить лень что способ просто рабочий без всяких объяснений, С кем тут о чем спорить? чтобы мне минусов наставили вместо спасибо? Мне это не надо. Да и вообще люди стараются, разбираются, изучают, делятся бесплатно полезной инфой и что? приходят хейтеры и минусуют, кому охота после этого что-то сюда писать и объяснять? На форумах чтобы поставить минус надо иметь большую репутацию и написать за что и это проверит модераторы и админ -защита от ботов, мультов и неадекватных.
Наверное, момент, который может показаться непонятным — почему в PHP и массивы и хэш-таблицы называются одинаково
array? Собственно, отсюда ноги и растут — потому что если мимо проходящий человек видит in_array/array_key_exists — ну да, конечно можно немного поразмыслить и понять разницу даже без документации, но все-таки когда и там и там «array», то это не очень прозрачно. И вот так и появляются такие, как топикстартер, решающие сделать, кхм, разоблачающее расследование.
Может, всё-таки наоборот, прозрачно, раз там и там array, значит и там, и там одно и то же?
array это массив, индекс число.
ассоциативный массив это по сути словарь ключ-значение, у него индекс это строка.
В питоне это тип dict там понятней. в php/js это одинаково и числа это тоже как строки- быстрее не ищет, значит тоже по хеш, а не по смещению.
ассоциативный массив это по сути словарь ключ-значение, у него индекс это строка.
В питоне это тип dict там понятней. в php/js это одинаково и числа это тоже как строки- быстрее не ищет, значит тоже по хеш, а не по смещению.
Вы сравнивали in_array не с array_key_exists, а с isset. Это несколько разные вещи хотя бы потому, что isset не является функцией и дает другой результат. Попробуйте добавить NULL в изначальный массив и посмотрите, что вам вернет isset при попытке узнать, есть ли в массиве этот NULL.
Про необходимость включения array_combine (или array_flip) в тело цикла для корректного сравнения вам уже выше написали. И если делать честное сравнение с array_flip+isset/array_key_exists, то получим результат в разы хуже, чем если бы использовали in_array.
Про необходимость включения array_combine (или array_flip) в тело цикла для корректного сравнения вам уже выше написали. И если делать честное сравнение с array_flip+isset/array_key_exists, то получим результат в разы хуже, чем если бы использовали in_array.
Уже комментировали, но я попинаю труп ещё раз.
Вам, уважаемый, следует ознакомиться с hash таблицами. Совершенно две разные операции которые не взаимозаменяемы без танцев с бубном.
Поиск вообще дело сильно зависящее от данных и его нужно подгонять под каждый конкретный случай где много данных. Не редки случаи, когда вместо in_array и прочих встроенных вариантов поиска написанный на голом PHP алгоритм может быть быстрее. Такое бывает не часто конечно, т.к. не очень умно гонять такие массивы данных в скриптовом языке, но случается время от времени.
Вам, уважаемый, следует ознакомиться с hash таблицами. Совершенно две разные операции которые не взаимозаменяемы без танцев с бубном.
Поиск вообще дело сильно зависящее от данных и его нужно подгонять под каждый конкретный случай где много данных. Не редки случаи, когда вместо in_array и прочих встроенных вариантов поиска написанный на голом PHP алгоритм может быть быстрее. Такое бывает не часто конечно, т.к. не очень умно гонять такие массивы данных в скриптовом языке, но случается время от времени.
там комментировали трупы, можно их попинать, чтобы сходили проверили тесты раз, и написали свои тесты и проверили на своих серверах в разных версиях пхп и питона два.
Хеш таблицы это отображение одного множества строк в другое. Каждый байт хеша уменьшает область поиска в 256 раз, а бинарный поиск=метод половинного деления делает это за 8 шагов в одном потоке.
К сожалению на скриптовом языке сейчас много алгоритмов в том числе и связанными с обработкой биг дата, так как писать на норм. языке накладно. Нужно это редко и не всем, а понять судя по коментам может один из ста. Можно это как тест на IQ/знание алгоритмов и PHP использовать, кто не понял — тот пока junior :)
Хеш таблицы это отображение одного множества строк в другое. Каждый байт хеша уменьшает область поиска в 256 раз, а бинарный поиск=метод половинного деления делает это за 8 шагов в одном потоке.
К сожалению на скриптовом языке сейчас много алгоритмов в том числе и связанными с обработкой биг дата, так как писать на норм. языке накладно. Нужно это редко и не всем, а понять судя по коментам может один из ста. Можно это как тест на IQ/знание алгоритмов и PHP использовать, кто не понял — тот пока junior :)
Более бестолковой статьи я на хабре не видел за последние пару лет. Как ЭТО попало сюда?
Автор путает кислое с мягким, пытается открыть какую-то истину, которую и так все знают.
ЧСВ зашкаливает «Про текущий алгоритм отвечу когда мне +100 поставят, за попытку поделится с адекватными думающими людьми рабочим способом-костылем, исправляющим косяки разрабов, а не ерундой никому не нужной.»
Чувак, какие плюсы. Твою статью и комментарии минусуют. Может это не просто так?
Автор путает кислое с мягким, пытается открыть какую-то истину, которую и так все знают.
ЧСВ зашкаливает «Про текущий алгоритм отвечу когда мне +100 поставят, за попытку поделится с адекватными думающими людьми рабочим способом-костылем, исправляющим косяки разрабов, а не ерундой никому не нужной.»
Чувак, какие плюсы. Твою статью и комментарии минусуют. Может это не просто так?
А я видел коменты еще бестолковей. Статья уже такая была, но давно, получила 19 плюсов, я о ней не знал, когда стал эту постить — поискал на всякий случай чтобы не повторяться. Может тогда тогда люди умней были? В последнее время ботов и мультов много, сами себе накручивают, других топят. И не только здесь, в ВК дизлайки запретили.
Оказывается, как долго можно комментировать суффиксное дерево.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
PHP: array_key_exists ищет быстрее чем in_array в 500 раз