Блог

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

Пожалуйста, также имейте в виду, что эта карта будет действительно большой (100 тысяч или даже 10 миллионов записей размером).

Итак, в основном я ищу следующую функциональность:

Предположим, что у нас есть класс ‘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();
  

что должно дать мне запись ‘oranges’

РЕДАКТИРОВАТЬ: я новичок в Java, поэтому, пожалуйста, уточните немного в своих ответах — спасибо

РЕДАКТИРОВАНИЕ 2: это может помочь: я использую это для подсчета слов (для тех, кто знаком: в частности, n-граммов) в огромных текстовых файлах. Итак, мне нужно создать карту, где ключи — это слова, а значения — это частоты этих слов. Однако из-за ограничений (например, оперативной памяти) я хочу сохранить только X наиболее часто встречающихся слов, но вы не можете заранее знать, какие слова будут самыми частыми, конечно. Итак, я подумал, что это может сработать (в качестве приближения), чтобы начать подсчет слов, и когда карта достигнет верхнего предела (например, 1 миллион записей), наименее частая запись будет удалена, чтобы размер карты всегда оставался равным 1 миллиону.

Сохраняйте 2 структуры данных:

• Словарь слов -> количество. Просто используйте обычный HashMap<String, Long> .

• «Массив» для отслеживания порядка, такой, который list[count] содержит a Set<String> слов с таким количеством.

  Я пишу это так, как если бы это был массив для удобства обозначения. На самом деле, вы, вероятно, не знаете верхнюю границу количества вхождений, поэтому вам нужна структура данных с изменяемым размером. Реализовать с помощью Map<Long, Set<String>> . Или, если это требует слишком много памяти, используйте an 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:

 //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
  

Я обнаружил необходимость подобной структуры для хранения списка объектов, упорядоченных по связанным значениям. Основываясь на предложении Mechanical snail в этой теме, я закодировал базовую реализацию такой карты. Не стесняйтесь использовать.

 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 или что-то подобное.

Обновление: вы не можете сортировать карты по значениям, извините.

Вы можете использовать SortedMap реализацию, подобную TreeMap с Comparator определением порядка по значениям (вместо по умолчанию — по ключам).

Или, что еще лучше, вы можете поместить элементы в PriorityQueue с предопределенным компаратором по значениям. Это должно быть быстрее и занимать меньше памяти по сравнению с TreeMap.

Вы можете обратиться к реализации java.util.LinkedHashMap . Основная идея заключается в использовании внутреннего связанного списка для хранения заказов. Вот некоторые подробности:

Расширяется из HashMap. В HashMap каждая запись имеет ключ и значение, которые являются базовыми. Вы можете добавить указатель next и prev для хранения записей в порядке по значению. И указатель заголовка и хвоста для получения первой и последней записи. Для каждого изменения (добавления, удаления, обновления) вы можете добавить свой собственный код для изменения порядка списка. Это не более чем линейный поиск и переключение указателя.

Конечно, добавление / обновление будет медленным, если записей слишком много, потому что это связанный список, а не массив. Но пока список отсортирован, я считаю, что есть много способов ускорить поиск.

Итак, вот что вы получили: карта, которая имеет ту же скорость, что и HashMap при получении записи по ключу. Связанный список, в котором записи хранятся по порядку.

Мы можем обсудить это подробнее, если это решение соответствует вашим требованиям.

для jtahlborn: как я уже сказал, это, безусловно, медленно без какой-либо оптимизации. Поскольку мы говорим о производительности, а не о производительности, многое можно сделать.

Одним из решений является использование дерева вместо связанного списка, например, красно-черного дерева. Затем выполните итерацию дерева вместо итерации карты.

Что касается наименьшего значения, это проще. Просто используя переменную-член для хранения наименьшего, при добавлении или обновлении элемента обновляйте наименьшее значение. При удалении выполните поиск в дереве наименьшего (это очень быстро)

если дерево слишком сложное, также можно использовать другой список / массив для обозначения некоторых позиций в списке. например, может быть, по 100 элементов в каждой. Затем при поиске просто выполните поиск сначала в списке позиций, а затем в реальном списке. Этот список также необходимо поддерживать, было бы разумно пересчитать список позиций для определенных периодов изменения, возможно, 100.

если все, что вам нужно, это значение «min», то просто используйте карту нормалей и отслеживайте значение «min» в любое время, когда оно изменяется.

Редактировать:

итак, если вам действительно нужен порядок значений и вы хотите использовать готовые решения, вам в основном нужны 2 коллекции. Одна карта нормалей (например, HashMap) и один сортируемый набор (например, TreeSet>). вы можете перемещаться по упорядоченным элементам через TreeSet и находить частоты по ключу, используя HashMap.

очевидно, что вы всегда можете самостоятельно создать что-то вроде LinkedHashMap, где элементы можно найти по ключу и перемещаться по порядку, но это в значительной степени будет полностью настраиваемый код (я сомневаюсь, что что-то конкретное уже существует, но я могу ошибаться).