Как хранить целые числа в диапазоне 0-9 только в 4 битах и ​​использовать их так же, как Key in HashMap? - PullRequest
Новая
       22

Как хранить целые числа в диапазоне 0-9 только в 4 битах и ​​использовать их так же, как Key in HashMap?

0 голосов
/ 26 июня 2019

Меня попросили найти решение, в котором у вас есть файл, в котором каждая строка представляет собой 10-значный номер телефона, и мы должны указать, присутствует ли в файле данный 10-значный номер телефона.

Я придумал структуру данных Trie, в которой каждый дочерний элемент - не что иное, как Карта целых чисел как Ключ и Три как Значение. 

class Trie{

   boolean isEnd;
   Map<Integer, Trie> map = new HashMap<>();
}

Я также могу использовать int [] arr для хранения детей.

Поскольку у нас есть только числа в диапазоне от 0 до 9, мы можем хранить эти числа только в 4 битах. Зачем принимать int или Integer в качестве типа данных. Как уменьшить память здесь?

Как мы можем хранить эти числа в Map или массиве, но не принимая int, поскольку в итоге мы тратим много памяти.

Кроме того, есть ли лучшее решение, чем Три?

1 Ответ

1 голос
/ 26 июня 2019

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

Более того, давайте подумаем об использовании пространства в дереве.Даже если у каждого телефонного номера был длинный общий префикс, каждому узлу в дереве требуется место для хранения его дочерних указателей.Если вы сохраняете хотя бы один (64-разрядный) указатель на узел, вы используете тот же объем пространства, который вы использовали бы для хранения 10-значного телефонного номера (который удобно помещается в 64-разрядное целое число).Если у телефонных номеров нет длинных общих префиксов, вы потенциально можете хранить десять указателей на номер, что приводит к огромному увеличению пространства независимо от того, насколько велики ключи хеш-таблицы.

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

...