Remplissage tableau avec valeurs uniques. Demande de conseil

**Sve@r** · 16/02/2018, 10h18

Bonjour

J'ai une toute petite question à propos d'un algo pour remplir un tableau. Je dois récupérer les valeurs à partir d'un fichier pour les stocker dans un tableau. Jusque là... Toutefois je ne dois avoir en final que des valeurs distinctes.

Et là je me demande: question d'optimisation, vaut-il mieux remplir le tableau sans me poser de questions puis, en final, écrire tab=set(tab) ; ou bien tester avant chaque insertion si la valeur n'est pas déjà présente ???

Peut-être que cela pourrait devenir une FAQ de plus...

Cordialement

**fred1599** · 16/02/2018, 11h59

Bonjour,

J'aurai tendance à dire que c'est équivalent, avec une préférence pour le set.

Maintenant question optimisation, il faut faire des tests...

**Sve@r** · 16/02/2018, 20h03

Hey, heureux de te voir t'impliquer

Merci de ta réponse. Je dois te dire qu'intuitivement moi aussi je me dis que les programmeurs du set ont dû optimiser un peu le truc (comme par exemple trier le tableau etc).

Bon pour les tests oui on peut les faire mais bon, je dois avoir à peu près 2000 valeurs donc pour aussi peu d'éléments l'un ou l'autre... C'était surtout pour avoir des avis de développeurs ayant affronté cette situation...

Merci de ta venue

**fred1599** · 16/02/2018, 20h42

Bon je te dis, dernièrement j'ai fais un test, et il se trouve que le test avait été gagnant sur le set mais de peu, d'où ma réponse... La sémantique veut que je choisisse le set, plus court, on connaît l'objet, on sait ce qu'il fait et c'est rapide à écrire. J'avais gagné 0,7 seconde sur 1 000 000 itérations, donc sur 2 000 données, t'imagines bien que l'un ou l'autre va pas changer grand chose à la résolution de ta problématique sur le temps d'exécution.

Dans ton cas, si j'ai bien compris ce que tu fais, tu ajoutes l'ensemble des éléments dans une liste, puis tu utilises set, il y a donc création de deux objets : list et set + un test pour vérifier si l'élément se trouve ou non dans l'objet set.

Dans ton cas de figure, je créerai dès le départ un objet set et j'utiliserai sa méthode add qui fera certe un test aussi mais on évitera la création et l'ajout des éléments d'une liste.
Similairement, la liste sera créée, et avec un test optimisé comme if ... in ... et l'ajout dans une liste, on sera très proche voir mieux certaines fois qu'un set.

Comme je l'ai dis précédemment, seul le test pourrait démontrer cela, mais honnêtement je ne crois pas à une grosse différence, sinon j'ai pas tout compris aux implémentations des objets python.

Je sais pas si j'ai été suffisamment clair dans ma réponse, n'hésites pas à demander.

**wiztricks** · 16/02/2018, 20h55

Envoyé par Sve@r

C'était surtout pour avoir des avis de développeurs ayant affronté cette situation...

En fait çà dépend de l'organisation des traitements et des résultats à produire.

Si le traitement m'impose de lui passer l'ensemble des valeurs, lire le fichier et supprimer les doublons via set est simple à écrire, à documenter et à relire.

Si je dois faire un traitement pour chaque ligne lue, noter ceux les déjà traités s'il faut éviter de "refaire" ou utiliser un décorateur à la memoize qui évitera de refaire tout le boulot pour un résultat déjà connu.

- W

**YCL-1** · 17/02/2018, 16h00

Bonjour,

rien de mieux que de tester les performances avec timeit.

Je me suis penché sur la question et c'est effectivement l’objet set qui est le plus performant.

On est légèrement plus performant en utilisant un set pour ajouter les éléments plutôt que d'appliquer un set à la fin d'une liste.
Cela doit s'expliquer par le fait que la liste doit conserver un ordre des objets qui n'est pas le cas du type set.

La méthode la pire est de loin celle de tester si un élément existe déjà avant de l'insérer avec la syntaxe 'if item in object'.

Voici le code Python 2 & 3, en générant une liste aléatoire d'entiers ce qui permet de vérifier l'accès aléatoire dans une liste lors du filtrage.

Je suis assez surpris par les piètres performances de Python 3 par rapport à Python 2, il semblerait que ce soit le type int qui est en cause mais je n'ai pas trouvé d'article fiable à ce sujet.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# -*- coding: utf-8 -*-
# Python 2 & 3
 
import random # Generate pseudo-random numbers
import timeit # Measure execution time of small code snippets
 
def filtered_list_method1(size_list, random_range): # {
    my_list = list()
    for i in range(size_list):
        number = random.randint(0, random_range - 1)
        if number not in my_list:
            my_list.append(number)
    return my_list
# }
 
def filtered_list_method2(size_list, random_range): # {
    my_list = list()
    for i in range(size_list):
        my_list.append(random.randint(0, random_range - 1))
    return set(my_list)
# }
 
def filtered_list_method3(size_list, random_range): # {
    my_list = [random.randint(0, random_range - 1) for i in range(size_list)]
    return set(my_list)
# }
 
def filtered_gen_method1(size_list, random_range): # {
    def generate_randint(size_list, random_range): #*{
        for i in range(size_list):
            yield random.randint(0, random_range - 1)
    # }
    my_gen = generate_randint(size_list, random_range)
    return set(my_gen)
# }
 
def filtered_gen_method2(size_list, random_range): # {
    my_gen = (random.randint(0, random_range - 1) for i in range(size_list))
    return set(my_gen)
# }
 
def set_method1(size_list, random_range): # {
    my_set = set()
    for i in range(size_list):
        my_set.add(random.randint(0, random_range - 1))
    return my_set
# }
 
def set_method2(size_list, random_range): # {
    my_set = {random.randint(0, random_range - 1) for i in range(size_list)}
    return my_set
# }
 
if __name__ == '__main__': # {
    size_list = int(1e3)
    random_range = size_list // 10
    print("Random range: {}, Size list: {}\n".format(random_range, size_list))
 
    timeit_nb_execution = int(1e3)
    for function in (
        filtered_list_method1,
        filtered_list_method2,
        filtered_gen_method1,
        filtered_gen_method2,
        set_method1,
        set_method2,
    ): # {
        total_duration = timeit.timeit(
            "{}(size_list, random_range)".format(function.__name__),
            "from __main__ import {}, size_list, random_range".format(function.__name__),
            number=timeit_nb_execution
        )
        print("\n\t".join([
            "{} execution time:".format(function.__name__),
            "Total ({} times): {:.03f} s".format(timeit_nb_execution, total_duration),
            "Average: {:.03f} ms".format(total_duration / timeit_nb_execution * 1e3),
        ]) + "\n")
    # } for
# } __main__

Avec un range de 100 valeurs pour une liste de 1000 éléments la première méthode avec la condition if est de loin la pire, le reste des méthodes se valent:

Python 2:

Python 3:

Avec un range de 10k valeurs pour une liste de 100k éléments la première méthode avec la condition if n'est même pas envisageable car 40 à 50 fois plus longue que les autres :

Python 2:

Python 3:

**Sve@r** · 17/02/2018, 23h41

Envoyé par YCL-1

Je me suis penché sur la question

Super travail

Peut-être toutefois générer la liste une seule fois au début du code pour pouvoir traiter la même liste de façon différente. En effet, la générer dans chaque fonction donne alors des listes différentes et où la différence peut alors (chance) aider dans certains cas ce qui fausse les calculs.
Mais cela n'enlève rien à l'exploit

PS: j'aime bien les accolades mises en commentaire. Je sens ici l'habitué de "vi" et de sa commande "%" permettant de basculer d'une accolade ouvrante à sa fermante et inversement

Remplissage tableau avec valeurs uniques. Demande de conseil [Python 2.X]

Python

Vue hybride

Discussions similaires

Partager

Partager