Алгоритм - Как удалить дублирующиеся элементы в списке эффективно?

Однострочное решение на Python .
Использование lists-comprehesion:

>>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5]
>>> M = []
>>> zip(*[(e,M.append(e)) for e in L if not e in M])[0]
(2, 1, 4, 3, 5, 6)

• просмотреть список и присвоить каждому элементу последовательный индекс
• отсортировать список на основе некоторой функции сравнения для элементов
• удалить дубликаты
• отсортировать список на основе присвоенных индексов

для простоты индексы для элементов могут храниться в чем-то вроде std :: map

выглядит как O (n * log n), если я ничего не пропустил

It depends on what you mean by "efficently". The naive algorithm is O(n^2), and I assume what you actually mean is that you want something of lower order than that.

As Maxim100 says, you can preserve the order by pairing the list with a series of numbers, use any algorithm you like, and then resort the remainder back into their original order. In Haskell it would look like this:

superNub :: (Ord a) => [a] -> [a]
superNub xs = map snd 
              . sortBy (comparing fst) 
              . map head . groupBy ((==) `on` snd) 
              . sortBy (comparing snd) 
              . zip [1..] $ xs

Of course you need to import Data.List (sort), Data.Function (on) and Data.Ord (comparing). I could just recite the definitions of those functions, but what would be the point?

В java, это однострочный.

Set set = new LinkedHashSet(list);

даст вам коллекцию с удаленными повторяющимися элементами.

Для Java можно использовать следующее:

private static <T> void removeDuplicates(final List<T> list)
{
    final LinkedHashSet<T> set;

    set = new LinkedHashSet<T>(list); 
    list.clear(); 
    list.addAll(set);
}

В Python

>>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5]
>>> a=[]
>>> for i in L:
...   if not i in a:
...     a.append(i)
...
>>> print a
[2, 1, 4, 3, 5, 6]
>>>

Если порядок не имеет значения, вы можете попробовать этот алгоритм, написанный на Python:

>>> array = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6]
>>> unique = set(array)
>>> list(unique)
[1, 2, 3, 4, 5, 6]

в haskell это будет покрыто функциями nub и nubBy

nub :: Eq a => [a] -> [a]
nub [] = []
nub (x:xs) = x : nub (filter (/= x) xs)

nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy f [] = []
nubBy f (x:xs) = x : nub (filter (not.f x) xs)

nubBy ослабляет зависимость от Eq класс типов, позволяющий вместо этого определять вашу собственную функцию равенства для фильтрации дубликатов.

Эти функции работают со списком согласованных произвольных типов (например, [1,2, «три»] не является разрешено в haskell), и оба они сохраняют порядок.

Чтобы сделать это более эффективным, можно использовать Data.Map (или реализовать сбалансированное дерево) для сбора данных в набор (ключ является элементом, и value является индексом в исходном списке, чтобы иметь возможность вернуть исходный порядок), затем сбор результатов обратно в список и сортировка по индексу. Я постараюсь реализовать это позже.

import qualified Data.Map as Map

undup x = go x Map.empty
    where
        go [] _ = []
        go (x:xs) m case Map.lookup x m of
                         Just _  -> go xs m
                         Nothing -> go xs (Map.insert x True m)

Это прямой перевод решения @FogleBird. К сожалению, это не работает без импорта.

Самой простой попыткой заменить импорт Data.Map было бы реализовать дерево, что-то вроде этого

data Tree a = Empty
            | Node a (Tree a) (Tree a)
            deriving (Eq, Show, Read)

insert x Empty = Node x Empty Empty
insert x (Node a left right)
    | x < a = Node a (insert x left) right
    | otherwise = Node a left (insert x right)

lookup x Empty = Nothing --returning maybe type to maintain compatibility with Data.Map
lookup x (Node a left right)
    | x == a = Just x
    | x < a = lookup x left
    | otherwise = lookup x right

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

Кажется, я принимаю запросы. В ответ на запрос @Jonno_FTWs вот решение, которое полностью удаляет дубликаты из результата. Он не совсем отличается от оригинала, просто добавлен дополнительный футляр. Однако производительность во время выполнения будет намного медленнее, поскольку вы дважды просматриваете каждый подсписок, один раз для элемента, а второй раз для отшельничества. Также обратите внимание, что теперь он не будет работать с бесконечными списками.

nub [] = []
nub (x:xs) | elem x xs = nub (filter (/=x) xs)
           | otherwise = x : nub xs

Интересно, что вам не нужно фильтровать второй рекурсивный случай, потому что elem уже обнаружил отсутствие дубликатов.

Удалить дубликаты в списке на месте в Python

Случай: элементы в списке не могут быть хешированы или сопоставимы

То есть мы не можем использовать set ( dict ) или sort .

from itertools import islice

def del_dups2(lst):
    """O(n**2) algorithm, O(1) in memory"""
    pos = 0
    for item in lst:
        if all(item != e for e in islice(lst, pos)):
            # we haven't seen `item` yet
            lst[pos] = item
            pos += 1
    del lst[pos:]

Случай: элементы можно хешировать

Решение взято из здесь :

def del_dups(seq):
    """O(n) algorithm, O(log(n)) in memory (in theory)."""
    seen = {}
    pos = 0
    for item in seq:
        if item not in seen:
            seen[item] = True
            seq[pos] = item
            pos += 1
    del seq[pos:]

Случай: элементы сопоставимы, но not hashable

То есть мы можем использовать sort . Это решение не сохраняет исходный порядок.

def del_dups3(lst):
    """O(n*log(n)) algorithm, O(1) memory"""
    lst.sort()
    it = iter(lst)
    for prev in it: # get the first element 
        break
    pos = 1 # start from the second element
    for item in it: 
        if item != prev: # we haven't seen `item` yet
            lst[pos] = prev = item
            pos += 1
    del lst[pos:]

Особый случай: хеширование и равенство

Во-первых, нам нужно определить кое-что о допущениях, а именно существование отношения равенства и наличия функции. Что я имею в виду? Я имею в виду, что для набора исходных объектов S, учитывая любые два объекта x1 и x2, которые являются элементами S, существует (хеш-функция) F такая, что:

if (x1.equals(x2)) then F(x1) == F(x2)

Java имеет такое отношение. Это позволяет вам проверять дубликаты как операцию, близкую к O (1), и, таким образом, сводит алгоритм к простой задаче O (n). Если порядок не важен, это просто один лайнер:

List result = new ArrayList(new HashSet(inputList));

Если порядок важен:

List outputList = new ArrayList();
Set set = new HashSet();
for (Object item : inputList) {
  if (!set.contains(item)) {
    outputList.add(item);
    set.add(item);
  }
}

Вы заметите, что я сказал «около O (1)». Это потому, что такие структуры данных (как Java HashMap или HashSet) полагаются на метод, в котором часть хеш-кода используется для поиска элемента (часто называемого корзиной) в резервном хранилище. Количество ковшей - степень двойки. Таким образом, индекс в этом списке будет легко вычислить. hashCode () возвращает int. Если у вас есть 16 сегментов, вы можете найти, какое из них использовать, сложив И хэш-код с 15, получив число от 0 до 15.

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

Поиск также может быть дорогостоящим. Рассмотрим этот класс:

public class A {
  private final int a;

  A(int a) { this.a == a; }

  public boolean equals(Object ob) {
    if (ob.getClass() != getClass()) return false;
    A other = (A)ob;
    return other.a == a;
  }

  public int hashCode() { return 7; }
}

Этот код совершенно законен и выполняет контракт equals-hashCode.

Предполагая, что ваш набор не содержит ничего, кроме экземпляров A, ваша вставка / поиск теперь превращается в операцию O (n), превращая всю вставку в O (n ² ).

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

Наконец, необходимо сказать, что это особый случай ]. Если вы используете язык без такого «ярлыка хеширования», то это совсем другая история.

Общий случай: без упорядочивания

Если для списка не существует функции упорядочивания, то вы застряли с O (n ² ) сравнение методом перебора каждого объекта с любым другим объектом. Так в Java:

List result = new ArrayList();
for (Object item : inputList) {
  boolean duplicate = false;
  for (Object ob : result) {
    if (ob.equals(item)) {
      duplicate = true;
      break;
    }
  }
  if (!duplicate) {
    result.add(item);
  }
}

Общий случай: упорядочивание

Если существует функция упорядочивания (как, например, с список целых чисел или строк), затем вы сортируете список (который равен O (n log n)), а затем сравниваете каждый элемент в списке со следующим (O (n)), поэтому общий алгоритм равен O (n log n) . В Java:

Collections.sort(inputList);
List result = new ArrayList();
Object prev = null;
for (Object item : inputList) {
  if (!item.equals(prev)) {
    result.add(item);
  }
  prev = item;
}

Примечание: в приведенных выше примерах предполагается, что в списке нет нулей.

Возможно, вам стоит изучить возможность использования ассоциированных массивов (также известных как dict в Python), чтобы избежать дублирования элементов.