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

Question

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

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

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

Предполагается, что у нас есть класс '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();

, которая должна дать мне «апельсины»entry

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

EDIT2: Это может помочь: я использую это для подсчета слов (для тех, кто знаком:в частности, n-грамм) в огромных текстовых файлах.Поэтому мне нужно построить карту, где ключи - это слова, а значения - частоты этих слов.Однако из-за ограничений (например, ОЗУ) я хочу сохранить только X наиболее часто встречающихся слов - но вы не можете заранее знать, какие слова будут самыми частыми, конечно.Таким образом, я думал, что это может работать (в качестве приблизительного значения), чтобы начать подсчет слов, и когда карта достигает верхнего предела (например, 1 миллион записей), наименее частая запись будет удалена, чтобы сохранить размер карты1 мил всегда.

Answer 1

Сохранить 2 структуры данных:

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

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

  IЯ пишу это так, как будто это массив для удобства записи.На самом деле, вы, вероятно, не знаете верхнюю границу количества вхождений, поэтому вам нужна структура данных с изменяемым размером.Реализуйте используя 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);

Answer 2

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

Вы также можете написать Куча .

Answer 3

Попробуйте решение, опубликованное на 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

Answer 4

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

Answer 5

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

Answer 6

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

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

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

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

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

---

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

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

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

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

Answer 7

Если вам нужно только значение min, просто используйте карту нормалей и отслеживайте значение min при каждом изменении.

EDIT:

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

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

Answer 8

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

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

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