Форум программистов, компьютерный форум, киберфорум
PHP для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/18: Рейтинг темы: голосов - 18, средняя оценка - 4.56
5 / 4 / 4
Регистрация: 03.09.2012
Сообщений: 90
1

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

01.02.2013, 14:28. Показов 3153. Ответов 13
Метки нет (Все метки)

Не знал как назвать тему. В общем проблема в следующем.
Есть 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
1
2
3
4
5
6
7
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 миллиард раз быстрее))

такого компа в ближайшем будущем я не найду, поэтому нужен совет, может быть есть какой нибудь более простой способ перебора элементов массивов?
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.02.2013, 14:28
Ответы с готовыми решениями:

Дорогие знатоки! Какой по вашему мнению самый лучший способ перевести кракозябры на русский?
Сканирую директорию(scandir()),проблемы с русским языком, вместо русского кракозябры. Неужели...

Лучший способ идентификации и аутентификации (Auth0/Firebase)
Ломают голову, какой способ идентификации и аутентификации выбрать на сайт. Структура примерно...

Прошу предложить лучший вариант перебора массива
Всем доброго дня, такой вопросик. есть массив int array = { 1, 2, 3, 4, 5, 6, 7 }; ...

Лучший способ апгрейда
Сразу расскажу, для чего мне нужен апгрейд. Мой ПК пока тянет доту на приемлемых настройках в 100...

13
87 / 87 / 8
Регистрация: 02.09.2012
Сообщений: 510
01.02.2013, 15:36 2
Архитектурная ошибка. Для подобного поиска используются не массивы, а деревья... Как вариант:организовать деревья в виде вложенных множеств
0
5 / 4 / 4
Регистрация: 03.09.2012
Сообщений: 90
04.02.2013, 13:45  [ТС] 3
прочитал несколько статей на эту темку, но так и не до понял. может напишите как делается?
0
3836 / 2768 / 641
Регистрация: 08.06.2007
Сообщений: 9,456
Записей в блоге: 4
04.02.2013, 14:10 4
1. Ускорить работу могло бы хранение чисел не в виде строк, а в виде чисел.
2. Работа пошла бы еще быстрее, если написать перебор на компилируемом языке (си, дельфи) и подключить к PHP. Как это сделать я не знаю, но знаю, что это возможно.
3. Если бы про сами числа было известно больше, (например, все числа неотрицательны), то можно было бы сэкономить на алгоритме. А когда про числа ничего не известно, то оптимальней вашего сам алгоритм написать, по-моему, нельзя.
1
603 / 578 / 103
Регистрация: 16.07.2012
Сообщений: 1,762
04.02.2013, 18:17 5
вот немного похожая задача на вашу https://www.youtube.com/watch?v=iNTmu2STGGQ
1
5 / 4 / 4
Регистрация: 03.09.2012
Сообщений: 90
07.02.2013, 15:07  [ТС] 6
Цитата Сообщение от palva Посмотреть сообщение
1. Ускорить работу могло бы хранение чисел не в виде строк, а в виде чисел.
2. Работа пошла бы еще быстрее, если написать перебор на компилируемом языке (си, дельфи) и подключить к PHP. Как это сделать я не знаю, но знаю, что это возможно.
3. Если бы про сами числа было известно больше, (например, все числа неотрицательны), то можно было бы сэкономить на алгоритме. А когда про числа ничего не известно, то оптимальней вашего сам алгоритм написать, по-моему, нельзя.
1. Элементы массива теперь как числа. Быстродействие скрипта увеличился на 25-35% (950000 операций вместо старых 700000).
2. На Си пока не пробовал, если пхп не справится с задачей, тогда попробую.
3. Числа в диапазоне от 0-2000. Что посоветуете изменить в алгоритме?
0
3836 / 2768 / 641
Регистрация: 08.06.2007
Сообщений: 9,456
Записей в блоге: 4
07.02.2013, 15:27 7
Если первые числа большие, так что сумма заведомо превысит $сhislo, то цикл можно прервать и не заниматься перебором чисел из второго и третьего массивов. Можно кое-что вычислить перед циклом, чтобы многократно не вычислять одно и то же внутри цикла.
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$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 "Тут выводится результат...";
        }
    }
}
1
36 / 36 / 9
Регистрация: 13.07.2011
Сообщений: 95
07.02.2013, 17:06 8
Где-то тут лишняя скобка, ну да это не проблема найти.
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, куда-то запоминается)
1
155 / 25 / 6
Регистрация: 06.06.2009
Сообщений: 262
07.02.2013, 17:11 9
Цитата Сообщение от hellmin Посмотреть сообщение
отличается только дополнительно используемой памятью и лишней строкой, но не как не скоростью.
Вроде скоростью тоже. Поставил эксперимент:
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
$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
1
36 / 36 / 9
Регистрация: 13.07.2011
Сообщений: 95
07.02.2013, 17:48 10
Не поленился и тоже провел эксперимент из 3-х циклов. Размер массива 30 элементов, количество итераций оставил такое же (10000000).
PHP
1
2
3
4
5
6
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-х элементах в массиве)
1
36 / 37 / 16
Регистрация: 23.03.2010
Сообщений: 2,825
07.02.2013, 17:56 11
Sherzant не знаю правильно ли я понял но почему бы не использовать foreach?

PHP
1
2
3
4
5
6
7
8
9
10
11
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);
0
603 / 578 / 103
Регистрация: 16.07.2012
Сообщений: 1,762
07.02.2013, 19:03 12
Цитата Сообщение от hellmin Посмотреть сообщение
PHP
1
for ($j = 0; $j < count($array); $j++)
не пишите так, при такой записи на каждой итерации цикла производится подсчет елементов функцией count, хотя это значение достаточно посчитать один раз
PHP
1
for ($j = 0, $cnt = count($array); $j < $cnt; $j++)
0
36 / 36 / 9
Регистрация: 13.07.2011
Сообщений: 95
08.02.2013, 12:53 13
Цитата Сообщение от Nebiros Посмотреть сообщение
но почему бы не использовать foreach?
А ведь и правда... при количестве элементов массива 40 разница по времени в два раза.
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 - число введенных пользователем
        }
    }
}
0
5 / 4 / 4
Регистрация: 03.09.2012
Сообщений: 90
12.02.2013, 16:25  [ТС] 14
Цитата Сообщение от palva Посмотреть сообщение
Если первые числа большие, так что сумма заведомо превысит $сhislo, то цикл можно прервать и не заниматься перебором чисел из второго и третьего массивов. Можно кое-что вычислить перед циклом, чтобы многократно не вычислять одно и то же внутри цикла.
об этом как то не подумал, хороший совет, спасибо)

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

Добавлено через 6 минут
Кликните здесь для просмотра всего текста
Цитата Сообщение от Nebiros Посмотреть сообщение
Sherzant не знаю правильно ли я понял но почему бы не использовать foreach?

PHP
1
2
3
4
5
6
7
8
9
10
11
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 секунд.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.02.2013, 16:25

Способ расчета без перебора
Здравствуйте, Есть таблица, состоящая из 3 столбцов: ФИО, условие и сумма. Нужно по ФИО суммы с...

Лучший способ сохранения настроек
Какой? :) Есть: - настройки окна и видимости контролов - настройки пользователя по таблицам...

Лучший способ доступа в инет
Подскажите пожалста, какой способ доступа в инет лучше(скорость/деньги). Что нужно купить для этого?

Лучший способ избавиться от магических строк
Вопрос, конечно, праздный, но всё же... public static class AntiMagic { public const string...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru