Merge Sort 2 Lists Поиск общих элементов

Question

Для задания нам было предложено написать функцию, которая принимает в качестве входов 2 списка, а затем возвращает список, содержащий все имена, которые были как в «списке 1», так и в «списке 2».

Было предложено выполнить алгоритм сортировки по методу слияния. То, что у меня до сих пор возвращает правильный список, однако я делаю слишком много сравнений, чтобы получить этот список. VoterList - это заданный нам класс, так что мы не используем обычные списки python. Только объекты VoterName (из которых состоят два списка входных данных), могут быть добавлены в VoterList. Перечисляемые списки находятся в лексикографическом порядке.

Любые советы о том, как уменьшить мои сравнения, приветствуются. Спасибо.

from classes import VoterList 
def fraud_detect_merge(first_booth_voters, second_booth_voters): 

    fraud = VoterList() 
    length_first = len(first_booth_voters) 
    length_second = len(second_booth_voters) 
    first_booth_position = 0 
    second_booth_position = 0 
    comparisons = 0 
    while first_booth_position < length_first: 

     if second_booth_position == length_second: 
      first_booth_position += 1 
      second_booth_position = 0 

     else: 
      name_comparison = first_booth_voters[first_booth_position] 
      comparisons += 1 

      if second_booth_voters[second_booth_position] == name_comparison: 
       fraud.append(second_booth_voters[second_booth_position]) 
       first_booth_position += 1 
       second_booth_position = 0 

      else: 
       second_booth_position += 1 


    return fraud, comparisons 

Answer 1

Непонятно, что ваш вход, он уже отсортирован? Вам даются списки. Проверьте, какие операции могут выполняться в списках, и вы найдете операцию pop(). Это удаляет один элемент из списка и дает вам его значение. Поскольку списки как для того, следующий подход может быть использован:

def fraud_detect_merge(first_booth_voters, second_booth_voters): 
    fraud = VoterList() 
    comparisons = 0 

    first_booth_voters.sort()  # if not already sorted 
    second_booth_voters.sort() # if not already sorted 

    first = first_booth_voters[0] 
    second = second_booth_voters[0] 

    while first_booth_voters and second_booth_voters: 
     comparisons += 1 

     if first == second: 
      fraud.append(first) 
      first = first_booth_voters.pop(0) 
      second = second_booth_voters.pop(0) 
     elif first < second: 
      first = first_booth_voters.pop(0) 
     else: 
      second = second_booth_voters.pop(0) 

    return fraud, comparisons 

Answer 2

Отнесение точно спрашивает вы найти решение, и есть большой намек сортировки слияния, поэтому я не буду проливать из ответа для вас :) Но, возможно, я могу указать на то, что происходит в вашем коде: с петлей в то время как вы по существу сделать два вложенных цикла длин length_first и length_second в худшем случае:

for name_comparison in first_booth_voters: 
    for second_name in second_booth_voters: 
    comparisons += 1 
    if second_name == name_comparison: 
     fraud.append(second_name) 
     break 

, что приводит к length_first x length_second сравнения в худшем случае. Это, конечно, не оптимально, учитывая, что списки ввода отсортированы. Вам нужно использовать сортировку. И если входные списки не отсортированы, вам следует рассмотреть возможность замены более сложного для чтения/отладки/понимания цикла while с более читаемыми вложенными циклами.