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

Question

Это вопрос об интервью в Google:

В памяти должно храниться около тысячи телефонных номеров, каждый из которых имеет 10 цифр.Вы можете предположить, что первые 5 цифр каждой цифры одинаковы для тысяч номеров.Вы должны выполнить следующие операции: a.Поиск, если данный номер существует.б.Выведите все число

Какой самый эффективный способ сэкономить место для этого?

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

Можно ли использовать суффикс три справки?

В идеале для сохранения 1000 чисел требуется 4 байта на число, поэтому всего для хранения 1000 номеров потребуется 4000 байтов.Количественно я хочу уменьшить объем памяти до <4000 байт, это то, что объяснил мне мой интервьюер. </p>

Answer 1

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

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

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

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

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

Если это статический , то когда придет время заполнять базу данных, подсчитайте количество цифр <50 000 и количество цифр> = 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, вы начнете добавлять 50000 к значениям массива.

Это делает вставки очень дорогими, но поиск очень прост, и вы не собираетесь тратить намного больше 2 КБ на хранилище.

Answer 2

Мое решение: лучший случай 7,025 бит / число, наихудший случай 14,193 бит / число, грубое среднее 8,551 бит / число. Потоковое кодирование без произвольного доступа.

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

55555-12 3 45
* 1008 55555-12 * 4 45
55555-12 5 45

Если бы это было так, для кодирования различий между числами потребовалось бы нулевое хранение, поскольку это известная константа. К сожалению, числа могут отличаться от идеальных шагов 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 ZigZag, вплоть до отклонений от -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

1031 *

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

 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. На первом проходе можно провести дополнительный анализ, чтобы разрешить разбиение телефонной книги, причем каждый раздел имеет свой ожидаемый прирост.и оптимизация размера куска.Это позволило бы уменьшить размер первого чанка для некоторых весьма однородных частей телефонной книги (уменьшить количество потребляемых битов) и увеличить размеры чанков для неоднородных частей (уменьшить количество битов, теряемых на флагах продолжения).

Answer 3

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

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

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

Использование 32-битных типов данных - пустая трата времени, потому что нам нужен только 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).