Отсортированная хеш-таблица (карта, словарь) дизайн структуры данных
Вот описание структуры данных:
Это работает как обычная карта с get, put, и remove методы, но имеет a sort метод, который можно назвать к видам картой. Однако карта помнит свою отсортированную структуру, таким образом, последующие вызовы к виду могут быть намного более быстрыми (если структура не изменяется слишком много между вызовами к sort).
Например:
- Я звоню
putметод 1,000,000 раз. - Я звоню
sortметод. - Я звоню
putметод еще 100 раз. - Я звоню
sortметод.
Во второй раз я звоню sort метод должен быть намного более быстрой операцией, поскольку структура карты не изменилась очень. Обратите внимание, что карта не должна поддерживать отсортированный порядок между вызовами к sort.
Я понимаю, что это не могло бы быть возможно, но я надеюсь на O (1) get, put, и remove операции. Что-то как TreeMap обеспечивает гарантируемый O (журнал (n)) время, стоившее за эти операции, но всегда поддерживает отсортированный порядок (нет sort метод).
Таким образом, каков дизайн этой структуры данных?
Редактирование 1 - возврат главных-K записей
Alhough я любил бы слышать ответ на общий случай выше, мой вариант использования, стал более конкретным: Мне не нужно все это отсортированное; просто вершина K элементы.
Структура данных для того, чтобы эффективно возвратить главные-K записи хеш-таблицы (карта, словарь)
Спасибо!
6 ответов
Из MSDN вы обнаружите, что DateTime.Now имеет приблизительное разрешение 10 миллисекунд во всех операционных системах NT.
Фактическая точность зависит от аппаратных средств. Более высокую точность можно получить с помощью QuurePerformureCounter .
Ищите заметки лекций Рэдфорда Нила Маркова Chain Monte Carlo.
-121--3505025- Зачем именно нужна функция сортировки ()?
Что вам, возможно, нужно, так это Красное-Черное Дерево.
http://en.wikipedia.org/wiki/Red-black_tree
Эти деревья автоматически сортируют введенные данные по указанному компаратору. Они сложны, но имеют превосходные O (n) характеристики. Объединение записей дерева в качестве ключа с хэшем отображение в виде словаря и получение структуры данных.
В Java он реализован как TreeMap как экземпляр SortedMap.
Мне неизвестна классификация структуры данных с таким поведением, по крайней мере, не в Java Collections (или в классе нелинейных структур данных). Возможно, вы сможете реализовать ее, и отныне она будет известна как RudigerMap.
] Не знаю, есть ли имя, но вы можете хранить текущий индекс каждого элемента в хэше.[
] [] То есть, у вас есть []HashMap<Объект, пара( Целое, Объект) >[].
и []List] objects[
] When you []put[], добавьте в хвост или заголовок списка и вставьте в хэшмэп со своими данными и индексом вставки. Это []O(1)[].[
]Когда вы []получите[], извлеките из хеш-карты и проигнорируйте индекс. Это []O(1)[].[
] Когда Вы [] извлекаете [], извлекаете из карты. Возьмите индекс и удалите его из списка. Это []O(1)[][
] Когда вы [] сортируете [], просто сортируйте список. Или обновите индексы на карте во время сортировки, или обновите после завершения сортировки. Это не влияет на сортировку []O(nlgn)[], так как это линейный шаг. []O(nlgn + n) == O(nlgn)[][
] Для "O(1) get, put, and remove operations" (Операции получения, установки и удаления), по сути, нужен поиск O(1), что подразумевает хэш-функцию (как вы знаете), но требования хорошей хэш-функции часто нарушают требование легкой сортировки. (Если бы у вас была хэш-таблица, в которой соседние значения отображаются в одно и то же ведро, она выросла бы до O(N) на множестве общих данных, что еще хуже, если вы, как правило, хотите, чтобы хэш-функция отсутствовала)[
] []Я могу придумать, как достать вам 90% пути туда. Установите хэш-функцию рядом с параллельным индексом, который будет отсортирован. Индекс имеет чистую (упорядоченную) и грязную (неупорядоченную) части. Индекс будет сопоставлять ключи к значениям (или ссылкам на значения, хранящиеся в хэш-таблице - в зависимости от того, что подходит вам с точки зрения производительности или использования памяти). При добавлении в хэш-таблицу новая запись выталкивается на обратную сторону "грязного" списка. При удалении из хэшбэбля запись обнуляется/удаляется из чистой и грязной части индекса. Вы можете отсортировать индекс, который сортирует только грязные записи, а затем объединить их в уже отсортированную "чистую" часть индекса. И, очевидно, вы можете выполнить итерацию по индексу.[
] []Насколько я вижу, это дает вам O(1) везде, кроме операции удаления, и все еще довольно просто реализуется со стандартными контейнерами (по крайней мере, как это предусмотрено C++, Java или Python). Это также дает вам условие "вторая сортировка дешевле", так как нужно только отсортировать грязные записи индекса, а затем позволить вам выполнить слияние O(N). Стоимость всего этого, очевидно, является дополнительной памятью для индекса и дополнительной индирекцией при его использовании[
].Указанный словарь
Недавние версии Python (2.7, 3.1) имеют «упорядоченные словари», которые звучат, как то, что вы описываете.
Официальный Python «Указанный словарь» вдохновлен предыдущими 3 -д-сторонние реализации, как описано в PEP 372 .
Список литературы:
То, на что вы смотрите, является Hashtable с указателями в записях к следующей записи в отсортированном порядке. Это очень похоже на LinkedHashmap в Java, за исключением того, что ссылки отслеживают порядок сортировки, а не заказа в размере. На самом деле вы можете полностью реализовать это, обернув ссылку на ссылку и выполняв реализацию сортировки записей из LinkedHashmap в TREEWAP, а затем обратно в ссылку на ссылку.
Вот реализация, которая сортирует записи в списке массива, а не передаю на карту дерева. Я думаю, что алгоритм сортировки, используемый Collection.Sort, сделает хорошую работу по слиянию новых записей в уже отсортированную часть.
public class SortaSortedMap<K extends Comparable<K>,V> implements Map<K,V> {
private LinkedHashMap<K,V> innerMap;
public SortaSortedMap() {
this.innerMap = new LinkedHashMap<K,V>();
}
public SortaSortedMap(Map<K,V> map) {
this.innerMap = new LinkedHashMap<K,V>(map);
}
public Collection<V> values() {
return innerMap.values();
}
public int size() {
return innerMap.size();
}
public V remove(Object key) {
return innerMap.remove(key);
}
public V put(K key, V value) {
return innerMap.put(key, value);
}
public Set<K> keySet() {
return innerMap.keySet();
}
public boolean isEmpty() {
return innerMap.isEmpty();
}
public Set<Entry<K, V>> entrySet() {
return innerMap.entrySet();
}
public boolean containsKey(Object key) {
return innerMap.containsKey(key);
}
public V get(Object key) {
return innerMap.get(key);
}
public boolean containsValue(Object value) {
return innerMap.containsValue(value);
}
public void clear() {
innerMap.clear();
}
public void putAll(Map<? extends K, ? extends V> m) {
innerMap.putAll(m);
}
public void sort() {
List<Map.Entry<K,V>> entries = new ArrayList<Map.Entry<K,V>>(innerMap.entrySet());
Collections.sort(entries, new KeyComparator());
LinkedHashMap<K,V> newMap = new LinkedHashMap<K,V>();
for (Map.Entry<K,V> e: entries) {
newMap.put(e.getKey(), e.getValue());
}
innerMap = newMap;
}
private class KeyComparator implements Comparator<Map.Entry<K,V>> {
public int compare(Entry<K, V> o1, Entry<K, V> o2) {
return o1.getKey().compareTo(o2.getKey());
}
}
}