多年前，Richard Hendricks 犯了一个大错，他为一个有序列表编写了一个暴力搜索算法。我们都会犯傻瓜错误，我在写这篇文章时也犯了几个。
如果在我刚刚购买的公司的工作会议上提到了我以前的一个傻瓜错误，我会觉得自己很幸运。
现在，Richard 犯了更严重的错误，他没有让团队回到正轨。在让团队取笑他之后，Richard 应该提醒 Ethan 谁才是现在的老板。Dinesh 太胆怯了，没有为他的朋友说话。
如果你不立即理解为什么暴力搜索有序列表是如此严重的错误，互联网上有很多文章解释它，我在这篇文章中也会解释，以确保你明白。
我没有看到任何关于为什么 Richard 会犯这个错误的文章。我相信他已经犯了很多愚蠢的算法错误，但我怀疑他会犯那个特别的错误。
明确一下，Richard Hendricks 是一个虚构的角色，由 Thomas Middleditch 在 HBO 的电视剧《硅谷》中扮演。Dinesh Chugtai 由 Kumail Nanjiani 扮演，Ethan 由 George Basil 扮演。
所讨论的集数是第六季的“Maximizing Alphaness”，但不用担心剧透，Ethan 挖出 Richard 多年前犯的错误发生在第一季之前。这一切都是为了嘲笑 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 开发工具包（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> 练习，因为它是一个很好的数据结构练习，而不是因为我们在实际项目中可能需要它。如果你在实际项目中发现自己需要 SortedList<E>，考虑使用 java.util.SortedSet<E>。
为了开始我们的 SortedList<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 值来方便测试，因此没有必要在它所在的包之外进行访问。
根据你选择的单元测试框架（例如 JUnit、TestNG），开始编写 SortedListTest 或 SortedListNGTest。引入 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 的解决方案有何可笑之处，我想让你考虑一副全新的纸牌，例如你用于扑克或二十一点。
如果封条未被打破，则几乎总是可以指望卡片以特定顺序排列。
然后，如果我让你从全新的、从未洗过的一副牌中挑出一张牌，例如方块10或梅花J，你可能会从牌堆的中间开始搜索。
因此，你在大约中间的地方切割牌堆，假设你找到了梅花Q（请记住，在全新的、从未洗过的牌中，或者已经洗过但是按全新的牌的顺序排序的牌中，梅花和红心是“反过来的”，King 到 Ace）。
然后，你回溯到方块10之前的梅花、方块和红心的K、Q和J。在此示例中，在找到你要查找的卡之前，你查看了五张卡。
但是，如果我洗了牌，即使只洗了一次，要查找的卡可能在牌堆的任何位置。此时，可能需要从牌堆的顶部或底部开始查看每张卡片，直到找到所需的卡片。
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 的每个元素，这可能需要在我的计算机上花费十二分钟（基于上一个测试的性能），而更有效的算法只需要几毫秒。
我们可以使用设置为填充一百万个元素的列表和超时的测试类进行测试。如果查找所请求的元素需要超过半秒钟，测试将失败。
这个测试的问题在于它过于依赖于它运行的特定系统。
假设，假设你的计算机可以在一秒钟内迭代通过 700,000 个项目。这表明在你的计算机上，更有效的算法可能只需要不到一毫秒，但如果超时间隔为半秒钟，则效率较低的算法仍将通过你的计算机上的测试。
然而，这实际上给了我一个更好的想法。我们可以创建一个 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，所请求的元素必须在列表的第二半部分中。
然后，下一步是在比较指示的一半的中间查找。也许项目就在那半部分的中间，否则，不断将其减半，直到找到元素或找到可以插入元素并保持列表有序的位置为止。
例如，在按全新牌组顺序排列的 Ten of Diamonds 示例中，二分搜索将从 Diamond King 开始，对吧？由于方块十“小于”方块王，它必须在牌组的上半部分。
因此，二分搜索将搜索空间缩小到仅包括方块牌，然后是更高价值的方块牌，以此类推，直到最终找到方块十。
也许这看起来很慢，但是它比从小丑开始并经过所有黑桃牌和然后经过方块牌要快得多。
当然，二分搜索的最坏情况是元素在列表的第一个或最后一个。
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 的打印行。
哎呀，我忘记记录 compareTo() 的调用了。算了，也没那么多。比 256 少多了。
这里有很多重构的机会。要么改进我上面发布的内容，要么跳到使用 Arrays 中的某些东西。
如果你也做了可变、不一定排序的基于数组的列表练习，你可能还记得在测试 indexOf() 之前测试 add()。对于 SortedList<E> 来说，先测试 indexOf() 要容易得多。
这是因为唯一有效的插入点是那些保持列表有序的点，除非你宁愿让 add() 的工作方式是将新元素添加到 elements 数组的末尾，然后再次对数组进行排序。
还有假设你想继续进行这个特定的练习，当然你也可能不想。
更大的教训是我们在算法中都会犯愚蠢的错误。但是通过 TDD，我们可以利用这些愚蠢的错误，迈向更优雅的程序之旅。
译自：https://alonso-delarte.medium.com/data-structures-exercise-sorted-lists-in-java-with-tdd-abc9569afeb
评论(0)