* Par tout, je veux dire l'exécution relativement rapide des opérations sur un seul élément d'un tableau.Les structures de données qui implémentent la liste sont complètes. Chacun a ses avantages et ses inconvénients. Par exemple, dans le monde Java - selon les opérations nécessaires - vous pouvez utiliser:- add (obj), get (obj), set (index, obj): un ensemble de base de presque toutes les listes, par exemple ArrayList.
- add (index, obj): structures arborescentes, par exemple TreeList from apache common-collections.
- remove (index): comme ci-dessus.
- contient (obj), indexOf (obj): vous pouvez utiliser un tas d'ArrayList et HashMap.
- remove (obj): ... j'ai du mal à répondre. Dans certains cas, vous pouvez vous en tirer avec un LinkedHashSet. Il est résolu trivialement en présence des deux points précédents, mais quelles structures peuvent à la fois rapidement?
Lorsque j'avais besoin d'une structure avec ajout rapide (obj), get (index), remove (index) et indexOf (obj), google n'a pas donné de réponse. Je n'ai trouvé aucun exemple de code ou description de telles structures. Peut-être que je n'y regardais pas, j'ai dû l'inventer moi-même. Mais si quelqu'un laisse tomber le lien dans les commentaires, je l'apprécierai grandement.Peut-être que quelqu'un a réalisé que vous pouvez prendre une TreeList, qui peut rapidement insérer / supprimer des éléments au milieu de la liste et ajouter un HashMap de l'objet à l'index dans la TreeList pour une exécution rapide de indexOf (obj). Et ce sera une décision simple, élégante, mais incorrecte. Après tout, lors de l'ajout au milieu ou de la suppression du milieu, il sera nécessaire de recalculer les indices, en moyenne, pour la moitié des éléments. Cela dégradera les performances en O (n).Ensuite, je vais parler d'une structure de données qui peut faire tout ce qui précède. Qui effectue toute opération sur un élément en temps O (log (n)). Eh bien, presque - car le logarithme est effectué dans le cas où tous les objets de la liste sont différents. Si la liste contient les mêmes objets, il est possible d'affaiblir les performances jusqu'à O (log (n) ^ 2).Je vous préviens tout de suite que je ne peindrai pas le code ici. Cela peut être assez compliqué pour l'article. Mais c'est écrit en Java. Basé sur la classe TreeList d'Apache Common-Collections. La demande de tirage existe déjà, mais au moment de la rédaction, l'article n'est pas encore versé.De plus, je ne décrirai pas des algorithmes bien connus. Par exemple, les algorithmes d'équilibrage des arbres. Pour la plupart, il peut suffire de tenir pour acquis le fait que l'arbre peut être maintenu en équilibre. Cela n'affecte pas la compréhension de l'idée générale. Ceux qui veulent en savoir plus peuvent facilement trouver des informations. Mais je vais vous parler très brièvement de certaines choses de base, car sans la connaissance des bases, de nombreux éléments clés ne peuvent pas être compris.Les liens seront à la fin.Pourquoi est-ce nécessaire
En fait, ce n'est pas si facile de trouver des situations où tout est nécessaire directement à partir de la liste. Il est peu probable que ce soit une sorte de structure super nécessaire, sinon tout le monde le saurait. Cependant, quelques exemples où une telle liste pourrait être utile peuvent être donnés.Je reconnais que de nombreux exemples sont farfelus. Tout ou presque peut être résolu d'une autre manière.Mise en cache et compression
Ma tâche initiale, à cause de laquelle j'ai commencé à rechercher la question. Joué avec la compression de données spécifiques et avait besoin d'une liste pour le cache d'objets.L'idée est la suivante: lors du traitement d'un autre objet, nous le recherchons dans la liste. S'il n'est pas trouvé, enregistrez l'objet et ajoutez-le en haut de la liste. S'il est trouvé, nous prenons son index dans la liste et au lieu de l'objet, nous enregistrons uniquement son index, après quoi nous déplaçons l'objet en haut de la liste. Ainsi, les objets qui se produisent reçoivent souvent de petits index et les objets qui se produisent une seule fois finissent par se déplacer à la fin de la liste et sont supprimés.Tour
Si, au lieu de la file d'attente FIFO habituelle, pour certaines tâches, une structure similaire est utilisée, les opérations suivantes peuvent être effectuées:- Répondez à la question: combien de tâches sont dans la file d'attente avant cette tâche.
- Supprimez les tâches de la file d'attente.
C’est comme dans un supermarché. Si vous êtes venu pour une barre de chocolat, mais que vous voyez que la ligne se déplace lentement, alors peut-être que la barre de chocolat n'est pas si nécessaire? :)Tableau des meilleurs scores
Supposons que nous voulons stocker le temps pendant lequel les joueurs terminent un niveau dans une partie. Il y a beaucoup de joueurs et ils s'affrontent tous, essayant de montrer le temps minimum. Les données des joueurs peuvent être placées dans un tableau et triées par heure. En utilisant cette structure, vous pouvez:- Déplacez les joueurs plus haut dans la liste s'ils montrent de meilleurs résultats qu'auparavant.
- Supprimez des joueurs de la liste, par exemple, en cas d'interdiction de tricherie.
- Montrez à chaque joueur où il se trouve.
- Afficher le tableau des enregistrements page par page.
- Afficher une table clairsemée à des endroits, par exemple, temps 1, 2, 3, 5, 10, 20, 50, 100, 1000, 10000 endroits.
Structure de données
La structure est basée sur un arbre avec une clé implicite. C'est sur cette approche, par exemple, que se base TreeList dans apache common-collections. Pour continuer, vous devez comprendre le fonctionnement de cette structure.Arbre de clé implicite
Un arbre se compose de nœuds (nœuds). Chaque nœud contient un lien vers un objet qui est stocké dans le nœud et 2 liens vers d'autres nœuds: gauche et droite. Le nœud supérieur est appelé nœud racine. Dans le cas le plus simple, le nœud ressemble à ceci:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
}
Dans l'arbre binaire classique pour chaque nœud dans le sous-arbre gauche, tous les objets sont plus petits que dans le nœud actuel, et dans la droite - grands. Par exemple: [ element: 25 ]
/ \
/ \
[ element: 14 ] [ element: 45 ]
/ \ / \
/ \ / \
[ element: 10 ] [ element: 22 ] [ element: 27 ] [ element: 90 ]
/ \ /
/ \ /
[ element: 17 ] [ element: 23 ] [ element: 80 ]
Mais pour notre objectif, un tel arbre ne convient pas. Nous n'avons pas besoin de stocker les objets triés, mais nous devons y avoir accès par index, comme dans un tableau.Comment puis-je mettre un tableau dans un arbre? Sélectionnons un élément d'index i au milieu du tableau. Placez le ième élément du tableau dans le nœud racine. 2 sous-arbres quittent le nœud racine. Dans le sous-arbre gauche, nous mettons la moitié du tableau avec index <i, et dans le droit avec index> i. Comment faire? De la même manière: nous sélectionnons un élément du milieu dans un sous-tableau, mettons cet élément dans un nœud, nous obtenons 2 sous-réseaux plus petits. Et donc jusqu'à ce que nous mettions tous les éléments du tableau dans les nœuds de l'arbre.Par exemple, un tableau avec les éléments ["q", "w", "e", "r", "t", "y", "u"] pourrait ressembler à ceci: [el: r, size: 7]
/ : \
/ : \
[el: w, size: 3] : [el: y, size: 3]
/ : \ : / : \
/ : \ : / : \
[el: q, size: 1] : [el: e, size: 1] : [el: t, size: 1] : [el: u, size: 1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
L'élément du milieu dans le tableau «r», nous le mettons dans le nœud racine. Deux sous-réseaux ["q", "w", "e"] et ["t", "y", "u"] sont placés dans les sous-arbres gauche et droit. Pour cela, les éléments centraux sont sélectionnés dans les sous-réseaux, dans notre cas ce sont «w» et «y», et ils tombent dans les nœuds du niveau suivant. Et ainsi de suite.Dans notre cas, l'arbre est équilibré, la profondeur de tous les sous-arbres est la même. Mais il ne doit pas en être ainsi.Dans l'image ci-dessus, chaque nœud, en plus de l'élément et des liens vers les nœuds gauche et droit, contient le nombre d'éléments de l'ensemble du sous-arbre. Ces informations doivent être mises à jour correctement lorsque l'arborescence change.Voyons comment trouver, par exemple, un élément avec index = 4 dans un tel arbre.Nous commençons l'analyse à partir du nœud racine (racine, dans notre cas avec l'élément «r»). Nous avons 3 options: nous sommes déjà sur le nœud droit, le nœud droit sur la gauche, le nœud droit sur la droite. Afin de comprendre où chercher l'élément souhaité, vous devez comparer la taille du sous-arbre gauche (dans notre cas, left.size = 3) et l'indice actuel (dans notre cas 4). Si ces 2 nombres sont égaux, alors nous y avons trouvé le nœud nécessaire et l'élément souhaité. Si la taille du sous-arbre gauche est plus grande, alors le nœud requis dans le sous-arbre gauche. Si c'est moins, alors vous devez regarder dans le sous-arbre de droite, mais vous devez réduire l'index souhaité: index = index - left.size - 1.Étant donné que dans notre cas, left.size <index, nous recherchons dans le sous-arbre de droite l'élément avec le nouvel index 4 - 3 - 1 = 0. Accédez au nœud avec l'élément «y».Ensuite, nous faisons la même chose que nous avons fait dans le nœud racine. Comparez left.size et index. Depuis 1> 0, nous regardons dans le sous-arbre gauche, passons au nœud avec l'élément «t».Il n'y a pas de sous-arbre gauche dans ce noeud, et sa taille est 0. index = left.size, ce qui signifie que nous avons trouvé un noeud avec l'index 4 et pouvons en obtenir l'élément "t" requis.En pseudo code, cela ressemble à ceci:function get(node: Node<T>, index: int): T {
val leftSize: int = (node.left == null) ? 0 : node.left.size;
if (leftSize == index) {
return node.obj;
} else if (leftSize > index) {
return get(node.left, index);
} else {
return get(node.right, index — leftSize — 1);
}
}
J'ai essayé de décrire le principe clé de la façon de mettre un tableau dans un arbre. Une telle structure fonctionne, bien sûr, plus lentement que le tableau classique, pour O (log (n)) contre O (1). Mais il présente un avantage important: l'ajout d'un élément au milieu ou la suppression du milieu fonctionne également pour O (log (n)) par rapport à O (n) pour le tableau. Bien sûr, à condition que l'arbre soit plus ou moins équilibré. Il existe de nombreux algorithmes pour maintenir un arbre de manière presque équilibrée. Par exemple, arbre rouge-noir, arbre AVL, arbre cartésien. Je n'écrirai pas les détails de l'équilibrage de l'arbre, tout algorithme nous convient. Supposons simplement que l'arbre est équilibré en moyenne et que sa profondeur maximale n'est pas très différente du minimum.Légère optimisation
L'approche décrite ci-dessus, avec la vérification de la taille de l'arbre à gauche est pratique pour la perception, mais peut être effectuée un peu plus efficacement. Afin de ne pas regarder dans le sous-arbre gauche à chaque fois, au lieu de la taille de l'arbre, on peut stocker dans le nœud sa position par rapport à la position de son nœud parent. Le nœud racine stocke une position absolue qui correspond à la taille du sous-arbre gauche. [el: r, pos: 3]
/ : \
/ : \
[el: w, pos: -2] : [el: y, pos: +2]
/ : \ : / : \
/ : \ : / : \
[el: q, pos: -1] : [el: e, pos: +1] : [el: t, pos: -1] : [el: u, pos: +1]
: : : : : : :
: : : : : : :
[q] [w] [e] [r] [t] [y] [u]
Index: 0 1 2 3 4 5 6
Par exemple, le nœud racine «r» a la position 3. Le nœud «w» a la position -2 par rapport au nœud parent ou la position absolue 3 + (-2) = 1. De même, vous pouvez descendre d'un niveau supplémentaire, par exemple, le nœud «e» a la position 3 + (-2) + (+1) = 2. Autrement dit, l'indice de nœud est la somme des positions de la racine de l'arbre à ce nœud.Cette optimisation, en plus d'une recherche plus rapide d'un élément dans la liste, permettra une recherche plus rapide et plus facile de l'index sur le nœud. Mais, bien sûr, la mise à jour correcte de la position lors du changement d'arbre est devenue un peu plus difficile.Ajouter l'indexation
Ainsi, dans l'arbre, nous pouvons prendre un élément par index, changer sa valeur, ajouter des éléments au milieu et supprimer. Essentiellement, nous avons juste besoin d'ajouter une recherche d'index rapide par valeur, indexOf (obj). Ensuite, contient (obj) et supprimer (obj) sera résolu trivialement.Mais d'abord, simplifions un peu la tâche. Faisons une structure qui ne stocke que des éléments uniques.Afin de rechercher rapidement quelque chose, ils utilisent généralement une table. Dans le monde Java, les tables sont appelées Map; elles ont 2 implémentations principales: HashMap et TreeMap. La clé de la table sera un lien vers l'objet et la valeur sera un lien vers son nœud:class IndexedTreeListSet<T> {
root: Node<T>
indexMap: Map<T, Node<T>>
}
Ceux. la structure se compose de deux parties: l'arborescence de la liste elle-même et le tableau avec des liens vers les objets et les nœuds de cet arbre. Lors de la mise à jour de l'arborescence, la table doit également être mise à jour. Je ne décrirai pas le processus en détail. Intuitivement, cela devrait être compréhensible: ajoutez un nœud - mettez-le dans le tableau, supprimez le nœud - supprimez-le de la table. Dans la pratique, il y a des nuances à équilibrer l'arbre: l'algorithme doit changer les liens entre les nœuds et ne pas déplacer les objets entre les nœuds. Sinon, vous devrez effectuer de nombreuses mises à jour dans le tableau et les performances chuteront.Ok, nous supposerons que nous pouvons trouver rapidement le nœud par l'élément qu'il contient. Et alors? Nous devons trouver son index, mais cela ne peut pas encore être fait. Mais nous pouvons compliquer la classe de nœuds afin qu'elle contienne non seulement des liens vers les nœuds gauche et droit, mais aussi vers son parent:class Node<T> {
obj: T
left: Node<T>
right: Node<T>
parent: Node<T>
pos: int
}
Bien sûr, la mise à jour de l'arbre est un peu plus compliquée, car maintenant nous devons soigneusement mettre à jour le lien vers le parent. Mais maintenant, connaissant le nœud, nous pouvons remonter dans l'arbre et calculer l'indice de n'importe quel nœud. Si nous avons utilisé l'optimisation du chapitre précédent, il nous suffit de calculer la somme des positions du nœud actuel à la racine.Pour une liste contenant des éléments uniques, le problème peut être considéré comme résolu.Certes, nous avons un petit problème. Supposons que nous appelons set (index, obj). Nous pouvons facilement remplacer un élément d'un nœud par un autre, mais uniquement s'il n'y a pas encore de nouvel élément dans la liste. Et si oui, que dois-je faire? Retirer l'article en excès de l'ancienne position et en mettre un nouveau? Ou vice versa, ajoutez d'abord, puis supprimez? Le résultat peut être différent. Et vous ne pouvez rien faire du tout ou lever une exception. Il n'y a pas de solution parfaite.Le tri par des méthodes standard d'une telle liste, très probablement, ne fonctionnera pas non plus. Après tout, l'algorithme de tri ne connaîtra pas la nécessité d'unicité des objets et créera des doublons lors du déplacement des éléments dans la liste.Nous supprimons l'unicité
Ok, compliquant encore les choses, gardons les mêmes objets. De toute évidence, vous devez faire quelque chose avec la table. La première idée d'y stocker une liste de nœuds ne semble pas très bonne: avec une augmentation de la longueur de la liste, les performances vont se dégrader. Jusqu'à O (n) si tous les éléments de la liste sont identiques.Essayons ensuite de stocker un arbre trié de nœuds dans une table au lieu d'une liste. Trié par position dans la liste.class IndexedTreeList<T> {
root: Node<T>
indexMap: Map<T, TreeSet<Node<T>>>
}
Ensuite, l'insertion / suppression vers / depuis le TreeSet <Node> de taille m se produira pendant les comparaisons log (m) des positions des nœuds, et chaque comparaison se produira sur la durée log (n). La complexité finale de l'insertion ou de la suppression dans une structure similaire se produira dans O (log (n) * (1 + log (m))), où n est le nombre total d'éléments dans la liste et m est le nombre d'éléments dans la liste égal à l'inséré / supprimé. Dans le pire des cas, lorsque tous les éléments sont égaux, on obtient la complexité O (log (n) ^ 2).Un lecteur attentif objectera probablement: mais qu'en est-il de l'immuabilité? Après tout, nous ne pouvons pas changer les objets s'ils sont des clés de table? En général, c'est le cas. Cependant, pour un arbre qui stocke des objets triés dans des clés, en plus des règles standard de comparaison, il suffit de conserver l'invariant: si a <b, alors cette propriété ne doit pas changer avec le temps. C'est juste notre cas: si la position d'un nœud est inférieure à la position d'un autre nœud, alors cette propriété sera préservée quel que soit le nombre de nœuds ajoutés ou supprimés entre eux.Est-il possible de rendre la structure persistante?
Réponse courte: non, c'est impossible. En raison de la biconnectivité de l'arbre, de la racine aux feuilles et en arrière, nous avons chaque nœud d'arbre connecté à chacun. La persistance ne peut pas être effectuée de cette manière; vous devez recréer la structure entière avec n'importe quel changement.Mais j'ai une compréhension de la façon de mettre en œuvre une structure persistante pour les cas où nous n'avons pas besoin d'insérer des éléments au milieu de la liste. Vous pouvez ajouter des éléments au début ou à la fin, et vous pouvez supprimer du milieu. Les propriétés restantes sont les mêmes.Si cela vous intéresse, je vais essayer d'écrire un article sur cette structure. Peut-être même que je l'implémente en Java, Kotlin ou Scala. Mais, très probablement, ce ne sera pas bientôt.Quelques fonctionnalités d'implémentation
Ici, je veux décrire certaines caractéristiques auxquelles j'ai dû faire face.À propos de l'une des optimisations concernant le stockage de la position du nœud dans la liste, j'ai écrit ci-dessus. Ici, la force de l'Open Source se manifeste: j'ai pris le code TreeList prêt à l'emploi et je n'ai pas fouillé les détails de l'arborescence AVL, les rotations de nœuds, les mises à jour de position, etc.Une autre fonctionnalité héritée de TreeList est les liens vers les sous-arbres dans les feuilles des arbres. Chaque nœud stocke les booléens leftIsPrevious et rightIsNext. Ces variables indiquent la présence ou l'absence d'un sous-arbre gauche / droit. S'il n'y a pas de sous-arbre, alors à gauche / droite, au lieu d'un lien vers le sous-arbre, un lien vers le nœud qui correspond à l'élément précédent ou suivant est stocké. Dans notre exemple, ["q", "w", "e", "r", "t", "y", "u"] le nœud "e" est feuillu, il n'a pas de sous-arbres. En conséquence, leftIsPrevious et rightIsNext sont vrais, et gauche et droite pointent vers les nœuds "w" et "r", respectivement. Cette approche permet de parcourir la liste plus rapidement. Et cela interfère avec la programmation de nouvelles fonctionnalités :)Un peu sur l'utilisation de l'objet table → nœud. Idéalement, vous devez placer un élément dans le tableau une fois lors de son ajout à la structure et le supprimer une fois lors de la suppression de la structure. En pratique, je n'ai pas pu y parvenir. Lorsque vous ajoutez un élément, il est ajouté au tableau, tout est comme il se doit. Cependant, lorsque vous supprimez un élément, l'algorithme d'équilibrage déplace parfois des éléments entre les nœuds. Le résultat est deux suppressions et un enregistrement dans la table au lieu d'une suppression. Cela peut être résolu si vous supprimez l'optimisation de leftIsPrevious et rightIsNext. Et même obtenir un petit gain de performances, et pas seulement lors de la suppression. Dans certains tests, l'augmentation était de 10 à 20%. Mais la vitesse d'itération chute considérablement, 1,5 à 2,5 fois dans mes tests. J'ai décidé de laisser l'optimisation pour l'instant.En Java, les principaux types de tables sont HashMap et TreeMap. Pour une table, un objet → un nœud utilise HashMap par défaut. Cependant, vous pouvez utiliser TreeMap avec un comparateur spécifique à la tâche. Dans ce cas, indexOf (obj) et remove (obj) rechercheront / supprimeront l'objet qui est égal à l'objet spécifié selon le code du comparateur. Par exemple, nous stockons une liste d'utilisateurs et le comparateur compare les utilisateurs uniquement par leur nom. Ensuite, nous pouvons répondre à la question «Quelles positions de la liste sont les utilisateurs avec le nom« Napoléon? »». Ou supprimez tous les Napoléon de la liste :).La structure ne prend pas en charge null. Vous pouvez le réparer, mais il n'y a aucun sentiment que c'est nécessaire.En ce qui concerne le fait que la structure «sait tout», j'étais bien sûr un peu trompeur. Bien sûr, lorsque vous travaillez avec des éléments uniques, tout va bien et dans certaines conditions, même pour le logarithme. Cependant, elle ne sait pas certaines choses que d'autres structures peuvent. Par exemple, un arbre cartésien avec une clé implicite, il y avait des articles à ce sujet sur le hub Il ne sait pas comment faire rapidement indexOf, mais il peut faire une sous-liste et concaténer deux listes en une pour le logarithme (en moyenne, non garanti), en plus il peut être rendu persistant.Performance
En Java, les performances sont généralement mesurées à l'aide du framework jmh. Des tests ont été effectués sur le MacBook Pro 2017 sous Java11.J'ai comparé les performances de la ArrayList standard, TreeList de apache common-collections, et mes deux classes IndexedTreeList et IndexedTreeListSet dans plusieurs scénarios. Dans chaque scénario, 1000 opérations du même type ont été effectuées, le résultat doit donc être multiplié par 1000.Code sous le spoiler@Fork(1)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public class PerformanceCompare {
public static final Map<String, Class> CLASSES = Stream.of(TreeList.class, IndexedTreeListSet.class, IndexedTreeList.class,
ArrayList.class)
.collect(Collectors.toMap(c -> c.getSimpleName(), c -> c));
public static final int ITERATIONS = 1000;
@State(Scope.Benchmark)
public static class Plan {
@Param({"10", "100", "1000", "10000", "100000", "1000000"/*, "10000000"*/})
public int size;
@Param({"ArrayList", "TreeList", "IndexedTreeList", "IndexedTreeListSet"})
public String className;
private Random random;
private List<Integer> list;
@Setup
public void init() throws IllegalAccessException, InstantiationException {
random = new Random();
list = (List<Integer>) CLASSES.get(className).newInstance();
for (int i = 0; i < size; i++) {
list.add(i);
}
}
}
@Benchmark
public void indexOfKnown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value = list.indexOf(random.nextInt(plan.size));
}
blackhole.consume(value);
}
@Benchmark
public void indexOfUnknown(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.indexOf(random.nextInt());
}
blackhole.consume(value);
}
@Benchmark
public void addRemoveRandom(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
list.add(random.nextInt(list.size() + 1), random.nextInt());
value += list.remove(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Benchmark
public void get(Plan plan, Blackhole blackhole) {
List<Integer> list = plan.list;
Random random = plan.random;
int value = 0;
for (int i = 0; i < ITERATIONS; i++) {
value += list.get(random.nextInt(list.size()));
}
blackhole.consume(value);
}
@Timeout(time = 1, timeUnit = TimeUnit.MILLISECONDS)
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(PerformanceCompare.class.getSimpleName())
.forks(1)
.build();
new Runner(opt).run();
}
}
Pour commencer, j'ai comparé la vitesse d'obtention d'un élément aléatoire dans une liste. Je vous préviens tout de suite que dans ce test, les frais généraux sont très importants. Les résultats approchant 100 000 * 1 000 opérations par seconde sont gravement faussés.Obtenez le résultat du testPerformanceCompare.get ArrayList 10 thrpt 5 79865.412 ± 10145.202 ops/s
PerformanceCompare.get ArrayList 100 thrpt 5 81862.243 ± 983.727 ops/s
PerformanceCompare.get ArrayList 1000 thrpt 5 81033.507 ± 4540.206 ops/s
PerformanceCompare.get ArrayList 10000 thrpt 5 64096.123 ± 1430.361 ops/s
PerformanceCompare.get ArrayList 100000 thrpt 5 41289.491 ± 11286.114 ops/s
PerformanceCompare.get ArrayList 1000000 thrpt 5 8598.944 ± 2048.461 ops/s
PerformanceCompare.get TreeList 10 thrpt 5 33912.275 ± 3754.284 ops/s
PerformanceCompare.get TreeList 100 thrpt 5 21346.854 ± 863.588 ops/s
PerformanceCompare.get TreeList 1000 thrpt 5 14808.414 ± 508.098 ops/s
PerformanceCompare.get TreeList 10000 thrpt 5 8679.384 ± 109.250 ops/s
PerformanceCompare.get TreeList 100000 thrpt 5 4605.998 ± 1028.945 ops/s
PerformanceCompare.get TreeList 1000000 thrpt 5 2241.381 ± 768.147 ops/s
PerformanceCompare.get IndexedTreeList 10 thrpt 5 34054.357 ± 3682.829 ops/s
PerformanceCompare.get IndexedTreeList 100 thrpt 5 21934.002 ± 2339.947 ops/s
PerformanceCompare.get IndexedTreeList 1000 thrpt 5 14626.691 ± 369.893 ops/s
PerformanceCompare.get IndexedTreeList 10000 thrpt 5 7386.863 ± 342.150 ops/s
PerformanceCompare.get IndexedTreeList 100000 thrpt 5 4562.126 ± 352.772 ops/s
PerformanceCompare.get IndexedTreeList 1000000 thrpt 5 2105.718 ± 702.064 ops/s
PerformanceCompare.get IndexedTreeListSet 10 thrpt 5 33317.503 ± 2307.829 ops/s
PerformanceCompare.get IndexedTreeListSet 100 thrpt 5 21247.440 ± 1253.386 ops/s
PerformanceCompare.get IndexedTreeListSet 1000 thrpt 5 14665.557 ± 487.833 ops/s
PerformanceCompare.get IndexedTreeListSet 10000 thrpt 5 7667.214 ± 80.093 ops/s
PerformanceCompare.get IndexedTreeListSet 100000 thrpt 5 3454.023 ± 82.994 ops/s
PerformanceCompare.get IndexedTreeListSet 1000000 thrpt 5 1768.701 ± 35.878 ops/s
Ici, curieusement, le plus grand intérêt est le ArrayList standard. Théoriquement, la vitesse de sortie devrait être constante et ne pas dépendre du nombre d'éléments. En pratique, les performances détiennent d'abord environ 90 000 * 1 000 opérations par seconde (rappelez-vous les frais généraux), mais avec une longueur de liste de plusieurs milliers d'éléments, elles commencent à s'affaisser. Cela est dû au manque de cache de plus en plus fréquent: le cache du processeur n'a pas les données nécessaires et de plus en plus souvent vous devez aller chercher des données dans la RAM. Avec un million d'éléments, la vitesse du test est 10 fois inférieure, mais en pratique, le rabattement des performances est encore plus important.TreeList, IndexedTreeList et IndexedTreeListSet devraient afficher des résultats similaires. Attendu beaucoup plus lentement qu'ArrayList. Même avec un petit nombre d'éléments, TreeList est plusieurs fois plus lent qu'ArrayList, bien que le test ne montre la différence que 2 fois.Le prochain test est addRemoveRandom. Ici, dans chaque test, j'insère un élément dans une position aléatoire et je supprime un élément d'une position aléatoire.Résultat du test AddRemoveRandomPerformanceCompare.addRemoveRandom ArrayList 10 thrpt 5 12440.764 ± 485.642 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100 thrpt 5 9880.123 ± 464.014 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000 thrpt 5 5288.905 ± 1219.055 ops/s
PerformanceCompare.addRemoveRandom ArrayList 10000 thrpt 5 1024.942 ± 179.366 ops/s
PerformanceCompare.addRemoveRandom ArrayList 100000 thrpt 5 91.219 ± 25.380 ops/s
PerformanceCompare.addRemoveRandom ArrayList 1000000 thrpt 5 5.499 ± 0.400 ops/s
PerformanceCompare.addRemoveRandom TreeList 10 thrpt 5 6242.607 ± 350.290 ops/s
PerformanceCompare.addRemoveRandom TreeList 100 thrpt 5 3117.945 ± 116.066 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000 thrpt 5 1829.778 ± 80.516 ops/s
PerformanceCompare.addRemoveRandom TreeList 10000 thrpt 5 1230.077 ± 53.381 ops/s
PerformanceCompare.addRemoveRandom TreeList 100000 thrpt 5 443.571 ± 69.207 ops/s
PerformanceCompare.addRemoveRandom TreeList 1000000 thrpt 5 308.963 ± 84.077 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10 thrpt 5 3556.511 ± 144.596 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100 thrpt 5 2120.777 ± 83.848 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000 thrpt 5 1211.112 ± 92.288 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 10000 thrpt 5 789.458 ± 19.450 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 100000 thrpt 5 302.989 ± 40.030 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeList 1000000 thrpt 5 178.822 ± 92.853 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10 thrpt 5 4138.007 ± 119.943 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100 thrpt 5 2435.803 ± 20.276 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000 thrpt 5 1445.054 ± 276.909 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 10000 thrpt 5 972.256 ± 19.987 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 100000 thrpt 5 366.608 ± 94.487 ops/s
PerformanceCompare.addRemoveRandom IndexedTreeListSet 1000000 thrpt 5 227.677 ± 48.276 ops/s
On pourrait supposer qu'ArrayList est plus rapide sur de petites listes. Cependant, le fait qu'il gagne dans ce test sur des listes allant jusqu'à 10 000 éléments semble intéressant. Apparemment, System.arrayCopy est très bien optimisé et utilise toutes les fonctionnalités des processeurs modernes. À partir de 10 000 éléments, les structures de données spécialisées commencent à gagner. Avec 1 000 000 d'éléments, la différence de vitesse est de 30 à 50 fois.IndexedTreeList et IndexedTreeListSet devraient être plus lents que TreeList. Environ 1,5 à 2 fois.Les 2 tests restants indexOfKnown et indexOfUnknown devraient simplement démontrer la caractéristique principale de cette structure. La différence entre les tests est que dans un cas, nous recherchons un élément qui est dans la liste, et dans l'autre cas, nous recherchons un élément qui n'est pas dans la liste.Résultat du test indexOfKnown et indexOfUnknownPerformanceCompare.indexOfKnown ArrayList 10 thrpt 5 41424.356 ± 549.047 ops/s
PerformanceCompare.indexOfKnown ArrayList 100 thrpt 5 17216.477 ± 1444.744 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000 thrpt 5 2296.306 ± 76.372 ops/s
PerformanceCompare.indexOfKnown ArrayList 10000 thrpt 5 233.863 ± 26.926 ops/s
PerformanceCompare.indexOfKnown ArrayList 100000 thrpt 5 23.208 ± 2.776 ops/s
PerformanceCompare.indexOfKnown ArrayList 1000000 thrpt 5 0.919 ± 0.455 ops/s
PerformanceCompare.indexOfKnown TreeList 10 thrpt 5 26740.708 ± 1323.125 ops/s
PerformanceCompare.indexOfKnown TreeList 100 thrpt 5 5670.923 ± 99.638 ops/s
PerformanceCompare.indexOfKnown TreeList 1000 thrpt 5 745.408 ± 26.827 ops/s
PerformanceCompare.indexOfKnown TreeList 10000 thrpt 5 52.288 ± 1.362 ops/s
PerformanceCompare.indexOfKnown TreeList 100000 thrpt 5 4.224 ± 0.855 ops/s
PerformanceCompare.indexOfKnown TreeList 1000000 thrpt 5 0.193 ± 0.052 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10 thrpt 5 34485.128 ± 1582.703 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100 thrpt 5 29209.412 ± 1544.268 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000 thrpt 5 21139.584 ± 1442.867 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 10000 thrpt 5 12544.306 ± 312.097 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 100000 thrpt 5 3538.201 ± 272.537 ops/s
PerformanceCompare.indexOfKnown IndexedTreeList 1000000 thrpt 5 1420.119 ± 538.476 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10 thrpt 5 39201.995 ± 1887.065 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100 thrpt 5 34204.112 ± 1122.517 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000 thrpt 5 25374.557 ± 1596.746 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 10000 thrpt 5 14291.317 ± 391.180 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 100000 thrpt 5 4215.898 ± 283.680 ops/s
PerformanceCompare.indexOfKnown IndexedTreeListSet 1000000 thrpt 5 1729.100 ± 1260.815 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10 thrpt 5 59053.313 ± 1845.665 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100 thrpt 5 10867.572 ± 142.823 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000 thrpt 5 1186.583 ± 28.003 ops/s
PerformanceCompare.indexOfUnknown ArrayList 10000 thrpt 5 120.953 ± 4.146 ops/s
PerformanceCompare.indexOfUnknown ArrayList 100000 thrpt 5 11.936 ± 0.320 ops/s
PerformanceCompare.indexOfUnknown ArrayList 1000000 thrpt 5 0.566 ± 0.335 ops/s
PerformanceCompare.indexOfUnknown TreeList 10 thrpt 5 28134.237 ± 2291.670 ops/s
PerformanceCompare.indexOfUnknown TreeList 100 thrpt 5 3153.930 ± 158.734 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000 thrpt 5 322.383 ± 44.245 ops/s
PerformanceCompare.indexOfUnknown TreeList 10000 thrpt 5 25.674 ± 1.787 ops/s
PerformanceCompare.indexOfUnknown TreeList 100000 thrpt 5 1.867 ± 0.291 ops/s
PerformanceCompare.indexOfUnknown TreeList 1000000 thrpt 5 0.093 ± 0.008 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10 thrpt 5 66625.126 ± 5232.668 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100 thrpt 5 70038.055 ± 5803.848 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000 thrpt 5 63240.467 ± 885.956 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 10000 thrpt 5 54731.988 ± 3950.150 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 100000 thrpt 5 22049.476 ± 821.924 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeList 1000000 thrpt 5 9459.862 ± 804.738 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10 thrpt 5 70274.968 ± 15830.355 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100 thrpt 5 71017.685 ± 6920.447 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000 thrpt 5 66405.960 ± 1127.231 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 10000 thrpt 5 57983.963 ± 3276.142 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 100000 thrpt 5 41277.110 ± 9919.893 ops/s
PerformanceCompare.indexOfUnknown IndexedTreeListSet 1000000 thrpt 5 9840.185 ± 2159.352 ops/s
Ici, ArrayList et TreeList n'ont presque aucune surprise. Avec une taille croissante, la vitesse diminue presque linéairement. La recherche d'un élément d'une non-liste devrait être 2 fois plus lente que la recherche d'un élément de la liste, car vous devez parcourir l'ensemble du tableau au lieu de la moitié en moyenne.Mais IndexedTreeList et IndexedTreeListSet montrent ici le bon résultat attendu. Ces structures de données montrent une vitesse d'exécution indexOf comparable à ArrayList même avec 10 éléments. Avec 1 000 éléments, ces structures sont 10 fois plus rapides, avec 1 000 000 plus rapides 1 000 fois. Lors de la recherche d'un élément qui ne figure pas dans la liste, ils sont censés donner une meilleure vitesse que lors de la recherche d'un élément dans la liste.Il est également intéressant de prêter attention à l'affaissement des performances d'IndexedTreeList et IndexedTreeListSet dans le test indexOfUnknown. Ici, la situation est similaire à celle du test avec ArrayList.get. Théoriquement, nous n'aurions pas dû obtenir une baisse des performances, mais dans la pratique, en raison d'un échec de cache, nous l'avons obtenu, en outre, de manière significative.Au lieu d'une conclusion
Je ne sais toujours pas si la structure proposée a une nouveauté ou non. D'une part, l'idée n'est pas compliquée si vous savez comment fonctionne l'arbre par une clé implicite. Par contre, je n'ai pas vu de description d'une structure avec de telles propriétés. Et si oui, alors il est logique de rendre la structure plus célèbre, cela pourrait être utile à quelqu'un.Mais même s'il s'agit d'un autre vélo, j'ai essayé de le rendre utile. Une demande de tirage dans les collections communes a été créée, mais au moment de la rédaction de cet article, cet article n'est pas encore versé. Sachant à quel point tout peut arriver lentement en open source, je ne serai pas surpris si le processus se prolonge pendant des mois.Un peu surpris par le résultat de la comparaison des performances d'ArrayList et TreeList. Les tests ont montré que TreeList n'a pas de sens d'utiliser jusqu'à 10 000 éléments sur la taille de la liste. Il serait intéressant d'essayer b-tree au lieu d'un arbre binaire. Cette structure doit utiliser la mémoire plus soigneusement et, très probablement, fonctionner plus rapidement. Et pour cela, vous pouvez adapter l'idée avec l'indexation.Dans tous les cas, c'est amusant d'avoir un instrument dans l'arsenal qui peut (presque) tout faire avec une complexité prévisible.Références
Projet original de
demande de tirage dans Apache Common-CollectionsTicket à Jira