Форум программистов, компьютерный форум, киберфорум
Наши страницы
PHP для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
SerjInsane
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 30
#1

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

30.07.2014, 11:25. Просмотров 1315. Ответов 11
Метки нет (Все метки)

Задам свой вопрос на примере:
имеется массив:
PHPHTML
1
$words = array('as', 'asd', 'asdf', 'asdfg', 'sdf', 'dfg', 'adf', 'sdg', 'gsd', 'rsdr');
и переменная $part в которую будет приходить набор символов. В нашем примере скажем она будет выглядеть след образом:
PHPHTML
1
$part = 'sd';
далее необходимо найти совпадения фрагмента $part в массиве $words. пока у меня это реализовано след образом:
PHPHTML
1
2
3
4
5
foreach ($words as $word) {
    if (substr_count($word, $part) > 0) {
          $suggestions[] = $word;
    }
}
Вопрос в следующем:
Можно ли как-то более оптимизировать вариант поиска? Т.к. массив $words будет очень большой. Т.е. может foreach заменить на нечто другое(например iterator)? Или использовать что-нибудь другое вместо sub_str? Буду благодарен за толковые советы.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2014, 11:25
Ответы с готовыми решениями:

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

Поиск по массиву
Добрый день. Нужна помощь. Допустим, у нас есть такой вот массив: $mass =...

Поиск по массиву
Задание:Описать массив расписание, содержащий день недели; количество пар в...

Поиск по массиву
Всем привет. Помогите справиться с задачей. Есть два массива. 1. Массив...

Поиск по массиву
Можете подсказать как реализовать, функцию, которая будет искать все значения...

11
Miwa123
37 / 37 / 22
Регистрация: 16.04.2013
Сообщений: 319
Записей в блоге: 1
31.07.2014, 11:09 #2
думаю strpos() будет быстрее работать.
они ищет первое вхождение, затем останавливается и возвращает число.
count - же идет до конца, затем возвращает число.

Добавлено через 11 часов 0 минут
и кстати массив не ассоциативный.
нужно использовать for
PHP
1
2
3
for($i=0;$i<count($arr);$i++)
     if(strpos($words[$i],$part)
          $suggestions[] = $word;
1
SerjInsane
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 30
06.08.2014, 10:57  [ТС] #3
Погуглив выяснил, что foreach все же работает быстрее, чем for. За strpos() спасибо. Будут ли еще какие-нибудь советы?
0
KOPOJI
Почетный модератор
Эксперт HTML/CSSЭксперт PHP
16750 / 6641 / 864
Регистрация: 12.06.2012
Сообщений: 19,892
Завершенные тесты: 1
06.08.2014, 13:28 #4
Цитата Сообщение от 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... Только в погоне за наносекундами можно упустить что-то более важное
1
SerjInsane
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 30
21.08.2014, 15:00  [ТС] #5
Цитата Сообщение от KOPOJI Посмотреть сообщение
ну а по поводу вариантов - их можно много придумать.. например, такой
да, вариантов куча. вот только меня интересует самый оптимальный по быстроте. а array_walk уступает в быстроте по сравнению с foreach.
0
KOPOJI
Почетный модератор
Эксперт HTML/CSSЭксперт PHP
16750 / 6641 / 864
Регистрация: 12.06.2012
Сообщений: 19,892
Завершенные тесты: 1
21.08.2014, 15:46 #6
так важны эти наносекунды?

Добавлено через 19 минут
Код
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


------------------
1
SerjInsane
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 30
21.08.2014, 15:49  [ТС] #7
Цитата Сообщение от KOPOJI Посмотреть сообщение
так важны эти наносекунды?
как говориться, наносекунда микросекунду бережет)
ну а вообще да, я себе поставил задачу найти самый оптимальный вариант. на данный момент это strpos + foreach.
Цитата Сообщение от KOPOJI Посмотреть сообщение
помимо этого, preg_match зачастую работает быстрее strpos... Только в погоне за наносекундами можно упустить что-то более важное
на счет этого. тут вот выдержка из официального мануала http://php.net/manual/ru/function.preg-match.php:
Не используйте функцию preg_match(), если необходимо проверить наличие подстроки в заданной строке. Используйте для этого strpos() либо strstr(), поскольку они выполнят эту задачу гораздо быстрее.
0
KOPOJI
Почетный модератор
Эксперт HTML/CSSЭксперт PHP
16750 / 6641 / 864
Регистрация: 12.06.2012
Сообщений: 19,892
Завершенные тесты: 1
21.08.2014, 15:57 #8
Цитата Сообщение от SerjInsane Посмотреть сообщение
как говориться
Скорее, "в погоне за мелочами упустишь важное"
Вот вам на 30 итераций
Код
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 Посмотреть сообщение
тут вот выдержка
я это видел и до этого. Не всегда это так, как там написано.
1
SerjInsane
0 / 0 / 0
Регистрация: 18.10.2012
Сообщений: 30
21.08.2014, 16:01  [ТС] #9
KOPOJI, Спасибо! теперь все видно более наглядно. А как бы мне самому такие тесты проводить, где такое взять?
0
KOPOJI
Почетный модератор
Эксперт HTML/CSSЭксперт PHP
16750 / 6641 / 864
Регистрация: 12.06.2012
Сообщений: 19,892
Завершенные тесты: 1
21.08.2014, 16:02 #10
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;
        });
    }
));
1
ads
364 / 371 / 89
Регистрация: 01.12.2013
Сообщений: 1,629
21.08.2014, 16:09 #11
Цитата Сообщение от KOPOJI Посмотреть сообщение
preg_match зачастую работает быстрее strpos
Если не сложно, можно ссылку на тест. preg_match интерпретатор текстового выражения, а strpos уже скомпилированная функция посимвольного(побайтового в однобайтной кодировке) сравнения.. ну просто интересно и насколько это принципиально
0
KOPOJI
Почетный модератор
Эксперт HTML/CSSЭксперт PHP
16750 / 6641 / 864
Регистрация: 12.06.2012
Сообщений: 19,892
Завершенные тесты: 1
21.08.2014, 16:10 #12
Вот вам, кстати, пример, когда 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
Код
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;
    }
));
Хотя эти два кода несколько различаются, все же
0
21.08.2014, 16:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.08.2014, 16:10

Поиск по многомерному массиву
Делаю для своего сайта форму бронирования, уже сделал все остался последний...

Поиск по отсортированному массиву
Добрый день. Не знаю подходит ли вопрос к теме: &quot;php для начинающих&quot; или нет,...

Поиск по массиву с несколькими критериями
допустим у меня есть массив чтото вроде этого $arr=array( ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru