J'ai récemment regardé Raymond Hettingers parler de dictionnaires python (et par jeux d'extensions ...) et il a mentionné que les entiers se hachaient et que l'ajout d'entiers à un dict (ou à un ensemble ...) les insérera dans l'ordre et tant que vous ne supprimez pas les éléments, l'ordre sera conservé en python 3.6 (et probablement au-dessus? ). Dans la réponse à cette question, il est indiqué que les dictionnaires préservent l'ordre des insertion, mais pour les ensembles, les coutures comme des entiers sont ordonnées en fonction de leur valeur.

Maintenant: selon la section complexité temporelle de python.org et plus en détail ici, il est indiqué que la complexité temporelle moyenne de l'ajout d'un élément à un ensemble est O (1). Cela signifie que si vous avez une liste d'entiers non triés, il devrait être possible de les trier en faisant simplement:

sorted_list = list(set(unsorted_list))

Cela semble être le cas pour autant que je l'ai testé (l'a fait quelques 1000 fois avec des séquences aléatoires).

Ma question est maintenant: cela signifie-t-il qu'il est possible de trier les entiers en python en temps O (n)?

Pour moi, cela semblerait ainsi, car il faut O (n) pour construire l'ensemble et O (n) pour reconvertir l'ensemble en liste ou ai-je raté quelque chose ici?

2
Chris 8 avril 2020 à 13:28

4 réponses

Meilleure réponse

Non. Les ensembles ne permettent pas de trier les entiers. Alors que les hachages d'entiers sont bien définis , l'ordre des ensembles est arbitraire .

L'ordre des ensembles peut varier selon l'implémentation, le processus et l'instance.

# CPython 3.7.4
>>> list({1, 8})
[8, 1]
>>> list({8, 1})
[8, 1]
# PyPy 3.6.9 (PyPy 7.3.0)
>>> list({1, 8})
[1, 8]
>>> list({8, 1})
[8, 1]
# CPython 2.7.10
>>> list({1, 8})
[8, 1]
>>> list({8, 1})
[8, 1]
# Jython 2.7.1 (java13.0.2)
>>> list({1, 8})
[1, 8]
>>> list({8, 1})
[1, 8]

L'ordre des ensembles peut également dépendre de l'historique d'une instance.

# CPython 3.7.4
>>> a = {1, 3, 4, 8}
>>> list(a)
[8, 1, 3, 4]
>>> a.add(2)
>>> list(a)
[1, 2, 3, 4, 8]
>>> a.discard(2)
>>> list(a)
[1, 3, 4, 8]
3
MisterMiyagi 8 avril 2020 à 12:23

Généralement, le tri O(n) est possible pour les entiers, les chaînes et de nombreux autres types de données. O (n log n) est le meilleur que vous puissiez faire avec des algorithmes de tri qui utilisent uniquement des comparaisons (>, <, ==) pour déterminer l'ordre des éléments, mais pour de nombreux types, vous n'êtes pas limité à de tels algorithmes. En particulier, voir Tri Radix pour le tri des entiers.

3
Ch3steR 8 avril 2020 à 10:40

Non, pas en général. Vous devez l'avoir essayé avec des cas spéciaux, par exemple où la liste d'entrée non triée contient tous les nombres de 0 à n, chaque fois.

Voici un cas simple qui échoue:

>>> list(set([8, 1]))
[8, 1]

Fait avec CPython 3.8.1 32 bits.

3
Heap Overflow 8 avril 2020 à 11:59

J'ai testé cela et j'ai commenté les résultats en bas. Si j'utilisais des entiers, cela retournerait simplement une liste d'entiers dans la plage - pas très utile, mais pour une liste de flottants, cela fonctionnait bien.

import random
import time

resultTimes = []
for t in range(100):
    # time the execution
    st = time.time()

    # generate an unsorted list
    unsortedList = [random.uniform(0, 1) for x in range(1000)]

    # "sort" it
    sortedList = list(set(unsortedList))

    # print the new length to check that no values were removed and the time it took to sort
    print(len(sortedList), time.time()-st)

    # save to the results list
    resultTimes.append(time.time()-st)
print()
print(f"Average Time: {sum(resultTimes)/len(resultTimes)}")


# average
# 1000000 = 0.45235085010528564
# 100000 = 0.03488146781921387
# 10000 = 0.0031537079811096193
# 1000 = 0.0002842378616333008
-1
It's not a bug... 8 avril 2020 à 10:45