tag - tld java

Colección ordenada en Java

Question

Soy un principiante en Java. Sugiera qué colección (es) puede / debe (n) usarse para mantener una lista ordenada en Java. He intentado Map and Set , pero no eran lo que estaba buscando.

Answer 1

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:

Sort Iterative

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

Clasificar 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?

Clasificar con java 8 usando expresión lambda

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

Answer 2

Desea las implementaciones SortedSet , concretamente TreeSet .

Answer 3

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

Repaso este problema utilizando com.google.common.collect.TreeMultimap, pero proporciono un Comparador personalizado para los valores, envuelto en un Pedido, que nunca devuelve 0.

ex. para el 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 forma obtengo los valores en orden cuando llamo a .toArray (), y también tengo duplicados.

Answer 4

Esto llega muy tarde, pero hay una clase en el JDK solo con el propósito de tener una lista ordenada. Se denomina (algo fuera de servicio con las otras interfaces Sorted* ) " java.util.PriorityQueue ". Puede ordenar Comparable<?> O utilizando un Comparator .

La diferencia con una List ordenada mediante Collections.sort(...) es que mantendrá un orden parcial en todo momento, con O (log (n)) rendimiento de inserción, mediante el uso de una estructura de datos de montón, mientras que inserta en una ordenada ArrayList será O (n) (es decir, utilizando búsqueda binaria y movimiento).

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

Answer 5

Hay algunas opciones. Sugeriría TreeSet si no quieres duplicados y los objetos que insertas son comparables.

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

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

Answer 6

La forma más eficiente de implementar una lista ordenada como lo desearía sería implementar skiplist indexable como aquí: Wikipedia: Lista de skip 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, subestimada. Lamentablemente, no existe una implementación de skiplist en la biblioteca base de Java, pero puede usar una de las implementaciones de código abierto o implementarla usted mismo.

Answer 7

Lo que he hecho es implementar List que tiene 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 lo reemplaza 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 "configurar".

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

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

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

Answer 8

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 la Lista, pero luego el acceso al índice se complica.

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

Answer 9

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

Answer 10

Si desea mantener una lista ordenada que modificará con frecuencia (es decir, una estructura que, además de ser ordenada, permite duplicados y cuyos elementos pueden ser referenciados de manera eficiente por índice), utilice una lista de arreglos pero cuando necesite insertar un elemento , siempre use 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.

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

Usa TreeSet que da elementos en orden ordenado. O use Collection.sort() para la clasificación externa con Comparator() .

Answer 15

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, vea el enlace: http://tutorials.jenkov.com/java-collections/sorting.html

Answer 16

Utilice TreeMultiset de Google Guava. Guava es una espectacular API de colecciones.

Guava: https://github.com/google/guava

TreeMultiset: https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/TreeMultiset.html

Un problema al proporcionar una implementación de List que mantiene el orden ordenado es la promesa hecha en los Javadocs del método ''agregar''.

Answer 17

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