Алгоритм уменьшения и ограничения использования памяти для поиска набора комбинаций

Question

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

например, если у меня есть пункты A, B, C, D, E, FI, необходимо сравнить все различные комбинации

  A B C D E F
A  
B x
C x x
D x x x
E x x x x
F x x x x x

и так далее. Наборы, как правило, состоят из 100–10 000 документов с метаданными, которые проверяются различными эвристиками.

В настоящее время я достигаю этого (не загружая все элементы в память одновременно), дважды повторяя набор в два идентичных вложенных запроса к базе данных с использованием курсора в каждом для итерации по двум измерениям комбинаций. Это теоретически не ограничено в масштабе и использует очень мало памяти, но кажется немного расточительным, так как я буду запрашивать каждый элемент N + 1 раз (где N - размер набора). Конечно, это немного напрягает базу данных.

Это текущий простой алгоритм:

• Подготовить запрос для набора
• , когда cursor.next A:
  • Подготовить запрос к набору, исключая A
  • во время курсора. Следующий B:
    • Сравнить A с B

Это приводит к последовательности AB, A C, AD, AE, AF, BA, B C, BD et c. и я храню только два документа одновременно, но у него две проблемы. Во-первых, внутренний запрос происходит N раз. Если бы я не исключал A в запросе, это был бы тот же самый запрос, повторный N раз, который просто кажется расточительным. Вторая проблема - это перестановки, поэтому я выполняю вдвое больше работы, чем необходимо, и вынужден выводить результаты.

Я думал о кэшировании элементов по мере продвижения, но понял, что со временем он просто возрастет содержат все предметы, чтобы завершить все комбинации. Таким образом, это привело к полному кругу идеи базового c простого выбора всего набора один раз в память и сканирования комбинаций из одного массива. Это просто, но, конечно, не масштабируемо.

Итак, существует ли алгоритм для сравнения всех комбинаций различных пар в наборе, используя только разделы набора в любой момент времени, что гарантированно суммирует, чтобы покрыть все комбинации?

Я не мог придумать одну наивно. например, если вы разделите его на две половины, вам все равно нужно загрузить комбинацию двух подмножеств в какой-то момент. Возможно, «все шансы» и «все четы», но это только вдвое уменьшит проблему масштабируемости.

  B D F
B 
D x  
F x x  

, затем

  A C E
A  
C x  
E x x 

, но это пропускает половину комбинаций.

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

ОБНОВЛЕНИЕ - вопрос отредактирован и, надеюсь, прояснен после первоначальных комментариев.

Nikos.M дал мне идею предварительно сгенерировать "индексы" пары комбинации. тогда я мог бы запросить для каждой пары.

Изначально я надеялся достичь того, что MicSim называет «сладким пятном» некоторого среднего уровня размеров партий. Так что не атомная загрузка каждой пары в одном крайнем случае, ни загрузка всего набора на другом конце, а некоторый метод пакетной обработки фиксированного размера, чтобы сохранить объем обработки на одном уровне.

Answer 1

ОБНОВЛЕНИЕ =========================================

Если я правильно понял вопрос. нет способа для разбиения набора на независимые подмножества, которые не перекрываются , чтобы уменьшить использование памяти, поскольку по определению все должно быть по сравнению со всем остальным. Таким образом, нет такого сокращения, которое может разделить множество. Однако, используя комбинации, можно минимизировать воздействие, имея в памяти только 2 активных документа в каждом экземпляре, и обновлять документы, когда следующая комбинация фактически ссылается на другой документ (, ссылающийся на 2 различные документы от предыдущей комбинации на самом деле редки, только одна ссылка на документ в среднем меняется от одной комбинации к следующей ). Кроме того, при использовании подхода, описанного ниже, процесс может в какой-то момент остановиться и сохранить последнюю комбинацию на диске, а в более позднее время возобновить с этого момента процесс. Так что это может быть эффективно, но в некотором смысле вид N+1 problem все еще существует. Комбинированный подход см. Ниже в оригинальном ответе.

============================== ===================

Существуют алгоритмы для систематической генерации комбинаций, где вам НЕ нужно хранить ВСЕ комбинации в памяти сразу, но ТОЛЬКО ОДИН активен в каждый момент.

Алгоритм работает, имея на входе комбинацию и возвращая следующую комбинацию (например, в лексикографическом порядке c), пока не будет достигнута последняя.

Начальная комбинация выбора 2 из n (где n >= 2) равна [0,1]

note , если n < 2, то нет комбинаций, которые выбирают 2 элементов из набора, содержащего менее 2 элементов.

Алгоритм-преемник (в python):

def next_combination( item, n, k ):
    MIN = 0
    MAX = k-1
    j = n-k
    i = MAX
    index = -1
    # find index to move
    while(MIN<=i and i<=MAX):
        if item[i] < j+i:
            index = i
            break
        i -= 1
    # adjust next indexes after the moved index
    if MIN<=index and index<=MAX:
        curr = item[index]+1
        j = n-k+index
        if curr == j:
            item[index] = curr
        elif curr < j:
            i = index
            while(MIN<=i and i<=MAX):
                item[i] = curr
                curr += 1
                i += 1
    else:
        # last item
        item = None
    return item

используется следующим образом:

comb = [0, 1] # first combination
doc1 = None
doc2 = None
prevcomb = None
while (comb):
    # process combination
    # eg:
    # doc1 = docs.get(comb[0]) if (not prevcomb) or (prevcomb[0]!=comb[0]) else doc1
    # doc2 = docs.get(comb[1]) if (not prevcomb) or (prevcomb[1]!=comb[1]) else doc2
    # compare(doc1, doc2)
    # when finished, compute next combination untill last
    prevcomb = comb[:] # copy
    comb = next_combination(comb, n, 2) # get next combination in order

Онлайн-тест для k = 2, n = 6

note2 временная сложность вышеупомянутого алгоритма эффективна, фактически это Алгоритм CAT (ie т akes постоянное среднее время на комбинацию ) для генерации всего набора комбинаций.

note3 есть даже более быстрые алгоритмы для особых случаев, например, где n мало. Один из таких алгоритмов использует только умные побитовые операции с 32bit или 64bit целыми числами без знака (таким образом, это возможно только для n <= 64)

note4 Приведенный выше алгоритм (для python) может также можно настроить на использование шаблона iterator или шаблона generator (ie yield), но, как это можно легко реализовать на любом языке, даже в тех, которые не поддерживают генераторы

note5 для k=2 алгоритм комбинаций также может быть реализован с использованием вложенного l oop (поскольку в этом случае они совпадают) ie:

def next_combination2(n):
    for i in range(n-1):
        for j in range(i+1, n):
            yield [i, j]

note6 если используется другой язык, дайте мне знать, чтобы повторно опубликовать алгоритм на другом языке, если это возможно (например: php, javascript, c)