Является ли создание «карты привязки» хорошей идеей для случайного поиска O (1) на карте? - PullRequest
Новая
       18

Является ли создание «карты привязки» хорошей идеей для случайного поиска O (1) на карте?

2 голосов
/ 17 марта 2011

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

Подход к этому грубой силыпроблемы могут быть примерно такими. 

// Bruteforce approach
x = new integer between 0 and the number of entries in the map
iterate x times
return the element

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

Зачем мне повторять более тысячиэлементов, чтобы найти что-то, что я не особо ищу?

Единственный способ избежать грубой силы и иметь O (1) случайный поиск - это иметь целое число в качестве ключа карты, потому чтодве точки:

  • Единственный случайный объект, который мы можем получить, является целым числом
  • Единственный способ поиска O (1)на карте, это знать ключ.

Но так как вы можете иметь только один ключ, если вы поставите целое число в качестве ключа, то вы не можете иметь O (1)поиск определения данного слова, который был точкойиспользуя Map во-первых.

Я нашел способ сделать это - объявить вторую карту, «привязывающую» карту, которая просто связывает каждый ключ словаря с целым числом.

Таким образом, в итоге вы получите две карты:

  • Словарь, в котором у вас есть слова в качестве ключей и определения в качестве значений
  • у вас есть целые числа в качестве ключей и слова в качестве значений

Итак, если вы хотите получить определение данного слова, вы делаете: 

dictionary.get("hello");

И если вы хотите получитьслучайное слово, которое вы просто делаете: 

dictionary.get(bindingMap.get(myRandomNumber));

Плюсы:

  • Это позволяет O (1) поиск И случайный доступ

Минусы:

  • Сложность пространства - это O (2n) вместо O (n) ... Что все еще равно O (n) ...

Что вы думаете об этом методе?Видите ли вы лучший способ сделать это?

1 Ответ

0 голосов
/ 17 марта 2011

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

Если вы используетеСтроки в качестве ключей, вы также можете рассмотреть модификацию конструкции, чтобы у вас была «строка статистики по заказам», в которой вы сохраняли бы строки в дереве, дополненном количеством элементов в каждой ветви.Это обеспечило бы очень быстрый поиск элементов при одновременной поддержке быстрых случайных запросов.

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

Надеюсь, это поможет!

...