Использование списка индексов для удаления из другого списка дает мне ошибку индекса вне диапазона - почему?

Question

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

Вот мой код:

toDelFromrbIndex = []
toDelFromabIndex = []
for rbIndex, (barcode, timestamp, prepack, workorder) in enumerate(restoredBottles):
    for abIndex, (idx, bcode, tstamp, tableName) in enumerate(allBottles):
         if barcode==bcode and timestamp == tstamp:
             #Remove from both lists
             toDelFromrbIndex.append(rbIndex)
             toDelFromabIndex.append(abIndex)

 for index in toDelFromrbIndex:
     del restoredBottles[index]

 for index in toDelFromabIndex:
     del allBottles[index]

До этого я удалял их в месте, где находится 'toDelFromrbIdnex.append (rbIndex)', и понял, что портит мои итерации, возможные пропуски элементов.Поэтому я сначала сохраняю индекс, а затем просто удаляю их все из обоих списков.

Однако, это for index in toDelFromrbIdnex: del restoredBottles[index] дает мне ошибку index out of range, почему?

Answer 1

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

В конце последние индексы, которые вы пытаетесь удалить, могут теперь указывать за пределысписок.Следующее также выдает IndexError:

foo = [17, 42]
for index in (0, 1):
    del foo[index]

, потому что сначала мы удаляем 17 по индексу 0.Удаление первого элемента означает, что 42 затем становится элементом с индексом 0, и с индексом 1 больше ничего нет.

Вам необходимо удалить самый высокий индекс first ,так что обрабатывайте ваши индексы в обратном порядке :

 for index in reversed(toDelFromrbIdnex):
     del restoredBottles[index]

 for index in sorted(toDelFromabIdnex, reverse=True):
     del allBottles[index]

Я отсортировал toDelFromabIndnex, потому что вы можете добавить идентификаторы к нему в произвольном порядке.

На дополнительном примечании: вы в настоящее время подбираете «бутылки» очень неэффективно.Вы используете вложенный цикл, поэтому для N restoredBottles записей и M allBottles вы делаете O (NM) тесты.По мере роста любого списка вы увеличиваете время выполнения квадратично.Например, для N = 100 и M = 1000 вы делаете 100 000 сравнений, для N = 200 - 200 000 сравнений или меняете M на 5000, и вам нужно 500 000 сравнений.

Если вы используете посредникасловарь, вы можете уменьшить это до O (N + M) шагов:

# mapping from barcode and timestamp, to index in restoredBottles
bcts_idx = {}
for i, (bc, ts, *_) in enumerate(restoredBottles)
    bcts_idx.setdefault((bc, ts), []).append(i)

toDelFromrbIndex = []
toDelFromabIndex = []
for abIndex, (idx, bcode, tstamp, tableName) in enumerate(allBottles):
    for rbIndex in bcts_idx.get((bcode, tstamp), ()):
        # Remove from both lists
        toDelFromrbIndex.append(rbIndex)
        toDelFromabIndex.append(abIndex)