генерирование уникальных комбинаций без исчерпания памяти в php

Question

Я пишу алгоритм для генерации комбинаций предметов из базы данных. Они должны быть уникальными перестановками (т.е. 145, 156 == 156, 145). Проблема, с которой я сталкиваюсь, заключается в том, как отслеживать предыдущие комбинации, чтобы у меня не было 145, 156 и 156, 145.

В настоящее время я добавляю их в массив с индексом id1_id2 ... (отсортированный так, чтобы идентификаторы всегда были в порядке убывания), и устанавливаю значение равным 1, когда генерируется комбо, чтобы я мог проверить, если $ combos [ $ index] существует или нет. Если его не существует, создайте его. (Существуют другие критерии, чтобы отсеять КАЖДУЮ перестановку, но они не имеют значения) Как только эти комбинации сгенерированы, они сохраняются в таблице в MySQL.

Проблема, с которой я сталкиваюсь, состоит в том, что с помощью тестовых элементов, которые я использую (около 85), я не могу сгенерировать комбинации с более чем 3 элементами (id1_id2_id3) без исчерпания памяти, так как количество комбинаций MASSIVE и Массив $ combos занимает больше, чем 64M, которые я выделил в памяти PHP.

Есть ли способ, которым я могу сделать это а), не отслеживая предыдущие комбинации или б) пропуская маршрут массива $ combos и только добавляя уникальную строку в mysql и позволяя mysql обрабатывать проверку дубликатов.

Вот некоторый псевдокод для справки:

$items = array(/*85 items*/);
foreach ($items as $item1){
    generate(array($item1));
        foreach($items as $item2){
            generate(array($item1, $item2));
        }
    }
}

function generate($items_arary){
    $temp_array = array();
    foreach ($items_array as $item){
        $temp_array[] = $item['id'];
    }

    sort($temp_array);
    $index = implode("_", $temp_array);

    if (!$combos[$index]){
        $combos[$index] = 1;
        /* some code to generate query to store to db */
    }
}

запрос выглядит примерно так: (база данных усекается в начале скрипта)

INSERT INTO `combos` (combo_id, more_info) VALUES ('id1_id2', 'Item Name');

В процессе написания этого вопроса я подумал о возможном решении: убедиться, что id3> id2> id1. Будет ли это жизнеспособным решением для устранения необходимости использования $ combos?

Answer 1

Причина, по которой я спросил о структуре данных before, заключается в том, что вы можете сделать что-то вроде этого:

$sql = "SELECT id FROM test_a";
$result = mysql_query($sql);
while ($row = mysql_fetch_array($result)) {
  $item1 = $row['id'];

  $sql2 = "SELECT id FROM test_a";
  $result2 = mysql_query($sql2);
  while ($row2 = mysql_fetch_array($result2)) {
    $item2 = $row2['id'];

    $combo1 = $item1 . "_" . $item2;
    $combo2 = $item2 . "_" . $item1;

    $sql3 = "SELECT * FROM combos WHERE combo_id = '$combo1' OR combo_id = '$combo2'";
    $result3 = mysql_query($sql3);
    if (mysql_num_rows($result3) == 0) {
      $sql4 = "INSERT INTO combos (combo_id, more_info) VALUES ('$combo1','Item Name')";
      $result4 = mysql_query($sql4);
    }
  }
}

Когда таблица test_a имеет значения 1,2,3 и 4, этот скрипт вставляет: 1_1 1_2 1_3 1_4 2_2 2_3 2_4 3_3 3_4 4_4

У этого не должно быть проблем с памятью. Хотя, если у вас огромная база данных, вы можете столкнуться с проблемой с ограничением времени php

Answer 2

Это та же концепция, что и в моем другом ответе, но в формате SQL.

INSERT INTO combos (combo_id, more_info) 
  SELECT CONCAT_WS("_",t1.id,t2.id), "item_name" 
  FROM test_a t1, test_a t2 
  WHERE NOT EXISTS (SELECT * FROM combos WHERE combo_id = CONCAT_WS("_",t1.id,t2.id))
    AND NOT EXISTS (SELECT * FROM combos WHERE combo_id = CONCAT_WS("_",t2.id,t1.id))

Предполагая, что вы можете получить item_name из базы данных где-то, это, вероятно, будет вашим самым быстрым и наименее ресурсоемким решением. Сейчас я провожу тестирование около 1000 идентификаторов. Я обновлю это, когда он закончится.

Answer 3

В TSQL вы можете использовать рекурсивный CTE, не могу вспомнить, где я его получил, но довольно мило. Примечание. MYSQL не использует параметр «С», поэтому он не будет работать в MySQL

.

WITH Numbers(N) AS (
                    SELECT N
                    FROM ( VALUES(1), (2), (3), (4), (5), (6)) Numbers(N)),
                        Recur(N,Combination) AS (
                        SELECT N, CAST(N AS VARCHAR(20)) 
                        FROM Numbers


UNION ALL

SELECT n.N,CAST(r.Combination + ',' + CAST(n.N AS VARCHAR(10)) AS VARCHAR(20)) 
FROM Recur r
INNER JOIN Numbers n ON n.N > r.N)



select Combination
from RECUR
ORDER BY LEN(Combination),Combination;

Answer 4

Если вам не нужно автоматически обеспечивать ссылочную целостность (чего нельзя делать, если вы используете конкатенацию строк), используйте одну таблицу для 85 элементов, присвойте им индекс (0-84) и используйте вторую таблица для представления заданного набора элементов с использованием числового типа данных, где каждая битовая позиция в номере представляет один элемент. (например, 000001101 представляет пункты 0, 2 и 3)

Для элементов более 64 вам, возможно, придется разделить их на несколько полей или использовать BLOB или строку (gack!).

Если вы используете это в качестве поля первичного ключа, вы можете принудительно применять недубликаты.

Answer 5

Да. Вы можете сохранить и использовать лексикографический индекс комбинации, чтобы восстановить или повторить их, или Серые коды, если вам нужно выполнить итерацию всех из них.

Взгляните на: «Алгоритм 515: генерация вектора из лексикографического индекса»; Баклс, Б. П., и Ливан, М. Транзакции ACM по математическому программному обеспечению, Vol. 3, № 2, июнь 1977 года.

Я перевел на C здесь , и опишите больше здесь .

Answer 6

для увеличения изменения памяти

memory_limit = 512M в вашем php.ini
или
ini_set ('memory_limit', '512M') в вашем php-скрипте
или
php_value memory_limit 512M в вашем .htaccess