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

Question

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

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

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

Есть ли способ, которым я могу это сделать: a) не отслеживая предыдущие комбо или b) пропуская маршрут массива $ 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. Будет ли это жизнеспособным решением для устранения необходимости комбо-комбо?

Answer 1

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

$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_

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

Answer 2

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

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

Answer 3

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

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

Я перевел на C here и опишу более here.

Answer 4

Вот та же концепция, что и мой другой ответ, но во всем формате 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 5

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

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

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

Answer 6

В TSQL вы можете использовать рекурсивный CTE, Can''t помните, где я его получил, но довольно сладкий. Примечание. 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;