Discussion :

[Zarkoro]

Bonjour ou bonsoir,

Premièrement je ne savais pas où poster la question donc si un autre endroit serait plus adapter faites-le moi savoir.
Ensuite la "Big O notation" est un domaine qui m'est assez étranger dans lequel je ne connais que très peu de base. Je me demandais donc entre une fonction "ma_liste.sorted()" (qui vérifierait par exemple que ma liste de chiffres est bien triée) et une recherche d'index dans une table de hachage (avec par exemple "if element in dict") lequel pourrait s'avérer le plus rapide.
De ce que j'ai constaté, si on prend la taille t du dictionnaire et le nombre n formé par la liste de chiffres, je trouve qqch comme t = n^1/2 (même si y a 0 calculs derière c'est juste du à peu près)
J'ai observé avec des tests que à petite échelle ".sorted()" est plus lent mais je me dis que, à terme, ça pourrait s'inverser (?)

Bref, désolé pour l'explication un peu longue et merci d'avance pour vos réponses...

[fred1599]

Bonjour,

Je me demandais donc entre une fonction "ma_liste.sorted()" (qui vérifierait par exemple que ma liste de chiffres est bien triée)

Non ça retourne une liste triée, du coup votre comparaison n'est plus cohérente...

EDIT : Pour la comparaison des complexités, vous pouvez regarder cette doc

[wiztricks]

Salut,

En général on compare des opérations qui produisent le même résultat... et je ne vois pas trop le rapport entre le tri d'une liste (qui n'a rien à voir avec tester si une liste est bien triée) et la recherche d'une clef dans un dict.

Dans la pratique, on fait un jeu de test (significatif) et on mesure le temps pris par les deux moutures.
De toutes façons, si le nombre de données est "petit", les performances de l'algo. ne sont généralement pas importantes.
Là où on s'inquiète, c'est lorsque la taille des données devient assez ou trop "grande" (trop vs l'algo utilisé) *et* lorsqu'on souhaite que l'opération dure moins de X secondes dans X pourcent des cas et pas plus de Y s. dans les autres cas.

- W

[Zarkoro]

Non ça retourne une liste triée, du coup votre comparaison n'est plus cohérente...

En effet désolé j'ai inversé avec autre chose ^^"""

EDIT : Pour la comparaison des complexités, vous pouvez regarder cette doc

Merci beaucoup je vais aller regarder ça !

[Zarkoro]

En général on compare des opérations qui produisent le même résultat... et je ne vois pas trop le rapport entre le tri d'une liste (qui n'a rien à voir avec tester si une liste est bien triée) et la recherche d'une clef dans un dict.

En réalité mon but et d'effectuer des opérations sur des nombres à partir de leurs chiffres. Le truc c'est que leur ordre n'a aucune importance et comme je vais devoir en tester au moins qlq millions, je cherche le moyen le plus optimisé de passer les nombres inutils (comme par exemple 213 dans la mesure où 123 a déjà été testé au préalable).
Deux des solutions qui me paraissaient prometteuses étaient de vérifier si les chiffres du nombre étaient triés ou alors de tout mettre dans une table de hachage et de regarder si je suis déjà passé par un cas similaire.

[wiztricks]

Deux des solutions qui me paraissaient prometteuses étaient de vérifier si les chiffres du nombre étaient triés ou alors de tout mettre dans une table de hachage et de regarder si je suis déjà passé par un cas similaire.

Votre description est bien trop succincte pour voir comment cela va pouvoir marcher (l'enfer est dans les détails) si on ne fabrique pas la clef d'un dictionnaire en faisant chaine de caractère (un non mutable) des chiffres triés.
Mais ça ne fait qu'une solution.

- W

[papajoker]

Bonjour

Trier plusieurs millions ... tu as la ram pour mettre tout cela en mémoire ?

Existe des outils pour mesurer la durée, donc c'est à toi de faire les 2 tests (et peut-être avec pandas)
Puisque on ignore tout de ton traitement c'est a toi de l'écrire !

Peut-être une chose de ce type a un petit rapport avec ce que tu désires ? (aucune recherche d'optimisation !)

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
from functools import partial
 
datas= (
    [1, 8, "123", "456"],
    [1, 8, "231", "545"],
    [1, 8, "131", "545"],
    [1, 8, "321", "456"],
) * 3  # je suppose qu'en fait, tu lis/charge datas ligne a ligne
 
def traiter(ligne, col : int, results : list):
    key = ''.join(sorted(str(ligne[col])))
    if key in results:
        print("\t#", key,"==",ligne[col], "déjà traité")
    else:
        results[key] = True   # ou resultat d'un calcul ?
        # print(" traiter:",key, "->", ligne)
        yield key, ligne
 
 
results = {}
# ou, plus réaliste, appeler "traiter()" à chaque chargement d'une ligne
for a_traiter in map(partial(traiter, col=2, results=results), datas):
    try:
        key, a_traiter = next(a_traiter)
        print(a_traiter, "clé unique", key)
        #TODO traitement
    except StopIteration:
        pass

Mais, il faut quand même créer un petit dico de plusieurs millions (ou milliers?) (de bool au minimum)