Angenommen, Sie nehmen die Zeichenfolgen "a" und "z" und listen alle Zeichenketten auf, die zwischen ihnen liegen, in alphabetischer Reihenfolge: ['a', 'b', 'c' ... 'x', 'y' , 'z']. Nimm den Mittelpunkt dieser Liste und du findest 'm'. Das ist ungefähr so, als würde man einen Durchschnitt dieser beiden Strings nehmen.
Sie könnten es auf Strings mit mehr als einem Zeichen erweitern, zum Beispiel würde der Mittelpunkt zwischen 'aa' und 'zz' in der Mitte der Liste ['aa', 'ab', 'ac' .. . 'zx', 'zy', 'zz'].
Könnte es irgendwo eine Python-Methode geben, die das tut? Wenn nicht, würde sogar der Name des Algorithmus helfen.
Ich fing an, meine eigene Routine zu machen, die einfach beide Strings durchläuft und den Mittelpunkt des ersten abweichenden Buchstabens findet, der großartig zu funktionieren schien, da "aa" und "az" Mittelpunkt "am" waren, aber dann scheitert an "cat", "doggie" midpoint, den es für "c" hält. Ich habe Googling für "binary search string midpoint" usw. versucht, aber ohne den Namen dessen zu kennen, was ich hier versuche, hatte ich wenig Glück.
Ich habe meine eigene Lösung als Antwort hinzugefügt
Wenn Sie ein Alphabet von Zeichen definieren, können Sie einfach in die Basis 10 konvertieren, einen Durchschnitt machen und zurück in die Basis-N konvertieren, wobei N die Größe des Alphabets ist.
%Vor%Bearbeiten : Basierend auf Kommentaren und anderen Antworten möchten Sie möglicherweise Strings unterschiedlicher Länge behandeln, indem Sie den ersten Buchstaben des Alphabets an das kürzere Wort anhängen, bis sie die gleiche Länge haben. Dies wird dazu führen, dass der "Durchschnitt" zwischen den beiden Eingaben lexikographisch fällt. Codeänderungen und neue Ausgaben unten.
%Vor%Wenn Sie alphabetisch meinen, verwenden Sie einfach den FogleBird-Algorithmus, aber kehren Sie die Parameter und das Ergebnis um!
%Vor%oder umschreiben wie so
%Vor%Es klingt wie das, was Sie wollen, ist, alphabetische Zeichen als Basis-26-Wert zwischen 0 und 1 zu behandeln. Wenn Sie Strings unterschiedlicher Länge haben (ein Beispiel in Basis 10), sagen Sie 305 und 4202, kommen Sie mit heraus ein Mittelpunkt von 3, da du die Charaktere nacheinander ansiehst. Behandle sie stattdessen als Fließkomma-Mantisse: 0.305 und 0.4202. Daraus ergibt sich ein mittlerer Punkt von .3626 (Sie können runden, wenn Sie möchten).
Machen Sie dasselbe mit der Basis 26 (a = 0 ... z = 25, ba = 26, bb = 27 usw.), um die Berechnungen für Buchstaben durchzuführen:
cat wird zu "a.cat" und doggie wird "a.dogie", die Berechnung ergibt cat einen Dezimalwert von 0,078004096, doggie einen Wert von 0,136390697, mit einem Durchschnitt von 0,107197397, der in der Basis 26 ungefähr "cumcqo" ist
Basierend auf Ihrer vorgeschlagenen Verwendung scheint konsistentes Hashing ( Ссылка ) mehr Sinn zu ergeben.
Danke für alle, die geantwortet haben, aber ich habe letztendlich meine eigene Lösung geschrieben, weil die anderen nicht genau das waren, was ich brauchte. Ich versuche, die Schlüsselnamen der App-Engines zu berechnen, und nachdem ich sie ein wenig genauer studiert habe, habe ich entdeckt, dass sie tatsächlich alle 7-Bit-ASCII-Zeichen in den Namen zulassen. Außerdem konnte ich mich nicht wirklich auf die Lösungen verlassen, die die Schlüsselnamen zuerst in Fließkommawerte umwandelten, weil ich vermutete, dass Gleitkomma-Genauigkeit einfach nicht genug ist.
Um einen Durchschnittswert zu erhalten, addieren Sie zuerst zwei Zahlen zusammen und teilen sie dann durch zwei. Dies sind beide so einfache Operationen, dass ich mich dazu entschieden habe, einfach Funktionen zu machen, um Basis-128-Nummern, die als Listen dargestellt sind, hinzuzufügen und zu unterteilen. Diese Lösung wurde noch nicht in meinem System verwendet, so dass ich immer noch einige Fehler darin finden könnte. Auch könnte es wahrscheinlich viel kürzer sein, aber das ist nur etwas, was ich tun musste, anstatt zu versuchen, es perfekt zu machen.
%Vor%Arbeiten Sie noch an Saiten mit verschiedenen Längen ... irgendwelche Ideen?
Diese Version denkt, dass 'abc' ein Bruch wie 0.abc ist. In diesem Ansatz ist Platz Null und eine gültige Eingabe / Ausgabe.
%Vor%Leider ist der naive Algorithmus nicht in der Lage, die periodischen Z zu erkennen, das wäre etwa 0.99999 in Dezimal; deshalb ist 'a zzzzzzzz' tatsächlich 'aa' (der Raum vor der 'z' Periodizität muss um eins erhöht werden.
Um dies zu normalisieren, können Sie die folgende Funktion verwenden
%Vor%