Сортированная коллекция на Java

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

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

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

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

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

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

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

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

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

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

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

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

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

Что я сделал, так это реализовал 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();
}

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

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

TreeSet не будет работать, потому что они не допускают дублирования, плюс они не предоставляют метод для извлечения элемента в определенной позиции. PriorityQueue не будет работать, потому что он не позволяет извлекать элементы в определенной позиции, что является основным требованием для списка. Я думаю, что вам нужно реализовать свой собственный алгоритм для поддержки отсортированного списка в Java с O (logn) время вставки, если вам не нужны дубликаты. Возможно, решением может быть использование TreeMap, где ключ является подклассом элемента, переопределяющего метод equals, так что допускаются дубликаты.

Использование 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()));

Проблема с PriorityQueue заключается в том, что он поддерживается простым массивом, а логика, которая приводит элементы в порядок, выполняется штукой "queue [2 * n + 1] и queue [2 * (n + 1)]". Это прекрасно работает, если вы просто тянете с головы, но делает его бесполезным, если вы пытаетесь вызвать .toArray для него в какой-то момент.

Я обхожу эту проблему, используя com.google.common.collect.TreeMultimap, но я поставляю собственный компаратор для значений, заключенных в упорядочение, который никогда не возвращает 0.

ех. для двойной:

private static final Ordering<Double> NoEqualOrder = Ordering.from(new Comparator<Double>() {

    @Override
    public int compare(Double d1, Double d2)
    {
        if (d1 < d2) {
            return -1;
        }
        else {
            return 1;
        }
    }
});

Таким образом, я получаю значения в порядке, когда я вызываю .toArray (), а также есть дубликаты.

То, что вы хотите, это двоичное дерево поиска. Он поддерживает отсортированный порядок, предлагая логарифмический доступ для поиска, удаления и вставки (если у вас нет вырожденного дерева - тогда оно линейное). Это довольно легко реализовать, и вы даже можете заставить его реализовать интерфейс List, но тогда доступ по индексу усложняется.

Второй подход - иметь ArrayList, а затем реализацию с сортировкой пузырьков. Поскольку вы вставляете или удаляете по одному элементу за раз, время доступа для вставок и удалений является линейным. Поиски являются логарифмической и индексной константой доступа (времена для LinkedList могут отличаться). Единственный код, который вам нужен, - это 5, может быть, 6 строк пузырьковой сортировки.

Вы можете использовать Arraylist и Treemap, так как вы сказали, что вам также нужны повторные значения, тогда вы не можете использовать TreeSet, хотя он также отсортирован, но вам нужно определить компаратор.

Для Set вы можете использовать TreeSet. TreeSet упорядочивает свои элементы на основе естественного упорядочения или любого порядка сортировки, передаваемого в Comparable для этого конкретного объекта. Для карты используйте TreeMap. TreeMap обеспечивает сортировку по ключам. Чтобы добавить объект в качестве ключа в TreeMap, этот класс должен реализовать сопоставимый интерфейс, который, в свою очередь, заставляет реализовать метод сравнения с (), который содержит определение порядка сортировки. http://techmastertutorial.in/java-collection-impl.html

Используйте метод sort () для сортировки списка, как показано ниже:

List list = new ArrayList();

//add elements to the list

Comparator comparator = new SomeComparator();

Collections.sort(list, comparator);

Для справки смотрите ссылку: http://tutorials.jenkov.com/java-collections/sorting.html

Использование, TreeSetкоторое дает элементы в отсортированном порядке. ИЛИ использовать Collection.sort()для внешней сортировки с Comparator().

import java.util.TreeSet;

public class Ass3 {
    TreeSet<String>str=new TreeSet<String>();
    str.add("dog");
    str.add("doonkey");
    str.add("rat");
    str.add("rabbit");
    str.add("elephant");
    System.out.println(str);    
}

с Java 8 Comparator, если мы хотим отсортировать список, то вот 10 самых населенных городов мира, и мы хотим отсортировать их по названию, как сообщает Time. Осака, Япония. ... Мехико, Мексика. ... Пекин, Китай. ... Сан-Паулу, Бразилия. ... Мумбаи, Индия. ... Шанхай, Китай. ... Дели, Индия. ... Токио, Япония.

 import java.util.Arrays;
 import java.util.Comparator;
 import java.util.List;

public class SortCityList {

    /*
     * Here are the 10 most populated cities in the world and we want to sort it by
     * name, as reported by Time. Osaka, Japan. ... Mexico City, Mexico. ...
     * Beijing, China. ... São Paulo, Brazil. ... Mumbai, India. ... Shanghai,
     * China. ... Delhi, India. ... Tokyo, Japan.
     */
    public static void main(String[] args) {
        List<String> cities = Arrays.asList("Osaka", "Mexico City", "São Paulo", "Mumbai", "Shanghai", "Delhi",
                "Tokyo");
        System.out.println("Before Sorting List is:-");
        System.out.println(cities);
        System.out.println("--------------------------------");

        System.out.println("After Use of List sort(String.CASE_INSENSITIVE_ORDER) & Sorting List is:-");
        cities.sort(String.CASE_INSENSITIVE_ORDER);
        System.out.println(cities);
        System.out.println("--------------------------------");
        System.out.println("After Use of List sort(Comparator.naturalOrder()) & Sorting List is:-");
        cities.sort(Comparator.naturalOrder());
        System.out.println(cities);

    }

}

Сортировка ArrayList в соответствии с заданными пользователем критериями.

Модельный класс

 class Student 
 { 
     int rollno; 
     String name, address; 

     public Student(int rollno, String name, String address) 
     { 
         this.rollno = rollno; 
         this.name = name; 
         this.address = address; 
     }   

     public String toString() 
     { 
         return this.rollno + " " + this.name + " " + this.address; 
     } 
 } 

Класс сортировки

 class Sortbyroll implements Comparator<Student> 
 {         
     public int compare(Student a, Student b) 
     { 
         return a.rollno - b.rollno; 
     } 
 } 

Основной класс

 class Main 
 { 
     public static void main (String[] args) 
     { 
         ArrayList<Student> ar = new ArrayList<Student>(); 
         ar.add(new Student(111, "bbbb", "london")); 
         ar.add(new Student(131, "aaaa", "nyc")); 
         ar.add(new Student(121, "cccc", "jaipur")); 

         System.out.println("Unsorted"); 
         for (int i=0; i<ar.size(); i++) 
             System.out.println(ar.get(i)); 

         Collections.sort(ar, new Sortbyroll()); 

         System.out.println("\nSorted by rollno"); 
         for (int i=0; i<ar.size(); i++) 
             System.out.println(ar.get(i)); 
     } 
 } 

Вывод

 Unsorted
 111 bbbb london
 131 aaaa nyc
 121 cccc jaipur

 Sorted by rollno
 111 bbbb london
 121 cccc jaipur
 131 aaaa nyc