Автоматически сортируется по карте значений в Java

Ответ 1

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

• Словарь слов → count. Просто используйте обычный 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);

Ответ 2

Как насчет использования дополнительного индекса или только TreeMap<Long, TreeSet<String>> или TreeMap<Long, String>, если значения Long отличаются друг от друга?

Вы также можете написать Heap.

Ответ 3

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()); 

Ответ 4

Попробуйте решение, размещенное на 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

Ответ 5

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

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

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

Ответ 6

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

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

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

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

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

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

В одном решении используется дерево вместо Linked List, например Red-Black Tree. Затем переместите дерево вместо итератора на карту.

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

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

Ответ 7

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

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;
    }
}

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

Ответ 8

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

EDIT:

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

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