Лучший способ перебора

@Sherzant · Регистрация: 03.09.2012

Не знал как назвать тему. В общем проблема в следующем.
Есть 20-25 массивов по 10-30 элементами. Приведу пример с меньшим количеством скажем 3 массива по 4 элемента. Пользователь вводит в поле одно число, допустим 5000. Скрипт должен показать при сложении каких элементов массивов результат получится число, которое ввел пользователь, т.е. в нашем случае 5000. При сложении из каждого массива берется только 1 элемент.

К примеру,
$a1 = array("0", "500", "1000", "2300");
$a2 = array("200", "1400", "1600", "4000");
$a3 = array("0", "1100", "2900", "3100");

Результат должен быть типа таким:
1. $a1[1] + $a2[1] + $a3[3] равно 5000
2. $a1[1] + $a2[2] + $a3[2] равно 5000
3. $a1[2] + $a2[3] равно 5000
4. $a1[3] + $a2[2] + $a3[1] равно 5000

я написал такой код:

PHP

for($index_a1=0;$index_a1<count($a1);$index_a1++)
for($index_a2=0;$index_a2<count($a2);$index_a2++)
for($index_a3=0;$index_a3<count($a3);$index_a3++)
{
$result[$index_a1] = $a1[$index_a1] + $a2[$index_a2] + $a3[$index_a3];
if($chislo == $result[$index_a1]) echo "Тут выводится результат..."; //$chislo - число введенных пользователем
}

при маленьких массивах этот код работает нормально, но как говорил выше когда массивы становятся 20-25 и у каждого по 10-30 элементов скрипт зависает, так как циклы увеличиваются. чтобы выполнить такой скрипт нужен комп который смог бы обрабатывать 546 750 триллион (10^12) операций в секунду. а мой комп как показал скрипт обрабатывает ~700 000 операций в секунду, т.е. нужен комп работающий в 781 миллиард раз быстрее))

такого компа в ближайшем будущем я не найду, поэтому нужен совет, может быть есть какой нибудь более простой способ перебора элементов массивов?

@casual_visitor · 01.02.2013, 15:36

Архитектурная ошибка. Для подобного поиска используются не массивы, а деревья... Как вариант:организовать деревья в виде вложенных множеств

@Sherzant · 04.02.2013, 13:45 **[ТС]**

прочитал несколько статей на эту темку, но так и не до понял. может напишите как делается?

@palva · 04.02.2013, 14:10

1. Ускорить работу могло бы хранение чисел не в виде строк, а в виде чисел.
2. Работа пошла бы еще быстрее, если написать перебор на компилируемом языке (си, дельфи) и подключить к PHP. Как это сделать я не знаю, но знаю, что это возможно.
3. Если бы про сами числа было известно больше, (например, все числа неотрицательны), то можно было бы сэкономить на алгоритме. А когда про числа ничего не известно, то оптимальней вашего сам алгоритм написать, по-моему, нельзя.

@alpex · 04.02.2013, 18:17

вот немного похожая задача на вашу https://www.youtube.com/watch?v=iNTmu2STGGQ

@Sherzant · 07.02.2013, 15:07 **[ТС]**

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

1. Ускорить работу могло бы хранение чисел не в виде строк, а в виде чисел.
2. Работа пошла бы еще быстрее, если написать перебор на компилируемом языке (си, дельфи) и подключить к PHP. Как это сделать я не знаю, но знаю, что это возможно.
3. Если бы про сами числа было известно больше, (например, все числа неотрицательны), то можно было бы сэкономить на алгоритме. А когда про числа ничего не известно, то оптимальней вашего сам алгоритм написать, по-моему, нельзя.

1. Элементы массива теперь как числа. Быстродействие скрипта увеличился на 25-35% (950000 операций вместо старых 700000).
2. На Си пока не пробовал, если пхп не справится с задачей, тогда попробую.
3. Числа в диапазоне от 0-2000. Что посоветуете изменить в алгоритме?

@palva · 07.02.2013, 15:27

Если первые числа большие, так что сумма заведомо превысит $сhislo, то цикл можно прервать и не заниматься перебором чисел из второго и третьего массивов. Можно кое-что вычислить перед циклом, чтобы многократно не вычислять одно и то же внутри цикла.

PHP

$ca1=count($a1);
$ca2=count($a2);
$ca3=count($a3);
for($index_a1=0;$index_a1<$ca1);$index_a1++) {
    $result=$a1[$index_a1];
    if($result>$chislo) break;
    for($index_a2=0;$index_a2<$ca2);$index_a2++) {
        $result+=$a2[$index_a1];
        if($result>$chislo) break;
        for($index_a3=0;$index_a3<$ca3);$index_a3++) {
            $result+=$a3[$index_a1];
            if($chislo == $result[$index_a1]) echo "Тут выводится результат...";
        }
    }
}

@hellmin · 07.02.2013, 17:06

Где-то тут лишняя скобка, ну да это не проблема найти.

PHP

1	for($index_a1=0;$index_a1<$ca1);$index_a1++) {

а вот код

PHP

1 2	$ca1=count($a1); for($index_a1=0;$index_a1<$ca1;$index_a1++) {

от кода

PHP

1	for($index_a1=0;$index_a1<count($a1);$index_a1++) {

отличается только дополнительно используемой памятью и лишней строкой, но не как не скоростью.

Добавлено через 16 минут
Упс, по поводу скорости и памяти я не прав. http://php.net/manual/ru/contr... es.for.php .
Хотя раньше находил инфу, что count, куда-то запоминается)

@oke11o · 07.02.2013, 17:11

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

отличается только дополнительно используемой памятью и лишней строкой, но не как не скоростью.

Вроде скоростью тоже. Поставил эксперимент:

PHP

$array = array();
for ($i = 0; $i < 10; $i++) {
    $array[] = null;
}
$iterations = 10000000;
 
$tstart = microtime(true);
for ($i = 0; $i < $iterations; $i++) {
    for ($j = 0; $j < count($tstart); $j++) {
        $test = null;
    }
}
$tact = microtime(true) - $tstart;
echo "Время count() - {$tact}sec<br/>" . PHP_EOL;
 
$tstart = microtime(true);
$count = count($tstart);
for ($i = 0; $i < $iterations; $i++) {
    for ($j = 0; $j < $count; $j++) {
        $test = null;
    }
}
$tact = microtime(true) - $tstart;
echo "Время \$count - {$tact}sec<br/>" . PHP_EOL;

Код

Вывод:
Время count() - 6.8720488548279sec
Время $count - 2.5031878948212sec

@hellmin · 07.02.2013, 17:48

Не поленился и тоже провел эксперимент из 3-х циклов. Размер массива 30 элементов, количество итераций оставил такое же (10000000).

PHP

for ($j = 0; $j < count($array); $j++) {
 
$count = count($array);
for ($j = 0; $j < $count; $j++) {
 
for ($j = 0, $count = count($array); $j < $count; $j++) {

результаты получились такие

Код

Время count() - 69.72768497467sec
Время $count - 19.816310882568sec
Время $count - 21.433360099792sec

а вот результат, когда 60 элементов массива

Код

Время count() - 135.37351417542sec
Время $count - 38.991626977921sec
Время $count - 40.667366981506sec

Занимательно, что последние два результа отличаются на 2 сек, даже при 3-х элементах в массиве)

@Nebiros · 07.02.2013, 17:56

Sherzant не знаю правильно ли я понял но почему бы не использовать foreach?

PHP

function total_sum($arr){
 $n=0;
 foreach($arr as $vl){
  $n=$n+$vl;
  }
 return $n;
 }
 
echo total_sum($a1);
echo total_sum($a2);
echo total_sum($a3);

@alpex · 07.02.2013, 19:03

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

PHP

1	for ($j = 0; $j < count($array); $j++)

не пишите так, при такой записи на каждой итерации цикла производится подсчет елементов функцией count, хотя это значение достаточно посчитать один раз

PHP

1	for ($j = 0, $cnt = count($array); $j < $cnt; $j++)

@hellmin · 08.02.2013, 12:53

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

но почему бы не использовать foreach?

А ведь и правда... при количестве элементов массива 40 разница по времени в два раза.

PHP

foreach($a1 as $k1=>$v1)
{
    if($v1>$chislo)
        break;
    foreach($a2 as $k2=>$v2)
    {
        if(($v1+$v2)>$chislo)
            break;
        foreach($a3 as $k3=>$v3)
        {
            $result[$k1] = $v1 + $v2 + $v3;
            if($chislo == $result[$k1])
                echo "Тут выводится результат... $k1 $k2 $k3 \n"; //$chislo - число введенных пользователем
        }
    }
}

@Sherzant · 12.02.2013, 16:25 **[ТС]**

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

Если первые числа большие, так что сумма заведомо превысит $сhislo, то цикл можно прервать и не заниматься перебором чисел из второго и третьего массивов. Можно кое-что вычислить перед циклом, чтобы многократно не вычислять одно и то же внутри цикла.

об этом как то не подумал, хороший совет, спасибо)

Спасибо и экспериментаторам oke11o, hellmin )) узнал новые методы

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

Кликните здесь для просмотра всего текста

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

Sherzant не знаю правильно ли я понял но почему бы не использовать foreach?

PHP

function total_sum($arr){
 $n=0;
 foreach($arr as $vl){
  $n=$n+$vl;
  }
 return $n;
 }
 
echo total_sum($a1);
echo total_sum($a2);
echo total_sum($a3);

нет, вы меня не совсем поняли. если не ошибаюсь ваша функция сложит все элементы одного массива и выводит общую сумму. а мне надо чтобы в результат входил максимум по 1 элементу из всех массивов.

Кликните здесь для просмотра всего текста

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

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

А ведь и правда... при количестве элементов массива 40 разница по времени в два раза.

PHP

foreach($a1 as $k1=>$v1)
{
    if($v1>$chislo)
        break;
    foreach($a2 as $k2=>$v2)
    {
        if(($v1+$v2)>$chislo)
            break;
        foreach($a3 as $k3=>$v3)
        {
            $result[$k1] = $v1 + $v2 + $v3;
            if($chislo == $result[$k1])
                echo "Тут выводится результат... $k1 $k2 $k3 \n"; //$chislo - число введенных пользователем
        }
    }
}

такой подход действительно интересный, сейчас попробую)

Добавлено через 1 час 4 минуты
действительно для этой задачки метод foreach оказался лучше.
для теста использовал 5 массивов с 30 элементами.
метод for обработал и вывел результаты за 12.429224968 секунд.
метод foreach за 7.36549782753 секунд.

@casual_visitor 87 / 87 / 8 Регистрация: 02.09.2012 Сообщений: 510
	01.02.2013, 15:36	2
	Архитектурная ошибка. Для подобного поиска используются не массивы, а деревья... Как вариант:организовать деревья в виде вложенных множеств 0

@Sherzant 5 / 4 / 4 Регистрация: 03.09.2012 Сообщений: 91
	04.02.2013, 13:45 [ТС]	3
	прочитал несколько статей на эту темку, но так и не до понял. может напишите как делается? 0

@palva 3944 / 2858 / 665 Регистрация: 08.06.2007 Сообщений: 9,662 Записей в блоге: 4
	04.02.2013, 14:10	4
	1. Ускорить работу могло бы хранение чисел не в виде строк, а в виде чисел. 2. Работа пошла бы еще быстрее, если написать перебор на компилируемом языке (си, дельфи) и подключить к PHP. Как это сделать я не знаю, но знаю, что это возможно. 3. Если бы про сами числа было известно больше, (например, все числа неотрицательны), то можно было бы сэкономить на алгоритме. А когда про числа ничего не известно, то оптимальней вашего сам алгоритм написать, по-моему, нельзя. 1

@alpex 603 / 578 / 103 Регистрация: 16.07.2012 Сообщений: 1,762
	04.02.2013, 18:17	5
	вот немного похожая задача на вашу https://www.youtube.com/watch?v=iNTmu2STGGQ 1

@Sherzant 5 / 4 / 4 Регистрация: 03.09.2012 Сообщений: 91
	07.02.2013, 15:07 [ТС]	6
	Сообщение от palva 1. Ускорить работу могло бы хранение чисел не в виде строк, а в виде чисел. 2. Работа пошла бы еще быстрее, если написать перебор на компилируемом языке (си, дельфи) и подключить к PHP. Как это сделать я не знаю, но знаю, что это возможно. 3. Если бы про сами числа было известно больше, (например, все числа неотрицательны), то можно было бы сэкономить на алгоритме. А когда про числа ничего не известно, то оптимальней вашего сам алгоритм написать, по-моему, нельзя. 1. Элементы массива теперь как числа. Быстродействие скрипта увеличился на 25-35% (950000 операций вместо старых 700000). 2. На Си пока не пробовал, если пхп не справится с задачей, тогда попробую. 3. Числа в диапазоне от 0-2000. Что посоветуете изменить в алгоритме? 0