Sort-Merge-Join алгоритм в Python

Question

Мой код:

def merge_join(self, outer, outer_join_index, inner, inner_join_index): 
    a=list(inner) 
    b=list(outer) 
    if not a or not b: 
     return 
    inner_copy = sorted(a,key=lambda tup: tup[inner_join_index]) 
    outer_copy = sorted(b,key=lambda tup: tup[outer_join_index]) 
    inner_counter=0 
    outer_counter=0 
    while inner_counter < len(inner_copy) and outer_counter < len(outer_copy): 
     if outer_copy[outer_counter][outer_join_index]==inner_copy[inner_counter][inner_join_index]: 
      yield outer_copy[outer_counter]+inner_copy[inner_counter] 
      outer_counter+=1 
     elif outer_copy[outer_counter][outer_join_index]<inner_copy[inner_counter][inner_join_index]: 
      outer_counter+=1 
     else: 
      inner_counter+=1 

Где внешняя и внутренняя являются генераторами.

Я выполнил заданный тест для алгоритма, но он возвратил генератор из 127 элементов в отличие от ожидаемого числа 214. Может ли кто-нибудь помочь мне проверить, где ошибка может быть в моем коде? Спасибо!!

Answer 1

Если вы хотите, чтобы выбрать правильную outer строки для каждого inner строки (без дубликатов в inner и пропуская строки, если нет матча, то в случае матча вы должны увеличивать inner_counter, не outer_counter, как вы делаете.

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

Если вместо этого вы хотите, чтобы сделать полный присоединиться (продуцирующие все декартово произведение строк из inner и outer для заданное значение столбца объединения) t то это должно быть закодировано явно с чем-то вроде

while inner_counter < len(inner_copy) and outer_counter < len(outer_copy): 
    key = min(inner_copy[inner_index][inner_join_index], 
       outer_copy[outer_index][outer_join_index]) 
    inner_group = [] 
    while inner_index < len(inner) and key == inner_copy[inner_index][inner_join_index]: 
     inner_group.append(inner_copy[inner_index]) 
     inner_index += 1 
    outer_group = [] 
    while outer_index < len(outer) and key == outer_copy[outer_index][outer_join_index]: 
     outer_group.append(outer_copy[outer_index]) 
     outer_index += 1 
    # Here you can handle left or right join by replacing an 
    # empty group with a group of one empty row (None,)*len(row) 
    for i in inner_group: 
     for o in outer_group: 
      yield i + o