Liste de tableaux triés en Java

85

Je suis déconcerté de ne pas trouver de réponse rapide à cela. Je recherche essentiellement une structure de données en Java qui implémente l' java.util.Listinterface, mais qui stocke ses membres dans un ordre trié. Je sais que vous pouvez utiliser un normal ArrayListet l'utiliser Collections.sort()dessus, mais j'ai un scénario dans lequel j'ajoute et récupère souvent des membres de ma liste et je ne veux pas avoir à le trier à chaque fois que je récupère un membre au cas où un un nouveau a été ajouté. Quelqu'un peut-il me diriger vers une telle chose qui existe dans le JDK ou même des bibliothèques tierces?

EDIT : La structure de données devra conserver les doublons.

RÉSUMÉ DE RÉPONSE : J'ai trouvé tout cela très intéressant et j'ai beaucoup appris. Aioobe en particulier mérite d'être mentionné pour sa persévérance à essayer de répondre à mes exigences ci-dessus (principalement une implémentation triée de java.util.List qui prend en charge les doublons). J'ai accepté sa réponse comme étant la plus précise pour ce que j'ai demandé et la plupart des réflexions sur les implications de ce que je cherchais même si ce que je demandais n'était pas exactement ce dont j'avais besoin.

Le problème avec ce que j'ai demandé réside dans l'interface List elle-même et le concept de méthodes optionnelles dans une interface. Pour citer le javadoc:

L'utilisateur de cette interface a un contrôle précis sur l'endroit où dans la liste chaque élément est inséré.

L'insertion dans une liste triée n'a pas de contrôle précis sur le point d'insertion. Ensuite, vous devez réfléchir à la manière dont vous allez gérer certaines des méthodes. Prenons addpar exemple:

public boolean add (objet o)

 Appends the specified element to the end of this list (optional operation).

Vous vous retrouvez maintenant dans la situation inconfortable de 1) Rompre le contrat et implémenter une version triée de l'add 2) Laisser addajouter un élément à la fin de la liste, briser votre ordre trié 3) Oublier add(comme facultatif) en lançant an UnsupportedOperationExceptionet implémentant une autre méthode qui ajoute des éléments dans un ordre trié.

L'option 3 est probablement la meilleure, mais je trouve qu'il est peu recommandable d'avoir une méthode add que vous ne pouvez pas utiliser et une autre méthode sortedAdd qui n'est pas dans l'interface.

Autres solutions associées (sans ordre particulier):

  • java.util.PriorityQueue qui est probablement plus proche de ce dont j'avais besoin que de ce que j'ai demandé. Une file d'attente n'est pas la définition la plus précise d'une collection d'objets dans mon cas, mais fonctionnellement, elle fait tout ce dont j'ai besoin.
  • net.sourceforge.nite.util.SortedList . Cependant, cette implémentation rompt le contrat de l'interface List en implémentant le tri dans la add(Object obj)méthode et a bizarrement une méthode sans effet add(int index, Object obj). Le consensus général suggère throw new UnsupportedOperationException()que ce serait un meilleur choix dans ce scénario.
  • TreeMultiSet de Guava Une implémentation d'ensemble qui prend en charge les doublons
  • ca.odell.glazedlists.SortedList Cette classe est accompagnée de la mise en garde dans son javadoc:Warning: This class breaks the contract required by List
Chris Knight
la source
4
Si vous insérez occasionnellement et lisez fréquemment, pourquoi ne pas simplement le trier lors de l'insertion?
serg

Réponses:

62

Solution minimaliste

Voici une solution «minimale».

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

L'insertion s'exécute en temps linéaire, mais c'est ce que vous obtiendriez quand même en utilisant une ArrayList (tous les éléments à droite de l'élément inséré devraient être décalés d'une manière ou d'une autre).

L'insertion de quelque chose de non comparable entraîne une exception ClassCastException. (C'est également l'approche adoptée par PriorityQueue: une file d'attente prioritaire reposant sur un ordre naturel ne permet pas non plus l'insertion d'objets non comparables (cela peut entraîner une exception ClassCastException). )

Primordial List.add

Notez que remplacer List.add(ou List.addAlld'ailleurs) insérer des éléments de manière triée constituerait une violation directe de la spécification d'interface . Ce que vous pouvez faire, c'est remplacer cette méthode pour lancer un fichier UnsupportedOperationException.

D'après la documentation de List.add:

boolean add(E e)
    Ajoute l'élément spécifié à la fin de cette liste (opération facultative).

Le même raisonnement s'applique pour les deux versions de add, les deux versions de addAllet set. (Toutes sont des opérations facultatives selon l'interface de liste.)


Quelques tests

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

.... imprime:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]
aioobe
la source
Un bon début, mais appeler add ou addall ajouterait des membres de manière non triée.
Chris Knight
Oui. Tout sauf les ajouter à la liste serait une violation directe de l'interface de liste. Voir ma réponse mise à jour.
aioobe
@aioobe Bon point. Mais une opération non prise en charge d'une méthode d'interface n'est-elle pas une odeur de code? La bonne façon pourrait être de ne pas étendre ArrayList mais d'implémenter List, mais même dans ce cas, peut-être que List n'était tout simplement pas destiné à cet effet. De la Javadoc for List: The user of this interface has precise control over where in the list each element is insertedqui n'est pas la meilleure description pour insérer des éléments de manière triée et vous devez toujours gérer la add(int index, Object obj)méthode d'interface. Ces problèmes expliquent probablement pourquoi List n'a pas été implémenté de manière triée.
Chris Knight
Eh bien, l'opération est facultative pour une raison. Je ne serais pas surpris si .addj'obtenais un UnsupportedExceptionOperation lors de l'exécution sur un SortedArrayList. Oui, le même raisonnement s'applique aux deux versions de add, les deux versions de addAll et set. (Toutes sont des opérations optionnelles selon l'interface de la liste.)
aioobe
Ah, je ne savais pas que c'était des opérations optionnelles. L'intrigue s'épaissit ...;)
Chris Knight
10

Utilisez java.util.PriorityQueue.

Gadolin
la source
7
ce n'est pas une liste, c'est-à-dire pas d'accès aléatoire.
Thilo
1
C'est un tas de priorité basé sur la file d'attente qui n'implémente pas la liste.
zengr
3
Bien sûr, avec une liste qui maintient l'ordre de tri, les index changent tout le temps, donc l'accès aléatoire n'est probablement pas nécessaire de toute façon.
Thilo
5
@Qwerky, notez que la réponse exacte n'est pas toujours la meilleure réponse ou la réponse recherchée par le PO.
aioobe
3
la file d'attente prioritaire n'accorde pas d'ordre trié sur l'itération.
marcorossi
6

Jetez un œil à SortedList

Cette classe implémente une liste triée. Il est construit avec un comparateur qui peut comparer deux objets et trier les objets en conséquence. Lorsque vous ajoutez un objet à la liste, il est inséré au bon endroit. Les objets qui sont égaux selon le comparateur, seront dans la liste dans l'ordre où ils ont été ajoutés à cette liste. Ajoutez uniquement les objets que le comparateur peut comparer.


Lorsque la liste contient déjà des objets égaux selon le comparateur, le nouvel objet sera inséré immédiatement après ces autres objets.

Jigar Joshi
la source
5
Cela a l'air bien, mais cela semble aussi bogué: il n'y a pas de remplacement de l'une ou l'autre des versions de addAll, donc la liste ne sera pas triée après les avoir appelés.
Tom Anderson
3
Et la méthode add "n'a aucun effet". Il doit plutôt lancer une exception UnsupportedOperationException s'il ne peut pas être utilisé.
Thilo
@Tom Anderson @Thilo, d'accord avec vous deux.
Jigar Joshi
1
Intéressant, mais je me méfie plutôt de quelqu'un à l'avenir qui utilise addAll()et pense que tous les éléments seraient triés. Acceptez également l'exception UnsupportedOperationException.
Chris Knight
1
Quelle est la complexité temporelle de l'ajout à cette liste?
shrini1000
6

Vous pouvez essayer le TreeMultiSet de Guava .

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);
Emil
la source
+1. C'est une excellente bibliothèque. MultiSet estA collection that supports order-independent equality, like Set, but may have duplicate elements
Shervin Asgari
5

L'approche d'Aioobe est la voie à suivre. Je voudrais cependant suggérer l'amélioration suivante par rapport à sa solution.

class SortedList<T> extends ArrayList<T> {

    public void insertSorted(T value) {
        int insertPoint = insertPoint(value);
        add(insertPoint, value);
    }

    /**
     * @return The insert point for a new value. If the value is found the insert point can be any
     * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
     */
    private int insertPoint(T key) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = (Comparable<T>) get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else {
                return mid; // key found
            }
        }

        return low;  // key not found
    }
}

La solution d'aioobe devient très lente lors de l'utilisation de grandes listes. Utiliser le fait que la liste soit triée nous permet de trouver le point d'insertion des nouvelles valeurs en utilisant la recherche binaire.

J'utiliserais aussi la composition plutôt que l'héritage, quelque chose du genre

SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Emanuel Moecklin
la source
4

Les listes conservent généralement l'ordre dans lequel les éléments sont ajoutés. Avez-vous vraiment besoin d'une liste ou un ensemble trié (par exemple TreeSet<E>) vous conviendrait-il? En gros, avez-vous besoin de conserver les doublons?

Jon Skeet
la source
2
Merci Jon, mais je dois préserver les doublons
Chris Knight
2

C'est peut-être un peu trop lourd pour vous, mais GlazedLists a une SortedList qui est parfaite pour être utilisée comme modèle de table ou JList

I82Much
la source
1

Vous pouvez sous-classer ArrayList et appeler Collections.sort (this) après l'ajout d'un élément - vous devrez remplacer deux versions de add et deux de addAll pour ce faire.

Les performances ne seraient pas aussi bonnes qu'une mise en œuvre plus intelligente qui insère des éléments au bon endroit, mais cela ferait le travail. Si l'ajout à la liste est rare, le coût amorti sur toutes les opérations de la liste doit être faible.

Tom Anderson
la source
1

Créez simplement une nouvelle classe comme celle-ci:

public class SortedList<T> extends ArrayList<T> {

private final Comparator<? super T> comparator;

public SortedList() {
    super();
    this.comparator = null;
}

public SortedList(Comparator<T> comparator) {
    super();
    this.comparator = comparator;
}

@Override
public boolean add(T item) {
    int index = comparator == null ? Collections.binarySearch((List<? extends Comparable<? super T>>)this, item) :
            Collections.binarySearch(this, item, comparator);
    if (index < 0) {
        index = index * -1 - 2;
    }
    super.add(index+1, item);
    return true;
}

@Override
public void add(int index, T item) {
    throw new UnsupportedOperationException("'add' with an index is not supported in SortedArrayList");
}

@Override
public boolean addAll(Collection<? extends T> items) {
    boolean allAdded = true;
    for (T item : items) {
        allAdded = allAdded && add(item);
    }
    return allAdded;
}

@Override
public boolean addAll(int index, Collection<? extends T> items) {
    throw new UnsupportedOperationException("'addAll' with an index is not supported in SortedArrayList");
}

}

Vous pouvez le tester comme ceci:

    List<Integer> list = new SortedArrayList<>((Integer i1, Integer i2) -> i1.compareTo(i2));
    for (Integer i : Arrays.asList(4, 7, 3, 8, 9, 25, 20, 23, 52, 3)) {
        list.add(i);
    }
    System.out.println(list);
user13750620
la source
0

Je pense que le choix entre SortedSets / Lists et les collections triables «normales» dépend du fait que vous ayez besoin de trier uniquement à des fins de présentation ou à presque tous les moments de l'exécution. L'utilisation d'une collection triée peut être beaucoup plus coûteuse car le tri est effectué chaque fois que vous insérez un élément.

Si vous ne pouvez pas opter pour une collection dans le JDK, vous pouvez jeter un œil aux collections Apache Commons

codeporn
la source
0

Étant donné que les implémentations actuellement proposées qui implémentent une liste triée en cassant l'API Collection, ont une propre implémentation d'un arbre ou quelque chose de similaire, j'étais curieux de savoir comment une implémentation basée sur TreeMap fonctionnerait. (Surtout puisque le TreeSet se base également sur TreeMap)

Si quelqu'un est également intéressé par cela, il ou elle peut se sentir libre de l'examiner:

TreeList

Il fait partie de la bibliothèque principale , vous pouvez bien sûr l'ajouter via la dépendance Maven. (Licence Apache)

Actuellement, l'implémentation semble se comparer assez bien au même niveau que le guava SortedMultiSet et la TreeList de la bibliothèque Apache Commons.

Mais je serais heureux si plus que moi je testais l'implémentation pour être sûr de ne pas manquer quelque chose d'important.

Meilleures salutations!

Omnaest
la source
0

J'ai eu le même problème. J'ai donc pris le code source de java.util.TreeMap et écrit IndexedTreeMap . Il implémente ma propre IndexedNavigableMap :

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

L'implémentation est basée sur la mise à jour des poids des nœuds dans l'arbre rouge-noir lorsqu'il est modifié. Le poids est le nombre de nœuds enfants sous un nœud donné, plus un - soi. Par exemple, lorsqu'un arbre pivote vers la gauche:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight met simplement à jour les poids jusqu'à la racine:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

Et quand nous avons besoin de trouver l'élément par index, voici l'implémentation qui utilise des poids:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Il est également très pratique de trouver l'index d'une clé:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);

    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

Vous pouvez trouver le résultat de ce travail sur http://code.google.com/p/indexed-tree-map/

TreeSet / TreeMap (ainsi que leurs équivalents indexés du projet indexed-tree-map) n'autorisent pas les clés en double, vous pouvez utiliser 1 clé pour un tableau de valeurs. Si vous avez besoin d'un SortedSet avec des doublons, utilisez TreeMap avec des valeurs sous forme de tableaux. Je ferais ça.

Vitaly Sazanovich
la source