За последние 24 часа нас посетили 20676 программистов и 1107 роботов. Сейчас ищут 349 программистов ...

Генерация вариаций... или как бороться с нехваткой памяти?

Тема в разделе "Решения, алгоритмы", создана пользователем SPOG, 22 авг 2007.

  1. SPOG

    SPOG Активный пользователь

    С нами с:
    16 фев 2007
    Сообщения:
    27
    Симпатии:
    0
    Адрес:
    Россия, 63
    Всем привет!

    Недавно потребовалось написать функцию для генерации всевозможных вариаций из последовательности чисел (ну или что-то вроде этого), получилось нечто следющее:

    PHP:
    1. function get_variations($ferst_val, $last_val, $variations = "", $pref = ""){
    2.  
    3.         $ferst_val = round($ferst_val);
    4.         $last_val = round($last_val);
    5.  
    6.         If($variations == "" && $pref == ""){
    7.  
    8.             for($nnn = $ferst_val; $nnn <= $last_val; $nnn++){
    9.  
    10.                 $variations[$nnn] = 1;
    11.  
    12.             }
    13.  
    14.         }
    15.  
    16.         for($n = $ferst_val; $n <= $last_val; $n++){
    17.  
    18.             $sec_val = $n;
    19.  
    20.             If($n != $ferst_val){
    21.                 If(!isset($variations[$pref.$ferst_val.",".$sec_val])) $variations[$pref.$ferst_val.",".$sec_val] = 1;
    22.             }
    23.  
    24.             If($last_val > $sec_val && $sec_val != $ferst_val){
    25.  
    26.                 $variations_new = $this->get_variations($sec_val, $last_val, "", $pref.$ferst_val.",");
    27.  
    28.                 $variations = array_merge($variations, $variations_new);
    29.  
    30.             }
    31.  
    32.         }
    33.  
    34.         $second_val = $ferst_val + 1;
    35.  
    36.         If($second_val != $last_val && $pref == ""){
    37.             $variations = $this->get_variations($second_val, $last_val, $variations);
    38.         }
    39.  
    40.         If($pref == "") $variations[$last_val] = 1;
    41.         return $variations;
    42.  
    43.     }
    Пример запуска: $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 очищать память во время работы цикла? Или стоит как-то доработать функцию?
     
  2. stas_t

    stas_t Активный пользователь

    С нами с:
    24 апр 2007
    Сообщения:
    500
    Симпатии:
    0
    Адрес:
    Courbevoie, France
    рекурсивное программирование -- программирование богов. только они могут себе позволить бесконечный стэк. перепишите алгоритм на итеративный вариант. и выдавайте вариации не в память, а на диск их пишите, что ли. только дисками запаситесь про запас.
     
  3. Vladson

    Vladson Старожил

    С нами с:
    4 фев 2006
    Сообщения:
    4.040
    Симпатии:
    26
    Адрес:
    Estonia, Tallinn
    Ну не всегда, есть случаи когда глубина рекурсии не может быть выше "разумных придёлов" (хотя данный случай под это понятие не подходит)
     
  4. basist

    basist Активный пользователь

    С нами с:
    7 июл 2007
    Сообщения:
    388
    Симпатии:
    0
    Адрес:
    Орел
    Вы имеете в виду перестановки???

    хм.. если же это всё-таки перестановки, то они считаются как n!
    чисел - 15,
    15! = 1 307 674 368 000
    1 307 674 368 000 !== 32766
     
  5. Sergey89

    Sergey89 Активный пользователь

    С нами с:
    4 янв 2007
    Сообщения:
    4.796
    Симпатии:
    0
    PHP:
    1. get_variations(1, 2)
    Код (Text):
    1. Array
    2. Array
    3. (
    4.     [1] => 1
    5.     [2] => 1
    6.     [1,2] => 1
    7. )
    А как же вариант 2,1? Функция явно не все комбинации перебирает.
     
  6. Veem

    Veem Активный пользователь

    С нами с:
    21 авг 2007
    Сообщения:
    76
    Симпатии:
    0
    Думаю, вам следует поискать альтернативные решения.
    При такой постановке вопроса бороться с нехваткой памяти можно только увеличением объемов памяти.
     
  7. basist

    basist Активный пользователь

    С нами с:
    7 июл 2007
    Сообщения:
    388
    Симпатии:
    0
    Адрес:
    Орел
    если это они, то можно наверно так:


    PHP:
    1.  
    2. <?php
    3.  
    4. function factorial($num){
    5.     if ($num < 0){
    6.         return 0;      
    7.     }
    8.     if ($num == 0){
    9.        
    10.         return 1;
    11.     }
    12.     return $num*factorial($num-1);
    13. }
    14.  
    15. function perestanovki ($a, $b){
    16.     $c=abs($a-$b)+1;
    17.     return factorial($c);
    18. }
    19.  
    20. echo perestanovki (1, 15);
    21. ?>
    22.  
    23.  
    результат:

    Код (Text):
    1. 1.307674368E+012
     
  8. Sergey89

    Sergey89 Активный пользователь

    С нами с:
    4 янв 2007
    Сообщения:
    4.796
    Симпатии:
    0
    basist ты считаешь факториал, тоесть число перестановок, а нужно найти все возможные варианты.
     
  9. Veem

    Veem Активный пользователь

    С нами с:
    21 авг 2007
    Сообщения:
    76
    Симпатии:
    0
    Факториал-то посчитать не проблема, а вот записать все перестановки, число которых равно этому факториалу, так просто не получится. Бумаги не хватит ;)
     
  10. basist

    basist Активный пользователь

    С нами с:
    7 июл 2007
    Сообщения:
    388
    Симпатии:
    0
    Адрес:
    Орел
    Sergey89, я же сказал, что
    тогда что такое все возможные варианты??

    например есть 3 числа: 3,5,7
    полученные "вариации":
    3 5 7
    3 7 5
    5 3 7
    5 7 3
    7 3 5
    7 5 3
    так?

    т.е. вывести все комбинации???
     
  11. Veem

    Veem Активный пользователь

    С нами с:
    21 авг 2007
    Сообщения:
    76
    Симпатии:
    0
    Не, достаточно просто сгенерировать, судя по первому посту автора темы :)
     
  12. basist

    basist Активный пользователь

    С нами с:
    7 июл 2007
    Сообщения:
    388
    Симпатии:
    0
    Адрес:
    Орел
    Veem, ясно

    но вот почему их получилось 32766?
     
  13. Veem

    Veem Активный пользователь

    С нами с:
    21 авг 2007
    Сообщения:
    76
    Симпатии:
    0
  14. SPOG

    SPOG Активный пользователь

    С нами с:
    16 фев 2007
    Сообщения:
    27
    Симпатии:
    0
    Адрес:
    Россия, 63
    Затронула тема:)

    Хорошо, вот пример, чтобы было яснее о чем я.

    Допустим у нас есть статистика прибыли по месяцам каких-либо ресурсов. Нам необходимо отобрать те, которые в сумме (по месяцам) всегда давали прибыль (допустим более 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%... пробовал ставить условие в написанную функцию - тот же результ - не зависимо от того, что в массиве вариаций в разы меньше, скорость расчетов и нехватка памяти остались те же.... отсюда вопрос: почему занимается память, если в массиве информации остается в разы меньше? На что уходит память? И можно ли ее как-нибудь освобождать в процессе расчетов? (думаю, при записи в файл проблема останется).
     
  15. Anonymous

    Anonymous Guest

    На рекурсивные вызовы класса с данными, на работу с ключами массива как со строками...
    Советую в корне пересмотреть реализацию - тут все вполне линейно, либо если так хочется рекурсии, работать с данными по ссылке — и пересмотреть формат хранения... ну в ключах вариации через запятую хранить не кошерно.
     
  16. Dagdamor

    Dagdamor Активный пользователь

    С нами с:
    4 фев 2006
    Сообщения:
    2.095
    Симпатии:
    1
    Адрес:
    Барнаул
    SPOG, если у вас не хватает ресурсов на генерацию вариантов, то на их исследование и выбор лучшего и тем более ресурсов не хватит.
    В данном случае задача перебора примитивная - надо просто ваш список ресурсов представить как биты в двоичном числе, и в этом числе расставить единички и нолики. Единица - ресурс учитывается, нолик - нет. Это простой перебор значений от 1 до 2**n-1. Если нужно ставить ограничение на количество единичек в числе, то алгоритм усложняется, но не слишком сильно. Там уже нужно перебирать количество единичек (допустим c, от 0.85*n до n), и для каждого значения c всеми возможными вариантами перебирать их расстановки.
    НО. У меня сильное подозрение, что вас не в ту степь понесло. :) Зачем вообще перебирать варианты? Насколько я понял условие задачи, она решается аналитически, без переборов.
     
  17. SPOG

    SPOG Активный пользователь

    С нами с:
    16 фев 2007
    Сообщения:
    27
    Симпатии:
    0
    Адрес:
    Россия, 63
    Горбунов Олег, Dagdamor. Спасибо за рекомендации, переписал фунцию. Убрал рекурсивный вызов, строки в ключах массивов и перевел в двоичный вид, вот что получилось:


    PHP:
    1. <?php
    2. function get_variations2($last_val){
    3.  
    4.     $ferst_val = 1;
    5.     $last_val = round($last_val);
    6.  
    7.     // выставляем по умолчанию все единицы
    8.     for($n = 1; $n <= $last_val; $n++){
    9.  
    10.         $vals[$n] = 1;
    11.  
    12.     }
    13.  
    14.     // находим количество вариаций
    15.     $vars_count = 1;
    16.     for($n = 2; $n <= $last_val; $n++){
    17.  
    18.         $vars_count = ($vars_count * 2) + 1;
    19.  
    20.     }
    21.  
    22.     // генерируем вариации
    23.     $nval = sizeof($vals);
    24.     $nums_change = 1;
    25.     for($n = 0; $n < $vars_count; $n++){
    26.  
    27.         $new_val = "";
    28.         $true_vals = 0;
    29.         foreach($vals as $key=>$val){
    30.  
    31.             $new_val .= $val;
    32.             If($val = 1) $true_vals++;
    33.  
    34.         }
    35.         $true_vals = round($true_vals/$nval, 2) * 100;
    36.  
    37.         If($true_vals >= 85) $variations[] = $new_val;
    38.  
    39.         // количество изменяемых цифр
    40.         If($n == 1){
    41.  
    42.             $nums_change++;
    43.             $prev = 2;
    44.  
    45.         } ElseIf($n >= 3){
    46.  
    47.             If(($n+1) == ($prev*2)){
    48.  
    49.                 $nums_change++;
    50.                 $prev = $prev*2;
    51.  
    52.             }
    53.  
    54.         }
    55.  
    56.         for($c = 1, $cc = 1; $c <= $nums_change; $c++, $cc *= 2){
    57.  
    58.             $key = $nval - $c + 1;
    59.  
    60.             If(($n+1)/$cc == ((int)(($n+1)/$cc))){
    61.  
    62.                 If($vals[$key] == 0){
    63.                     $vals[$key] = 1;
    64.                 } Else {
    65.                     $vals[$key] = 0;
    66.                 }
    67.  
    68.             }
    69.  
    70.         }
    71.  
    72.     }
    73.  
    74.     //print_r($vals);
    75.  
    76.     return $variations;
    77.  
    78. } // end of 'get_variations2()'
    79. ?>
    Скорость расчетов увеличилась. Теперь можно рассчитывать вариации из 20 чисел не более чем за 40 секунд (19 за 20 сек, 18 за 10 сек и т.д.). Однако этого недостаточно (при такой тенденции к увеличению времени расчета вариации из 30 чисел будут составляться более 11 часов)... Может кто знает что еще можно сделать для увеличения скорости? Может я написал слишком "мудреный" алгоритм получения вариаций?
     
  18. Psih

    Psih Активный пользователь
    Команда форума Модератор

    С нами с:
    28 дек 2006
    Сообщения:
    2.678
    Симпатии:
    6
    Адрес:
    Рига, Латвия
    Скажем так, для такого кол-ва расчётов PHP просто слишком медлителен. Вам нужно помотреть в сторону C/C++/Java.
     
  19. armadillo

    armadillo Активный пользователь

    С нами с:
    6 апр 2007
    Сообщения:
    2.380
    Симпатии:
    0
    Адрес:
    Russia, Moscow
    +1.
    Если голова дурная, то Си не поможет.
    Ну будет оно в разы быстрее. 30 чисел будут подбираться не за 11, а за полчаса. 40 - ...
    И что?
     
  20. SPOG

    SPOG Активный пользователь

    С нами с:
    16 фев 2007
    Сообщения:
    27
    Симпатии:
    0
    Адрес:
    Россия, 63
    Не спорю, алгоритм далеко не лучший для данной задачи, но другого не придумал... Есть предложения как реализовать это другим способом?

    Psih, сорри за оффтоп, но как раз думал о переходе с PHP+MySQL на C+что-нибудь.... есть задачи, которые требудую от часа и более непрерывной работы, восновном из-за долгой работы с базой даных. Есть ли смысл изучать Си ради скорости?
     
  21. armadillo

    armadillo Активный пользователь

    С нами с:
    6 апр 2007
    Сообщения:
    2.380
    Симпатии:
    0
    Адрес:
    Russia, Moscow
    реализовать ЧТО? задача не поставлена, только "переберите триллионы цыфирей".
    Как обычно, проблема в том, чтобы сформулировать задачу на человеческом языке. Этому в самоучителях не учат.
    Конечный результат какой ожидается?
    Выбрать Х случайных несовпадающих комбинаций чисел из диапазона или списка? или несовпадающих по всем частям? или что?
    чем rand() плох?
     
  22. armadillo

    armadillo Активный пользователь

    С нами с:
    6 апр 2007
    Сообщения:
    2.380
    Симпатии:
    0
    Адрес:
    Russia, Moscow
    Задачи этого НЕ ТРЕБУЮТ. Нет таких в природе. Этого требует дурная голова. Си никак не поможет ускорить любую базу, нагруженную дурной работой.

    НЕТ способов исправить дурь в голове, кроме самого себя. Никакие "серверы", "языки" или что там еще кажется не помогут.
     
  23. Vladson

    Vladson Старожил

    С нами с:
    4 фев 2006
    Сообщения:
    4.040
    Симпатии:
    26
    Адрес:
    Estonia, Tallinn
    Вы когда нибудь сравнивали скорость Си и РНР ?
    (на досуге сравните, даже самые тупо написанные вещи на Си в тысячи раз быстрее и экономичнее по памяти)
     
  24. armadillo

    armadillo Активный пользователь

    С нами с:
    6 апр 2007
    Сообщения:
    2.380
    Симпатии:
    0
    Адрес:
    Russia, Moscow
    Vladson я вообще-то на Си лет на 10 раньше чем на ПХП стал писать. Это спор ради спора? Так я могу микрокоманды отдельных процессоров приплести и как надо под кеш каждого оптимизировать.
    Прочти внимательно его пост. Он базу грузит часовыми запросами. Или ты вообще ветку не читал? Поинтересуйся.))
    На что спорим что я на пхп напишу быстрее чем он на чем угодно? Без головы абсолютно неважно, интерпретатор или компилятор и т.п.
     
  25. Vladson

    Vladson Старожил

    С нами с:
    4 фев 2006
    Сообщения:
    4.040
    Симпатии:
    26
    Адрес:
    Estonia, Tallinn
    Я внимательно читал твой, и ты утверждаешь что
    А я говорю что есть...
    (не будешь же ты драйвера видеокарты на JavaScript писать)