Сравнение значений строк в строке эффективно

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

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

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

Спасибо.

источник

2010-03-11 seanieb

Пусть все элементы имеют ряд ItemNumber

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

например

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

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

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

источник

2010-03-11 15:44:27 Hogan

Я тоже об этом думал, но, возможно, OP не хочет менять классы моделей. –

@ Феликс: Круто ... скажите, что вы имеете в виду? Модельный класс? Что это такое? – Hogan

Ну, я полагаю, что OP каким-то образом использует класс для представления документов (модель) (может быть, он использует ORM). Но я просто понял, что это легко сделать с индексами списка. Сначала я думал, что вы хотите сделать документы сопоставимыми. Я все еще думаю, что вы могли бы предоставить лучший пример;). Но не бери в голову. –

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

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)

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

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

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

источник

2010-03-11 15:37:19

Мое решение гораздо быстрее. Нет накладных расходов на пару. – Hogan

Не реализует ли эта реализация сложность от n^2 до n^3?Мало того, что у вас есть вложенный цикл, но «пара не сравнивается» - это операция O (n). Существуют более простые/более эффективные реализации. Но похоже, что @seanieb удовлетворен. –

@Traveling Tech Guy: Верно, я перешел из списков в 'set' и' frozenset'. Я думаю, набор имеет доступ к O (1), поскольку он реализован как словарные ключи. –

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

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

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

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

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

источник

2010-03-11 15:41:03 symcbean

Нечто подобное?

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:]]

источник

2010-03-11 17:32:47 medina

Сравнение значений строк в строке эффективно

ответ

Смежные вопросы