Une bonne liste triée pour Java

Question

Je suis à la recherche d'une bonne liste triée pour java. Googler autour de me donner quelques conseils sur l'utilisation de TreeSet/TreeMap. Mais ces composants est le manque d'une chose: l'accès aléatoire à un élément de l'ensemble. Par exemple, je veux accéder à la nième élément dans l'ensemble trié, mais avec TreeSet, je doit itérer sur les autres éléments n-1 avant que je puisse y arriver. Ce serait un gâchis que j'ai serait avez jusqu'à plusieurs milliers d'éléments dans mon Jeu.

En gros, je suis à la recherche de quelque chose de semblable à une liste triée dans .NET, avec la capacité d'ajouter un élément rapide, enlevez l'élément rapide, et ont un accès aléatoire à n'importe quel élément dans la liste.

A ce genre de liste triée mis en œuvre quelque part? Merci.

Édité

Mon intérêt dans SortedList se développe à partir de ces problèmes: J'ai besoin d'tient à jour une liste de plusieurs milliers d'objets (et peut atteindre jusqu'à plusieurs centaines de milliers). Ces objets seront conservées dans la base de données. Je veux choisir au hasard quelques dizaines d'élément de la liste. Donc, j'ai essayé de les maintenir séparés en mémoire une liste qui contient les clés primaires (Long nombre) de tous les objets. J'ai besoin d'ajouter/supprimer des clés de la liste lorsque l'objet est ajouté / supprimé de la base de données. Je suis à l'aide d'une liste de tableaux pour l'instant, mais j'ai peur ArrayList ne conviendra pas à tous quand le nombre de dossiers augmente. (Imaginez que vous avez à parcourir plusieurs centaines de milliers d'éléments à chaque fois qu'un objet est supprimé de la base de données). À l'époque où je l'ai fait .NET de programmation, alors je voudrais utiliser une Liste triée (Liste de est une .NET de classe qu'une fois Triés propriété est définie à vrai, de maintenir l'ordre de son élément, et de fournir des binaires de recherche qui aident à retirer/insérer un élément très rapide). J'espère que je peux trouver quelque chose de similaire à partir de java BCL, mais malheureusement, je n'ai pas trouvé un bon match.

Answer 1

Il semble que vous voulez une structure de liste avec très élimination rapide et aléatoire de l'accès par index (pas par clé) fois. Un ArrayList vous donne celui-ci et un HashMap ou TreeMap vous donner de l'ancien.

Il y a une structure dans Apache Commons Collections qui peut être ce que vous cherchez, la liste arborescente. La JavaDoc précise qu'il est optimisé pour le montage et démontage rapides à un index dans la liste. Si vous avez également besoin de génériques mais, ce ne sera pas vous aider.

Answer 2

C'est le SortedList mise en œuvre que j'utilise. Peut-être que cela aide à résoudre votre problème:

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 LinkedList<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;
    }
    /**
     * Add a new entry to the list. The insertion point is calculated using the
     * comparator.
     * 
     * @param paramT
     */
    @Override
    public boolean add(T paramT) {
        int insertionPoint = Collections.binarySearch(this, paramT, comparator);
        super.add((insertionPoint > -1) ? insertionPoint : (-insertionPoint) - 1, paramT);
        return true;
    }
    /**
     * 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
     */
    @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);
    }
}

Cette solution est très flexible et utilise Java existant fonctions:

• Entièrement basé sur les médicaments génériques
• Utilise java.util.Des Collections pour la recherche et l'insertion d'éléments de la liste
• L'Option d'utiliser un Comparateur pour le tri

Notez que cette liste triée est pas synchronisé depuis il hérite de java.util.LinkedList. L'Utilisation Des Collections.synchronizedList si vous avez besoin de ce (reportez-vous à la documentation de Java pour java.util.LinkedList pour plus de détails).

Answer 3

Phuong:

Tri de 40 000 nombres aléatoires:

0.022 secondes

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

Étant donné que vous avez rarement besoin de trier, selon votre énoncé de problème, ceci est probablement plus efficace que nécessaire.

Answer 4

Selon la façon dont vous utilisez la liste, il peut être intéressant d’utiliser un TreeSet, puis d’utiliser la méthode toArray () à la fin. J'avais un cas où j'avais besoin d'une liste triée, et j'ai trouvé que TreeSet + toArray () était beaucoup plus rapide que d'ajouter à un tableau et de fusionner le tri à la fin.

Answer 5

GlazedLists a une très, très bonne implémentation de liste triée