Эффективно сравнивать значения строк в БД

Question

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

Упрощенный, наивный метод вложил бы цикл в другой цикл. Это приведет к тому, что программа будет сравнивать документы дважды, а также сравнивать каждый документ с самим собой.

Есть ли название алгоритма для эффективного выполнения этой задачи? Есть ли название для этого подхода?

Спасибо.

Answer 1

Предположим, что все предметы имеют номер ItemNumber

Простое решение - всегда иметь ItemNumber 2-го элемента больше, чем первый элемент.

например

for (firstitem = 1 to maxitemnumber)
  for (seconditem = firstitemnumber+1 to maxitemnumber)
    compare(firstitem, seconditem)

визуальное примечание: если вы думаете о сравнении как о матрице (номер элемента один на одной оси, элемент другой на другой оси), это смотрит на один из треугольников.

........
x.......
xx......
xxx.....
xxxx....
xxxxx...
xxxxxx..
xxxxxxx.

Answer 2

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

Вы можете избежать дублирования пар, просто проведя сравнение по любому значению, которое может отличаться в разных строках - первичный ключ очевиденвыбор, например,

Уникальные пары:

SELECT a.item as a_item, b.item as b_item
FROM table AS a, table AS b
WHERE a.id<b.id

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

C.

Answer 3

Как то так?

src = [1,2,3]
for i, x in enumerate(src):
    for y in src[i:]:
        compare(x, y)

Или вместо этого вы можете создать список пар:

pairs = [(x, y) for i, x in enumerate(src) for y in src[i:]]

Answer 4

Вы можете отслеживать, какие документы вы уже сравнили, например, (с номерами;))

compared = set()

for i in [1,2,3]:
    for j in [1,2,3]:
        pair =  frozenset((i,j))
        if i != k and pair not in compared:
            compare.add(pair)
            compare(i,j)

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

Обновление
Если у вас есть документы в списке, то ответ Хогана действительно лучше. Но я думаю, что нужен лучший пример:

docs = [1,2,3]
l = len(docs)
for i in range(l):
    for j in range(i+1,l):
        compare(l[i],l[j])