example - Una buena lista ordenada para Java

sort java example

Question

Estoy buscando una buena lista ordenada para Java. Buscar en Google me da algunas pistas sobre el uso de TreeSet / TreeMap. Pero estos componentes carecen de una cosa: acceso aleatorio a un elemento en el conjunto. Por ejemplo, quiero acceder al n-ésimo elemento en el conjunto ordenado, pero con TreeSet, debo iterar sobre otros elementos n-1 antes de que pueda llegar allí. Sería un desperdicio ya que tendría hasta varios miles de elementos en mi Set.

Básicamente, estoy buscando algo similar a una lista ordenada en .NET, con capacidad para agregar elementos rápidamente, eliminar elementos rápidamente y tener acceso aleatorio a cualquier elemento de la lista.

¿Este tipo de lista ordenada ha sido implementada en alguna parte? Gracias.

Editado

Mi interés en SortedList surge de estos problemas: necesito mantener una lista de muchos miles de objetos (y puedo crecer hasta cientos de miles). Estos objetos se conservarán en la base de datos. Quiero seleccionar aleatoriamente algunas docenas de elementos de toda la lista. Entonces, traté de mantener una lista separada en la memoria que contiene las claves principales (números largos) de todos los objetos. Necesito agregar / eliminar claves de la lista cuando el objeto se agrega / elimina de la base de datos. Estoy usando una ArrayList en este momento, pero me temo que ArrayList no se adaptaría a ella cuando crezca la cantidad de registros. (Imagine que tiene que iterar sobre varios cientos de miles de elementos cada vez que se elimina un objeto de la base de datos). De regreso a la época en que hacía la programación .NET, usaba una lista ordenada (List es una clase .NET que una vez que la propiedad Sorted se establece en true, mantiene el orden de su elemento y proporciona una búsqueda binaria que ayuda a eliminar / insertar elementos muy rápido). Espero poder encontrar algo similar de Java BCL, pero desafortunadamente, no encontré un buen partido.

Answer 1

¿Qué hay de usar un HashMap ? La inserción, borrado y recuperación son todas operaciones O (1). Si desea ordenar todo, puede tomar una Lista de los valores en el Mapa y ejecutarlos a través de un algoritmo de clasificación O (n log n).

editar

Una búsqueda rápida ha encontrado LinkedHashMap , que mantiene el orden de inserción de sus claves. No es una solución exacta, pero es bastante cercana.

Answer 2

Dependiendo de cómo esté usando la lista, puede valer la pena usar un TreeSet y luego usar el método toArray () al final. Tenía un caso en el que necesitaba una lista ordenada, y descubrí que TreeSet + toArray () era mucho más rápido que agregarlo a una matriz y fusionar la ordenación al final.

Answer 3

El decorador SortedList de Java Happy Libraries se puede usar para decorar TreeList desde Apache Collections. Eso produciría una nueva lista cuyo rendimiento es comparable a TreeSet. https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/

Answer 4

En general, no puede tener un tiempo constante de búsqueda y registro de eliminaciones / inserciones de tiempo, pero si está satisfecho con las búsquedas de tiempo de registro, entonces puede usar una Lista ordenada.

No estoy seguro de si va a confiar en mi codificación, pero recientemente escribí una implementación SortedList en Java, que puede descargar desde http://www.scottlogic.co.uk/2010/12/sorted_lists_in_java/ . Esta implementación le permite buscar el elemento i-ésimo de la lista en tiempo de registro.

Answer 5

Esta es la implementación de SortedList que estoy usando. Quizás esto ayude con tu problema:

import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
/**
 * This class is a List implementation which sorts the elements using the
 * comparator specified when constructing a new instance.
 * 
 * @param <T>
 */
public class SortedList<T> extends ArrayList<T> {
    /**
     * Needed for serialization.
     */
    private static final long serialVersionUID = 1L;
    /**
     * Comparator used to sort the list.
     */
    private Comparator<? super T> comparator = null;
    /**
     * Construct a new instance with the list elements sorted in their
     * {@link java.lang.Comparable} natural ordering.
     */
    public SortedList() {
    }
    /**
     * Construct a new instance using the given comparator.
     * 
     * @param comparator
     */
    public SortedList(Comparator<? super T> comparator) {
        this.comparator = comparator;
    }
    /**
     * Construct a new instance containing the elements of the specified
     * collection with the list elements sorted in their
     * {@link java.lang.Comparable} natural ordering.
     * 
     * @param collection
     */
    public SortedList(Collection<? extends T> collection) {
        addAll(collection);
    }
    /**
     * Construct a new instance containing the elements of the specified
     * collection with the list elements sorted using the given comparator.
     * 
     * @param collection
     * @param comparator
     */
    public SortedList(Collection<? extends T> collection, Comparator<? super T> comparator) {
        this(comparator);
        addAll(collection);
    }
    /**
     * Add a new entry to the list. The insertion point is calculated using the
     * comparator.
     * 
     * @param paramT
     * @return <code>true</code> if this collection changed as a result of the call.
     */
    @Override
    public boolean add(T paramT) {
        int initialSize = this.size();
        // Retrieves the position of an existing, equal element or the 
        // insertion position for new elements (negative).
        int insertionPoint = Collections.binarySearch(this, paramT, comparator);
        super.add((insertionPoint > -1) ? insertionPoint : (-insertionPoint) - 1, paramT);
        return (this.size() != initialSize);
    }
    /**
     * Adds all elements in the specified collection to the list. Each element
     * will be inserted at the correct position to keep the list sorted.
     * 
     * @param paramCollection
     * @return <code>true</code> if this collection changed as a result of the call.
     */
    @Override
    public boolean addAll(Collection<? extends T> paramCollection) {
        boolean result = false;
        if (paramCollection.size() > 4) {
            result = super.addAll(paramCollection);
            Collections.sort(this, comparator);
        }
        else {
            for (T paramT:paramCollection) {
                result |= add(paramT);
            }
        }
        return result;
    }
    /**
     * Check, if this list contains the given Element. This is faster than the
     * {@link #contains(Object)} method, since it is based on binary search.
     * 
     * @param paramT
     * @return <code>true</code>, if the element is contained in this list;
     * <code>false</code>, otherwise.
     */
    public boolean containsElement(T paramT) {
        return (Collections.binarySearch(this, paramT, comparator) > -1);
    }
    /**
     * @return The comparator used for sorting this list.
     */
    public Comparator<? super T> getComparator() {
        return comparator;
    }
    /**
     * Assign a new comparator and sort the list using this new comparator.
     * 
     * @param comparator
     */
    public void setComparator(Comparator<? super T> comparator) {
        this.comparator = comparator;
        Collections.sort(this, comparator);
    }
}

Esta solución es muy flexible y usa funciones Java existentes:

• Completamente basado en genéricos
• Utiliza java.util.Collections para buscar e insertar elementos de lista
• Opción para usar un comparador personalizado para la clasificación de listas

Algunas notas:

• Esta lista ordenada no está sincronizada porque hereda de java.util.ArrayList . Use Collections.synchronizedList si lo necesita (consulte la documentación de Java para java.util.ArrayList para obtener más información).
• La solución inicial se basó en java.util.LinkedList . Para un mejor rendimiento, específicamente para encontrar el punto de inserción (comentario de Logan) y operaciones de obtención más rápida ( https://dzone.com/articles/arraylist-vs-linkedlist-vs ), esto se ha cambiado a java.util.ArrayList .

Answer 6

Para comprobar la eficacia de Konns Holl, hice una comparación rápida con lo que pensé que sería la forma lenta de hacerlo:

package util.collections;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 *
 * @author Earl Bosch
 * @param <E> Comparable Element
 *
 */
public class SortedList<E extends Comparable> implements List<E> {

    /**
     * The list of elements
     */
    private final List<E> list = new ArrayList();

    public E first() {
        return list.get(0);
    }

    public E last() {
        return list.get(list.size() - 1);
    }

    public E mid() {
        return list.get(list.size() >>> 1);
    }

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

    @Override
    public boolean add(E e) {
        list.add(e);
        Collections.sort(list);
        return true;
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public boolean contains(Object obj) {
        return list.contains((E) obj);
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }

    @Override
    public Object[] toArray() {
        return list.toArray();
    }

    @Override
    public <T> T[] toArray(T[] arg0) {
        return list.toArray(arg0);
    }

    @Override
    public boolean remove(Object obj) {
        return list.remove((E) obj);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return list.containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {

        list.addAll(c);
        Collections.sort(list);
        return true;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return list.removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return list.retainAll(c);
    }

    @Override
    public E get(int index) {
        return list.get(index);
    }

    @Override
    public E set(int index, E element) {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public void add(int index, E element) {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public E remove(int index) {
        return list.remove(index);
    }

    @Override
    public int indexOf(Object obj) {
        return list.indexOf((E) obj);
    }

    @Override
    public int lastIndexOf(Object obj) {
        return list.lastIndexOf((E) obj);
    }

    @Override
    public ListIterator<E> listIterator() {
        return list.listIterator();
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return list.listIterator(index);
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        throw new UnsupportedOperationException("Not supported.");
    }

}

¡Resulta ser aproximadamente el doble de rápido! Creo que es debido a SortedLinkList slow get, que no es una buena opción para una lista.

Tiempos comparados para la misma lista aleatoria:

• SortedLinkList: 15731.460
• SortedList: 6895.494
• ca.odell.glazedlists.SortedList: 712.460
• org.apache.commons.collections4.TreeList: 3226.546

Parece glazedlists.SortedList es realmente rápido ...

Answer 7

Parece que desea una estructura de listas con eliminación muy rápida y acceso aleatorio por índice (no por clave) veces. Un ArrayList te da el último y un HashMap o TreeMap te dan el primero.

Hay una estructura en las Colecciones de Apache Commons que puede ser lo que está buscando, la TreeList . JavaDoc especifica que está optimizado para una inserción y eliminación rápida en cualquier índice de la lista. Si también necesitas genéricos, esto no te ayudará.

Answer 8

Phuong:

Clasificando 40,000 números aleatorios:

0.022 segundos

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;


public class test
{
    public static void main(String[] args)
    {
        List<Integer> nums = new ArrayList<Integer>();
        Random rand = new Random();
        for( int i = 0; i < 40000; i++ )
        {
            nums.add( rand.nextInt(Integer.MAX_VALUE) );
        }

        long start = System.nanoTime();
        Collections.sort(nums);
        long end = System.nanoTime();

        System.out.println((end-start)/1e9);
    }
}   

Dado que rara vez necesita clasificación, según la declaración del problema, probablemente sea más eficiente de lo que debe ser.

Answer 9

GlazedLists tiene una muy buena lista de implementación ordenada