Оптимальный поиск фрагментов по массиву

@SerjInsane · Регистрация: 18.10.2012

Студворк — интернет-сервис помощи студентам

Задам свой вопрос на примере:
имеется массив:

PHP/HTML
1
$words = array('as', 'asd', 'asdf', 'asdfg', 'sdf', 'dfg', 'adf', 'sdg', 'gsd', 'rsdr');

и переменная $part в которую будет приходить набор символов. В нашем примере скажем она будет выглядеть след образом:

PHP/HTML
1
$part = 'sd';

далее необходимо найти совпадения фрагмента $part в массиве $words. пока у меня это реализовано след образом:

PHP/HTML
1
2
3
4
5
foreach ($words as $word) {
    if (substr_count($word, $part) > 0) {
          $suggestions[] = $word;
    }
}

Вопрос в следующем:
Можно ли как-то более оптимизировать вариант поиска? Т.к. массив $words будет очень большой. Т.е. может foreach заменить на нечто другое(например iterator)? Или использовать что-нибудь другое вместо sub_str? Буду благодарен за толковые советы.

@Miwa123 · 31.07.2014, 11:09

думаю strpos() будет быстрее работать.
они ищет первое вхождение, затем останавливается и возвращает число.
count - же идет до конца, затем возвращает число.

Добавлено через 11 часов 0 минут
и кстати массив не ассоциативный.
нужно использовать for

PHP
1
2
3
for($i=0;$i<count($arr);$i++)
     if(strpos($words[$i],$part)
          $suggestions[] = $word;

@SerjInsane · 06.08.2014, 10:57 **[ТС]**

Погуглив выяснил, что foreach все же работает быстрее, чем for. За strpos() спасибо. Будут ли еще какие-нибудь советы?

KOPOJI · 06.08.2014, 13:28

Сообщение от Miwa123

PHP
1
if(strpos($words[$i],$part)

вы забыли скобку. Помимо этого вхождение может находится в первом символе, т.е. в нулевом индексе. Strpos вернет 0, он приведется к булеву типу и получите false, хотя должны получить true. Необходимо тождественное сравнение

PHP
1
if(false !== strpos($words[$i], $part))

ну а по поводу вариантов - их можно много придумать.. например, такой

PHP
1
2
3
4
5
6
7
8
$words = array('as', 'asd', 'asdf', 'asdfg', 'sdf', 'dfg', 'adf', 'sdg', 'gsd', 'rsdr');
$part = 'sd';
$suggestions = array();
array_walk($words, function($word) use (&$suggestions, $part) {
    if(false !== strpos($word, $part))
        $suggestions[] = $word;
});
var_dump($suggestions);

Добавлено через 7 минут
помимо этого, preg_match зачастую работает быстрее strpos... Только в погоне за наносекундами можно упустить что-то более важное

@SerjInsane · 21.08.2014, 15:00 **[ТС]**

Сообщение от KOPOJI

ну а по поводу вариантов - их можно много придумать.. например, такой

да, вариантов куча. вот только меня интересует самый оптимальный по быстроте. а array_walk уступает в быстроте по сравнению с foreach.

KOPOJI · 21.08.2014, 15:46

так важны эти наносекунды?

Добавлено через 19 минут

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
Benchmark: timing 1_000_000 iterations of foreach + strpos, foreach + preg_match, for + strpos, for + preg_match, array_walk + strpos, array_walk + preg_match
 
 function               : total sec. @ iterations/sec.
-------------------------------------------------------
 foreach + strpos       :     3.8322 @      260945.0066
 foreach + preg_match   :     7.3149 @      136707.2880
 for + strpos           :     4.0579 @      246431.8589
 for + preg_match       :     7.7775 @      128576.2151
 array_walk + strpos    :     7.8949 @      126663.9214
 array_walk + preg_match:    12.8711 @       77693.4318
 
 
------------------

@SerjInsane · 21.08.2014, 15:49 **[ТС]**

Сообщение от KOPOJI

так важны эти наносекунды?

как говориться, наносекунда микросекунду бережет)
ну а вообще да, я себе поставил задачу найти самый оптимальный вариант. на данный момент это strpos + foreach.

Сообщение от KOPOJI

помимо этого, preg_match зачастую работает быстрее strpos... Только в погоне за наносекундами можно упустить что-то более важное

на счет этого. тут вот выдержка из официального мануала http://php.net/manual/ru/function.preg-match.php:
Не используйте функцию preg_match(), если необходимо проверить наличие подстроки в заданной строке. Используйте для этого strpos() либо strstr(), поскольку они выполнят эту задачу гораздо быстрее.

KOPOJI · 21.08.2014, 15:57

Сообщение от SerjInsane

как говориться

Скорее, "в погоне за мелочами упустишь важное"
Вот вам на 30 итераций

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
Benchmark: timing 30 iterations of foreach + strpos, foreach + preg_match, for + strpos, for + preg_match, array_walk + strpos, array_walk + preg_match
 
 function               : total sec. @ iterations/sec.
-------------------------------------------------------
 foreach + strpos       :     0.0001 @      219214.4948
 foreach + preg_match   :     0.0003 @      100986.4526
 for + strpos           :     0.0001 @      230879.1193
 for + preg_match       :     0.0002 @      120525.9770
 array_walk + strpos    :     0.0003 @      116293.0869
 array_walk + preg_match:     0.0004 @       71250.9173
 
 
------------------

Разница - пара-тройка десятитысячных секунды на 30 итерациях. На одной итерации разница не ощутима.

Сообщение от SerjInsane

тут вот выдержка

я это видел и до этого. Не всегда это так, как там написано.

@SerjInsane · 21.08.2014, 16:01 **[ТС]**

KOPOJI, Спасибо! теперь все видно более наглядно. А как бы мне самому такие тесты проводить, где такое взять?

KOPOJI · 21.08.2014, 16:02

benchmark.php

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
<?php
 
function timethese($count, array $functions) {
    if (!$functions)
        throw new \Exception("No callback function specified");
 
    $names = array_keys($functions);
    $width = max(max(array_map('strlen', $names)), 8);
 
    printf("Benchmark: timing %s iterations of %s" . PHP_EOL, number_format($count, 0, '', '_'), join(', ', $names));
    echo PHP_EOL;
    printf(" %-{$width}s: %10s @ %s", 'function', 'total sec.', 'iterations/sec.');
    echo PHP_EOL, '------', str_repeat('-', $width + 10 + 16), PHP_EOL;
    foreach ($functions as $name => $function) {
        printf(" %-{$width}s: ", $name);
        $start = microtime(true);
        for ($i = 0; $i < $count; ++$i)
            $function();
 
        $total = microtime(true) - $start;
        printf("%10.4F ", $total);
        if ($total >= 0.0001)
            printf("@ %16.4F", $count / $total);
        else
            echo '! Too few inerations';
 
        echo PHP_EOL;
    }
}

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
<?php
 
ini_set('memory_limit', '128M');
set_time_limit(0);
 
require 'benchmark.php';
 
timethese(30, array(
    'foreach + strpos' => function() {
        $words = array('as', 'asd', 'asdf', 'asdfg', 'sdf', 'dfg', 'adf', 'sdg', 'gsd', 'rsdr');
        $part = 'sd';
        $suggestions = array();
        foreach($words as $word)
            if(false !== strpos($word, $part))
                $suggestions[] = $word;
    },
    'foreach + preg_match' => function() {
        $words = array('as', 'asd', 'asdf', 'asdfg', 'sdf', 'dfg', 'adf', 'sdg', 'gsd', 'rsdr');
        $part = 'sd';
        $suggestions = array();
        foreach($words as $word)
            if(1 === preg_match('~' . $part . '~', $word))
                $suggestions[] = $word;
    },
    'for + strpos' => function() {
        $words = array('as', 'asd', 'asdf', 'asdfg', 'sdf', 'dfg', 'adf', 'sdg', 'gsd', 'rsdr');
        $part = 'sd';
        $suggestions = array();
        for($i = 0, $cnt = count($words); $i < $cnt; ++$i)
            if(false !== strpos($words[$i], $part))
                $suggestions[] = $words[$i];
    },
    'for + preg_match' => function() {
        $words = array('as', 'asd', 'asdf', 'asdfg', 'sdf', 'dfg', 'adf', 'sdg', 'gsd', 'rsdr');
        $part = 'sd';
        $suggestions = array();
        for($i = 0, $cnt = count($words); $i < $cnt; ++$i)
            if(1 === preg_match('~' . $part . '~', $words[$i]))
                $suggestions[] = $words[$i];
    },
    'array_walk + strpos' => function() {
        $words = array('as', 'asd', 'asdf', 'asdfg', 'sdf', 'dfg', 'adf', 'sdg', 'gsd', 'rsdr');
        $part = 'sd';
        $suggestions = array();
        array_walk($words, function($word) use (&$suggestions, $part) {
            if(false !== strpos($word, $part))
                $suggestions[] = $word;
        });
    },
    'array_walk + preg_match' => function() {
        $words = array('as', 'asd', 'asdf', 'asdfg', 'sdf', 'dfg', 'adf', 'sdg', 'gsd', 'rsdr');
        $part = 'sd';
        $suggestions = array();
        array_walk($words, function($word) use (&$suggestions, $part) {
            if(1 === preg_match('~' . $part . '~', $word))
                $suggestions[] = $word;
        });
    }
));

@ads · 21.08.2014, 16:09

Сообщение от KOPOJI

preg_match зачастую работает быстрее strpos

Если не сложно, можно ссылку на тест. preg_match интерпретатор текстового выражения, а strpos уже скомпилированная функция посимвольного(побайтового в однобайтной кодировке) сравнения.. ну просто интересно и насколько это принципиально

KOPOJI · 21.08.2014, 16:10

Вот вам, кстати, пример, когда preg_match работает быстрее

PHP
1
2
3
4
5
6
7
8
9
Benchmark: timing 1_000_000 iterations of foreach + mb_strpos, foreach + preg_match
 
 function            : total sec. @ iterations/sec.
----------------------------------------------------
 foreach + mb_strpos :     9.4202 @      106155.0509
 foreach + preg_match:     9.0798 @      110135.0340
 
 
------------------

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
timethese(1000000, array(
    'foreach + mb_strpos' => function() {
        $words = array('слово1', 'слово2', 'слово3', 'слово4', 'слово5', 'слово6', 'слово7', 'слово8', 'слово9', 'слово10');
        $part = 'ово';
        $suggestions = array();
        foreach($words as $word)
            if(false !== mb_strpos($word, $part, 0, 'UTF-8'))
                $suggestions[] = $word;
    },
    'foreach + preg_match' => function() {
        $words = array('слово1', 'слово2', 'слово3', 'слово4', 'слово5', 'слово6', 'слово7', 'слово8', 'слово9', 'слово10');
        $part = 'ово';
        $suggestions = array();
        foreach($words as $word)
            if(1 === preg_match('~' . $part . '~u', $word))
                $suggestions[] = $word;
    }
));

И тут же пример обратного, когда кодировка задается с помощью mb_internal_encoding

Code
1
2
3
4
5
6
7
8
9
Benchmark: timing 1_000_000 iterations of foreach + mb_strpos, foreach + preg_match
 
 function            : total sec. @ iterations/sec.
----------------------------------------------------
 foreach + mb_strpos :     6.0457 @      165406.1116
 foreach + preg_match:    10.8769 @       91938.1380
 
 
------------------

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
mb_internal_encoding('UTF-8');
 
timethese(1000000, array(
    'foreach + mb_strpos' => function() {
        $words = array('слово1', 'слово2', 'слово3', 'слово4', 'слово5', 'слово6', 'слово7', 'слово8', 'слово9', 'слово10');
        $part = 'ово';
        $suggestions = array();
        foreach($words as $word)
            if(false !== mb_strpos($word, $part))
                $suggestions[] = $word;
    },
    'foreach + preg_match' => function() {
        $words = array('слово1', 'слово2', 'слово3', 'слово4', 'слово5', 'слово6', 'слово7', 'слово8', 'слово9', 'слово10');
        $part = 'ово';
        $suggestions = array();
        foreach($words as $word)
            if(1 === preg_match('~' . $part . '~u', $word))
                $suggestions[] = $word;
    }
));

Хотя эти два кода несколько различаются, все же

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@SerjInsane 0 / 0 / 0 Регистрация: 18.10.2012 Сообщений: 30
	06.08.2014, 10:57 [ТС]
	Погуглив выяснил, что foreach все же работает быстрее, чем for. За strpos() спасибо. Будут ли еще какие-нибудь советы? 0

@SerjInsane 0 / 0 / 0 Регистрация: 18.10.2012 Сообщений: 30
	21.08.2014, 16:01 [ТС]
	KOPOJI, Спасибо! теперь все видно более наглядно. А как бы мне самому такие тесты проводить, где такое взять? 0