Сортированная коллекция на Java - PullRequest
157 голосов
/ 06 января 2009

Я новичок в Java. Пожалуйста, предложите, какую коллекцию (ы) можно / нужно использовать для поддержания отсортированного списка в Java. Я пробовал Map и Set, но это было не то, что я искал.

Ответы [ 19 ]

182 голосов
/ 24 февраля 2010

Это приходит очень поздно, но в JDK есть класс только для того, чтобы иметь отсортированный список. Он назван (несколько не в порядке с другими Sorted* интерфейсами) "java.util.PriorityQueue". Он может сортировать Comparable<?> с или Comparator.

Разница с List, отсортированным с использованием Collections.sort(...), заключается в том, что это всегда будет поддерживать частичный порядок при производительности вставки O (log (n)), используя структуру данных кучи, тогда как вставка в отсортирован ArrayList будет O (n) (т. Е. С использованием двоичного поиска и перемещения).

Однако, в отличие от List, PriorityQueue не поддерживает индексированный доступ (get(5)), единственный способ получить доступ к элементам в куче - вынимать их по одному (при этом название PriorityQueue).

53 голосов
/ 06 января 2009

TreeMap и TreeSet дадут вам итерацию по содержимому в отсортированном порядке. Или вы можете использовать ArrayList и использовать Collections.sort () для его сортировки. Все эти классы находятся в java.util

32 голосов
/ 06 января 2009

Если вы хотите сохранить отсортированный список , который вы будете часто модифицировать (т. Е. Структуру, которая, помимо сортировки, допускает дублирование и на элементы которой можно эффективно ссылаться с помощью index), затем используйте ArrayList, но когда вам нужно вставить элемент, всегда используйте Collections.binarySearch (), чтобы определить индекс , при котором вы добавляете данный элемент. Последний метод сообщает вам индекс, в который нужно вставить список, чтобы сохранить список в отсортированном порядке.

31 голосов
/ 21 апреля 2011

Используйте класс Google Guava TreeMultiset . Гуава имеет потрясающий API коллекций.

Одной из проблем с предоставлением реализации List, поддерживающей отсортированный порядок, является обещание, данное в JavaDocs метода add().

12 голосов
/ 06 января 2009

Есть несколько вариантов. Я бы предложил TreeSet, если вам не нужны дубликаты, а вставляемые объекты сравнимы.

Для этого вы также можете использовать статические методы класса Collections.

См. Collections # sort (java.util.List) и TreeSet для получения дополнительной информации.

12 голосов
/ 06 января 2009

Вы хотите реализации SortedSet , а именно TreeSet .

9 голосов
/ 06 января 2009

Если вы просто хотите отсортировать список, используйте любой тип Список и используйте Collections.sort () . Если вы хотите убедиться, что элементы в списке уникальны и всегда отсортированы, используйте SortedSet .

5 голосов
/ 29 ноября 2012

Что я сделал, так это реализовал List, имеющий внутренний экземпляр со всеми делегированными методами.

 public class ContactList implements List<Contact>, Serializable {
    private static final long serialVersionUID = -1862666454644475565L;
    private final List<Contact> list;

public ContactList() {
    super();
    this.list = new ArrayList<Contact>();
}

public ContactList(List<Contact> list) {
    super();
    //copy and order list
    List<Contact>aux= new ArrayList(list);
    Collections.sort(aux);

    this.list = aux;
}

public void clear() {
    list.clear();
}

public boolean contains(Object object) {
    return list.contains(object);
}

После этого я реализовал новый метод "putOrdered", который вставляет в правильное положение, если элемент не существует, или заменяет его, если он существует.

public void putOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
        list.add(index, contact);
    }else{
        list.set(index, contact);
    }
}

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

public void addOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
    }
    list.add(index, contact);
}

Если вы хотите избежать вставок, вы также можете вызвать исключение и неподдерживаемую операцию для методов «add» и «set».

public boolean add(Contact object) {
    throw new UnsupportedOperationException("Use putOrdered instead");
}

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

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}
4 голосов
/ 12 марта 2014

Использование LambdaJ

Вы можете попробовать решить эти задачи с помощью LambdaJ , если вы используете предыдущие версии для Java 8. Вы можете найти его здесь: http://code.google.com/p/lambdaj/

Вот вам пример:

Итеративная сортировка

List<Person> sortedByAgePersons = new ArrayList<Person>(persons);
Collections.sort(sortedByAgePersons, new Comparator<Person>() {
        public int compare(Person p1, Person p2) {
           return Integer.valueOf(p1.getAge()).compareTo(p2.getAge());
        }
}); 

Сортировка с помощью LambdaJ

List<Person> sortedByAgePersons = sort(persons, on(Person.class).getAge()); 

Конечно, такая красота влияет на производительность (в среднем в 2 раза), но вы можете найти более читаемый код?

Сортировка с использованием Java 8 с использованием лямбда-выражения

Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge()));
//or
persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge()));
4 голосов
/ 29 декабря 2016

Самый эффективный способ реализовать отсортированный список, как вы хотите, - это реализовать индексируемый пропускаемый список, как показано здесь: Википедия: Индексируемый пропускаемый список . Это позволило бы иметь вставки / удаления в O (log (n)) и позволило бы иметь индексированный доступ одновременно. И это также позволило бы дубликаты.

Skiplist - довольно интересная и, я бы сказал, недооцененная структура данных. К сожалению, в базовой библиотеке Java нет индексированной реализации списка пропусков, но вы можете использовать одну из реализаций с открытым исходным кодом или реализовать ее самостоятельно. Существуют регулярные реализации Skiplist, такие как ConcurrentSkipListSet и ConcurrentSkipListMap

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...