Colección ordenada en Java

Soy un principiante en Java. Sugiera qué colección (es) pueden / deben usarse para mantener una lista ordenada en Java. Lo intenté Mapy Set, pero no eran lo que estaba buscando.

Esto llega muy tarde, pero hay una clase en el JDK solo con el fin de tener una lista ordenada. Se llama (algo fuera de orden con las otras Sorted*interfaces) " java.util.PriorityQueue". Puede ordenar Comparable<?>s o usar unComparator .

La diferencia con un Listuso ordenado Collections.sort(...)es que esto mantendrá un orden parcial en todo momento, con un rendimiento de inserción O (log (n)), mediante el uso de una estructura de datos de almacenamiento dinámico, mientras que la inserción en un ordenado ArrayListserá O (n) (es decir, usando búsqueda y movimiento binarios).

Sin embargo, a diferencia de a List, PriorityQueueno admite el acceso indexado ( get(5)), la única forma de acceder a los elementos en un montón es eliminarlos, uno a la vez (de ahí el nombre PriorityQueue).

TreeMap y TreeSet le darán una iteración sobre los contenidos en orden ordenado. O puede usar una ArrayList y usar Collections.sort () para ordenarla. Todas esas clases están en java.util

Si desea mantener una lista ordenada que modificará con frecuencia (es decir, una estructura que, además de estar ordenada, permite duplicados y cuyos elementos pueden ser referenciados eficientemente por índice), utilice una ArrayList pero cuando necesite insertar un elemento , use siempre Collections.binarySearch () para determinar el índice en el que agrega un elemento determinado. El último método le indica el índice en el que debe insertar para mantener su lista ordenada.

Utilice la clase TreeMultiset de Google Guava . La guayaba tiene una espectacular colección de API.

Un problema al proporcionar una implementación de List que mantiene el orden ordenado es la promesa hecha en los JavaDocs del add()método.

Desea las implementaciones de SortedSet , es decir, TreeSet .

Hay algunas opciones Sugeriría TreeSet si no desea duplicados y los objetos que está insertando son comparables.

También puede usar los métodos estáticos de la clase Colecciones para hacer esto.

Consulte Colecciones # sort (java.util.List) y TreeSet para obtener más información.

Si solo desea ordenar una lista, use cualquier tipo de Lista y use Collections.sort () . Si desea asegurarse de que los elementos de la lista sean únicos y estén siempre ordenados, use un SortedSet .

Lo que he hecho es implementar List con una instancia interna con todos los métodos delegados.

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

Después, he implementado un nuevo método "putOrdered" que se inserta en la posición correcta si el elemento no existe o se reemplaza solo en caso de que exista.

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

Si desea permitir elementos repetidos, simplemente implemente addOrdered en su lugar (o ambos).

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

Si desea evitar las inserciones, también puede lanzar una excepción de operación no admitida en los métodos "agregar" y "establecer".

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

... y también debe tener cuidado con los métodos ListIterator porque podrían modificar su lista interna. En este caso, puede devolver una copia de la lista interna o volver a lanzar una excepción.

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

La forma más eficiente de implementar una lista ordenada como desee sería implementar una lista de salto indexable como aquí: Wikipedia: Lista de salto indexable . Permitiría tener inserciones / eliminaciones en O (log (n)) y permitiría tener acceso indexado al mismo tiempo. Y también permitiría duplicados.

Skiplist es una estructura de datos bastante interesante y, diría yo, subestimada. Desafortunadamente, no hay una implementación de listas de salto indexadas en la biblioteca base de Java, pero puede usar una de las implementaciones de código abierto o implementarla usted mismo. Hay implementaciones regulares de Skiplist como ConcurrentSkipListSet y ConcurrentSkipListMap

TreeSet no funcionaría porque no permiten duplicados y además no proporcionan un método para recuperar elementos en una posición específica. PriorityQueue no funcionaría porque no permite buscar elementos en una posición específica, que es un requisito básico para una lista. Creo que necesita implementar su propio algoritmo para mantener una lista ordenada en Java con tiempo de inserción O (logn), a menos que no necesite duplicados. Tal vez una solución podría ser usar un TreeMap donde la clave es una subclase del elemento que anula el método igual para que se permitan duplicados.

Usando LambdaJ

Puede intentar resolver estas tareas con LambdaJ si está utilizando versiones anteriores de Java 8. Puede encontrarlo aquí: http://code.google.com/p/lambdaj/

Aquí tienes un ejemplo:

Ordenar iterativo

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

Ordenar con LambdaJ

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

Por supuesto, tener este tipo de belleza impacta en el rendimiento (un promedio de 2 veces), pero ¿puedes encontrar un código más legible?

Ordenar con java 8 usando la expresión lambda

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

El problema con PriorityQueue es que está respaldado por una matriz simple, y la lógica que pone los elementos en orden se realiza mediante la cosa "cola [2 * n + 1] y cola [2 * (n + 1)]". Funciona muy bien si solo tira de la cabeza, pero lo hace inútil si está tratando de llamar al .toArray en algún momento.

Evito este problema usando com.google.common.collect.TreeMultimap, pero proporciono un comparador personalizado para los valores, envuelto en un pedido, que nunca devuelve 0.

ex. para doble:

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

De esta manera obtengo los valores en orden cuando llamo .toArray (), y también tengo duplicados.

Lo que quieres es un árbol de búsqueda binario. Mantiene el orden ordenado al tiempo que ofrece acceso logarítmico para búsquedas, eliminaciones e inserciones (a menos que tenga un árbol degenerado, entonces es lineal). Es bastante fácil de implementar e incluso puede hacer que implemente la interfaz de Lista, pero luego el acceso al índice se complica.

El segundo enfoque es tener una ArrayList y luego una implementación de clasificación de burbujas. Debido a que está insertando o eliminando un elemento a la vez, los tiempos de acceso para inserciones y eliminaciones son lineales. Las búsquedas son logarítmicas y el acceso al índice es constante (los tiempos pueden ser diferentes para LinkedList). El único código que necesita es 5, quizás 6 líneas de burbuja.

Puede usar Arraylist y Treemap, ya que dijo que también desea valores repetidos, luego no puede usar TreeSet, aunque también está ordenado, pero debe definir el comparador.

Para Set puedes usar TreeSet. TreeSet ordena sus elementos sobre la base de un orden natural o cualquier orden de clasificación pasado al Comparable para ese objeto en particular. Para el mapa use TreeMap. TreeMap proporciona la clasificación por claves. Para agregar un objeto como clave al TreeMap, esa clase debe implementar una interfaz comparable que a su vez obliga a implementar el método compare to () que contiene la definición del orden de clasificación. http://techmastertutorial.in/java-collection-impl.html

Use el método sort () para ordenar la lista de la siguiente manera:

List list = new ArrayList();

//add elements to the list

Comparator comparator = new SomeComparator();

Collections.sort(list, comparator);

Para referencia, consulte el enlace: http://tutorials.jenkov.com/java-collections/sorting.html

Uso TreeSetque da elementos en orden ordenado. O use Collection.sort()para la ordenación externa con 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);    
}

con Java 8 Comparator, si queremos ordenar la lista, aquí están las 10 ciudades más pobladas del mundo y queremos ordenarla por nombre, según lo informado por Time. Osaka, Japón. ... Ciudad de México, México. ... Beijing, China. ... São Paulo, Brasil. ... Mumbai, India. ... Shanghai, China. ... Delhi, India. ... Tokio, Japón.

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

    }

}

Ordenar una ArrayList de acuerdo con los criterios definidos por el usuario.

Clase de modelo

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

Clase de clasificación

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

Clase principal

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

Salida

 Unsorted
 111 bbbb london
 131 aaaa nyc
 121 cccc jaipur

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