Pourquoi la comparaison de chaînes est-elle si rapide en python?

Question

Je suis devenu curieux de comprendre le fonctionnement interne de la façon de comparaison de chaîne fonctionne en python quand j'étais résolution de l'exemple suivant l'algorithme de problème:

Compte tenu de deux chaînes, de retour de la longueur du plus long préfixe commun

Solution 1: charByChar

Mon intuition me dit que la solution optimale serait de commencer avec un curseur au début de ces deux mots et de réitérer l'avant jusqu'à ce que les préfixes ne correspondent plus. Quelque chose comme

def charByChar(smaller, bigger):
  assert len(smaller) <= len(bigger)
  for p in range(len(smaller)):
    if smaller[p] != bigger[p]:
      return p
  return len(smaller)

Pour simplifier le code, la fonction suppose que la longueur de la première chaîne, smaller, est toujours plus petite ou égale à la longueur de la deuxième chaîne, bigger.

Solution 2: binarySearch

Une autre méthode consiste à traversent, les deux chaînes de créer deux préfixe de sous-chaînes. Si les préfixes sont égaux, nous savons que le préfixe commun point est au moins aussi longtemps que le milieu. Sinon, le préfixe commun point est au moins pas plus grande que le milieu. On peut alors répéter pour trouver la longueur du préfixe.

Aka binaire de recherche.

def binarySearch(smaller, bigger):
  assert len(smaller) <= len(bigger)
  lo = 0
  hi = len(smaller)

  # binary search for prefix
  while lo < hi:
    # +1 for even lengths
    mid = ((hi - lo + 1) // 2) + lo

    if smaller[:mid] == bigger[:mid]:
      # prefixes equal
      lo = mid
    else:
      # prefixes not equal
      hi = mid - 1

  return lo

J'ai d'abord supposé que l' binarySearch serait plus lent en raison de la comparaison des chaînes de comparer tous les personnages plusieurs fois plutôt que de simplement les caractères de préfixe comme en charByChar.

Il est surprenant que l' binarySearch s'est avéré être beaucoup plus rapide après quelques préliminaires de l'analyse comparative.

La Figure A

Ci-dessus montre comment la performance est affectée que la longueur du préfixe est augmenté. Suffixe de longueur reste constante à 50 caractères.

Ce graphique montre deux choses:

1. Comme prévu, les deux algorithmes effectuer de façon linéaire pire que la longueur de préfixe augmente.
2. La Performance de l' charByChar se dégrade à un rythme beaucoup plus rapide.

Pourquoi est - binarySearch tellement mieux? Je pense que c'est parce que

1. La comparaison de chaînes de caractères en binarySearch est probablement optimisé par l'interprète / CPU derrière les coulisses.
2. charByChar crée de nouvelles chaînes pour chaque caractère accessible et ce produit une surcharge importante.

Pour valider cette j'ai comparé les performances de comparaison et de découpage d'une chaîne, étiquetés cmp et slice respectivement ci-dessous.

La Figure B

Ce graphique montre deux choses importantes:

1. Comme prévu, la comparaison et le découpage augmentent de façon linéaire avec la longueur.
2. Le coût de la comparaison et de tranchage augmenter très lentement avec la longueur par rapport à l'algorithme de la performance, la Figure A. Note les deux figures aller jusqu'à des chaînes de longueur 1 Milliards de caractères. Par conséquent, le coût de la comparaison de 1 caractère 1 Milliard de fois est beaucoup, beaucoup plus grande que la comparaison de 1 Milliard de caractères à la fois. Mais ce n'est toujours pas la réponse à pourquoi ...

Disponible

Dans un effort pour savoir comment le disponible interprète optimise la comparaison de chaînes de caractères, j'ai généré l'octet code de la fonction suivante.

In [9]: def slice_cmp(a, b): return a[0] == b[0]

In [10]: dis.dis(slice_cmp)
            0 LOAD_FAST                0 (a)
            2 LOAD_CONST               1 (0)
            4 BINARY_SUBSCR
            6 LOAD_FAST                1 (b)
            8 LOAD_CONST               1 (0)
           10 BINARY_SUBSCR
           12 COMPARE_OP               2 (==)
           14 RETURN_VALUE

J'ai tourné autour de la disponible code et constaté ce qui suit deux morceaux de code, mais je ne suis pas sûr que c'est là que la comparaison de chaînes se produit.

La question

• Où en la disponible ne de comparaison de chaînes se produire?
• Est-il une optimisation du CPU? Existe t il une instruction x86 qui n'comparaison de chaînes de caractères? Comment puis-je voir ce que les instructions de montage sont générés par disponible? Vous pouvez supposer que je suis avec python3 dernière, Intel Core i5, OS X 10.11.6.
• Pourquoi comparer une longue chaîne de beaucoup plus rapide que la comparaison de chacun de ses personnages?

---

Question Bonus: quel est charByChar plus performant?

Si le préfixe est suffisamment petite par rapport à la longueur du reste de la chaîne, à un certain point, le coût de la création de sous-chaînes dans charByChar devient de moins que le coût de comparer les sous-chaînes en binarySearch.

Pour décrire cette relation j'ai fouillé dans l'analyse de l'exécution.

Analyse de l'exécution

Pour simplifier les équations ci-dessous, supposons que smaller et bigger sont de la même taille et je vais me référer à eux comme s1 et s2.

charByChar

charByChar(s1, s2) = costOfOneChar * prefixLen

Où l'

costOfOneChar = cmp(1) + slice(s1Len, 1) + slice(s2Len, 1)

Où cmp(1) est le coût de la comparaison de deux chaînes de longueur 1 char.

slice est le coût d'accès à un char, l'équivalent de charAt(i). Python est immuable des chaînes et de l'accès à un char en fait crée une nouvelle chaîne de longueur 1. slice(string_len, slice_len) est le coût de découper une chaîne de caractères de longueur string_len d'une tranche de taille de l' slice_len.

Donc

charByChar(s1, s2) = O((cmp(1) + slice(s1Len, 1)) * prefixLen)

binarySearch

binarySearch(s1, s2) = costOfHalfOfEachString * log_2(s1Len)

log_2 est le nombre de fois pour diviser les chaînes de la moitié jusqu'à atteindre une chaîne de longueur 1. Où

costOfHalfOfEachString = slice(s1Len, s1Len / 2) + slice(s2Len, s1Len / 2) + cmp(s1Len / 2)

Ainsi, la grande-O de l' binarySearch grandira en fonction

binarySearch(s1, s2) = O((slice(s2Len, s1Len) + cmp(s1Len)) * log_2(s1Len))

Basé sur de notre dernière analyse du coût de la

Si nous supposons que costOfHalfOfEachString environ de l' costOfComparingOneChar alors nous pouvons nous référer à eux comme x.

charByChar(s1, s2) = O(x * prefixLen)
binarySearch(s1, s2) = O(x * log_2(s1Len))

Si nous les assimiler

O(charByChar(s1, s2)) = O(binarySearch(s1, s2))
x * prefixLen = x * log_2(s1Len)
prefixLen = log_2(s1Len)
2 ** prefixLen = s1Len

Donc, O(charByChar(s1, s2)) > O(binarySearch(s1, s2) lorsque

2 ** prefixLen = s1Len

Afin de le brancher dans la formule ci-dessus j'ai régénéré les tests pour la Figure A, mais avec des chaînes de longueur totale 2 ** prefixLen attend les performances des deux algorithmes pour être à peu près égal.

Toutefois, clairement charByChar effectue beaucoup mieux. Avec un peu d'essais et d'erreurs, les performances des deux algorithmes sont à peu près égales lorsqu' s1Len = 200 * prefixLen

Pourquoi les relations 200x?

Answer 1

C'est à la fois dépendant de l'implémentation et de la fonction du matériel. Sans connaître votre machine cible et de distribution spécifique, je ne pouvais pas dire à coup sûr. Cependant, je pense fortement que le matériel sous-jacent, comme la plupart des, a la mémoire de bloc d'instructions. Entre autres choses, cela peut comparer une paire de arbitrairement longues chaînes (jusqu'à aborder les limites) en parallèle et en pipeline de la mode. Par exemple, on peut comparer 8 octets tranches à une tranche par cycle d'horloge. C'est beaucoup plus rapide que de bricoler avec des octets indices de niveau.