Каков наиболее эффективный способ, с точки зрения памяти, хранить 1 миллион телефонных номеров?
По-видимому, это вопрос интервью в Google, пожалуйста, дайте свои идеи.
Сохранение 1 миллиона телефонных номеров
Ответ 1
Если память является нашим самым большим соображением, нам не нужно хранить номер вообще, просто дельта между я и я + 1.
Теперь, если числа варьируются от 200 0000 до 999 9999, тогда есть 7999999 возможных телефонных номеров. Поскольку у нас есть 1-миллионное число, и если мы предположим, что они равномерно распределены, у нас есть ожидаемое расстояние E = n_i + 1 - n_i ~ 8 (3 бит) между последовательными числами n_i и n_i + 1. Таким образом, для 32-битного int мы могли бы хранить до 10 последовательных смещений (~ 400kb оптимальный общий объем памяти), однако его вероятность того, что у нас будут некоторые случаи, когда нам нужно смещение больше 8 (возможно, у нас есть 400 или 1500??). В этом случае мы можем просто зарезервировать первые 2 бита int как заголовок, который сообщает нам, какой размер кадра мы используем для чтения бит, который он хранит. Например, мы можем использовать: 00 = 3x10, 01 = 5x6, 10 = 7x4, 11 = 1 * 30.
Ответ 2
Запишите их в ASCII, разделенные пробелами.
Замените полученную строку, используя ваш любимый алгоритм сжатия. Если порядок не важен, сначала их сортировка может помочь сжатию, дает вам больше повторений.
О, вам нужен эффективный случайный доступ? Тогда вы должны были сказать.
Ответ 3
Возможное решение:
- сортировать числа
- кодирует дельта от одного числа до следующего.
Частотное распределение дельта будет сильно искажено.
Я сделал эксперимент, используя простой подход BER-подобной упаковки для дельт, используя кодировку 7 + 3 + 3 +... bit; функция кодирования была
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)
(оба параметра 7 и 3 были определены экспериментально)
При таком подходе я получил миллион 10-значных чисел с первыми 5 цифрами, выбранными из тысячи случайных префиксов со средним значением 8,83 бит на номер (упакованный размер 1104188).
Ответ 4
Сначала я замечаю, что они никогда не начинаются с 0, так как в начале используется как escape-символ. Поэтому я могу просто рассматривать номера телефонов как целые числа. Если бы это было не так, я бы просто добавил "1" к числу, а затем преобразовал его в целое. Это существенно не повлияет на эффективность кодирования (вероятно, постоянные накладные расходы на несколько байтов). Если есть другие символы за пределами 10 цифр внутри телефонных номеров, просто кодируйте базой выше 10. Это, однако, повредит эффективности.
Я заказываю их по размеру по возрастанию. Затем вычислите различия. И затем сериализуйте различия, используя protobuf как заполненные повторяющиеся поля.
Этот метод похож на метод RexKerr, за исключением того, что я использую ленивое решение protobuf над кодировщиком huffman. Вероятно, немного больше, поскольку кодирование целых чисел protobuf является общим назначением и не учитывает распределение вероятностей телефонных номеров. Но это намного проще для кода, поскольку мне просто нужно использовать существующий сериализатор protobuf. Это будет проблематично, если вы превысите размер UInt64, т.е. Имеются номера телефонов длиной более 19 цифр. Формат файла по-прежнему поддерживает его, но большинство реализаций не будет.
Без времени доступа к индексу будет довольно плохо, но он должен быть довольно компактным.
Ответ 5
Тройное дерево поиска, которое является специальной структурой данных trie, будет эффективным с точки зрения памяти и будет по-прежнему включать (как trie) частичное согласование.
Ответ 6
Кодирование Хаффмана на цифровых блоках, вероятно, даст очень хорошие результаты. Если числа были смешанного типа (например, некоторые из США, некоторые из них за рубежом, включая код доступа), вам понадобятся другие биты пары, чтобы указать, какой тип они были (и, следовательно, какие блоки использовать).
Если числа были в небольшом диапазоне - например. семь цифр - самый компактный способ их хранения, вероятно, заключался бы в том, чтобы рассматривать их как целые числа, сортировать их и хранить (кодированные Хаффманом) различия в значениях. Например. с 10 ^ 6 номерами в 7 цифр (10 ^ 7 возможностей), вы ожидаете, что потребуется около log2 (10) ~ = 3,3 бит на номер.
Ответ 7
Если вы посмотрите на представления полей данных Североамериканского плана нумерации, вы сделаете вывод, что номера телефонов США 1+ NPA + NXX + xxxx может храниться менее чем за 22 бит в поле номера телефона в каждом регистровом коде. Добавьте коды областей, и данные, представляющие любой телефонный номер США (плюс канадский), могут с комфортом поместиться в 32 бита. Это как представление битового поля, а не как int.
Ваше мышление об этом не должно быть, однако, Центром США. Разумеется, вопрос заключается не только в том, что упражнение сжимает 1 миллион телефонных номеров в наименьшее количество бит.
Номера телефонов в США могут быть короткими, как 3 цифры (внутренние абонентские номера PBX), до 22 цифр (1 + NPA + NXX + xxxx + 11digit внутренняя абонентская группа PBX). Если номер телефона был ограничен обозначенным номером формата ITU, у вас есть до 15 цифр плюс 1 бит для '+'.
Затем вам следует, вероятно, определить представление поля битового поля любого телефонного номера между 3 цифрами и 22 цифрами (или 15 цифр для ITU) с каждым полем бит, имеющим поле заголовка X бит, чтобы указать формат поля.
Затем поместите эти битовые поля в сжатый массив . Потенциально этот бит-массив может быть проиндексирован с помощью trie или каким-либо другим способом.
Эффективность этого основана на формате 1 миллиона телефонных номеров, как быстро вы хотите получить к ним доступ и насколько гибкой структура данных для большего количества телефонных номеров в будущем в разных форматах. Это не просто подсчет бит для "правильного" ответа ИМХО.
Ответ 8
Предположим, что каждый номер телефона соответствует американскому формату (3-значный код области) - (7-значный номер)
Это 10-значное число.
Однако при работе с телефонными номерами существуют правила взаимодействия. Они разрежены, для одного, то есть используются не все возможные коды областей. В этом случае простое дерево является a-ok. Я имею в виду думать об этом... вам нужно только 269 + 26 для Канады. Это довольно мало, и вы вырезали большую часть пространства PLUS, увеличили время поиска. Не только это, но и может быть дополнено информацией о местоположении.
После этого у вас есть 7-значный номер. Это может быть сохранено в одном 32-битном целом. Сортировка по вставке, и у вас есть довольно быстрый механизм для извлечения, поскольку вы можете выполнять двоичный поиск на оставшейся части номера.
Ответ 9
Я думаю, что неподписанный Int32 или для международных номеров беззнаковый Int64
Использование 32-битных беззнаковых ints, которые будут 4MB
Ответ 10
Это действительно зависит от того, какие операции вы хотите запускать в сохраненной базе данных.
Тривиальный подход использует целые числа без знака, если вам просто нужно их хранить, возможно, некоторое сжатие в исходном текстовом представлении с использованием словаря будет меньше.
Ответ 11
На собеседовании вопрос заключается в том, чтобы оценить навыки решения проблем заявителя. Потому что в центре внимания вопроса эффективность памяти. На мой взгляд, правильный ответ заключается в том, чтобы спросить интервьюера: "Являются ли номера телефонов международными или они ограничены одной страной?" Если номера ограничены одной страной, задача максимизации эффективности памяти упрощается благодаря тому, что в каждой стране есть простые правила для распределения телефонных номеров по штату и городу.
Ответ 12
Я думаю, мы можем использовать бит-вектор размером 1 млн.
Пример Java:
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);
}
Ответ 13
8 миллионов бит с каждым битом 1 (используется) или 0 (доступно) для одного из 8 миллионов номеров Пример
100 0000
900 0000
= 8 million phone numbers, bit 1 = 1000000 and bit 8 million = 9000000
Ответ 14
/********************************************************************************
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 */