Java에서 정렬 된 컬렉션

Java에서 정렬 된 컬렉션

---

저는 Java 초보자입니다. Java에서 정렬 된 목록을 유지하는 데 사용할 수있는 모음을 제안하십시오. 나는 시도 Map하고 Set, 그러나 그들은 내가 찾던하지 무엇을했다.

---

이것은 매우 늦었지만 JDK에는 정렬 된 목록을 가질 목적으로 클래스가 있습니다. 이름이 Sorted*" 다른 인터페이스 와 순서가 맞지 않습니다 " java.util.PriorityQueue""입니다. 을 Comparable<?>사용 하거나을 사용하여 정렬 할 수 있습니다 Comparator.

List정렬 된 사용법 과의 차이점 Collections.sort(...)은 힙 데이터 구조를 사용하여 O (log (n)) 삽입 성능을 사용하여 항상 부분 순서를 유지하지만 정렬 된 삽입은 ArrayListO (n)입니다 (즉, 이진 검색 및 이동 사용).

그러나, 달리 List, PriorityQueue인덱스 액세스 (지원하지 않습니다 get(5)), 한 번에 힙이 그들을 걸릴 것입니다에 항목에 액세스 할 수있는 유일한 방법은, 하나의 (따라서 이름을 PriorityQueue).

---

TreeMap과 TreeSet은 내용을 정렬 된 순서로 반복합니다. 또는 ArrayList를 사용하고 Collections.sort ()를 사용하여 정렬 할 수 있습니다. 모든 클래스는 java.util에 있습니다.

---

자주 수정 하는 정렬 된 목록 을 유지 하려면 (즉, 정렬 외에도 중복을 허용하고 인덱스로 요소를 효율적으로 참조 할 수있는 구조), ArrayList를 사용하지만 요소를 삽입해야 할 때 지정된 요소를 추가 할 색인을 결정하려면 항상 Collections.binarySearch ()를 사용하십시오 . 후자의 방법은 목록을 정렬 된 순서로 유지하기 위해 삽입해야하는 색인을 알려줍니다.

---

Google Guava의 TreeMultiset 클래스를 사용하십시오 . 구아바 에는 화려한 컬렉션 API가 있습니다.

정렬 순서를 유지하는 List 구현을 제공하는 데있어 한 가지 문제점은 add()메소드 의 JavaDoc에서 작성된 약속 입니다.

---

당신은 원하는 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 메소드는 내부 목록을 수정할 수 있으므로주의해야합니다. 이 경우 내부 목록의 복사본을 반환하거나 예외를 다시 throw 할 수 있습니다.

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}

---

원하는 정렬 목록을 구현하는 가장 효율적인 방법은 Wikipedia : Indexable skiplist와 같이 색인 가능한 건너 뛰기 목록을 구현하는 것 입니다. O (log (n))에 삽입 / 제거를 허용하고 동시에 인덱스 액세스를 허용합니다. 또한 중복을 허용합니다.

스킵리스트는 꽤 흥미롭고 저평가 된 데이터 구조입니다. 불행히도 Java 기본 라이브러리에는 인덱싱 된 건너 뛰기 목록이 없지만 오픈 소스 구현 중 하나를 사용하거나 직접 구현할 수 있습니다. ConcurrentSkipListSet 및 ConcurrentSkipListMap 과 같은 일반적인 Skiplist 구현이 있습니다.

---

TreeSet은 중복을 허용하지 않기 때문에 작동하지 않으며 특정 위치에서 요소를 가져 오는 메소드를 제공하지 않습니다. PriorityQueue는 목록의 기본 요구 사항 인 특정 위치에서 요소를 페치 할 수 없으므로 작동하지 않습니다. 중복이 필요하지 않은 경우 O (logn) 삽입 시간으로 Java에서 정렬 된 목록을 유지하려면 자체 알고리즘을 구현해야한다고 생각합니다. 아마도 솔루션은 키가 equals 메서드를 재정의하는 항목의 하위 클래스 인 TreeMap을 사용하여 복제가 허용 될 수 있습니다.

---

LambdaJ 사용

Java 8 이전 버전을 사용하는 경우 LambdaJ로 이러한 작업을 해결할 수 있습니다. 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()); 

Of course, having this kind of beauty impacts in the performance (an average of 2 times), but can you find a more readable code?

Sort with java 8 using lambda expression

Collections.sort(persons, (p1, p2) -> p1.getAge().compareTo(p2.getAge()));
//or
persons.sort((p1, p2) -> p1.getAge().compareTo(p2.getAge()));

---

The problem with PriorityQueue is that it's backed up by an simple array, and the logic that gets the elements in order is done by the "queue[2*n+1] and queue[2*(n+1)]" thingie. It works great if you just pull from head, but makes it useless if you are trying to call the .toArray on it at some point.

I go around this problem by using com.google.common.collect.TreeMultimap, but I supply a custom Comparator for the values, wrapped in an Ordering, that never returns 0.

ex. for Double:

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

This way I get the values in order when I call .toArray(), and also have duplicates.

---

What you want is a binary search tree. It maintains sorted order while offering logarithmic access for searches, removals and insertions (unless you have a degenerated tree - then it's linear). It is quite easy to implement and you even can make it implement the List interface, but then the index-access gets complicated.

Second approach is to have an ArrayList and then a bubble sort implementation. Because you are inserting or removing one element at a time, the access times for insertions and removals are linear. Searches are logarithmic and index access constant (times can get different for LinkedList). The only code you need is 5, maybe 6 lines of bubble sort.

---

You can use Arraylist and Treemap, as you said you want repeated values as well then you cant use TreeSet, though it is sorted as well, but you have to define comparator.

---

For Set you can use TreeSet. TreeSet orders it's elements on the basis of a natural ordering or any sorting order passed to the Comparable for that particular object. For map use TreeMap. TreeMap provides the sorting over keys. To add an object as a key to the TreeMap that class should implement comparable interface which in turn forces to implement compare to() method which contains the definition of the sorting order. http://techmastertutorial.in/java-collection-impl.html

---

Use sort() method to sort the list as below:

List list = new ArrayList();

//add elements to the list

Comparator comparator = new SomeComparator();

Collections.sort(list, comparator);

For reference see the link: http://tutorials.jenkov.com/java-collections/sorting.html

---

Use TreeSet which gives elements in sorted order. OR use Collection.sort() for external sorting with 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);    
}

---

with Java 8 Comparator, if we want to sort list then 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.

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

    }

}

---

Sorting an ArrayList according to user defined criteria.

Model Class

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

Sorting Class

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

Main Class

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

Output

 Unsorted
 111 bbbb london
 131 aaaa nyc
 121 cccc jaipur

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

참고URL : https://stackoverflow.com/questions/416266/sorted-collection-in-java