Вы проверили эти тесты и алгоритмы? Быстрее стало или так же/хуже? Пока что никто не написал, все пишут какие то свои фантазии. Наверно никогда строки в массивах не искали.
А я видел коменты еще бестолковей. Статья уже такая была, но давно, получила 19 плюсов, я о ней не знал, когда стал эту постить — поискал на всякий случай чтобы не повторяться. Может тогда тогда люди умней были? В последнее время ботов и мультов много, сами себе накручивают, других топят. И не только здесь, в ВК дизлайки запретили.
там комментировали трупы, можно их попинать, чтобы сходили проверили тесты раз, и написали свои тесты и проверили на своих серверах в разных версиях пхп и питона два.
Хеш таблицы это отображение одного множества строк в другое. Каждый байт хеша уменьшает область поиска в 256 раз, а бинарный поиск=метод половинного деления делает это за 8 шагов в одном потоке.
К сожалению на скриптовом языке сейчас много алгоритмов в том числе и связанными с обработкой биг дата, так как писать на норм. языке накладно. Нужно это редко и не всем, а понять судя по коментам может один из ста. Можно это как тест на IQ/знание алгоритмов и PHP использовать, кто не понял — тот пока junior :)
array это массив, индекс число.
ассоциативный массив это по сути словарь ключ-значение, у него индекс это строка.
В питоне это тип dict там понятней. в php/js это одинаково и числа это тоже как строки- быстрее не ищет, значит тоже по хеш, а не по смещению.
А где я писал какой алгоритм там? Вам опять показалось. Я написал какие алгоритмы поиска есть и как можно еще улучшить, то что есть сейчас, но здесь большинству даже просто проверить лень что способ просто рабочий без всяких объяснений, С кем тут о чем спорить? чтобы мне минусов наставили вместо спасибо? Мне это не надо. Да и вообще люди стараются, разбираются, изучают, делятся бесплатно полезной инфой и что? приходят хейтеры и минусуют, кому охота после этого что-то сюда писать и объяснять? На форумах чтобы поставить минус надо иметь большую репутацию и написать за что и это проверит модераторы и админ -защита от ботов, мультов и неадекватных.
Вот когда тебе дадут реальное задание — есть миллион строк — слова/фразы/итд. биг дата, накопили за 10 лет. что то, и надо написать экспертную систему — которая в том числе и ищет в словарях — есть/нет и делает что-то, вот попробуй это сделать. Там не в 100 строках искать надо и времени надо очень много, тогда будешь писать это на си или можно найти способ попроще, ведь одну задачу можно решить разными путями, только затраты на разработку и время работы разное. Наличие строки это тоже поиск.
очень полезно, я начинал с него, а еще лучше пару лет пооптимизировать машинный код после стандартных компиляторов- тогда сразу понятно как и что можно ускорить, я иногда в сотни раз после них ускорял.
Мне это реально помогло, вот и написал, может другим поможет тоже, памяти надо больше, сразу сказал. Надо экономить- искать частями, выгружать, загружать. Выигрыш есть, и не копейки, массив может прийти из вне, или из файла, пока что надо флипать его заранее или переделывать сам in_array() или писать на др. языке свой оптимальный поиск, выбирать размер хеш и алгоритм хеширования и считать по шагам что лучше, через хеш можно в нес-ко потоков искать, а бинарный поиск только в одном. тут 1байт-и делать хеш, там сортировка и сравнения. В разных случаях — наилучший свой.
Писали что в 7.2 улучшили этот поиск через обратный массив и хеш, но я сравнил — разница не заметна, сейчас через индекс быстрее и намного.
Вообще глупо искать пусто в массиве, у меня таких задач никогда не было и вряд ли это имеет практически смысл, но если сильно надо, то можно не искать а проверить строку на пусто и это быстрее в миллион раз.
перебор? смешно, ну так и ищете перебором месяц, а мы будем за час искать через хеш или бинарный поиск — зависит от размера и памяти. Выше объяснил, кто не понял — гугл в помощь.
Не надо ля-ля, добавить значение в индекс не дольше чем в массив, а исправить можно так — делаем копию массива и хешей в первый раз и кешируем.
in_array это как раз та самая «правильная» ф-я которую надо использовать при поиске, а за костыль этот могут уволить или минусов наставить, людям не надо быстро — им надо понятно. А этот способ он не для всех, а кто шарит.
1. идем сюда ideone.com/Yb1mDa — общее время 0.68s, только поиск 0.66s
2. идем сюда ideone.com/gwSmFc — общее время 0.14s, только поиск 0.12s
во втором поисков больше в 100 раз. считаем. 6800/14=? в каком месте неправильно? за что там +6, а мне -5? Вы хоть в школе учились? или это боты?
Заголовок про поиск в массиве через in_array() — это проверка есть/нет а не позиции в массиве. Это очень сложно понять?
Про текущий алгоритм отвечу когда мне +100 поставят, за попытку поделится с адекватными думающими людьми рабочим способом-костылем, исправляющим косяки разрабов, а не ерундой никому не нужной.
Это тот же поиск строки в массиве строк, из тестов видно же, никаких фокусов и обмана. Возьмите массив миллиард строк и 10к строк для поиска. Надо узнать какие строки есть в этом массиве, а каких нет.
in_array() — это обычная ф-я, она для этого сделана. Но можно этот же массив превратить в массив индексов-строк для словаря(ассоц.массива) и тогда проверка есть ли такой ключ будет аналогом поиска в массиве, но здесь идет поиск по другому алгоритму (а именно через таблицу хешей, но об этом мало кто знает) и одинаковые и пустые значения запрещены. Но для поиска они обычно не нужны. Если надо, то на пусто можно проверять отдельно — это быстро.
Еще in_array() может искать 0, null,'' как пусто и значением может быть пустая строка, в индексах — не может, но '0', 0 — можно.
$m=array_combine($m,$m) делает массив уникальным без лишних вопросов.
array_flip меняет местами ключи и значения. на повторы и пусто не проверял. Да можно в простом цикле это сделать. $r=[];foreach($m as $v)if($v)$r[$v]=0;
На время почти не влияет если искать очень много: это делается один раз до поиска.
Да, все правильно, в небольших массивах разницы почти нет, а в очень больших есть, но надо больше памяти на хеш и массив хешей, я думал если в in_array бинарный поиск, то сортировка заранее может поможет и сделать уникальным массив — нет, не помогает, так же долго. Видимо сортирует каждый раз или хеш считает. А с ключами-индексами один раз и кешируется всё. Можно код посмотреть, он открыт. А почему это не сделано в in_array и в питоне. Вот вопрос. Поиск в массиве очень частая и нужная операция. Но все юзают медленный способ, так как быстрый не знают и не узнают. Статья ушла в минус. Наверно люди думают что это ерунда и бред. Кстати за за статью об «обыске массиве» 6 лет назад, ни одного минуса, а там про тоже самое почти но менее подробно, а заголовок неудачный — я бы даже читать не стал.
В статье код теста есть и видно что 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-кол-во байт на хеш.
Хеш таблицы это отображение одного множества строк в другое. Каждый байт хеша уменьшает область поиска в 256 раз, а бинарный поиск=метод половинного деления делает это за 8 шагов в одном потоке.
К сожалению на скриптовом языке сейчас много алгоритмов в том числе и связанными с обработкой биг дата, так как писать на норм. языке накладно. Нужно это редко и не всем, а понять судя по коментам может один из ста. Можно это как тест на IQ/знание алгоритмов и PHP использовать, кто не понял — тот пока junior :)
ассоциативный массив это по сути словарь ключ-значение, у него индекс это строка.
В питоне это тип dict там понятней. в php/js это одинаково и числа это тоже как строки- быстрее не ищет, значит тоже по хеш, а не по смещению.
Писали что в 7.2 улучшили этот поиск через обратный массив и хеш, но я сравнил — разница не заметна, сейчас через индекс быстрее и намного.
in_array это как раз та самая «правильная» ф-я которую надо использовать при поиске, а за костыль этот могут уволить или минусов наставить, людям не надо быстро — им надо понятно. А этот способ он не для всех, а кто шарит.
2. идем сюда ideone.com/gwSmFc — общее время 0.14s, только поиск 0.12s
во втором поисков больше в 100 раз. считаем. 6800/14=? в каком месте неправильно? за что там +6, а мне -5? Вы хоть в школе учились? или это боты?
Заголовок про поиск в массиве через in_array() — это проверка есть/нет а не позиции в массиве. Это очень сложно понять?
Про текущий алгоритм отвечу когда мне +100 поставят, за попытку поделится с адекватными думающими людьми рабочим способом-костылем, исправляющим косяки разрабов, а не ерундой никому не нужной.
in_array() — это обычная ф-я, она для этого сделана. Но можно этот же массив превратить в массив индексов-строк для словаря(ассоц.массива) и тогда проверка есть ли такой ключ будет аналогом поиска в массиве, но здесь идет поиск по другому алгоритму (а именно через таблицу хешей, но об этом мало кто знает) и одинаковые и пустые значения запрещены. Но для поиска они обычно не нужны. Если надо, то на пусто можно проверять отдельно — это быстро.
Еще in_array() может искать 0, null,'' как пусто и значением может быть пустая строка, в индексах — не может, но '0', 0 — можно.
array_flip меняет местами ключи и значения. на повторы и пусто не проверял. Да можно в простом цикле это сделать. $r=[];foreach($m as $v)if($v)$r[$v]=0;
На время почти не влияет если искать очень много: это делается один раз до поиска.
А насчет хеш, некоторые даже не знают что это такое, разработчики 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-кол-во байт на хеш.