Форумы портала PHP.SU :: Версия для печати :: Быстрая проверка существования строки среди других

Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770
Форумы портала PHP.SU :: Версия для печати :: Быстрая проверка существования строки среди других

Форумы портала PHP.SU » » Хранение данных, их вывод и обработка » Быстрая проверка существования строки среди других

Страниц (1): [1]

1. Edwvee - 24 Октября, 2013 - 15:10:37 - перейти к сообщению

Есть уникальные строки, есть потребность проверить существует ли среди них какая-либо строка. Интересно как в php добиться в этом максимальной скорости. Пока идея такая:

PHP:
скопировать код в буфер обмена

 
//тестовое представление структуры для поиска в ней
$strings = array();
for($i = 0; $i<1000000; ++$i)
{
    $strings[$i] = true; //значение не важно, надеюсь булевый тип меньше всего занимает память в php
}
 
...//тут другой код и инициализируется переменая $key
 
if (isset($strings[$key]))
{
   ...
}
 

2. IllusionMH - 24 Октября, 2013 - 15:16:58 - перейти к сообщению

Edwvee, array_search?

3. Edwvee - 24 Октября, 2013 - 15:54:15 - перейти к сообщению

Неа, для этой цели фигня. Если ищется существующее значение, то одно и то же время тратится. Если же ищется значение которое не существует, то при выполнении скриптов ниже у меня с моим способом выполняется за то же самое время 0.15, c array_search за 9-14 секунд на протестированнных значениях.
Скрипт с моим способом:

PHP:
скопировать код в буфер обмена

 
$strings = array();
 
$startTime = microtime(true);
for($i = 0; $i<100000; ++$i)
{
    $strings[md5($i)] = true; 
}
 
for ($j = 0; $j<1000; $j++)
{
        if (isset($strings[$key]))
        {
           echo 'found!';
        }
}
$endTime = microtime(true);
$time = $endTime - $startTime;
 
echo '<br>';
echo $time;
 

Скрипт с array_search:

PHP:
скопировать код в буфер обмена

 
<?PHP 
$strings = array();
 
$startTime = microtime(true);
for($i = 0; $i<100000; ++$i)
{
    $strings[] = md5($i); 
}
 
for ($j = 0; $j<1000; $j++)
{
        if (array_search($key, $strings))
        {
           echo 'found!';
        }
}
$endTime = microtime(true);
$time = $endTime - $startTime;
 
echo '<br>';
echo $time;
 

Попробуйте реализовать оба с
$key = md5(10000), например
и $key = md5(10000000000)

Я думаю код примерно одинаков по нагрузке для этих двух методов.

Может можно быстрее?

4. Ch_chov - 24 Октября, 2013 - 16:01:54 - перейти к сообщению

Нафига array_search внутри цикла?

5. Edwvee - 24 Октября, 2013 - 16:02:51 - перейти к сообщению

У меня если что apache на винде стоит, что есть не подходящая платформа для него и пхп.
На линуксовой машине оказалось ~0.5c мой способ и примерно ~4c cпособ с array_search
(Добавление)

Ch_chov пишет:

Нафига array_search внутри цикла?

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

6. Ch_chov - 24 Октября, 2013 - 16:11:38 - перейти к сообщению

Ясно. Ну если разделить полученное значение на 1000 то результат будет в микросекундах. Поэтому нет никакого смысла с этим заморачиваться. Для поиска ключей в массиве есть array_key_exist

http://ilia[dot]ws/archives/247-Performance-Analysis-of-isset-vs-array_key_exists.html

7. Edwvee - 24 Октября, 2013 - 16:24:48 - перейти к сообщению

Измеряется же не только время выполнения инструкций среднее, но и время для создания такого массива.
Насчет array_key_exists:
Время то же самое, выходит, но символов больше. А свойство ниже в данном случае не влияет на результат, так как нигде null не присваивается.

Цитата:

isset() does not return TRUE for array keys that correspond to a NULL value, while array_key_exists() does.

8. Мелкий - 24 Октября, 2013 - 16:26:52 - перейти к сообщению

Edwvee, для чего вы включили во время теста время генерации тестовых данных? Для получения статистического времени поиска в массиве, а не времени генерации тестовых данных, надо считать только время поиска, а так же количество итераций увеличить ещё хотя бы на 3-4 порядка.

По ключу всегда искать быстрее, чем по значению.

9. Edwvee - 24 Октября, 2013 - 16:48:25 - перейти к сообщению

Реальная задача недавняя
Есть таблица в бд, есть потребность загрузить из csv файла в эту таблицу, только нужно было в таблице сохранить уникальность сочетания столбец1, столбец2, столбец3. Я грузил таблицу целиком(меньше 50000 записей), формировал из записей строки по этим трем столбцам, и по записям из цсв файла тоже, и искал наличие строки из цсв файла в строках из бд, чтобы знать отсылать ли ее на insert. Так что время формирования нужной формы данных тоже влияет(может оно и не отличается особо в этих двух способах). Да и думаю во многих задачах представление набора строк можно формировать и так, и так.

10. Мелкий - 24 Октября, 2013 - 17:00:51 - перейти к сообщению

Edwvee пишет:

Так что время формирования нужной формы данных тоже влияет

Не влияет. Вы изобрели hash-индекс, его штатное свойство - врать о позитивных срабатываниях, но врать быстро.

Уникальный индекс и insert ignore или insert ... on duplicate key решает большинство поставленных вопросов.
create temporary table и последующим join'ом по having count(0)>1 и разруливанием из кода, какую из версию надо оставить, решает все остальные проблемы.
А ещё есть LOAD DATA.