*一切，我的意思是在数组的单个元素上相对快速地执行操作。实现该列表的数据结构已完成。每个人都有自己的优点和缺点。例如，在Java世界中-根据必要的操作-您可以使用：- 添加（obj），获取（obj），设置（index，obj）：几乎所有列表的基本集合，例如ArrayList。
- add（index，obj）：树状结构，例如来自Apache Common-Collections的TreeList。
- 删除（索引）：与上述相同。
- 包含（obj），indexOf（obj）：您可以使用一堆ArrayList和HashMap。
- 删除（obj）：...我觉得很难回答。在某些情况下，您可以使用LinkedHashSet。在存在前两点的情况下，可以轻松解决该问题，但是哪种结构都可以快速完成？
当我需要具有快速添加（obj），获取（index），删除（index）和indexOf（obj）的结构时，谷歌没有给出答案。我没有找到任何代码示例或此类结构的描述。也许我不在那儿，我必须自己发明它。但是，如果有人在评论中删除该链接，我将不胜感激。也许有人意识到您可以使用TreeList，它可以快速在列表中间插入/删除项目，并将HashMap从对象添加到TreeList中的索引，以快速执行indexOf（obj）。这将是一个简单，优雅但错误的决定。毕竟，当添加到中间或从中间删除时，平均而言，有必要重新计算一半元素的索引。这会将性能降低到O（n）。接下来，我将讨论可以完成上述所有操作的数据结构。在O（log（n））时间内对一个元素执行任何操作。好吧，几乎-对数是在列表中所有对象都不相同的情况下执行的。如果列表包含相同的对象，则有可能使性能降低到O（log（n）^ 2）。我会立即警告您，我不会在此处绘制代码。对于本文来说可能非常复杂。但这是用Java编写的。基于apache common-collections中的TreeList类。拉取请求已经存在，但是在撰写本文时，文章尚未注入。另外，我不会描述众所周知的算法。例如，树平衡算法。对于大多数人来说，将树保持平衡这一事实理所当然是足够的。这不会影响对一般概念的理解。那些想了解更多的人可以轻松找到信息。但是，我将简要介绍一些基本知识，因为如果不了解这些基本知识，就无法理解许多关键要素。链接将在末尾。为什么有必要
实际上，要直接从列表中提出所有需求的情况并非易事。这不太可能是某种超级必要的结构，否则每个人都会知道。但是，可以给出一些这样的列表可能有用的示例。我认识到很多例子牵强。所有或几乎所有事物都可以用另一种方式解决。缓存和压缩
因此，我的最初任务是开始研究这个问题。播放特定数据的压缩，并且需要对象缓存的列表。想法是这样的：处理另一个对象时，我们在列表中寻找它。如果未找到，请保存该对象并将其添加到列表的顶部。如果找到，则将其索引放在列表中，而不是对象，仅保存其索引，然后将对象移到列表的顶部。因此，出现的对象通常会收到较小的索引，而仅出现一次的对象最终将移至列表的末尾并被删除。转
如果对于某些任务，使用类似的结构代替通常的FIFO队列，则可以执行以下操作：- 回答问题：此任务之前队列中有多少个任务。
- 从队列中删除任务。
就像在超级市场。如果您是来购买巧克力棒的，但是您发现生产线运行缓慢，那么也许不需要那么多巧克力棒了吗？:)高分表
假设我们要存储玩家完成游戏关卡的时间。有很多球员，他们都竞争，试图显示最短的时间。播放器数据可以放入数组并按时间排序。使用此结构，您可以：- 如果玩家显示比以前更好的结果，请在列表中将其移到更高位置。
- 例如，在禁止作弊的情况下，从列表中删除玩家。
- 向每个玩家展示他的位置。
- 逐页显示记录表。
- 在地点中显示稀疏表，例如，时间1、2、3、5、10、20、50、100、1000、10000个地点。
数据结构
该结构基于带有隐式密钥的树。例如，apache common-collection中的TreeList就是基于这种方法的。为了继续前进，您需要了解此结构的工作原理。隐式密钥树
一棵树由节点（Nodes）组成。每个节点包含一个指向存储在该节点中的对象的链接，以及2个指向其他节点的链接：左和右。最顶层的节点称为根节点。在最简单的情况下，节点看起来像这样：class Node<T> {
obj: T
left: Node<T>
right: Node<T>
}
在左侧子树中每个节点的经典二叉树中，所有对象都比当前节点中的对象小，而右侧的对象则大。例如： [ element: 25 ]
/ \
/ \
[ element: 14 ] [ element: 45 ]
/ \ / \
/ \ / \
[ element: 10 ] [ element: 22 ] [ element: 27 ] [ element: 90 ]
/ \ /
/ \ /
[ element: 17 ] [ element: 23 ] [ element: 80 ]
但是出于我们的目的，这样的树不适合。我们不需要存储排序的对象，但是我们需要像数组一样按索引访问它们。如何将数组放入树中？让我们从数组中间选择一个索引为i的元素。将数组中的第ith个元素放在根节点中。 2个子树退出根节点。在左边的子树中，我们将一半索引为<i的数组放到右边，将索引为> i的数组放进去。怎么做？以相同的方式：我们从子数组的中间选择一个元素，将该元素放到节点中，再得到2个较小的子数组。因此，直到我们将数组的所有元素放入树的节点中为止。例如，包含元素[“ q”，“ w”，“ e”，“ r”，“ t”，“ y”，“ u”]的数组可能看起来像这样： [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
我们将“ r”数组中的中间元素放在根节点中。在左和右子树中放置了两个子数组[“ q”，“ w”，“ e”]和[“ t”，“ y”，“ u”]。为此，从子数组中选择中心元素，在我们的例子中是“ w”和“ y”，它们落入下一级的节点中。依此类推，在我们的例子中，树是平衡的，所有子树的深度都相同。但这不是必须的。在上图中，每个节点，除了元素和到左右节点的链接外，还包含整个子树的元素数量。树更改时，必须正确更新此信息。让我们看看如何在这样的树中查找索引为4的元素。我们从根节点（在本例中为root，以“ r”元素）开始爬网。我们有3个选项：我们已经在右边的节点上，右边的节点在左边，右边的节点在右边。为了了解在哪里寻找所需的元素，您需要比较左子树的大小（在我们的情况下为left.size = 3）和当前索引（在我们的情况下为4）。如果这两个数字相等，那么我们在其中找到了必要的节点和所需的元素。如果左子树的大小较大，则左子树中的必需节点。如果较小，则需要查看右侧的子树，但需要减少所需的索引：index = index-left.size-1。由于在我们的示例中left.size <index，我们在右侧子树中查找具有新索引4-3-的元素1 =0。移动到元素为“ y”的节点。然后，我们执行与根节点相同的操作。比较left.size和index。由于1> 0，我们在左侧子树中查找，移至元素为“ t”的节点。该节点中没有左子树，其大小为0。index = left.size，这意味着我们找到了一个索引为4的节点，并可以从中获得所需的元素“ t”。在伪代码中，它看起来像这样：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);
}
}
我试图描述如何在树中放置数组的关键原理。对于O（log（n））与O（1），这种结构当然比经典数组慢。但这有一个重要的优点：将元素添加到中间或从中间删除也适用于O（log（n））与O（n）的数组。当然，只要树或多或少保持平衡即可。有许多算法可以以几乎平衡的方式维护树。例如，红黑树，AVL树，笛卡尔树。我不会写下平衡树的细节，任何算法都适合我们。我们仅假设树是平均平衡的，并且其最大深度与最小没有太大差异。轻微优化
上述检查左侧树的大小的方法便于感知，但是可以更有效地完成。为了不每次查看左侧子树，而不是查看树的大小，可以在节点中存储相对于其父节点位置的位置。根节点存储与左侧子树大小匹配的绝对位置。 [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
例如，根节点“ r”的位置为3。节点“ w”的位置相对于父节点为-2，或者绝对位置3 +（-2）=1。类似地，您可以再向下一层，例如，节点“ e”的位置为3。 +（-2）+（+1）=2。即，节点索引是从树的根到此节点的位置之和。除了可以更快地搜索列表中的项目外，此优化还可以更快，更轻松地搜索节点上的索引。但是，当然，在更改树时正确更新位置变得有些困难。添加索引
因此，在树中，我们可以按索引获取一个元素，更改其值，将元素添加到中间并删除。本质上，我们只需要按值indexOf（obj）添加快速索引搜索。然后contains（obj）和remove（obj）将被简单地解决。但是首先，让我们简化一下任务。让我们构造一个仅存储唯一元素的结构。为了快速搜索内容，他们通常使用一个表。在Java世界中，表称为Map；它具有2个主要实现：HashMap和TreeMap。该表的键将是该对象的链接，而值是其节点的链接：class IndexedTreeListSet<T> {
root: Node<T>
indexMap: Map<T, Node<T>>
}
那些。该结构由两部分组成：列表树本身和带有指向该树的对象和节点的链接的表。更新树时，还必须更新表。我将不详细描述该过程。直观上，这应该是可以理解的：添加一个节点-将其放入表中，删除该节点-将其从表中删除。实际上，平衡树有一些细微差别：该算法应更改节点之间的链接，而不是在节点之间移动对象。否则，您将不得不在表中进行大量更新，并且性能会下降。好的，我们假设我们可以通过其包含的元素快速找到该节点。所以呢？我们需要找到它的索引，但这还不能完成。但是我们可以使节点类复杂化，以便它不仅包含指向左右节点的链接，还包含指向其父节点的链接：class Node<T> {
obj: T
left: Node<T>
right: Node<T>
parent: Node<T>
pos: int
}
当然，更新树要稍微复杂一点，因为现在我们需要仔细更新到父级的链接。但是现在，知道了节点，我们就可以上树并计算任何节点的索引。如果使用上一章中的优化，则只需要计算从当前节点到根的位置之和。对于包含唯一元素的列表，可以认为该问题已解决。是的，我们有一个小问题。假设我们调用集合（index，obj）。我们可以轻松地将节点中的一个元素替换为另一个元素，但前提是列表中还没有新元素。如果是这样，我该怎么办？从旧的位置移走多余的物品并放入新的物品？反之亦然，首先添加然后删除？结果可能会有所不同。而且您什么都不做或抛出异常。没有完美的解决方案。按标准方法排序，这样的列表很可能也不起作用。毕竟，排序算法不会知道对象唯一性的必要性，并且在移动列表中的项目时会创建重复项。我们去除唯一性
好的，进一步使事情复杂化，让我们保留相同的对象。显然，您需要对表做一些事情。在其中存储节点列表的第一个想法似乎不太好：随着列表长度的增加，性能将下降。如果所有列表项都相同，则最多为O（n）。然后，让我们尝试将排序后的节点树存储在表中而不是列表中。按列表中的位置排序。class IndexedTreeList<T> {
root: Node<T>
indexMap: Map<T, TreeSet<Node<T>>>
}
然后，在节点位置的日志（m）比较期间，将发生对大小为m的TreeSet <Node>的插入/删除操作，并且每次比较都将在log（n）时间内进行。在类似结构中插入或删除的最终复杂性将发生在O（log（n）*（1 + log（m）））中，其中n是列表中元素的总数，m是列表中等于已插入/删除的元素的数量。在最坏的情况下，当所有元素都相等时，我们得到复杂度O（log（n）^ 2）。细心的读者可能会反对：但是不变性呢？毕竟，如果它们是表键，我们不能更改对象吗？通常是这样。但是，对于将排序对象存储在键中的树而言，除了用于比较的标准规则外，还足以保留不变式：如果<b，则此属性不应随时间变化。这就是我们的情况：如果一个节点的位置小于另一个节点的位置，则无论在节点之间添加或删除了多少个节点，该属性都将保留。是否可以使结构持久化？
简短的回答：不，这是不可能的。由于树的双向连接，从根到叶再到叶，我们将每个树节点连接到每个树节点。持久性不能以这种方式完成；您必须进行任何更改来重新创建整个结构。但是我了解如何在不需要在列表中间插入元素的情况下实现持久结构。您可以在开头或结尾添加元素，也可以从中间删除元素。其余属性相同。如果您有兴趣，那么我将尝试撰写有关此结构的文章。也许我什至可以用Java，Kotlin或Scala实现它。但是，很可能不会很快。一些实施功能
在这里，我想描述一些我必须面对的功能。上面我写了关于将节点位置存储在列表中的一种优化方法。这里体现了开放源代码的优势：我采用了现成的TreeList代码，没有深入研究AVL树，节点旋转，位置更新等细节。从TreeList继承的另一个功能是链接到树叶中的子树。每个节点都存储布尔值leftIsPrevious和rightIsNext。这些变量指示左/右子树的存在或不存在。如果没有子树，则在左/右，而不是到子树的链接，而是存储到与上一个或下一个元素相对应的节点的链接。在我们的示例中，节点“ e”是多叶的，没有子树[[q]，“ w”，“ e”，“ r”，“ t”，“ y”，“ u”]。因此，leftIsPrevious和rightIsNext为true，左和右分别指向节点“ w”和“ r”。这种方法有助于更快地遍历列表。它会干扰新功能的编程：）关于使用表对象→节点的一些知识。理想情况下，将元素添加到结构中时需要一次将其放入表中，而从结构中删除则将其删除一次。实际上，我无法实现这一目标。当您添加一个项目时，该项目将被添加到表中，一切均应按原样进行。但是，删除项目时，平衡算法有时会在节点之间移动项目。结果是两次删除和表中的一条记录，而不是一次删除。如果从leftIsPrevious和rightIsNext中删除优化，则可以解决此问题。甚至会获得很小的性能提升，而且不仅在移除过程中。在某些测试中，增加了10-20％。但是迭代速度显着下降，在我的测试中是1.5-2.5倍。我决定暂时不进行优化。在Java中，表的主要类型是HashMap和TreeMap。对于表，默认情况下，对象→节点使用HashMap。但是，您可以将TreeMap与特定于任务的Comparator一起使用。在这种情况下，indexOf（obj）和remove（obj）将根据比较器代码搜索/删除等于指定对象的对象。例如，我们存储用户列表，比较器仅按名称比较用户。然后，我们可以回答“名称为“拿破仑”的用户在列表的哪些位置？”的问题。或者从列表中删除所有拿破仑:)。该结构不支持null。您可以修复它，但是没有必要的感觉。关于该结构“无所不知”的事实，我当然有点误导。当然，当使用单个元素时，即使在对数下，在某些条件下一切都很好。但是，她不知道其他结构可以做到的某些事情。例如，带有隐式键的笛卡尔树，中心上有关于它的文章 它不知道如何快速执行indexOf，但它知道如何创建一个子列表并将两个列表对数连接为一个（平均，不保证），并且可以使其持久化。性能
在Java中，通常使用jmh框架来衡量性能。测试是在Java11下的2017年MacBook Pro上进行的。我比较了标准ArrayList，apache common-collections中的TreeList和我的两个类IndexedTreeList和IndexedTreeListSet在几种情况下的性能。在每种情况下，均执行了1000次相同类型的操作，因此结果应乘以1000。剧透下的代码@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();
}
}
首先，我比较了从列表中获取随机项目的速度。我会立即警告您，在此测试中，开销非常大。每秒接近100,000 * 1,000次操作的结果严重失真。获取测试结果PerformanceCompare.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
奇怪的是，这里最大的兴趣是标准的ArrayList。从理论上讲，脱离它的速度应该是恒定的，而不取决于元素的数量。在实践中，性能首先保持每秒约90,000 * 1000次操作（记住开销），但列表长度为数千项时，它开始下降。这是由于越来越多的高速缓存未命中：处理器高速缓存没有必要的数据，越来越多的您需要在RAM中寻找数据。使用一百万个元素，测试速度会降低10倍，但实际上，性能下降会更大。TreeList，IndexedTreeList和IndexedTreeListSet预期显示相似的结果。预期比ArrayList慢得多。即使有少量元素，TreeList的速度也比ArrayList慢几倍，尽管测试仅显示出相差2倍。下一个测试是addRemoveRandom。在这里，在每个测试中，我都将元素插入随机位置，然后从随机位置移除元素。AddRemoveRandom测试结果PerformanceCompare.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
可以假设ArrayList在小列表上更快。但是，他在多达10,000个元素的列表中赢得测试的事实似乎很有趣。显然，System.arrayCopy已得到很好的优化，并使用了现代处理器的所有功能。从10,000项开始，专用数据结构开始获胜。拥有1,000,000个元素，速度差是30到50倍。预期IndexedTreeList和IndexedTreeListSet比TreeList慢。大约1.5-2倍。其余2个测试indexOfKnown和indexOfUnknown应该只演示此结构的主要功能。测试之间的区别在于，在一种情况下，我们正在寻找列表中的元素，而在另一种情况下，我们正在寻找列表中不存在的元素。测试结果indexOfKnown和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
在这里，ArrayList和TreeList几乎没有惊喜。随着尺寸的增加，速度几乎呈线性下降。从非列表中搜索项目预计比从列表中搜索项目慢2倍，因为您需要遍历整个数组，而不是平均一半。但是这里的IndexedTreeList和IndexedTreeListSet显示了预期的良好结果。这些数据结构显示indexOf的执行速度与ArrayList相当，即使有10个元素。使用1000个元素，这些结构的速度提高了10倍，而1000万个元素的速度提高了1,000,000。当搜索不在列表中的项目时，与从列表中搜索项目相比，它们的速度更快。还有一点需要注意的有趣的事情是indexOfUnknown测试中IndexedTreeList和IndexedTreeListSet的性能下降。这里的情况类似于使用ArrayList.get进行测试的情况。从理论上讲，我们不应该降低性能，但是实际上，由于高速缓存未命中，我们得到了显着的效果。而不是结论
我仍然不知道提议的结构是否具有新颖性。一方面，如果您知道树是如何通过隐式键工作的，则想法并不复杂。另一方面，我还没有看到具有这种特性的结构的描述。如果是这样，那么使该结构更出名是有意义的，这对某人可能有用。但是，即使这是另一辆自行车，我也尝试使其实用。在公共集合中创建了一个拉取请求，但是在撰写本文时，尚未提出。知道所有事情在开源中发生的速度是多么缓慢，如果这个过程拖延了几个月，我不会感到惊讶。比较ArrayList和TreeList的性能的结果有些令人惊讶。测试表明，TreeList在列表大小上最多使用10,000个元素没有意义。尝试使用b树而不是二叉树会很有趣。此结构应更仔细地使用内存，并且很有可能更快地工作。为此，您可以通过索引来适应这个想法。无论如何，在军械库中拥有一种可以（几乎）以可预测的复杂性完成所有事情的仪器很有趣。参考文献
吉拉（Apache）的Apache Common-collection Ticket中的原始Pull Request 项目