Структура данных для ранжирования объектов

Question

Я ищу структуру данных, которая будет сортировать объекты на основе заданного целого числа. Вот так:

Object    Score
Object1   86
Object2   85
Object3   85 

Каждый объект будет уникальным, но возможны повторяющиеся оценки. Пытался придумать, как это может сделать объект Map, но не может понять.

Структура может сортировать объекты во время / после вставки или когда я неявно вызываю сортировку.

Есть ли какая-то структура, которая это уже делает? Или я сам должен его кодировать?

Answer 1

Попробуйте поместить объекты в SortedSet, если вы хотите уникальные значения, или List, если вы хотите увидеть дубликаты, вместе с пользовательским Comparator, чтобы отсортировать их по их «оценкам».

Предоставление собственного компаратора позволит вам указать, что объекты должны быть отсортированы в их поле score и как.

Компаратор также можно использовать многократно, и его можно легко поменять местами, если хотите, например, выполнить сортировку элементов по убыванию.

Вот пример, который может быть:

  class ScoreComparator implements Comparator <ObjectHolder> {
    @Override
    public int compare(ObjectHolder o1, ObjectHolder o2) {
      return o1.getScore().compareTo(o2.getScore());
    }
  }

  class DescendingScoreComparator implements Comparator <ObjectHolder> {
    @Override
    public int compare(ObjectHolder o1, ObjectHolder o2) {
      return o2.getScore().compareTo(o1.getScore());
    }
  }


  class ObjectHolder {
    Object obj;
    Integer score;

    public ObjectHolder(Object o, Integer score) {
      this.obj = o;
      this.score = score;
    }

    public Object getObject() {
      return obj;
    }
    public Integer getScore() {
      return score;
    }
  }


  public void showExample() {
    SortedSet<ObjectHolder> sortedSet = new TreeSet<ObjectHolder>(new ScoreComparator());
    sortedSet.add(new ObjectHolder("addedFirst", 55));
    sortedSet.add(new ObjectHolder("addedSecond", 25));
    sortedSet.add(new ObjectHolder("addedThird", 75));
    sortedSet.add(new ObjectHolder("addedFourth", 25));
    sortedSet.add(new ObjectHolder("addedFifth", 95));

    // The resulting set will only have 4 items since sets don't allow duplicates
    for (ObjectHolder holder : sortedSet) {
      System.out.println(holder.getScore());
    }

    List<ObjectHolder> list = new LinkedList<ObjectHolder>();
    list.add(new ObjectHolder("addedFirst", 55));
    list.add(new ObjectHolder("addedSecond", 25));
    list.add(new ObjectHolder("addedThird", 75));
    list.add(new ObjectHolder("addedFourth", 25));
    list.add(new ObjectHolder("addedFifth", 95));

    Collections.sort(list, new ScoreComparator());

    // The resulting set will only have 5 items since lists allow duplicates
    System.out.println();
    for (ObjectHolder holder : list) {
      System.out.println(holder.getScore());
    }

    Collections.sort(list, new DescendingScoreComparator());

    System.out.println("\nWill print 5 items, but this time in descending order");
    for (ObjectHolder holder : list) {
      System.out.println(holder.getScore());
    }
  }

А вот и вывод вышеприведенного кода:

Напечатает 4 уникальных предмета, поскольку наборы не допускают дублирования

25 55 75 95

Будет напечатано 5 элементов, поскольку списки допускают дублирование

25 25 55 75 95

Напечатает 5 элементов, но на этот раз в порядке убывания

95 75 55 25 25

Answer 2

Если вам нужно использовать карту, используйте TreeMap и укажите свой собственный Comparator, который может быть таким же, как вы использовали бы для SortedSet, как предложено @Cuga.

Answer 3

Вы ищете приоритетную очередь. Ява не мой основной язык, но похоже, что JDK уже реализует его в java.util.PriorityQueue. Возможно, вам придется реализовать свой собственный объект сравнения.

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/PriorityQueue.html

Чтобы циклически проходить по очереди приоритетов в соответствующем порядке, просто вызовите poll () в цикле, пока poll () не вернет ноль.

Answer 4

Вы можете попробовать TreeMultimap из библиотек Google Guava.

Это позволит вам хранить ваши данные как:

Оценка -> [Объект, Объект, Объект]

Это облегчает поиск всех объектов с определенным счетом. Некоторые вещи, которые вы не можете сделать, хотя:

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