Блог

Это просто удалить дубликаты в списке неизменяемых объектов, просто сохранив список seen объектов.

 nums = [1, 1, 2, 3, 4, 4]
duplicates_removed
seen = dict()
for n in nums:
    if n not in seen:
        duplicates_removed.append(n)
        seen[n] = True
  

Но для изменяемых объектов вы не можете хэшировать их в словаре. Какой элегантный способ быстро удалить дубликаты (определенные некоторой пользовательской логикой в __eq__ классе object) в списке?

Вы можете хранить изменяемые объекты в хэш-таблицах, но, вероятно, не должны, потому что, если у вас есть указатель на объект, вы сохраняете объект в хэш-таблице, изменяете объект, а затем пытаетесь найти его с помощью указателя, вы (почти наверняка) не найдете его, потому что хэш теперь изменился. Однако, если ваш конкретный вариант использования заключается в удалении подобных дубликатов, наиболее эффективным методом будет хэш. Если вы не используете многопоточность, и это удаление дубликатов является автономным, вы можете безопасно использовать хэш-таблицу (либо dict такую, как у вас, либо set ), потому что данные фактически неизменяемы. Единственным риском в этом случае является добавление __hash__ функции, которая обычно бесполезна. Одним из вариантов может быть создание класса тонкой оболочки, который реализует __hash__ , оберните в него ваши данные, чтобы удалить дубликаты, а затем разверните его, что-то вроде этого:

 class Wrapper(object):
    __init__(self, wrapped):
        self.wrapped = wrapped

    __eq__(self, other):
        if not isinstance(other, Wrapper):
            return False
        return self.wrapped == other.wrapped

    __hash__(self):
        # custom logic here, e.g.
        return 31 * sum(hash(item) for item in self.wrapped)

def without_duplicate_lists(lists):
    wrappers = (Wrapper(l) for l in lists)
    result = []
    seen = set()
    for w in wrappers:
        if w not in seen:
            seen.add(w)
            result.append(w)
    return [w.wrapped for w in wrappers]
  

Есть несколько других способов сделать это без вычисления хэша, например, с использованием двоичного дерева поиска (tree map). Однако хэш не является неотъемлемой проблемой при хранении изменяемых данных в maps, а скорее тем, что если вы каким-либо образом измените ключ, вы потеряете свою ценность. В хэш-таблицах ключом является хэш. В двоичном дереве поиска порядок определяется самим ключом. Если сам ключ изменится, вы не сможете найти его, какой бы метод вы ни использовали.

Также обратите внимание, что в моем примере вычисление хэша — это операция O (n), поэтому, если вы удаляете дубликаты list s или set s или dict s , возможно, будет проще преобразовать их (или их ключи) в tuple s или frozenset s, которые являются неизменяемыми и могут быть использованы в set без беспокойства (то же самое относится и к другим объектам).

Если по какой-то причине существует промежуточный вариант, когда вы считаете, что удаление дубликатов изменяемых данных с помощью хэша — плохая идея, но вы все еще считаете, что удаление дубликатов изменяемых данных — это нормально, вероятно, следующий наиболее эффективный вариант — отсортировать данные. Таким образом, вместо O (n ^ 2) для наивного решения вложенной итерации вы можете выполнить сортировку за O (n * log (n)) время, а затем выполнить итерацию, сохраняя только элементы, текущее значение которых не равно последнему значению. Для этого потребуется реализовать __eq__ , __gt__ и __lt__ (или одно из последних и использовать @total_ordering ):

 def without_duplicates_sorted(objs):
    objs = sorted(objs)
    last = objs[0]
    result = [last]
    for current in objs[1:]:
        if current != last:
            result.append(current)
        last = current
    return result
  

Для полноты картины наивное решение:

 def without_duplicates_naive(objs):
    result = []
    for obj in objs:
        if obj not in objs[i 1:]:
            result.append(obj1)
    return result
  

Я не знаю, что это элегантно, но вы часто можете преобразовать нехешируемые элементы в хешируемый объект, такой как frozenset или кортеж. Например, вы можете преобразовать элементы() dict следующим образом:

 nums = [{'a':1}, {'a':1}, {'a':2, 'c':3}, {'a':3}, {'c':3, 'a':2}, {'b':4}, {'a':4}]

duplicates_removed = []
seen = set()

for n in nums:
    n_s = frozenset(n.items())
    if n_s not in seen:
        duplicates_removed.append(n)
        seen.add(n_s)

duplicates_removed
# [{'a': 1}, {'a': 2, 'c': 3}, {'a': 3}, {'b': 4}, {'a': 4}]
  

Вам не нужен диктант.

 nums = [1, 1, 2, 3, 4, 4]
duplicates_removed = []
for n in nums:
    if n not in duplicates_removed:
        duplicates_removed.append(n)
  

То же самое работает для пользовательских классов

 class X:
    def __init__(self, n):
        self.n = n

    def __eq__(self, cmp):
        return cmp.n == self.n

    def __ne__(self, cmp):
        return cmp.n != self.n

    def __repr__(self):
        return f"X({self.n})"


nums = [X(1), X(1), X(2), X(4), X(4), X(5)]
nodups = []

for n in nums:
    if n not in nodups:
        nodups.append(n)

print(nodups)
  

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

 def remove_dups(nums):

    duplicates_removed = []

    duplicates_removed.append(nums[0])

    for i in range(1,len(nums)):

        if(nums[i]!=nums[i-1]):

            duplicates_removed.append(nums[i])

lst1 = [1, 1, 2, 3, 4, 4]
remove_dups(lst1)
// Output:  [1, 2, 3, 4]

lst2 = [{'a':1}, {'a':1}, {'c':3}, {'d':4, 'a':1}, {'d':4, 'a': 1}]
remove_dups(lst2)
// Output:  [{'a': 1}, {'c': 3}, {'a': 1, 'd': 4}]