Когда working on an AoC puzzle, я обнаружил, что я хотел, чтобы вычесть списки (с сохранением упорядочения):О (п) список вычитание
def bag_sub(list_big, sublist):
result = list_big[:]
for n in sublist:
result.remove(n)
return result
Я не нравится, как list.remove
вызова (который сам по себе O (п)) содержится внутри цикла, что кажется бесполезным неэффективным. Так что я попытался переписать его, чтобы избежать этого:
def bag_sub(list_big, sublist):
c = Counter(sublist)
result = []
for k in list_big:
if k in c:
c -= Counter({k: 1})
else:
result.append(k)
return result
Является ли это сейчас O (п), или же
Counter.__isub__
использование еще винт вещи?Этот подход требует, чтобы элементы были хешируемыми, ограничение, которых оригинал не имел. Существует ли решение O (n), которое позволяет избежать этого дополнительного ограничения? Есть ли у Python лучший тип данных «bag», чем
collections.Counter
?
Можно предположить, sublist
составляет половину длины list_big
.
Имеются ли в этих списках какой-либо конкретный порядок? Вы можете сделать это в O (n) детерминированном времени, если они оба отсортированы. – user2357112
Я не уверен, что вы делаете с Counter Counter. Вы можете получить тот же результат более четко, преобразовывая подсписку в набор и просто проверяя членство. –
@ DanielRoseman - Я думаю, что счетчик обрабатывает дубликаты ('bag_sub ([foo, foo], [foo]) -> [foo]') – mgilson