Всем привет! Недавно потребовалось написать функцию для генерации всевозможных вариаций из последовательности чисел (ну или что-то вроде этого), получилось нечто следющее: PHP: function get_variations($ferst_val, $last_val, $variations = "", $pref = ""){ $ferst_val = round($ferst_val); $last_val = round($last_val); If($variations == "" && $pref == ""){ for($nnn = $ferst_val; $nnn <= $last_val; $nnn++){ $variations[$nnn] = 1; } } for($n = $ferst_val; $n <= $last_val; $n++){ $sec_val = $n; If($n != $ferst_val){ If(!isset($variations[$pref.$ferst_val.",".$sec_val])) $variations[$pref.$ferst_val.",".$sec_val] = 1; } If($last_val > $sec_val && $sec_val != $ferst_val){ $variations_new = $this->get_variations($sec_val, $last_val, "", $pref.$ferst_val.","); $variations = array_merge($variations, $variations_new); } } $second_val = $ferst_val + 1; If($second_val != $last_val && $pref == ""){ $variations = $this->get_variations($second_val, $last_val, $variations); } If($pref == "") $variations[$last_val] = 1; return $variations; } Пример запуска: $variations = get_variations(1, 15); // т.е. генерация вариаций последовательности чисел с 1 до 15... результат 32766 вариаций (в переменную $variations передется массив с вариациями). Все правильно работает с числами более 2х, но есть проблема: у меня ноут (1,73GHz, 512Mb RAM) при указании $last_val более 17 начинает грузиться и выдает через неск. минут сообщение о нехватке виртуальной памяти... результат не выдает и через 10 минут. Из 17 чисел должно получиться 131071 вариация, фунция нужна для генерации вариаций из примерно 30-50 чисел (из 30 чисел должно получиться 1,073,741,823 вариации). Что делать? Можно ли посредством PHP очищать память во время работы цикла? Или стоит как-то доработать функцию?
рекурсивное программирование -- программирование богов. только они могут себе позволить бесконечный стэк. перепишите алгоритм на итеративный вариант. и выдавайте вариации не в память, а на диск их пишите, что ли. только дисками запаситесь про запас.
Ну не всегда, есть случаи когда глубина рекурсии не может быть выше "разумных придёлов" (хотя данный случай под это понятие не подходит)
Вы имеете в виду перестановки??? хм.. если же это всё-таки перестановки, то они считаются как n! чисел - 15, 15! = 1 307 674 368 000 1 307 674 368 000 !== 32766
PHP: get_variations(1, 2) Код (Text): Array Array ( [1] => 1 [2] => 1 [1,2] => 1 ) А как же вариант 2,1? Функция явно не все комбинации перебирает.
Думаю, вам следует поискать альтернативные решения. При такой постановке вопроса бороться с нехваткой памяти можно только увеличением объемов памяти.
если это они, то можно наверно так: PHP: <?php function factorial($num){ if ($num < 0){ return 0; } if ($num == 0){ return 1; } return $num*factorial($num-1); } function perestanovki ($a, $b){ $c=abs($a-$b)+1; return factorial($c); } echo perestanovki (1, 15); ?> результат: Код (Text): 1.307674368E+012
Факториал-то посчитать не проблема, а вот записать все перестановки, число которых равно этому факториалу, так просто не получится. Бумаги не хватит
Sergey89, я же сказал, что тогда что такое все возможные варианты?? например есть 3 числа: 3,5,7 полученные "вариации": 3 5 7 3 7 5 5 3 7 5 7 3 7 3 5 7 5 3 так? т.е. вывести все комбинации???
Затронула тема Хорошо, вот пример, чтобы было яснее о чем я. Допустим у нас есть статистика прибыли по месяцам каких-либо ресурсов. Нам необходимо отобрать те, которые в сумме (по месяцам) всегда давали прибыль (допустим более 25%). Т.е. чтобы в каждом месяце сумма прибыли отобранных ресурсов была >= 25%.... Пусть у нас будет статистика по 3 ресурсам (для примера за 12 месяцев). Наиболее удобный, на мой взгляд, вариант - взять все вариации сочетаний этих ресурсов и вдальнейшем проверить прибыльность по ним. Это только пример - у меня задача отличается, но суть передана верно. Для удобства номеруем каждый ресурс, начиная с 1 = 1,2,3. Получаем $ferst_val = 1, $last_val = 3; Передаем в функцию для вывода вариаций: $variations = get_variations(1, 3); Получаем след. вариации: 1 1,2 1,3 1,2,3 2 2,3 3 В сумме 7 вариаций. Далее заменяем вариации на нужные названии (для сопостовления статистики) и считаем прибыль по каждой вариации для каждого месяца. Если вариация удовлетворяет условие >=25%, то заносим ее в отдельную переменную и т.д. Возможно слишком замудрил, но другого выхода пока не нашел... На счет 32766 вариаций из 15 чисел все по аналогии. Вообще заметил закономерность: сумма вариаций числа n равна (удвоенной сумме вариаций числа n-1) + 1. Т.е.: чисел => вариаций 2 => 3 3 => 7 4 => 15 5 => 31 6 => 63 7 => 127 8 => 255 9 => 511 10 => 1023 11 => 2047 12 => 4095 13 => 8191 14 => 16,383 15 => 32,766 ..... 25 => 33,554,431 .... 30 => 1,073,741,823 Sergey89, в первом посте я упомянул, что "Все правильно работает с числами более 2х", имелось ввиду что $last_val должен быть более 2х. Хотя и в данном случае все верно: для данного случая вариации 1,2 и 2,1 аналогичны. Забыл сразу написать. ................................ Попробую написать сохранение в файл.... но, тут, видимо тоже прийдется ставить ограничение не более 30 чисел... Есть другой вариант, брать вариации, где количество чисел не менее 85%... пробовал ставить условие в написанную функцию - тот же результ - не зависимо от того, что в массиве вариаций в разы меньше, скорость расчетов и нехватка памяти остались те же.... отсюда вопрос: почему занимается память, если в массиве информации остается в разы меньше? На что уходит память? И можно ли ее как-нибудь освобождать в процессе расчетов? (думаю, при записи в файл проблема останется).
На рекурсивные вызовы класса с данными, на работу с ключами массива как со строками... Советую в корне пересмотреть реализацию - тут все вполне линейно, либо если так хочется рекурсии, работать с данными по ссылке — и пересмотреть формат хранения... ну в ключах вариации через запятую хранить не кошерно.
SPOG, если у вас не хватает ресурсов на генерацию вариантов, то на их исследование и выбор лучшего и тем более ресурсов не хватит. В данном случае задача перебора примитивная - надо просто ваш список ресурсов представить как биты в двоичном числе, и в этом числе расставить единички и нолики. Единица - ресурс учитывается, нолик - нет. Это простой перебор значений от 1 до 2**n-1. Если нужно ставить ограничение на количество единичек в числе, то алгоритм усложняется, но не слишком сильно. Там уже нужно перебирать количество единичек (допустим c, от 0.85*n до n), и для каждого значения c всеми возможными вариантами перебирать их расстановки. НО. У меня сильное подозрение, что вас не в ту степь понесло. Зачем вообще перебирать варианты? Насколько я понял условие задачи, она решается аналитически, без переборов.
Горбунов Олег, Dagdamor. Спасибо за рекомендации, переписал фунцию. Убрал рекурсивный вызов, строки в ключах массивов и перевел в двоичный вид, вот что получилось: PHP: <?php function get_variations2($last_val){ $ferst_val = 1; $last_val = round($last_val); // выставляем по умолчанию все единицы for($n = 1; $n <= $last_val; $n++){ $vals[$n] = 1; } // находим количество вариаций $vars_count = 1; for($n = 2; $n <= $last_val; $n++){ $vars_count = ($vars_count * 2) + 1; } // генерируем вариации $nval = sizeof($vals); $nums_change = 1; for($n = 0; $n < $vars_count; $n++){ $new_val = ""; $true_vals = 0; foreach($vals as $key=>$val){ $new_val .= $val; If($val = 1) $true_vals++; } $true_vals = round($true_vals/$nval, 2) * 100; If($true_vals >= 85) $variations[] = $new_val; // количество изменяемых цифр If($n == 1){ $nums_change++; $prev = 2; } ElseIf($n >= 3){ If(($n+1) == ($prev*2)){ $nums_change++; $prev = $prev*2; } } for($c = 1, $cc = 1; $c <= $nums_change; $c++, $cc *= 2){ $key = $nval - $c + 1; If(($n+1)/$cc == ((int)(($n+1)/$cc))){ If($vals[$key] == 0){ $vals[$key] = 1; } Else { $vals[$key] = 0; } } } } //print_r($vals); return $variations; } // end of 'get_variations2()' ?> Скорость расчетов увеличилась. Теперь можно рассчитывать вариации из 20 чисел не более чем за 40 секунд (19 за 20 сек, 18 за 10 сек и т.д.). Однако этого недостаточно (при такой тенденции к увеличению времени расчета вариации из 30 чисел будут составляться более 11 часов)... Может кто знает что еще можно сделать для увеличения скорости? Может я написал слишком "мудреный" алгоритм получения вариаций?
Скажем так, для такого кол-ва расчётов PHP просто слишком медлителен. Вам нужно помотреть в сторону C/C++/Java.
+1. Если голова дурная, то Си не поможет. Ну будет оно в разы быстрее. 30 чисел будут подбираться не за 11, а за полчаса. 40 - ... И что?
Не спорю, алгоритм далеко не лучший для данной задачи, но другого не придумал... Есть предложения как реализовать это другим способом? Psih, сорри за оффтоп, но как раз думал о переходе с PHP+MySQL на C+что-нибудь.... есть задачи, которые требудую от часа и более непрерывной работы, восновном из-за долгой работы с базой даных. Есть ли смысл изучать Си ради скорости?
реализовать ЧТО? задача не поставлена, только "переберите триллионы цыфирей". Как обычно, проблема в том, чтобы сформулировать задачу на человеческом языке. Этому в самоучителях не учат. Конечный результат какой ожидается? Выбрать Х случайных несовпадающих комбинаций чисел из диапазона или списка? или несовпадающих по всем частям? или что? чем rand() плох?
Задачи этого НЕ ТРЕБУЮТ. Нет таких в природе. Этого требует дурная голова. Си никак не поможет ускорить любую базу, нагруженную дурной работой. НЕТ способов исправить дурь в голове, кроме самого себя. Никакие "серверы", "языки" или что там еще кажется не помогут.
Вы когда нибудь сравнивали скорость Си и РНР ? (на досуге сравните, даже самые тупо написанные вещи на Си в тысячи раз быстрее и экономичнее по памяти)
Vladson я вообще-то на Си лет на 10 раньше чем на ПХП стал писать. Это спор ради спора? Так я могу микрокоманды отдельных процессоров приплести и как надо под кеш каждого оптимизировать. Прочти внимательно его пост. Он базу грузит часовыми запросами. Или ты вообще ветку не читал? Поинтересуйся.)) На что спорим что я на пхп напишу быстрее чем он на чем угодно? Без головы абсолютно неважно, интерпретатор или компилятор и т.п.
Я внимательно читал твой, и ты утверждаешь что А я говорю что есть... (не будешь же ты драйвера видеокарты на JavaScript писать)