Автоматически сортируется по карте значений в Java
Мне нужно иметь автоматически отсортированную карту по значениям в Java, чтобы она продолжала сортироваться в любое время, пока я добавляю новые пары ключ-значение, или обновляю значение существующей пары ключ-значение, или даже удаляю некоторые запись.
Пожалуйста, имейте в виду, что эта карта будет очень большой (сотни тысяч или даже десятки миллионов записей по размеру).
Так что в основном я ищу следующую функциональность:
Предполагается, что у нас есть класс SortedByValuesMap, который реализует вышеупомянутую функциональность, и у нас есть следующий код:
SortedByValuesMap<String,Long> sorted_map = new SortedByValuesMap<String, Long>();
sorted_map.put("apples", 4);
sorted_map.put("oranges", 2);
sorted_map.put("bananas", 1);
sorted_map.put("lemons", 3);
sorted_map.put("bananas", 6);
for (String key : sorted_map.keySet()) {
System.out.println(key + ":" + sorted_map.get(key));
}
вывод должен быть:
bananas:6
apples:4
lemons:3
oranges:2
В частности, для меня действительно важно иметь возможность получить запись с наименьшим значением в любое время - с помощью такой команды:
smallestItem = sorted_map.lastEntry();
который должен дать мне запись "апельсины"
РЕДАКТИРОВАТЬ: Я новичок в Java, поэтому, пожалуйста, уточните ваши ответы - спасибо
РЕДАКТИРОВАТЬ 2: Это может помочь: я использую это для подсчета слов (для тех, кто знаком: в частности, n-грамм) в огромных текстовых файлах. Поэтому мне нужно построить карту, где ключи - это слова, а значения - частоты этих слов. Тем не менее, из-за ограничений (например, ОЗУ), я хочу сохранить только X наиболее часто встречающихся слов - но вы не можете заранее знать, какие слова будут самыми частыми, конечно. Таким образом, я думал, что это может работать (в качестве приблизительного значения), чтобы начать подсчет слов, и когда карта достигает верхнего предела (например, 1 миллион записей), наименее частая запись будет удалена, чтобы сохранить размер карты 1 мил всегда.
8 ответов
Сохраняйте 2 структуры данных:
- Словарь слов -> кол. Просто используйте обычный
HashMap<String, Long>, "Массив" для отслеживания порядка, такой, что
list[count]держитSet<String>слов с этим количеством.Я пишу это так, как будто это массив для удобства записи. На самом деле, вы, вероятно, не знаете верхнюю границу количества вхождений, поэтому вам нужна структура данных с изменяемым размером. Реализация с использованием
Map<Long, Set<String>>, Или, если он использует слишком много памяти, используйтеArrayList<Set<String>>(вам придется проверить наcount == size() - 1и если да, используйтеadd()вместоset(count + 1)).
Чтобы увеличить количество вхождений для слова (псевдокод):
// assumes data structures are in instance variables dict and arr
public void tally(final String word)
{
final long count = this.dict.get(word) or 0 if absent;
this.dict.put(word, count + 1);
// move word up one place in arr
this.arr[count].remove(word); // This is why we use a Set: for fast deletion here.
this.arr[count + 1].add(word);
}
Чтобы перебрать слова по порядку (псевдокод):
for(int count = 0; count < arr.size; count++)
for(final String word : this.arr[count])
process(word, count);
Как насчет использования дополнительного индекса или только TreeMap<Long, TreeSet<String>> или же TreeMap<Long, String> если длинные значения различны?
Вы также можете написать кучу.
Guava BiMap Solution:
//Prepare original data
BiMap<String, Integer> biMap = HashBiMap.create();
biMap.put("apples" , 4);
biMap.put("oranges", 2);
biMap.put("bananas", 1);
biMap.put("lemons" , 3);
biMap.put("bananas", 6);
//Create a desc order SortedMap
SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>(new Comparator<Integer>(){
@Override public int compare(Integer o1, Integer o2) {
return o2-o1;
}});
//Put inversed map
sortedMap.putAll(biMap.inverse());
for (Map.Entry<Integer, String> e: sortedMap.entrySet()) {
System.out.println(e);
}
System.out.println(sortedMap.lastKey());
Попробуйте решение, размещенное на http://paaloliver.wordpress.com/2006/01/24/sorting-maps-in-java/. У вас есть возможность делать сортировку по возрастанию или убыванию тоже.
Вот что они говорят
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
public class MapValueSort {
/** inner class to do soring of the map **/
private static class ValueComparer implements Comparator<String> {
private Map<String, String> _data = null;
public ValueComparer (Map<String, String> data){
super();
_data = data;
}
public int compare(String o1, String o2) {
String e1 = (String) _data.get(o1);
String e2 = (String) _data.get(o2);
return e1.compareTo(e2);
}
}
public static void main(String[] args){
Map<String, String> unsortedData = new HashMap<String, String>();
unsortedData.put("2", "DEF");
unsortedData.put("1", "ABC");
unsortedData.put("4", "ZXY");
unsortedData.put("3", "BCD");
SortedMap<String, String> sortedData = new TreeMap<String, String>(new MapValueSort.ValueComparer(unsortedData));
printMap(unsortedData);
sortedData.putAll(unsortedData);
System.out.println();
printMap(sortedData);
}
private static void printMap(Map<String, String> data) {
for (Iterator<String> iter = data.keySet().iterator(); iter.hasNext();) {
String key = (String) iter.next();
System.out.println("Value/key:"+data.get(key)+"/"+key);
}
}
}
Выходы
Value/key:BCD/3
Value/key:DEF/2
Value/key:ABC/1
Value/key:ZXY/4
Value/key:ABC/1
Value/key:BCD/3
Value/key:DEF/2
Value/key:ZXY/4
Я обнаружил необходимость в подобной структуре для хранения списка объектов, упорядоченных по связанным значениям. Основываясь на предложении Механической улитки в этой теме, я описал базовую реализацию такой карты. Не стесняйтесь использовать.
import java.util.*;
/**
* A map where {@link #keySet()} and {@link #entrySet()} return sets ordered
* with ascending associated values with respect to the the comparator provided
* at constuction. The order of two or more keys with identical values is not
* defined.
* <p>
* Several contracts of the Map interface are not satisfied by this minimal
* implementation.
*/
public class ValueSortedMap<K, V> extends HashMap<K, V> {
protected Map<V, Collection<K>> valueToKeysMap;
public ValueSortedMap() {
this((Comparator<? super V>) null);
}
public ValueSortedMap(Comparator<? super V> valueComparator) {
this.valueToKeysMap = new TreeMap<V, Collection<K>>(valueComparator);
}
public boolean containsValue(Object o) {
return valueToKeysMap.containsKey(o);
}
public V put(K k, V v) {
V oldV = null;
if (containsKey(k)) {
oldV = get(k);
valueToKeysMap.get(oldV).remove(k);
}
super.put(k, v);
if (!valueToKeysMap.containsKey(v)) {
Collection<K> keys = new ArrayList<K>();
keys.add(k);
valueToKeysMap.put(v, keys);
} else {
valueToKeysMap.get(v).add(k);
}
return oldV;
}
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
public V remove(Object k) {
V oldV = null;
if (containsKey(k)) {
oldV = get(k);
super.remove(k);
valueToKeysMap.get(oldV).remove(k);
}
return oldV;
}
public void clear() {
super.clear();
valueToKeysMap.clear();
}
public Set<K> keySet() {
LinkedHashSet<K> ret = new LinkedHashSet<K>(size());
for (V v : valueToKeysMap.keySet()) {
Collection<K> keys = valueToKeysMap.get(v);
ret.addAll(keys);
}
return ret;
}
public Set<Map.Entry<K, V>> entrySet() {
LinkedHashSet<Map.Entry<K, V>> ret = new LinkedHashSet<Map.Entry<K, V>>(size());
for (Collection<K> keys : valueToKeysMap.values()) {
for (final K k : keys) {
final V v = get(k);
ret.add(new Map.Entry<K,V>() {
public K getKey() {
return k;
}
public V getValue() {
return v;
}
public V setValue(V v) {
throw new UnsupportedOperationException();
}
});
}
}
return ret;
}
}
Эта реализация не учитывает все контракты интерфейса Map, такие как отражение изменений и удалений значений в возвращенном наборе ключей и наборах записей в фактической карте, но такое решение было бы немного большим для включения в подобный форум. Возможно, я поработаю над одним и сделаю его доступным через github или что-то подобное.
Вы можете обратиться к реализации java.util.LinkedHashMap, Основная идея заключается в использовании внутреннего связного списка для хранения заказов. Вот некоторые детали:
Распространяется из HashMap. В HashMap каждая запись имеет ключ и значение, которые являются основными. Вы можете добавить следующий и предыдущий указатель, чтобы хранить записи в порядке по значению. И заголовок и хвостовой указатель, чтобы получить первую и последнюю запись. Для каждой модификации (добавление, удаление, обновление) вы можете добавить свой собственный код для изменения порядка списка. Это не более чем линейный поиск и указатель.
Конечно, это будет медленно для добавления / обновления, если будет слишком много записей, потому что это связанный список, а не массив. Но пока список отсортирован, я думаю, что есть много способов ускорить поиск.
Итак, вот что вы получили: Карта, которая имеет ту же скорость, что и HashMap, при получении записи по ключу. Связанный список, в котором хранятся записи по порядку.
Мы можем обсудить это далее, если это решение соответствует вашим требованиям.
jtahlborn: как я уже сказал, это, конечно, медленно без какой-либо оптимизации. Поскольку речь идет о производительности, не подразумеваемой сейчас, многое можно сделать.
Одним из решений является использование дерева вместо связанного списка, например, красно-черного дерева. Затем итерируйте дерево вместо итератора карты.
Про наименьшее значение проще. Просто используйте переменную-член для хранения наименьшего, при добавлении или обновлении элемента обновите наименьшее значение. При удалении ищите в дереве самое маленькое (это очень быстро)
если дерево слишком сложное, можно также использовать другой список / массив, чтобы отметить некоторые позиции в списке. например, может быть 100 элементов каждый. Затем при поиске, просто сначала поиск списка позиций, а затем реальный список. Этот список также необходимо поддерживать, было бы разумно пересчитать список позиций для определенных времен модификации, возможно, 100.
Обновление: вы не можете сортировать карты по значениям, извините.
Ты можешь использовать SortedMap реализация как TreeMap с Comparator определение порядка по значениям (вместо по умолчанию - по ключам).
Или, что еще лучше, вы можете поместить элементы в PriorityQueue с предопределенным компаратором по значениям. Это должно быть быстрее и занимать меньше памяти по сравнению с TreeMap.
Если все, что вам нужно, это значение "min", то просто используйте карту нормалей и отслеживайте значение "min" каждый раз, когда оно изменяется.
РЕДАКТИРОВАТЬ:
так что, если вам действительно нужно упорядочить стоимость и вы хотите использовать готовые решения, вам в основном нужно 2 набора. Одна карта нормалей (например, HashMap) и один SortedSet (например, TreeSet>). Вы можете просматривать упорядоченные элементы с помощью TreeSet и находить частоты по ключу, используя HashMap.
очевидно, вы всегда можете написать что-то вроде своего рода LinkedHashMap, где элементы могут быть расположены по ключу и проходимы по порядку, но это в значительной степени будет полностью пользовательский код (я сомневаюсь, что что-то конкретное уже существует, но я мог бы быть неправильно).