Quel moyen pour avoir des éléments uniques à partir des éléments d'une liste ?

Le problème exposé dans ce sujet a été résolu.

Bonjour,

Etant donné une liste l, j’ai l’habitude pour me débarrasser de toutes les occurrences des éléments de simplement prendre set(l). Mais je me demande si c’est plus optimal (en mémoire et en temps) que de faire :

nouveau = [l[0]]
for i in l[1:]
  if i not in nouveau:
    nouveau.append(i)

Je ne sais pas trop comment appliquer set() à un itérateur fonctionne pour cela je sollicite votre aide pour m’indiquer quelle est la meilleure façon, ou si y’en a d’autres ^^.

Cordialement

En gros, le "contrat" que passe avec toi le constructeur de "set" c’est que si tu lui passe un itérable en paramètre, il te créera un objet de type set dont tous les éléments sont uniques.

L’équivalent fonctionnel de ton code est donc nouveau = list(set(l)).

Ce code dit qu’on prend un "set" à partir de la liste l, ce qui permet de dédoublonner les éléments, puis on en refait une liste avec tout ce que ça implique.

Bien sûr si tu as juste besoin de parcourir l’ensemble des valeurs sans les doublons, tu n’as pas besoin de repasser par la liste. faire simplement set(l) suffira.

Cela va dépendre de la taille de tes listes, mais asymptotiquement tu gagnerais à trier la liste et à éliminer les redondances au fur et à mesure. Ce sera en nlog(n) plutôt qu’un quadratique comme tu proposes

Je ne sais pas exactement ce que fait set, mais j’imagine que ça doit être mieux que quadratique

Salut,

Je ne sais pas exactement ce que fait set, mais j’imagine que ça doit être mieux que quadratique

Ça utilise une table de hashage, donc avec un temps amorti linéaire. Comme en plus ça repose entièrement sur du code en C, ce sera toujours largement plus efficace que n’importe quelle implémentation avec des boucles explicites en Python.

Je ne sais pas trop comment appliquer set() à un itérateur fonctionne pour cela je sollicite votre aide pour m’indiquer quelle est la meilleure façon, ou si y’en a d’autres ^^.

Si je comprends bien le code de CPython, le fait d’appliquer set() à une liste (un itérable en général) conduit à exécuter un algorithme que l’on pourrait écrire de cette façon en Python pur (j’ai essayé de faire le mapping avec le code en C) :

def make_new_set(it):
    so = set()  # PySetObject *so;
    
    # set_update_internal(so, iterable)
    for key in it:  # while ((key = PyIter_Next(it)) != NULL) {
        so.add(key)  # set_add_key(so, key)
      
    return so  # return (PyObject *)so;

Sauf qu’en faisant set(it) directement, on le fait directement en C, ce qui est donc vraisemblablement plus efficace que de le faire à la main en Python.

Autre détail important, déjà soulevé par @adri1, dans ton exemple tu testes un in sur une liste, donc en complexité linéaire : il faut parcourir successivement les éléments de nouveau jusqu’à ce qu’on trouve un doublon, ou non, auquel cas on aura parcouru l’intégralité de la liste. L’implémentation pur Python (ou son équivalent en C quand on fait set(it)) ne souffre pas de ce problème car l’implémentation sous-jacente permet de tester l’existence d’un élément de façon efficace grâce à l’utilisation d’un table de hashage (en temps constant ou à peu près1), un peu comme avec un dict. Lors d’un s.add() (ou du set_add_key(so, key) sous-jacent en C), l’existence est testée efficacement.

static int
set_add_key(PySetObject *so, PyObject *key)
{
    Py_hash_t hash;
    /* ... */
    return set_add_entry(so, key, hash);  // test et insertion si absent
}

En bref, si tu veux une liste l sans doublon, fais set(l), je ne pense pas que tu puisses faire mieux. Si tu as besoin d’avoir une liste sans doublon de type list et non pas de type set, tu peux la convertir en lui appliquant list() : list(set(l)).

Cependant, cela n’est pas gratuit. Toujours en lisant le code de CPython, j’ai l’impression que cela revient à créer une nouvelle liste (alors vide), puis de l’initialiser à l’aide d’un itérable arbitraire à coup de extend. Malgré cela, l’implémentation reste efficace en cela que la nouvelle liste est allouée une seule fois avec la bonne taille (avec list_preallocate_exact), à savoir celle de la longueur de l’objet de type set qu’on lui passe en argument. En Python pur, il ne serait sans doute pas possible de faire plus efficace.

En résumé : faire set(l) ou list(set(l)), c’est efficace par rapport à ce que tu pourrais écrire en Python pur à la main.

Si tu n’as pas besoin des propriétés des listes mais seulement des propriétés des itérables, tu peux te contenter de garder un set sans le passer en list pour économiser une allocation et des itération. Dans ton exemple, tu pourrais par exemple tout à fait itérer de façon unique sur les éléments d’une liste sans avoir à reconvertir :

for i in set(ma_liste):
   faire_qqchose_avec(i)

  1. Le code nous indique clairement que l’algorithme de lookup se base sur celui de D. Knuth: The basic lookup function used by all operations. This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. en haut du fichier C. Je suis incapable de lire un livre pareil, mais si tu veux le détail exact de l’algorithme et de son analyse et de pourquoi c’est très rapide, c’est là-dedans qu’il y a la réponse.
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte