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

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.

Bonsoir,

Merci pour vos réponses. Je vais continuer à utiliser donc set mais je vais garder à l’esprit cette technique de trier la liste avant d’éliminer les redondances.

Il n’y a pas moyen de créer la liste l directement sans doublons ?

Que veux-tu dire avec "directement" ? nouveau = list(set(l)) me semble déjà pas mal.

Bah vraiment la créer sans doublons. nouveau = list(set(l)), ça crée une nouvelle liste sans doublons. Mais si l’originale l est créée sans doublons (si c’est possible, bien sûr), c’est encore mieux.

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ès¹), 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)