Was ist die effizienteste Methode, um 1 Million Telefonnummern zu speichern?
Anscheinend ist dies eine Interviewfrage bei Google, bitte geben Sie Ihre Ideen.
algorithm
data-structures
Algo-Geeks
quelle
quelle
Apparently this is an interview question at Google, although this seems like its a bit too easy.
. Nicht so einfach für mich hartAntworten:
Wenn der Speicher unsere größte Überlegung ist, müssen wir die Zahl überhaupt nicht speichern, sondern nur das Delta zwischen i und i + 1.
Wenn die Nummern zwischen 200 0000 und 999 9999 liegen, gibt es 7.999.999 mögliche Telefonnummern. Da wir 1 Million Zahlen haben und davon ausgehen, dass sie gleichmäßig verteilt sind, haben wir einen erwarteten Abstand von E = n_i + 1 - n_i ~ 8 (3 Bits) zwischen den fortlaufenden Zahlen n_i und n_i + 1. Für einen 32-Bit-Int könnten wir also möglicherweise bis zu 10 aufeinanderfolgende Offsets speichern (~ 400 KB optimaler Gesamtspeicherbedarf). Es ist jedoch wahrscheinlich, dass wir in einigen Fällen einen Offset von mehr als 8 benötigen (möglicherweise haben wir 400 oder 1500 ??). In diesem Fall können wir einfach die ersten 2 Bits des int als Header reservieren, der uns sagt, welche Frame-Größe wir zum Lesen der darin gespeicherten Bits verwenden. Zum Beispiel verwenden wir vielleicht: 00 = 3x10, 01 = 5x6, 10 = 7x4, 11 = 1 * 30.
quelle
"1"x10^10
(alle 10 Milliarden Bits sind 1). Alle alternierenden Zahlen, die bei 0 beginnen, wären"01"x(10^10)/2
(wiederholen Sie die Zeichenfolge "01" 5 Milliarden Mal). Der Ansatz würde fehlschlagen, wenn Sie eine zufällige Verteilung von etwa einer halben Milliarde Zahlen erhalten, wobei die Codierungsgröße 10 Milliarden Bits überschreiten kann.Schreiben Sie sie in ASCII, durch Leerzeichen getrennt.
Zippen Sie die resultierende Zeichenfolge mit Ihrem bevorzugten Komprimierungsalgorithmus. Wenn die Reihenfolge nicht wichtig ist, kann das erstmalige Sortieren die Komprimierung unterstützen und zu mehr Wiederholungen führen.
Oh, wollten Sie einen effizienten Direktzugriff? Dann hättest du sagen sollen.
quelle
Eine mögliche Lösung ist
Die Delta-Häufigkeitsverteilung ist stark verzerrt.
Ich habe ein Experiment mit einem einfachen BER-ähnlichen Packungsansatz für Deltas unter Verwendung einer 7 + 3 + 3 + ... Bit-Codierung durchgeführt. Codierungsfunktion war
(Die beiden Parameter 7 und 3 wurden experimentell bestimmt)
Mit diesem Ansatz erhielt ich eine Million 10-stellige Zahlen, wobei die ersten 5 Stellen aus tausend zufälligen Präfixen mit einem Durchschnitt von 8,83 Bit pro Zahl (Packungsgröße 1104188) ausgewählt wurden.
quelle
Die Huffman-Codierung auf Ziffernblöcken würde wahrscheinlich sehr gute Ergebnisse liefern. Wenn die Nummern gemischten Typs wären (z. B. einige US-amerikanische, einige ausländische, einschließlich Zugangscode), würden Sie ein paar weitere Bits benötigen, um anzugeben, welcher Typ sie sind (und daher welche Blöcke verwendet werden sollen).
Wenn die Zahlen in einem kleinen Bereich liegen würden - z. B. sieben Ziffern -, wäre die kompakteste Art, sie zu speichern, wahrscheinlich, sie als Ganzzahlen zu behandeln, zu sortieren und (Huffman-codierte) Wertunterschiede zu speichern. Beispiel: Bei 10 ^ 6 Zahlen in 7 Ziffern (10 ^ 7 Möglichkeiten) würden Sie ungefähr log2 (10) ~ = 3,3 Bits pro Zahl benötigen.
quelle
Zuerst beobachte ich, dass sie niemals mit 0 beginnen, da 0 am Anfang als Escape-Zeichen verwendet wird. Ich kann Telefonnummern also einfach als ganze Zahlen betrachten. Wenn dies nicht der Fall wäre, würde ich der Zahl einfach eine "1" voranstellen und sie dann in eine Ganzzahl umwandeln. Dies würde die Codierungseffizienz nicht wesentlich beeinflussen (wahrscheinlich konstanter Overhead von einigen Bytes). Wenn andere Zeichen außerhalb der 10 Ziffern in den Telefonnummern vorhanden sind, codieren Sie einfach mit einer Basis über 10. Dies beeinträchtigt jedoch die Effizienz.
Ich würde sie nach aufsteigender Größe bestellen. Berechnen Sie dann die Differenzen. Und dann serialisieren Sie die Unterschiede mit protobuf als gepackte wiederholte Felder.
Diese Methode ähnelt der von RexKerr, außer dass ich die faule Lösung von Protobuf über einem Huffman-Encoder verwende. Wahrscheinlich etwas größer, da die Protobuf-Ganzzahlcodierung ein allgemeiner Zweck ist und die Wahrscheinlichkeitsverteilung von Telefonnummern nicht berücksichtigt. Das Codieren ist jedoch viel einfacher, da ich nur einen vorhandenen Protobuf-Serializer verwenden muss. Dies wird problematisch, sobald Sie die Größe eines UInt64 überschreiten, dh es gibt Telefonnummern, die länger als 19 Stellen sind. Das Dateiformat unterstützt es weiterhin, die meisten Implementierungen jedoch nicht.
Ohne Index sind die Zugriffszeiten ziemlich schlecht, aber es sollte ziemlich kompakt sein.
quelle
Ein ternärer Suchbaum, der eine spezielle Trie-Datenstruktur darstellt, ist speichereffizient und ermöglicht weiterhin (als Trie) eine teilweise Übereinstimmung.
http://en.wikipedia.org/wiki/Ternary_search_tree
quelle
Wenn Sie sich Datenfelddarstellungen des nordamerikanischen Nummerierungsplans ansehen , werden Sie zu dem Schluss kommen, dass die US-Telefonnummern von 1+ NPA + NXX + xxxx in jeder Vorwahl in weniger als 22 Bit pro Telefonnummernfeld gespeichert werden können. Fügen Sie die Vorwahlen hinzu, und die Daten, die eine beliebige US-amerikanische (plus kanadische) Telefonnummer darstellen, passen bequem in 32 Bit. Dies ist als Bitfelddarstellung - nicht als int.
Ihre Überlegungen dazu sollten jedoch nicht US-zentriert sein. Sicherlich ist die Frage nicht nur eine Übung, bei der 1 Million Telefonnummern auf die kleinstmöglichen Stellen komprimiert werden.
US-Telefonnummern können 3-stellig (interne PBX-Wählpläne) bis 22-stellig (1 + NPA + NXX + xxxx + 11-stelliger interner PBX-Wählplan) sein. Wenn die Telefonnummer auf das von der ITU angegebene Nummernformat beschränkt war , haben Sie bis zu 15 Ziffern plus 1 Bit für das '+'.
Sie sollten dann wahrscheinlich eine variable Bitfelddarstellung einer beliebigen Telefonnummer zwischen 3 und 22 Stellen (oder 15 Stellen für ITU) definieren, wobei jedes Bitfeld ein X-Bit-Headerfeld enthält, um das Format des Felds anzugeben.
Fügen Sie diese Bitfelder dann in ein komprimiertes Bitarray ein . Möglicherweise kann dieses Bitarray mit einem Trie oder einer anderen Methode indiziert werden.
Die Effizienz basiert auf dem Format der 1 Million Telefonnummern, wie schnell Sie darauf zugreifen möchten und wie flexibel diese Datenstruktur für künftig mehr Telefonnummern in unterschiedlichen Formaten ist. Es zählt meiner Meinung nach nicht nur Bits für die "richtige" Antwort.
quelle
Angenommen, wir gehen davon aus, dass jede Telefonnummer mit dem US-Format (3-stellige Vorwahl) - (7-stellige Nummer) übereinstimmt.
Dies ist eine 10-stellige Nummer.
Es gibt jedoch Regeln für das Engagement beim Umgang mit Telefonnummern. Zum einen sind sie spärlich, was bedeutet, dass nicht alle möglichen Vorwahlen verwendet werden. In diesem Fall ist ein einfacher Baum a-ok. Ich meine, denken Sie darüber nach ... Sie brauchen nur 269 + 26 für Kanada. Das ist ziemlich klein, und Sie haben einen großen Teil des Speicherplatzes sowie die längere Suchzeit ausgeschnitten. Darüber hinaus kann es für Standortinformationen erweitert werden.
Danach haben Sie eine 7-stellige Nummer. Dies kann in einer einzelnen 32-Bit-Ganzzahl gespeichert werden. Beim Einfügen sortieren, und Sie haben einen ziemlich schnellen Mechanismus zum Abrufen, da Sie den Rest der Zahl binär durchsuchen können.
quelle
Ich denke, wir können hier Bit Vector mit einer Größe von 1 Million verwenden.
Java Beispiel:
quelle
Ich vermute ein Int32 ohne Vorzeichen oder für internationale Nummern ein Int64 ohne Vorzeichen
Bei Verwendung von 32-Bit-Ints ohne Vorzeichen wären dies 4 MB
quelle
Int
oder pfiffige Verpackung erfordern , um die wahrscheinlich nicht verwendeten Werte von 0-999999999 zu eliminieren (das ist mehr als die Hälfte Ihres 34-Bit-Speicherplatzes!).Es hängt wirklich davon ab, welche Vorgänge Sie für die gespeicherte Datenbank ausführen möchten.
Der triviale Ansatz besteht darin, vorzeichenlose Ganzzahlen zu verwenden. Wenn Sie diese nur speichern müssen, ist die Komprimierung der Rohtextdarstellung mithilfe eines Wörterbuchs wahrscheinlich kleiner.
quelle
Bei einem Vorstellungsgespräch geht es bei dieser Frage darum, die Fähigkeiten des Bewerbers zur Problemlösung einzuschätzen. Da der Schwerpunkt der Frage auf der Speichereffizienz liegt , lautet die richtige Antwort meiner Meinung nach, den Interviewer zu fragen: "Sind die Telefonnummern international oder sind sie auf ein einzelnes Land beschränkt?" Wenn die Nummern auf ein einzelnes Land beschränkt sind, wird die Maximierung der Speichereffizienz durch die Tatsache vereinfacht, dass jedes Land einfache Regeln für die Verteilung von Telefonnummern nach Bundesstaat und Stadt hat.
quelle
8 Millionen Bits mit jedem Bit 1 (verwendet) oder 0 (verfügbar) für ein Beispiel mit 8 Millionen Zahlen
quelle
quelle