Algorithme - comment supprimer efficacement les éléments dupliqués dans une liste?

cas particulier: le hachage et L'égalité

tout d'abord, nous devons déterminer quelque chose au sujet des hypothèses, à savoir l'existence d'une relation égale et d'une relation de fonction. Ce que je veux dire par cela? Je veux dire que pour l'ensemble des objets de la source S, étant donné deux objets x1 et x2 qui sont des éléments de S, il existe un (hash) de la fonction F telle que:

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

Java a une telle relation. Cela vous permet de vérifier pour dupliquer comme une opération de près O(1) et réduit ainsi le algorithme à un simple problème O(n). Si l'ordre n'est pas important, c'est un simple liner:

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

Si l'ordre est important:

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

vous noterez que j'ai dit "près de O(1)". C'est parce que de telles structures de données (comme un Java HashMap ou HashSet) s'appuient sur une méthode où une partie du code de hachage est utilisée pour trouver un élément (souvent appelé un seau) dans le support de stockage. Le nombre de compartiments est une puissance de 2. De cette façon, l'index de la liste est facile à calculer. hashCode () renvoie une int. Si vous avez 16 seaux, vous pouvez trouver celui à utiliser par ANDing le hashCode avec 15, vous donnant un nombre de 0 à 15.

lorsque vous essayez de mettre quelque chose dans ce seau, il se peut qu'il soit déjà occupé. Si oui, alors un linéaire la comparaison de toutes les entrées dans ce seau se produira. Si le taux de collision est trop élevée ou que vous essayez de mettre trop d'éléments dans la structure seront cultivés, généralement doublé (mais toujours par une puissance de 2) et tous les éléments sont placés dans leurs nouveaux compartiments (basé sur le nouveau masque). Le redimensionnement de telles structures est donc relativement coûteux.

la recherche peut également être coûteuse. Considérez cette classe:

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; }
}

ce code est parfaitement légal et il remplit le contrat égal-hashCode.

en supposant que votre ensemble ne contient rien d'autre qu'une instance, votre insertion/recherche se transforme maintenant en une opération O(n), transformant toute l'insertion en O(N²).

évidemment ceci est un exemple extrême, mais il est utile de souligner que de tels mécanismes dépendent également d'une distribution relativement bonne des hachures dans l'espace de valeur que la carte ou l'ensemble utilise.

Enfin, il faut dire que c'est un cas particulier. Si vous utilisez un langage sans ce genre de "raccourci", alors c'est une autre histoire.

Cas Général: Pas De Commande

si aucune fonction de commande n'existe pour la liste alors vous êtes coincé avec un O(n²) force brute comparaison de chaque objet à chaque autre objet. Donc en 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);
  }
}

Cas Général: Commande

si une fonction d'ordre existe (comme elle le fait avec, disons, une liste d'entiers ou de chaînes) alors vous triez la liste (qui est O(N log n)) et comparez ensuite chaque élément de la liste au suivant (O(n)) de sorte que l'algorithme total est O(N log n). En Java:

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

Remarque: les exemples ci-dessus supposent qu'aucun null n'est liste.

Si l'ordre n'a pas d'importance, vous voudrez peut-être essayer cet algorithme écrit en 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, cela serait couvert par le nub et nubBy fonctions

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 détend la dépendance sur l' Eq typeclass, à la place vous permettant de définir votre propre fonction d'égalité pour filtrer les doublons.

ces fonctions fonctionnent sur une liste de types arbitraires cohérents (par exemple [1,2,"three"] n'est pas autorisé à haskell), et ils sont tous les deux de conservation d'ordre.

afin de rendre cela plus efficace, en utilisant des données.Carte (ou de la mise en œuvre d'un balanced tree) pourrait être utilisé pour rassembler les données dans un ensemble (la clé étant l'élément, et la valeur étant l'indice dans la liste originale afin d'être en mesure d'obtenir la commande originale de retour), puis la collecte des résultats dans une liste et le tri par index. J'essaierai de le mettre en œuvre plus tard.

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)

ceci est une traduction directe de la solution de @FogleBird. Malheureusement, il ne fonctionne pas sans l'importation.

un Très de base essayer de remplacer les données.Map import serait d'implémenter un arbre, quelque chose comme ça

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

une amélioration serait de le faire autobalancer sur insert en maintenant un attribut depth (qui empêche l'arbre de se dégrader dans une liste liée). Cette chose agréable à ce sujet sur une table de hachage est qu'il exige seulement votre type pour être dans l'Ord typeclass, qui est facilement dérivable pour la plupart des types.

je prends les demandes, il me semble. En réponse à @Jonno_FTWs enquête voici une solution qui élimine complètement les doublons du résultat. Ce n'est pas tout à fait différent de l'original, il suffit d'ajouter un étui supplémentaire. Cependant, la performance d'exécution sera beaucoup plus lente puisque vous allez passer en revue chaque sous-Liste deux fois, une fois pour l'elem, et la deuxième fois pour la recusion. Notez également que maintenant il ne fonctionnera pas sur des listes infinies.

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

il est intéressant de noter que vous n'avez pas besoin de filtrer sur le second cas récursif parce que elem a déjà détecté qu'il n'y a pas de doublons.

En 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]
>>>

En java, c'est un liner.

Set set = new LinkedHashSet(list);

vous donnera une collection avec les doublons supprimés.

Pour Java pourrait aller avec ceci:

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

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

• parcourez la liste et assignez un index séquentiel à chaque élément
• trier la liste en se basant sur une fonction de comparaison pour les éléments
• supprimer les doublons
• trier la liste en se basant sur les indices assignés

pour plus de simplicité, les indices des articles peuvent être stockés dans quelque chose comme std::map

ressemble O(n*log n) si je n'ai pas manqué de rien

cela dépend de ce que vous entendez par "efficace". L'algorithme naïf est O (N^2), et je suppose que ce que vous voulez réellement dire est que vous voulez quelque chose d'ordre inférieur que cela.

comme le dit Maxim100, vous pouvez préserver l'ordre en jumelant la liste avec une série de nombres, utiliser n'importe quel algorithme que vous aimez, et puis utiliser le reste de nouveau dans leur ordre original. À Haskell, cela ressemblerait à ceci:

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

bien sûr, vous devez importer des données.Liste (tri), des Données.Fonction (sur) et de Données.Ord (comparant). Je pouvais réciter les définitions de ces fonctions, mais à quoi servirait-il?

Supprimer les doublons dans une liste en place en Python

Case: les éléments de la liste ne sont pas hachables ou comparables

C'est que nous ne pouvons pas utiliser set (dict) ou 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:]

Affaire: les Articles sont hashable

la Solution est pris à partir de ici:

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:]

Cas: les Éléments sont comparables, mais pas hashable

C'est que nous pouvons utiliser sort. Cette solution ne préserve pas l'original ordre.

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:]

j'ai écrit un algorithme pour la chaîne. En fait, il n'a pas d'importance quel type de vous avez.

static string removeDuplicates(string str)
{
    if (String.IsNullOrEmpty(str) || str.Length < 2) {
        return str;
    }

    char[] arr = str.ToCharArray();
    int len = arr.Length;
    int pos = 1;

    for (int i = 1; i < len; ++i) {

        int j;

        for (j = 0; j < pos; ++j) {
            if (arr[i] == arr[j]) {
                break;
            }
        }

        if (j == pos) {
            arr[pos] = arr[i];
            ++pos;
        }
    }

    string finalStr = String.Empty;
    foreach (char c in arr.Take(pos)) {
        finalStr += c.ToString();
    }

    return finalStr;
}

Une solution en ligne en Python.

À l'aide de listes de 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)

peut-être devriez-vous chercher à utiliser des tableaux associés (alias dict en python) pour éviter d'avoir des éléments dupliqués en premier lieu.

mon code en Java:

ArrayList<Integer> list = new ArrayList<Integer>();

list.addAll({1,2,1,3,4,5,2,3,4,3});

for (int i=0; i<list.size(); i++)
{
    for (int j=i+1; j<list.size(); j++)
    {
        if (list.get(i) == list.get(j))
        {
            list.remove(i);
            j--;
        }
    }
}

ou simplement faire ceci:

SetList<Integer> unique = new SetList<Integer>();

unique.addAll(list);

les Deux façons d'avoir le Temps = nk ~ O(n^2)

où n est la taille de la liste des entrées,

k est le nombre de participants uniques de la liste d'entrée

algorithme delete_duplicates (a[1....n])

//Supprimer les doublons à partir du tableau donné

//paramètres d'entrée :a[1:n], un tableau de n éléments

{

temp[1:n]; //un tableau de n éléments

 temp[i]=a[i];for i=1 to n

     temp[i].value=a[i]

        temp[i].key=i

*//basé sur 'value' trier le tableau temp.*

//basé sur la "valeur" supprimer dupliquer éléments de temp.

/ / basé sur' key ' triez la température du tableau.// construisez un tableau p en utilisant temp.

p[i]=temp[i].value

return p

dans l'autre des éléments est maintenu dans le tableau de sortie en utilisant la "clé". Considérons que la clé est de longueur O(n), le temps nécessaire pour effectuer le tri sur la clé et la valeur est O(nlogn). Ainsi, le temps nécessaire pour supprimer tous les doublons du tableau est O(nlogn).