J'ai 2 fonctions de détection d'anagrammes; l'un utilise le tri et la comparaison et l'autre enregistre le nombre d'occurrences de chaque caractère alphabétique.

Supposons ici que les deux chaînes passées aux fonctions sont identiques, la première générée aléatoirement (non triée) et la seconde = à la première, de sorte que les deux fonctions exécutent "complètement" et retournent True.

D'après mon analyse algorithmique (évidemment probablement fausse ...), la première fonction devrait être 2 * n log (n) + n, et la deuxième fonction 2 + 2n + 2n + 26 = 28 + 5n.

def anag1(s1, s2):      
    s1 = list(s1)
    s1.sort()
    s2 = list(s2)
    s2.sort()

    for i in range(len(s1)):
        if s1[i] != s2[i]:
            return False

    return True

def anag2(s1, s2):
    l1 = [0] * 26
    l2 = [0] * 26
    for i in s1:
        k = ord(i) % 26
        l1[k] += 1
    for i in s2:
        k = ord(i) % 26
        l2[k] += 1

    return l1 == l2

Pour 2 chaînes de 100 000 caractères, cela devrait signifier que la première fonction serait de 3,4 millions d'unités de temps contre 400 000 unités de temps pour la deuxième fonction.

En d'autres termes, la deuxième fonction devrait être près de 8 fois plus rapide que la première .

Cependant, lorsque je chronomètre l'exécution des deux fonctions, la seconde n'est même pas deux fois plus rapide que la première. Pour 2 chaînes de 100 000 caractères, la première fonction s'exécute en 0,085 s et la seconde en 0,055 s.

Que se passe-t-il ?

1
jeremy radcliff 17 janv. 2017 à 17:39

2 réponses

Meilleure réponse

La complexité théorique peut avoir peu avec le temps réel passé. Considérer:

  • Diverses complexités d'opérations uniques (p. Ex. Division vs ajout)
  • Accès à la mémoire (un mauvais taux de réussite du cache dû à un accès aléatoire fréquent sur d'énormes baies peut le ralentir de plus de la moitié)
  • Optimisations du compilateur / interpréteur
  • etc.

Et tous les types ne sont pas O(n log (n))

  • Le tri par comptage, le tri par compartiment, le tri par radix sont tous O(n) ou proches de.

Edit: J'ai implémenté les deux en Java sur un tableau long de 100M. C'était 383 contre 161 ms. Sur 10M, les temps étaient presque égaux.

  • Votre baie de 100k est bien trop petite pour réchauffer les optimiseurs.
  • Java utilise DualPivotQuickSort, qui s'exécute presque O(n) sur des tableaux avec de nombreuses valeurs en double (cardinalité de petits caractères). Votre langue peut utiliser quelque chose de similaire.
3
Tomas F. 17 janv. 2017 à 15:13

Toutes les fonctions primitives ne prennent pas le même temps. Par exemple, votre deuxième méthode inclut les divisions, qui nécessitent souvent plus de cycles CPU que les autres opérations. Alors que la première fonction est O (n log (n)) et la seconde est O (n), vous ne savez pas quel est le facteur constant.

Ce que votre analyse indique vraiment, c'est que si vous le faites maintenant avec des millions de chaînes de caractères, vous devriez voir que la différence de vitesse s'élargit.

2
Warren Dew 17 janv. 2017 à 14:47