Самый эффективный способ хранения тысяч телефонных номеров

в дальнейшем я рассматриваю числа как целочисленные переменные (в отличие от строк):

1. сортировка чисел.
2. разделить каждое число на первые пять цифр и последние пять цифр.
3. первые пять цифр одинаковы по номерам, поэтому храните их только один раз. Для этого потребуется 17 бит памяти.
4. хранить последние пять цифр каждого номера по отдельности. Для этого потребуется 17 бит на число.

To Напомним: первые 17 бит-это общий префикс, последующие 1000 групп из 17 бит-это последние пять цифр каждого числа, хранящиеся в порядке возрастания.

в общей сложности мы смотрим на 2128 байт для 1000 номеров, или 17,017 бит на 10-значный номер телефона.

Поиск O(log n) (двоичный поиск) и полное перечисление O(n).

http://en.wikipedia.org/wiki/Acyclic_deterministic_finite_automaton

однажды у меня было интервью, где они спрашивали о структурах данных. Я забыл "массив".

Я, вероятно, рассмотрю возможность использования некоторой сжатой версии A Trie (возможно a чувак как предложил @Misha).

Что бы автоматически воспользоваться тем, что все они имеют общий префикс.

поиск будет выполняться в постоянное время, а печать будет выполняться в линейное время.

Я слышал об этой проблеме раньше (но без первого-5-значного-того же предположения), и самый простой способ сделать это был Кодирование Райса:

1) поскольку порядок не имеет значения, мы можем сортировать их и сохранять только различия между последовательными значениями. В нашем случае средние различия были бы 100.000 / 1000 = 100

2) кодируйте различия, используя коды риса (база 128 или 64) или даже коды Голомба (база 100).

EDIT: Оценка для кодирования риса с базой 128 (не потому, что это даст лучшие результаты, а потому, что его легче вычислить):

мы сохраним первое значение как есть (32 бита).
Остальные 999 значений разницы (мы ожидаем, что они будут небольшими, в среднем 100) будут содержать:

унарный стоимостью value / 128 (переменное число битов + 1 бит в качестве Терминатора)
двоичное значение для value % 128 (7 бит)

мы должны как-то оценить пределы (назовем это VBL) для количества переменных бит:
нижний предел: считайте, что нам повезло, и никакая разница не больше, чем наша база (128 в этом случае). это означало бы дать 0 дополнительных битов.
высокий предел: поскольку все различия, меньшие, чем база, будут кодироваться в двоичной части числа, максимальное число, которое нам нужно будет кодировать в унарном, равно 100000/128 = 781.25 (даже меньше, потому что мы не ожидаем, что большинство различий будет равно нулю).

Итак, результат 32 + 999 * (1 + 7) + переменная (0..Семьсот восемьдесят два) bits = 1003 + переменная (0..98) байт.

Это хорошо известная проблема от жемчуга программирования Бентли.

решение: Удалите первые пять цифр из чисел, поскольку они одинаковы для каждого число. Затем используйте побитовые операции для представления оставшихся 9999 возможных значение. Вам понадобится только 2^17 бит для представления чисел. каждый бит представляет собой число. Если бит установлен, номер находится в телефонной книге.

чтобы напечатать все числа, просто распечатайте все числа, где бит набор сцепленный с префиксом. Для поиска заданного числа сделайте необходимый бит арифметика для проверки побитового представления числа.

вы можете искать число в O (1), и эффективность пространства максимальна из-за битовой репрезентации.

HTH Крис.

исправлено хранение 1073 байт для 1000 чисел:

основной формат этого метода хранения состоит в том, чтобы хранить первые 5 цифр, количество для каждой группы и смещение для каждого числа в каждой группе.

префикс:
Наш 5-значный префикс занимает первое 17 бит.

группировка:
Далее, нам нужно выяснить хороший размер группировки для чисел. Давайте попробуем о 1 число в группе. Поскольку мы знаем, что есть около 1000 номеров для хранения, мы разделяем 99,999 на около 1000 частей. Если бы мы выбрали размер группы как 100, были бы потрачены впустую биты, поэтому давайте попробуем размер группы 128, который может быть представлен 7 битами. Это дает нам 782 группы для работы.

важно:
Далее, для каждой из 782 групп, нам нужно сохранить количество записей в каждой группе. 7-битный счетчик для каждой группы даст 7*782=5,474 bits, что очень неэффективно, потому что среднее число представленных составляет около 1 из-за того, как мы выбрали наши группы.

таким образом, вместо этого у нас есть счетчики переменного размера с ведущими 1 для каждого числа в группе, за которым следует 0. Таким образом, если бы мы имели x номера в группе, мы бы x 1's затем 0 для представления графа. Например, если бы у нас было 5 чисел в группе, счетчик был бы представлен 111110. С помощью этого метода, если есть 1000 номеров мы в конечном итоге с 1000 1 и 782 0 в общей сложности 1000 + 782 = 1,782 бит для отсчетов.

зачет:
Наконец, формат каждого числа будет Просто 7-битным смещением для каждой группы. Например, если 00000 и 00001 являются единственными числами в группе 0-127, биты для этой группы будут 110 0000000 0000001. Предполагая, что 1000 чисел, будет 7,000 бит для смещения.

таким образом, наш окончательный подсчет, предполагающий 1000 чисел, выглядит следующим образом следует:

17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes

теперь давайте проверим, был ли наш выбор размера группы путем округления до 128 бит лучшим выбором для размера группы. Выбор x как количество битов для представления каждой группы, формула для размера:

Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000

минимизация этого уравнения для целых значений x дает x=6, что дает 8 580 бит = 1,073 байт. Таким образом, наше идеальное хранилище выглядит следующим образом:

• размер группы: 2^6 = 64
• количество групп: 1,562

• объем внутренней памяти:

  1017 (prefix plus 1's) + 1563 (0's in count) + 6*1000 (offsets) = 8,580 bits = 1,073 bytes

принимая это как чисто теоретическую проблему и оставляя реализацию в стороне, единственный наиболее эффективный способ-просто индексировать все возможные наборы из 10000 последних цифр в гигантской таблице индексирования. Предполагая, что у вас есть ровно 1000 номеров, вам понадобится немного больше, чем 8000 бит, чтобы однозначно идентифицировать текущий набор. Нет возможности большего сжатия, потому что тогда у вас будет два набора, которые идентифицируются с одним и тем же состоянием.

проблемы с этим в том, что вы пришлось бы представлять каждый из 2^8000 наборов в вашей программе как lut, и даже google не был бы удаленно способен на это.

поиск будет O(1), печатая все число O (n). Вставка была бы O(2^8000), которая в теории является O (1), но на практике непригодна.

в интервью я бы только дал такой ответ, если бы был уверен, что компания ищет кого-то, кто способен много думать из коробки. В противном случае это может заставить вас выглядеть как теоретик без проблемы реального мира.

EDIT: хорошо, вот одна "реализация".

шаги для построения реализации:

1. возьмите постоянный массив размером 100 000 * (1000 выберите 100 000) бит. Да, я осознаю тот факт, что этот массив будет нуждаться в большем пространстве, чем атомы во Вселенной на несколько величин.
2. разделить этот большой массив на куски по 100 000 каждый.
3. в каждом чанке хранить битовый массив для одного определенная комбинация последних пяти цифр.

Это не программа, а своего рода метапрограмма, которая построит гигантский LUT, который теперь можно использовать в программе. Постоянный материал программы обычно не учитывается при расчете эффективности пространства, поэтому мы не заботимся об этом массиве, когда делаем наши окончательные расчеты.

вот как использовать этот LUT:

1. когда кто-то дает вам 1000 номеров, вы храните первые пять цифр отдельно.
2. узнайте, какой из фрагментов вашего массива соответствует этому набору.
3. храните номер набора в одном 8074-битном номере (назовите это c).

Это означает, что для хранения нам нужно только 8091 бит, которые мы доказали здесь, чтобы быть оптимальным кодированием. Однако поиск правильного куска занимает O (100 000*(100 000 выбирают 1000)), что в соответствии с математическими правилами равно O(1), но на практике всегда будет занимать больше времени, чем время вселенная.

Поиск прост, хотя:

1. полоса из первых пяти цифр (оставшееся число будет называться n').
2. проверить, если они совпадают
3. вычислить i=c * 100000+n'
4. проверьте, установлен ли бит в i в LUT на один

печать всех чисел также проста (и принимает O (100000)=O(1) на самом деле, потому что вам всегда нужно проверять все биты текущего куска, поэтому я просчитался выше.)

Я бы не назвал это "реализацией", из-за вопиющего игнорирования ограничений (размер Вселенной и время, в течение которого эта вселенная жила или будет существовать эта земля). Однако в теории это оптимальное решение. Для небольших проблем это действительно можно сделать, а иногда и будет сделано. Например сетей сортировка являются примером для этого способа кодирования и могут быть использованы в качестве последнего шага в алгоритмах рекурсивной сортировки, чтобы получить большой ускорение.

Это эквивалентно хранению одной тысячи неотрицательных целых чисел, каждое из которых меньше 100 000. Для этого мы можем использовать что-то вроде арифметического кодирования.

в конечном счете, номера будут храниться в отсортированном списке. Я отмечаю, что ожидаемая разница между соседними числами в списке составляет 100 000 / 1000 = 100, которые могут быть представлены в 7 битах. Также будет много случаев, когда необходимо более 7 бит. Простой способ представить эти менее распространенные случаи-принять схема utf-8, где один байт представляет собой 7-разрядное целое число, если не установлен первый бит, и в этом случае следующий байт считывается для получения 14-разрядного целого числа, если его первый бит установлен, и в этом случае следующий байт считывается как 21-битное целое число.

Так, по крайней мере, половина различия между последовательными целыми числами может быть представлен один байт, а почти все остальные требуют два байта. Несколько чисел, разделенных большими различиями, чем 16,384, потребуется три байта, но не может быть более чем 61 из них. Средняя память тогда будет около 12 бит на число, или немного меньше, или не более 1500 байт.

недостатком этого подхода является то, что проверка существования числа теперь O(n). Однако требование о временной сложности не было указано.

после написания я заметил, что Руслик уже предложил метод разницы выше, единственное отличие-схема кодирования. Мой, скорее всего, проще но менее эффективно.

просто быстро спросить любую причину, по которой мы не хотели бы менять числа в базу 36. Это может не сэкономить столько места, но это наверняка сэкономит время на поиске, так как u будет смотреть на намного меньше, чем 10digts. Или я бы разделил их на файлы в зависимости от каждой группы. поэтому я бы назвал файл (111) -222.txt, а затем я буду хранить только числа, которые вписываются в эту группу, а затем иметь их seearchable в числовом порядке таким образом, я всегда могу чакнуть, чтобы увидеть, выходит ли файл. прежде чем я начну более масштабный поиск. или, чтобы быть правильным, я бы побежал к двоичным поискам один для файла, чтобы увидеть, если он выходит. и еще бинарных поиск по содержанию файла

Почему бы не сделать это просто? Использовать массив структур.

таким образом, мы можем сохранить первые 5 цифр в качестве константы, так что забудьте их на данный момент.

65535-это самое большее, что может быть сохранено в 16-битном номере, а максимальное число, которое мы можем иметь, составляет 99999, что соответствует 17-битному номеру с максимальным значением 131071.

использование 32-разрядных типов данных является wast, потому что нам нужен только 1 бит из этих дополнительных 16-бит...поэтому мы можем определить структуру, которая имеет логическое значение (или символ) и 16-битное число..

Предполагая, Что C / C++

typedef struct _number {

    uint16_t number;
    bool overflow;
}Number;

эта структура занимает всего 3 байта, и нам нужен массив 1000, так что 3000 байт всего. Мы сократили общую площадь на 25%!

что касается хранения чисел, мы можем сделать простую побитовую математику

overflow = (number5digits & 0x10000) >> 4;
number = number5digits & 0x1111;

и наоборот

//Something like this should work
number5digits = number | (overflow << 4);

чтобы напечатать их все, мы можем использовать простой цикл по массиву. Получение определенного числа происходит в постоянное время, конечно, так как это матрица.

for(int i=0;i<1000;i++) cout << const5digits << number5digits << endl;

для поиска числа, мы хотели бы отсортированного массива. Поэтому, когда числа сохраняются, отсортируйте массив(я бы выбрал сортировку слиянием лично, O (nlogn)). Теперь, чтобы искать, я бы пошел на подход сортировки слиянием. Разделите массив и посмотрите, какой из них наш номер попадает между ними. Затем вызовите функцию только для этого массива. Рекурсивно делайте это до тех пор, пока не получите совпадение и не верните индекс, иначе он не существует и не выведет код ошибки. Этот поиск был бы вполне быстрый и худший случай все же лучше, чем O(nlogn), поскольку он будет абсолютно выполняться за меньшее время, чем сортировка слияния (только рекурсивная 1 сторона разделения каждый раз, а не обе стороны:)), которая является O(nlogn).

мое решение: лучшем случае 7.025 биты/количество, а в худшем случае 14.193 биты/количество, приблизительно 8.551 биты/количество. Потоковое кодирование, без произвольного доступа.

еще до прочтения ответа руслика я сразу подумал о кодировании разницы между каждым числом, так как она будет небольшой и должна быть относительно последовательной, но решение также должно быть в состоянии приспособить наихудший сценарий. У нас есть пространство из 100000 номеров, которые содержат только 1000 номеров. В идеальную форму телефонная книга, каждый номер будет больше, чем предыдущий номер на 100:

55555-12345
55555-12445
55555-12545

если бы это было так, то для кодирования различий между числами потребовалось бы нулевое хранилище, поскольку это известная константа. К сожалению, цифры могут отличаться от идеальных шагов 100. Я бы закодировал разницу от идеального приращения 100, так что если два соседних числа отличаются на 103, я бы кодировал число 3, и если два соседних числа отличаются на 92, я бы кодировал -8. Я называю дельту от идеального приращения 100 "дисперсия".

дисперсия может варьироваться от -99 (т. е. два последовательных номера) до 99000 (вся телефонная книга состоит из номеров 00000...00999 и дополнительного наиболее удаленного номера 99999), что составляет диапазон 99100 возможных значений.

Я хотел бы выделить минимальное хранилище для кодирования наиболее общие различия и расширить хранилище, если я столкнусь с большими различиями (например,ProtoBuf ' s varint). Я буду использовать куски из семи битов, шесть для хранения и дополнительный бит флага в конце, чтобы указать, что эта дисперсия хранится с дополнительным куском после текущего, максимум до трех кусков (что обеспечит максимум 3 * 6 = 18 бит хранения, которые являются 262144 возможным значением, больше, чем количество возможных дисперсий (99100). Каждый дополнительный фрагмент, который следует за поднятым флагом, имеет биты более высокого значения, поэтому первый фрагмент всегда имеет биты 0-5, необязательные вторые фрагменты имеют биты 6-11, а необязательный третий фрагмент имеет биты 12-17.

один кусок обеспечивает шесть бит памяти, которая может вместить 64 значения. Я хотел бы сопоставить 64 наименьших отклонения, чтобы вписаться в этот один кусок (т. е. отклонения от -32 до +31), поэтому я буду использовать кодировку зигзага ProtoBuf, вплоть до отклонений от -99 до + 98 (так как нет необходимости для отрицательной дисперсии за пределами -99), в этот момент я переключусь на обычную кодировку, смещенную на 98:  

 Variance  |  Encoded Value
-----------+----------------
    0      |       0
   -1      |       1
    1      |       2
   -2      |       3
    2      |       4
   -3      |       5
    3      |       6
   ...     |      ...
  -31      |      61
   31      |      62
  -32      |      63
-----------|--------------- 6 bits
   32      |      64
  -33      |      65
   33      |      66
   ...     |      ...
  -98      |      195
   98      |      196
  -99      |      197
-----------|--------------- End of ZigZag
   100     |      198
   101     |      199
   ...     |      ...
  3996     |     4094
  3997     |     4095
-----------|--------------- 12 bits
  3998     |     4096
  3999     |     4097
   ...     |      ...
 262045    |    262143
-----------|--------------- 18 bits

некоторые примеры того, как отклонения будут кодироваться в виде битов, включая флаг для указания дополнительного фрагмента:

 Variance  |  Encoded Bits
-----------+----------------
     0     |  000000 0
     5     |  001010 0
    -8     |  001111 0
   -32     |  111111 0
    32     |  000000 1  000001 0
   -99     |  000101 1  000011 0
   177     |  010011 1  000100 0
 14444     |  001110 1  100011 1  000011 0

таким образом, первые три номера образца телефонной книги будут закодированы в виде потока битов следующим образом:

BIN 000101001011001000100110010000011001   000110 1     010110 1 00001 0
PH#           55555-12345                 55555-12448     55555-12491
POS                1                           2               3

Лучший сценарий, телефонная книга несколько равномерно распределена и нет двух телефонных номеров, которые имеют дисперсию больше 32, поэтому он будет использовать 7 бит на номер плюс 32 бита для начального номера в общей сложности 32 + 7*999 = 7025 бит.
смешанный сценарий, где дисперсия 800 телефонных номеров укладывается в один кусок (800 * 7 = 5600), 180 номеров укладываются в два куска каждый (180 * 2 * 7 = 2520) и 19 чисел помещаются в три куска каждый (20 * 3 * 7 = 399), плюс начальные 32 бита, итого 8551 бит.
худший сценарий, 25 чисел помещаются в три куска (25 * 3 * 7 = 525 бит), а остальные 974 числа укладываются в два куска (974 * 2 * 7 = 13636 бит), плюс 32 бита для первого числа в общей сложности 14193 бит.

   Amount of encoded numbers   |
 1-chunk | 2-chunks | 3-chunks | Total bits
---------+----------+----------+------------
   999   |    0     |    0     |   7025
   800   |   180    |    19    |   8551
    0    |   974    |    25    |  14193

Я вижу четыре дополнительных оптимизации, которые могут быть выполнены для дальнейшего сокращения требуемого пространства:

1. третий кусок не нуждается в полных семи битах, это может быть просто пять бит и без флага бит.
2. там может быть начальный проход чисел для расчета лучших размеров для каждого куска. Возможно, для определенной телефонной книги было бы оптимально, чтобы первый кусок имел 5+1 бит, второй 7+1 и третий 5+1. Это еще больше уменьшило бы размер до минимума 6*999 + 32 = 6026 бит, плюс два набора из трех битов для хранения размеров кусков 1 и 2 (размер куска 3-это остаток необходимых 16 бит) в общей сложности 6032 биты!
3. тот же самый начальный проход может вычислить лучшее ожидаемое приращение, чем по умолчанию 100. Может быть, есть телефонная книга, которая начинается с 55555-50000, и поэтому она имеет половину диапазона чисел, поэтому ожидаемое приращение должно быть 50. Или, может быть, есть нелинейное распределение (возможно, стандартное отклонение), и можно использовать какое-то другое оптимальное ожидаемое приращение. Это уменьшило бы типичную дисперсию и могло бы позволить использовать еще меньший первый кусок.
4. далее анализ может быть сделан в первом проходе, чтобы позволить телефонной книге быть разделенной, с каждым разделом, имеющим свое собственное ожидаемое увеличение и оптимизацию размера куска. Это позволило бы уменьшить размер первого фрагмента для некоторых очень однородных частей телефонной книги (уменьшая количество потребляемых битов) и большие размеры фрагментов для неоднородных частей (уменьшая количество битов, потраченных впустую на флаги продолжения).

реальный вопрос заключается в хранении пятизначных телефонных номеров.

хитрость в том, что вам понадобится 17 бит для хранения диапазона чисел от 0..99,999. Но хранение 17 бит на обычных 8-байтовых границах слов-это хлопот. Вот почему они спрашивают, Можете ли вы сделать менее 4k, не используя 32-разрядные целые числа.

вопрос: возможны ли все комбинации чисел?

из-за особенностей телефонной системы, там может быть меньше чем 65k возможных комбинаций. Я буду считать, что да потому что речь идет о последних пяти позициях в телефонном номере, в отличие от кода города или префиксов обмена.

вопрос: будет ли этот список статическим или ему нужно будет поддерживать обновления?

Если это статический, затем, когда придет время заполнить базу данных, подсчитайте количество цифр = 50 000. Выделить два массивы на uint16 соответствующей длины: один для целых чисел ниже 50 000 и один для более высокого набора. При хранении целых чисел в более высоком массиве вычитайте 50 000 и при чтении целых чисел из этого массива добавьте 50 000. Теперь вы сохранили свои 1000 целых чисел в 2000 8-байтовых словах.

построение телефонной книги потребует двух входных обходов, но поиск должен происходить в половине случаев, в среднем, чем с одним массивом. Если время поиска были очень важны вы можно было бы использовать больше массивов для меньших диапазонов, но я думаю, что при таких размерах ваша производительность будет вытягивать массивы из памяти, и 2k, вероятно, будет прятаться в кэше процессора, если не регистрировать пространство на все, что вы будете использовать в эти дни.

Если это динамический, выделить один массив из 1000 или около того uint16 и добавить числа в отсортированном порядке. Установите первый байт в 50,001, а второй байт в соответствующее нулевое значение, например NULL или 65,000. Когда вы храните номера, храните их в отсортированном порядке. Если число ниже 50,001, то сохраните его до маркер 50,001. Если число равно 50 001 или больше, сохраните его после маркер 50,001, но вычесть 50,000 из сохраненного значения.

Ваш массив будет выглядеть примерно так:

00001 = 00001
12345 = 12345
50001 = reserved
00001 = 50001
12345 = 62345
65000 = end-of-list

Итак, когда вы ищете номер в телефонной книге, вы пройдете массив, и если вы нажмете значение 50,001, вы начнете добавлять 50,000 в свой массив ценности.

это делает вставки очень дорогими, но поиск легко, и вы не собираетесь тратить гораздо больше, чем 2k на хранение.