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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

Вот улучшение ответа Экс .Рассмотрите возможность использования трех «слоев» для структуры данных: первый является константой для первых пяти цифр (17 бит);поэтому с этого момента на каждом номере телефона остаются только пять оставшихся цифр.Мы рассматриваем эти оставшиеся пять цифр как 17-разрядные двоичные целые числа и сохраняем k этих битов одним методом, а 17 - k = m другим методом,определение k в конце, чтобы минимизировать требуемое пространство.

Сначала мы сортируем телефонные номера (все сокращены до 5 десятичных цифр).Затем мы подсчитываем, сколько существует телефонных номеров, для которых двоичное число, состоящее из первых m битов, равно 0, для скольких телефонных номеров первые m биты не больше 0...01, для скольких телефонных номеров первые m битов не более 0 ... 10 и т. Д., Вплоть до количества телефонных номеров, для которых первые m битов1 ... 11 - этот последний счет равен 1000 (десятичному).Есть 2 ^ m таких подсчетов, и каждый отсчет не более 1000. Если мы опускаем последний (потому что мы все равно знаем, что это 1000), мы можем сохранить все эти числа в непрерывном блоке (2 ^ м - 1) * 10 бит.(10 битов достаточно для хранения номера менее 1024.)

Последние k битов всех (сокращенных) телефонных номеров хранятся в памяти непрерывно;так что если k , скажем, 7, то первые 7 битов этого блока памяти (биты с 0 по 6) соответствуют последним 7 битам первого (сокращенного) номера телефона, биты с 7 по 13соответствуют последним 7 битам второго (уменьшенного) номера телефона и так далее.Для этого требуется 1000 * k битов в общей сложности 17 + (2 ^ (17 - k ) - 1) * 10 + 1000 * k , что достигаетего минимум 11287 для k = 10. Таким образом, мы можем хранить все телефонные номера в ceil (11287/8) = 1411 байт.

Дополнительное пространство можно сэкономить, заметив, что ни один из наших номеровможет начинаться, например, с 1111111 (двоичное), потому что наименьшее число, которое начинается с этого, - 130048, и у нас есть только пять десятичных цифр.Это позволяет нам убрать несколько записей из первого блока памяти: вместо 2 ^ m - 1 отсчет нам нужен только ceil (99999/2 ^ k ).Это означает, что формула становится

17 + ceil (99999/2 ^ k ) * 10 + 1000 * k

, что удивительным образом достигает своегоминимум 10997 для k = 9 и k = 10, или ceil (10997/8) = 1375 байт.

Если мы хотим знать, является ли определенный телефончисло находится в нашем наборе, мы сначала проверяем, соответствуют ли первые пять двоичных цифр пяти сохраненных нами цифр.Затем мы разбиваем оставшиеся пять цифр на его верхние m = 7 бит (скажем, m -битное число M ) и его нижние k = 10 бит (число K ).Теперь мы находим номер a [M-1] сокращенных телефонных номеров, для которых первые m цифры не более M - 1, и номер a [M] сокращенных телефонных номеров, для которых первые m цифр не более M , оба из первого блока битов.Теперь мы проверяем между a [M-1] -й и a [M] -ой последовательностью k бит во втором блоке памяти, чтобы увидеть,найти К ;в худшем случае существует 1000 таких последовательностей, поэтому, если мы используем двоичный поиск, мы можем завершить операции O (log 1000).

Далее следует псевдокод для печати всех 1000 чисел, где я получаю доступ к K '* k -битная запись первого блока памяти как a [K] и M ' th m -битовая запись второго блока памяти как b [M] (обе эти операции потребуют нескольких битовых операций, которые утомительны для записи).Первые пять цифр находятся в числе c .

i := 0;
for K from 0 to ceil(99999 / 2^k) do
  while i < a[K] do
    print(c * 10^5 + K * 2^k + b[i]);
    i := i + 1;
  end do;
end do;

Возможно, что-то не так с граничным регистром для K = ceil (99999/2 ^ k ), но это достаточно легко исправить.

Наконец, с точки зрения энтропии, невозможно сохранить подмножество из 10 ^ 3 натуральных чисел, все из которых меньше, чем 10 ^ 5, меньше чем ceil (log [2] (binomial (10 ^ 5, 10 ^) 3))) = 8073. Включая 17, которые нам нужны для первых 5 цифр, все еще остается разрыв в 10997 - 8090 = 2907 бит. Это интересная задача, чтобы увидеть, есть ли лучшие решения, где вы все еще можете получить доступ к номерам относительно эффективно!

Answer 3

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

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

Answer 4

Я бы, вероятно, подумал об использовании какой-либо сжатой версии Trie (возможно, DAWG , как предложено @Misha).

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

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

Answer 5

Я слышал об этой проблеме раньше (но без предположения "первые 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,782) бит = 1003 + переменная (0 ..98) байт.

Answer 6

Это хорошо известная проблема из Bentley's Programming Pearls.

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

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

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

HTH Крис.

Answer 7

Исправлено хранение 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 чисел, для смещений будет 7000 бит .

Таким образом, наше окончательное число, предполагающее 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, что дает 8580 битов = 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

Answer 8

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

Answer 9

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

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

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

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

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

Answer 10

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

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

Lookup будет 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)на самом деле, потому что вы всегда должны проверять все биты текущего чанка, поэтому я просчитал это выше).

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