多年前，Richard Hendricks 犯了一个大错误，他写了一个针对排序列表的暴力搜索。我们都会犯一些愚蠢的错误，我在写这篇文章时也犯了一些。
如果在我刚刚购买的公司的一次会议上提到了我过去的愚蠢错误，我会觉得自己很幸运。
如今，Richard 犯了一个更严重的错误，他没有让团队重新回到正轨。在让团队取笑他之后，Richard 应该提醒 Ethan 谁才是现在的老板。而 Dinesh 太懦弱了，没有为他的朋友说话。
如果你不立即理解为什么针对排序列表进行暴力搜索是如此严重的错误，互联网上有很多文章可以解释，我也会在本文中解释，以确保你理解。
我没有看到任何深入探讨为什么 Richard 会犯这个错误的文章。我相信他已经犯了很多蠢笨的算法错误，但我怀疑他会犯这个特定的错误。
需要明确的是，Richard Hendricks 是一个虚构的角色，由 Thomas Middleditch 在 HBO 的《硅谷》中扮演。Dinesh Chugtai 由 Kumail Nanjiani 扮演，Ethan 由 George Basil 扮演。
所讨论的集数是第六季的“Maximizing Alphaness”，但不用担心剧透，Ethan 所挖掘的事件发生在第一季之前。这一切都是为了嘲笑 Richard 在多年前犯的一个错误。
在片段中，显示的行号是 112 到 115，这是 Java 的代码，但也很容易是 C++ 的代码。
int index = 0;
while (!element.equals(sortedList.get(index))
&& sortedList.size() > ++index);
return index < sortedList.size() ? index : -1;
这些代码被归属于 Richard Hendricks，但我怀疑在他工作的版本中，sortedList 实际上只叫做 list，这使得 Richard 更容易忽视列表已经被排序的事实。
当然，在这里缺少很多上下文，Richard 试图提供一些上下文，但我们要记住，《硅谷》是一部为观众制作的节目，这些观众可能对编程一无所知。
在这个特定的场景中，观众需要理解的主要事情是 Ethan 不尊重 Richard，而 Richard 却让他这么做。你不需要成为数据结构专家就能理解这一点。
在我看来，这里非常重要的一个缺失的上下文是：为什么 Richard 需要编写这个搜索函数？C++ 标准库难道没有已经存在的排序列表类吗？这个排序列表类不会已经提供了高效的搜索函数吗？
或者程序是用 Java 写的，确实 Java Development Kit (JDK) 没有提供 SortedList<E>。所以也许 Richard 需要从头开始编写这个类。但如果是这种情况，Ethan 显示的代码看起来会更像以下代码：
int index = 0;
while (!element.equals(this.get(index))
&& this.size() > ++index);
return index < this.size() ? index : -1;
这也考虑到了 Richard 在第三季中表达的偏好，即使用制表符而不是空格，制表符停止位为 8 个空格。
还有一个问题，为什么 Richard 需要 SortedList<E>。我很难想出一个现实中的使用案例，除了它是数据结构的一个很好的练习之外。
这就是为什么我们要在这里做这个练习，因为这是数据结构的一个好练习，而不是因为我们在真实世界的项目中可能需要它。如果你发现自己认为需要 SortedList<E> 用在真实世界的项目中，请考虑使用 java.util.SortedSet<E>。
为了开始我们的 SortedList<E> 练习，我考虑重用 我文章 中的 ArrayBackedList<E> 桩代码，对 SortedList<E> 进行一些更改，但也许从头开始编写这个桩代码更好。
请在你最喜欢的 Java 集成开发环境 (IDE)，例如 Apache NetBeans 或 IntelliJ IDEA 中，放入以下桩代码。
package collections.mutable.lists;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class SortedList<E extends Comparable<E>>
implements Iterable<E> {
// TODO: Write tests for this
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
@Override
public boolean hasNext() {
return false;
}
@Override
public E next() {
return null;
}
};
}
SortedList(E[] originalElements) {
//
}
}
类型绑定 E extends Comparable<E> 可能不是最优的，但现在它足够了。如果你理解了可比较对象的概念，那么为比较器进行转换并不需要太多的努力。
请注意，现在唯一的构造函数是包私有的。我认为，以后这个类将有两个或三个公共构造函数，也许上面显示的构造函数桩代码最终会成为其中的一个公共构造函数。
现在，唯一构造函数的唯一用途是通过一次性加载一堆 E 值来促进测试，因此它不需要在所在的包之外访问。
启动 SortedListTest 或 SortedListNGTest，这取决于你选择的单元测试框架 (例如 JUnit、TestNG)。导入 java.util.Arrays、java.util.Iterator<E> 和 java.util.Random，以及实现 Comparable<E> 接口的两个或三个 JDK 中的 E 类型，例如来自 java.time.chrono 包的 ChronoLocalDate。
对于第一个测试，让我们甚至不用担心排序。我们的排序列表类应该允许重复，因此使用 Arrays.fill() 填充一个 E 数组（例如 ChronoLocalDate），随机选择一个容量，然后重复一个像 LocalDate.now() 这样的元素，直到达到该容量。
然后测试获得一个迭代器，并检查该迭代器按容量指示的次数给出了预期的元素。测试应该失败，因为我们希望第一次测试失败，因为我们正在进行测试驱动开发（TDD）。添加一个数组字段来保存originalElements，然后相应地更改构造函数和iterator()（如果你不知道如何编写迭代器，请参见我的迭代器文章）。然后验证这个测试通过。
对于下一个测试，我们希望看到构造函数对originalElements的元素进行排序。也许测试可以将随机选择的不同BigInteger实例放入一个小型数组中，比如五个或十个，然后使用它来实例化一个SortedList<BigInteger>。
编写测试时，请注意测试将原始元素数组复制到一个名为expected的新数组中，然后使用Arrays.sort()对expected进行排序，并且SortedList<E>实例不会得到任何指向测试排序的数组的指针。
实际上，还要确保在调用SortedList<E>构造函数之前，测试会制作expected数组。这样做的原因是我们想确保测试第一次失败是我们所期望的原因，而且我们也不想过早得到结果。
然后，使用迭代器，测试创建另一个名为actual的数组，并比较expected和actual数组以相同的顺序保存相同的元素。
记住，如果你正在使用JUnit，你必须使用assertArrayEquals()而不是assertEquals()。对于TestNG，不需要这个提醒。
这个测试应该失败。通过上一个测试，下面的构造函数更改以及导入java.util.Arrays，应该足以让它通过，加上：
SortedList(E[] originalElements) {
this.elements = originalElements;
Arrays.sort(this.elements);
}
这个构造函数可能会有不良副作用，排序调用者传入的数组，但是我将解决这个问题留给读者。
一旦元素在排序列表中，就应该可以使用get()函数检索它们。
// TODO: Write tests for this
public E get(int index) {
return null;
}
这个函数的第一个测试应该是针对超出范围的索引（负数或大于列表大小），但是在这个练习中，我们不用担心它。
对于get()的下一个测试，测试可以创建一个名为expected的伪随机比较数组，对数组进行排序，然后将排序后的数组传递给SortedList<E>构造函数。我们希望这个测试知道在哪里期望元素。
然后，测试将index从0到capacity的每个元素遍历排序后的数组，并检查get(index)是否与expected[index]匹配。
我在我编写的测试中使用BigInteger作为E类型，它第一次失败是因为它期望在索引0处得到285794907044928622647，但实际上得到了null。我通过一个非常简单的更改让测试通过：
public E get(int index) {
// TODO: Check index is within bounds
return this.elements[index];
}
现在让我们将注意力转向indexOf()函数，这是搜索函数。在要测试的类中放置这个存根：
// TODO: Write tests for this
public int indexOf(E element) {
return Integer.MAX_VALUE;
}
这个存根是为了使那些不在列表中的元素的测试失败。如果一个元素不在列表中，那么indexOf()应该返回-1或其他负整数。
@Test
void testNoIndexOfIfNotInList() {
int capacity = 20;
Integer[] evenNumbers = new Integer[capacity];
for (int i = 0; i < capacity; i++) {
evenNumbers[i] = 2 * i * RANDOM.nextInt();
}
SortedList<Integer> list = new SortedList<>(evenNumbers);
int oddNumber = 2 * RANDOM.nextInt() + 1;
String msg = "List of even numbers should not contain "
+ oddNumber;
assert list.indexOf(oddNumber) < 0 : msg;
}
第一次运行这个测试，它失败了，显示“偶数列表不应该包含-2141276887”。
通过让indexOf()返回-1或任何你想要的负整数来使测试通过。
如果元素在列表中，indexOf()应该根据元素在列表中的位置返回0或正整数。现在我们开始理解为什么Richard多年前的错误会引起他的现代下属的嘲笑。
以防你不理解Richard的解决方案有什么可笑之处，我希望你想想一副全新的扑克牌，就像你在玩扑克或二十一点时会用的那样。
如果盒子上的密封没有被打开，你几乎总是可以指望牌按照特定的顺序排列。
然后，如果我让你从一个全新的、从未洗过的牌组中挑选一张像方块十或草花杰克这样的牌，你可能会从牌组的中间左右开始搜索。
所以你在大约一半的位置切割了牌组，假设你找到了草花皇后（记住，草花和红心在全新的、从未洗过的牌组中是“反向”的，按照全新的牌组顺序排序）。
然后你沿着草花皇后、方块的国王、方块的国王、方块的女王和方块的杰克回溯，最终找到了方块十。在这个例子中，你在找到你要找的牌之前看了五张牌。
但是，如果我洗牌了这副牌，甚至只是洗了一次，那么请求的牌可能在牌组的任何地方。为了找到它，可能需要从牌组的顶部或底部开始，逐张查看牌，直到找到请求的牌。
Richard的indexOf()函数的工作原理基本上相当于把一副从未洗过的牌或者已经洗过但是按照全新的牌组顺序排序的牌当作我们不知道牌的顺序。
为了在全新的牌组中找到方块十，Richard的函数需要查看所有十三张黑桃牌和从Ace到Nine的方块和红桃牌，还有两张小丑。
对于计算机来说，在少于一百个项的短列表中，这种性能并不差。但在一本有一百万个数字的电话簿中，这将是无法接受的缓慢。
使用测试驱动开发（TDD），Richard的解决方案在过程的早期阶段可能是相当有效的，当我们编写一个只需要在列表中找到一个特定元素的测试时，而不考虑效率或“时间复杂度”。就像这个测试：
@Test
void testIndexOf() {
System.out.println("indexOf");
int capacity = RANDOM.nextInt(64) + 16;
Integer[] numbers = new Integer[capacity];
for (int i = 0; i < capacity; i++) {
numbers[i] = i;
}
SortedList<Integer> list = new SortedList<>(numbers);
for (int expected = 0; expected < capacity; expected++) {
int actual = list.indexOf(expected);
assertEquals(expected, actual);
}
}
然后，Richard的解决方案，根据我们还没有size()函数的事实进行调整，对于一个相对较少项目的列表的测试来说，可以完美地工作。
public int indexOf(E element) {
int index = 0;
while (!element.equals(this.get(index))
&& this.elements.length > ++index);
return index < this.elements.length ? index : -1;
}
IntelliJ IDEA会警告我While语句有一个空循环体，但没有明显的语法错误，这足以通过我们的简单测试。尽管在我的系统上它花费了67毫秒，这似乎有点多。那么我们如何编写一个测试，不仅要求找到请求的元素，还要以高效的方式找到它呢？
我想我们可以编写一个测试，用一百万个连续整数（例如1到1,000,000）填充一个已排序的列表，然后测试要求查找一个数字，例如687,500。
Richard的indexOf()函数版本必须从1查询到687,500个元素，这可能需要在我的计算机上花费12分钟（基于上一个测试的性能），而更有效的算法只需要几毫秒。
我们可以使用一个测试类，设置一个填充一百万个元素的列表和一个效率测试的超时时间。如果查找请求的元素需要超过半秒钟，测试将失败。
但这个测试的问题在于它过于依赖于运行它的特定系统。
假设，假设你的计算机可以在四分之一秒内遍历70万个项目。这表明在你的计算机上，更有效的算法可能只需要不到一毫秒的时间，但如果超时间隔为半秒钟，则较不有效的算法仍将在你的计算机上通过测试。
然而，这实际上给了我一个更好的想法。我们可以创建一个Comparable<E>，以跟踪其equals()函数被调用的次数。毕竟，我们关心的是，在搜索中调用equals()的次数，而不是equals()调用需要多长时间。
然后我们就不必担心我们选择的超时时间可能过于脆弱了。我们也不必把列表做得像一百万那么大。一千个项目应该足以获得非常有用的测试失败。
以下是编写嵌套在我们的测试类中的Comparable<E>的一种方法：
private static final class WrappedInteger
implements Comparable<WrappedInteger> {
private static int equalsCallCount = 0;
private final int wrapped;
static void resetEqualsCount() {
equalsCallCount = 0;
}
static int getEqualsCallCount() {
return equalsCallCount;
}
@Override
public boolean equals(Object obj) {
equalsCallCount++;
if (obj instanceof WrappedInteger) {
return this.wrapped == ((WrappedInteger) obj).wrapped;
} else {
return false;
}
}
@Override
public int hashCode() {
return this.wrapped;
}
@Override
public int compareTo(WrappedInteger other) {
return this.wrapped - other.wrapped;
}
WrappedInteger(int n) {
this.wrapped = n;
}
}
然后我编写了这个测试：
@Test
void testIndexOfIsEfficient() {
int capacity = 1024;
WrappedInteger[] numbers = new WrappedInteger[capacity];
for (int i = 0; i < capacity; i++) {
numbers[i] = new WrappedInteger(i);
}
SortedList<WrappedInteger> list = new SortedList<>(numbers);
WrappedInteger.resetEqualsCount(); // Just in case another test
// changed it
int expected = capacity / 2 + RANDOM.nextInt(capacity / 8) + 1;
WrappedInteger element = new WrappedInteger(expected);
int actual = list.indexOf(element);
int callCount = WrappedInteger.getEqualsCallCount();
assertEquals(expected, actual);
int maximumAcceptableCalls = capacity / 4;
String msg = "indexOf() should've found element at index "
+ expected + " out of " + capacity
+ " with fewer than " + maximumAcceptableCalls
+ " equals() calls, it took " + callCount
+ " calls";
assert callCount <= maximumAcceptableCalls : msg;
}
由于Richard的暴力搜索算法，测试失败了，我得到了这个失败消息：
indexOf() should’ve found element at index 587 out of 1024 with fewer than 256 equals() calls, it took 588 calls
值得一提的是，这花费了57毫秒。
所以现在我们考虑实现一些称为“二分查找”的东西。二分查找的基本思想是通过反复把列表分成两半来缩小列表中元素所在的位置或可能所在的位置。
第一个要查找元素的地方不是列表的开头或结尾，而是在列表的中间。最可能的情况是元素不在列表的中间。
但由于列表已经排序，比较结果要么告诉我们元素必须在列表的前半部分，要么告诉我们元素必须在列表的后半部分（如果它在列表中）。
在上面的测试运行中，二分查找会首先查看512。由于512小于587，所请求的元素必须在列表的第二半部分中。
然后，下一步是在比较所指示的一半的中间查找。也许这个项目在那一半的中间，否则，继续缩小，直到找到元素或找到可以将其插入并保持列表有序的位置为止。
例如，在全新的牌组顺序中使用方块十例子，二分查找将从方块王开始，对吧？由于方块十“小于”方块王，所以它必须在牌组的上半部分。
因此，二分查找将搜索空间缩小到仅为方块牌，然后是更高价值的方块牌，等等，直到最终找到方块十。
也许这看起来很慢，但它确实比从小丑开始并通过所有黑桃牌然后通过方块牌来查找卡牌要快得多。
当然，二分查找的最坏情况是元素在列表中的第一个或最后一个。
Richard的代码片段还缺少列表元素存储的上下文。链接节点？哈希桶？
如果它是一个数组支持的列表，那么也许Richard犯了不直接访问支持数组的错误。调用get()是可以的，除非它检查索引是否在边界内，那么这些检查会使暴力搜索的性能惩罚加剧。
因此，在我们的练习中，我们将直接访问支持数组。由于我的第一个解决方案不太优雅，所以我可能会分享它。
public int indexOf(E element) {
// TODO: Check element is not null
int rangeBegin = 0;
int rangeCenter = this.elements.length / 2;
int prevCenter = rangeCenter - 1;
int rangeEnd = this.elements.length;
while (rangeCenter != prevCenter) {
int comparison = element.compareTo(this
.elements[rangeCenter]);
if (comparison == 0) {
return rangeCenter;
}
if (comparison < 0) {
rangeEnd = rangeCenter;
} else {
rangeBegin = rangeCenter;
}
prevCenter = rangeCenter;
rangeCenter = rangeBegin + ((rangeEnd
- rangeCenter) / 2);
}
return -1;
}
它可能不够优雅，但比Richard的解决方案更优雅，并且通过了我们到目前为止所有的测试。我添加了一个msg的Print Line。
indexOf() should’ve found element at index 532 out of 1024 with fewer than 256 equals() calls, it took 0 calls
哎呀，我忘记记录compareTo()的调用了。不过，它并不多。比256少得多。
这里有很多重构的机会。要么改进我上面发布的内容，要么跳过到使用Arrays中的内容。
如果你还做了可变的、不一定排序的数组支持列表练习，你可能还记得在测试indexOf()之前测试add()。对于SortedList<E>来说，测试indexOf()比测试add()更容易。
这是因为唯一有效的插入点是那些使列表保持有序的插入点，除非你愿意让add()通过将新元素添加到elements数组的末尾，然后再对数组进行排序来工作。
并且也假设你想继续这个特定的练习，你可能想继续，也可能不想。
这里的更大教训是，我们都会犯愚蠢的算法错误。但是，通过TDD，我们可以利用这些愚蠢的错误来迈向更优雅的程序之旅。
译自：https://alonso-delarte.medium.com/data-structures-exercise-sorted-lists-in-java-with-tdd-abc9569afeb
评论(0)