Speichern von 1 Million Telefonnummern [geschlossen]

74

Was ist die effizienteste Methode, um 1 Million Telefonnummern zu speichern?

Anscheinend ist dies eine Interviewfrage bei Google, bitte geben Sie Ihre Ideen.

Algo-Geeks
quelle
29
@ Dylan: Nicht ganz Null, du musst dir merken, wo du den Ausdruck gelassen hast.
Steve Jessop
4
Apparently this is an interview question at Google, although this seems like its a bit too easy.. Nicht so einfach für mich hart
Benjamin Crouzier
3
Zuerst müssen Sie eine Telefonnummer definieren. 7 Ziffern (US-lokal)? 10 Ziffern (US-Ferngespräche)? Oder etwas Exotischeres - 5 bis 8 Ziffern (lokal in China)? 9 bis 12 Ziffern (China, wie von außerhalb des Landes gewählt)? Ich bin sicher, es gibt auch andere Muster, das sind nur die, die ich kenne. Die Dichte des Raums hängt davon ab, wie Sie ihn verpacken würden.
Loren Pechtel
3
Hat jemand anderes bemerkt, dass dies im Grunde eine Vereinfachung des Problems beim Sortieren der Festplatte auf den ersten 20 Seiten von Programming Pearls ist? Bis hin zur Verwendung von Telefonnummern als Domäne und Speicher als Ihre größte Überlegung bei der Abwägung von Design-Kompromissen. Die Antwort ist ein Bitarray oder ein Bitvektor.
nsfyn55

Antworten:

46

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.

Rob Leclerc
quelle
8
Ich mag diesen Kommentar wirklich. Für den Laien müssen Sie die Zahlen vom kleinsten zum größten sortieren. Speichern Sie die erste Nummer in der Liste. Speichern Sie dann für die nächste Nummer nur die Differenz. Ein einfaches Beispiel ist also a) 555-1234 b) 555-2234. In diesem Fall 5552234 - 5551234 = 1000. Ihr Speicher wäre also 5551234,1000, ... Großartiges Denken, ich denke, das ist es, wonach Google suchen würde. Sie haben die Zugriffsgeschwindigkeit nie erwähnt, aber ich hätte eine alternative Antwort beigefügt, die dies berücksichtigt.
Talon
1
Schätzen Sie das "Delta" zwischen einer Zahl und der anderen ... Wow! Genial!
CodeMad
Wie viel weiter können Sie kommen, wenn Sie ein Bit-Array zum Speichern von Zahlen verwenden, wie in einer anderen Antwort vorgeschlagen? Für 10-stellige Telefonnummern benötigen Sie ein 10-Milliarden-Bit-Bit-Array. Dann können Sie Muster komprimieren, z. B. werden alle möglichen Telefonnummern als codiert "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.
Marius
28

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.

Steve Jessop
quelle
2
Eine generische Verpackung ist ziemlich ineffizient, da sie die Sortierung nicht ernsthaft nutzen kann. Wenn Sie zum Beispiel Sortieren + Delta-Codierung verwenden, können Sie fast 1/3 der Größe von bzip2 --best erreichen (ich habe einen Test mit einer Million 10-stelliger Zahlen mit 1000 5-stelligen Präfixen durchgeführt: bzip2 = 3660874, delta = 1104188, raw = 10000000)
6502
10

Eine mögliche Lösung ist

  1. sortiere die Zahlen
  2. Kodieren Sie Deltas von einer Zahl zur nächsten

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

def delta_write(x, b1, b2):
    lim = 1 << (b1 - 1)
    if x < lim:
        bit_write(x, b1)
    else:
        bit_write(lim + (x & (lim - 1)), b1)
        delta_write(x >> (b1 - 1), b2, b2)

(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.

6502
quelle
Ich dachte über die gleichen Schritte 1. und 2. nach, wobei Huffman für die Codierung verwendet wurde. Neugierig, ob es ein besseres Ergebnis gibt ...
DK.
@DK: Kann sein. Das Schöne an der BER-Codierung ist, dass es keinen Baum zum Speichern gibt (weil es ein vordefinierter ist), also wie üblich YMMV. Wenn ich die Berechnung korrekt durchgeführt habe, beträgt der theoretische Mindestdurchschnitt der Bits pro Zahl beim Packen einer Million Zahlen, die aus 1000 Präfixen und 5 freien Ziffern erstellt wurden, etwa 4,68 Bit pro Zahl (zuzüglich des Speichers für 1000 Präfixe), sodass 8,83 anscheinend immer noch weit von dem entfernt ist Optimum.
6502
7

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.

Rex Kerr
quelle
7

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.

CodesInChaos
quelle
7

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

Cem
quelle
5

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.

der Wolf
quelle
3

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.

Collin Cusce
quelle
2

Ich denke, wir können hier Bit Vector mit einer Größe von 1 Million verwenden.

Java Beispiel:

private BitSet dir = new BitSet(1000000);

public void addTelephoneNumber(int number)
{
    dir.set(number);
}


public void removeTelephoneNumber(int number)
{
    if (dir.get(number))
    {
        dir.flip(number);
    }
}


public boolean isNumberPresent(int number)
{
    return dir.get(number);
}
Shailesh Kushwaha
quelle
1
Wie effizient ist diese BitSet-Lösung platzsparend?
Alexey Frunze
Dies ist die beste Antwort
craftsmannadeem
Dies ist keine gute Antwort. Es soll Telefonnummern speichern, keine Nummern von 1-1.000.000. Allerdings ist es nicht möglich, die Telefonnummern daraus abzurufen. Sie könnten eine Hashing-Funktion haben, die Telefonnummern einem bestimmten Index in diesem Bit-Array zuordnet, aber auch hier sind Hashing-Funktionen eine Möglichkeit, sodass es nicht möglich ist, die ursprüngliche Telefonnummernliste zu rekonstruieren. Die Idee hinter dem Speichern von Dingen ist, sie danach abrufen zu können.
Arian Acosta
1

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

cusimar9
quelle
Nun, da Telefonnummern mindestens 7-stellig sind (meiner Erfahrung nach), würden Sie Speicherplatz verschwenden, um die Nummern 0 - 999.999 zu speichern.
Kai
Telefonnummern sind keine Nummern. Versuchen Sie nicht, sie als Ganzzahlen zu speichern.
Nick Johnson
Ich wette, in der Praxis (in den meisten USA) müssten Sie die Vorwahl speichern, um nützlich zu sein. Dies macht die Telefonnummern 10-stellig und würde mindestens eine 34-Bit- Intoder 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!).
Thomas M. DuBuisson
1
In anderen Ländern müssen Sie möglicherweise die führende 0 speichern, und Sie müssen Extntions behandeln
Martin Beckett
@ NickJohnson Sie sind es nicht, aber wegen des Problems könnten Sie eine Ganzzahl als Index für eine Telefonnummer verwenden, oder? z.B. "(311) -0031-1151" kann auf 31100311151 indiziert werden. Ein ganzzahliger Index würde 37 Bit benötigen, aber Sie würden mindestens 7 * 11 Bit benötigen, um dieselbe Nummer wie ASCII zu speichern.
Andrew J
1

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.

Kornel Kisielewicz
quelle
Nein! Telefonnummern sind keine Nummern!
Nick Johnson
Führende Nullen können von Bedeutung sein, möglicherweise müssen Sie auch eine Verlängerung berücksichtigen
Martin Beckett
Der einfache Weg, mit führenden Nullen umzugehen, wenn Sie ein solches Codierungsschema wirklich verwenden möchten, besteht darin, der Zeichenfolge "1" voranzustellen und dann als Ganzzahl zu codieren. Wenn Sie die Ganzzahl wieder in eine Zeichenfolge dekodieren, entfernen Sie die führende "1". So wird die Telefonnummer "456" als "1456" gespeichert, während die Telefonnummer "0015833258881" als "10015833258881" gespeichert wird. Es gibt andere Probleme beim Speichern von Telefonnummern als Ganzzahlen, aber das führende "Problem" der Nullen ist keines davon.
NUR MEINE RICHTIGE MEINUNG
Ich stimme @NickJohnson in diesem Punkt zu. Ich würde nicht versuchen, sie als int oder einen auf Zahlen basierenden Datentyp zu speichern. Die Realität ist, sie sind Strings - sie haben keinen "rechnerischen" Wert
Robert Perry
1

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
1

8 Millionen Bits mit jedem Bit 1 (verwendet) oder 0 (verfügbar) für ein Beispiel mit 8 Millionen Zahlen

100 0000
900 0000
= 8 million phone numbers, bit 1 = 1000000 and bit 8 million = 9000000 
BK2
quelle
Dies nennt man Taubenlochsorte.
Ole Tange
Was ist mit einem Versuch, die Verwendung von Duplikaten so vieler Bits zu vermeiden? Die Struktur enthält nur das, was benötigt wird. Wenn die Telefonnummern spärlich sind, kann dies auch ohne Kollisionsprobleme zu erheblichen Kosteneinsparungen führen. Ich gehe davon aus, dass Ihre Lösung Kollisionen nicht berücksichtigt.
Andrew Scott Evans
-11
/******************************************************************************** 

  Filename: Phone_Numbers.c
    Author: Paul Romsky
   Company: Autoliv AEL
      Date: 11 MAR 2013

   Problem: What is the most efficient way, memory-wise, to store 1 million 
            phone numbers?

   Caveats: There is no mention if the numbers are contiguous or not, so, to save 
            space the numbers should be contiguous.  The problem (as a specification) 
            is rather vague and leaves a lot to interpretation, so many different 
            methods may be desired, but which one(s) desired is not surely known.

            Are the phone numbers just the extension (last four digits), or do they
            include the exchange (the leading 3 digits), or do they also include 
            area code and/or international numbers?

            There is no mention of the first number, only the range of numbers, so 
            the first number 000-0000 is used.  Although many numbers are not 
            normally used, they could in fact be used as valid number sequences 
            within the phone companies and are thus phone numbers nonetheless.

  Solution: A simple algorithm. If the numbers are not contiguous a fractal algorithm
            could be used.

            A standard ANSI C compiler should pack this program into a very small
            assembly module of only a few bytes.

 Revisions:

 Rev Date        By                   Description
 --- ----------- -------------------- -------------------------------------------
  -  11 MAR 2013 P. Romsky            Initial Coding

 ********************************************************************************/

/* Includes */

#include <stdio.h>


/* Functions */

/******************************************************************************** 
 *
 * Main Entry Point
 *
 ********************************************************************************/
int main()
{
  unsigned int Number;

  /* 1,000,000 Phone Number Storage 000-0000 through 999-9999 */

  for(Number = 0000000; Number < 10000000; Number++)
  {
    /* Retrieve Numbers */

    printf("%07u\n", Number);
  }

  return 0;
}

/* End */
Paul Romsky
quelle
1
Darf ich fragen, was das ist? Es ist nicht einmal vollständig. Wie beantwortet es die Frage?
Mysticial
Mystisch, es ist ein C-Programm. Ich hoffe, Sie können das Ganze sehen, es sind hauptsächlich Kommentare und der endgültige Code, der in den Speicher gelangt, befindet sich unten.
Paul Romsky
Können Sie eine Erklärung hinzufügen, wie dies das Problem löst?
Martijn Pieters
Martijn, können Sie die Hauptfunktion am Ende des Programms sehen? Es ist eine einfache Schleife. Das Programm ist sehr klein, enthält jedoch 1 Million Folgen. Die Formatierung wurde durcheinander gebracht, als ich meinen Code ausschneide und einfüge.
Paul Romsky
int main () {unsigned int Number; / * 1.000.000 Telefonnummernspeicher 000-0000 bis 999-9999 / für (Nummer = 0000000; Nummer <10000000; Nummer ++) {/ Nummern abrufen / printf ("% 07u \ n", Nummer); } return 0; } / Ende * /
Paul Romsky