问题

如何正确地用 Test Driven Development 实现算法?

回答
抛开那些生硬的列表式“最佳实践”,让我们来聊聊怎么实打实地用测试驱动开发(TDD)来搞定一个算法,从零开始,讲得透彻点,保证你读完能立刻上手。

核心思路:写测试,让测试失败,然后写代码让它通过,最后再重构。

听起来简单,但真正用起来,你会发现里面的门道不少。TDD 之于算法,就像是给你的思维加上了一个精准的 GPS,指引你一步步走向正确的解决方案,而不是在一个大方向上瞎摸索。

第一步:需求拆解与测试设计——“我到底要做什么?”

拿到一个算法需求,别急着撸起袖子写代码。咱们先冷静下来,把这个算法的“规矩”掰扯清楚。

明确输入输出: 这个算法接收什么样的数据?数据的格式、类型、范围是什么?它应该吐出什么样的数据?
边界条件: 这是最容易出错的地方。想想极端情况:
最小/最大值: 如果输入是空的?是只包含一个元素的?
异常值: 如果输入是无效的(比如字符串、负数,如果算法不支持的话)?
特殊组合: 如果输入是所有元素都相同?所有元素都递增/递减?
典型场景: 设计几个有代表性的、能覆盖算法核心逻辑的例子。
性能要求(可选但重要): 如果有时间复杂度或空间复杂度要求,也要提前考虑,虽然 TDD 主要关注正确性,但在后续阶段也可以用测试来衡量。

举个例子: 假设我们要实现一个“找到数组中第二大的元素”的算法。

输入: 一个整数数组。
输出: 数组中的第二大整数。
边界条件:
空数组:怎么处理?抛错?返回特定值?
只有一个元素的数组:第二大是什么?
数组中有重复元素:比如 `[5, 5, 3, 1]`,第二大是 5 还是 3?(根据需求定义,这里假设是 3)。
所有元素都相同:比如 `[7, 7, 7]`,第二大是什么?
典型场景:
`[3, 1, 4, 1, 5, 9, 2, 6]` > 6
`[1, 2, 3, 4, 5]` > 4
`[5, 4, 3, 2, 1]` > 4
`[10, 5, 10, 2, 8]` > 8

第二步:编写第一个测试(RED)——“让它失败!”

现在,我们有了第一个测试用例。假设我们选择了最简单的那个:“找到数组中第二大的元素”,输入 `[3, 1, 4, 1, 5, 9, 2, 6]`,期望输出是 `6`。

用你熟悉的测试框架(比如 Python 的 `unittest` 或 `pytest`,Java 的 `JUnit`),写下这个测试。代码大概会是这样(用 Python 伪代码):

```python
假设算法函数叫做 find_second_largest
def test_find_second_largest_basic():
input_array = [3, 1, 4, 1, 5, 9, 2, 6]
expected_output = 6
actual_output = find_second_largest(input_array)
assert actual_output == expected_output
```

在这一步,`find_second_largest` 函数压根儿还没写,所以运行这个测试,它肯定会报错(比如 `NameError`,因为它找不到 `find_second_largest` 这个函数)。这就是 TDD 里的 RED 阶段。

第三步:编写最小的、能让测试通过的代码(GREEN)——“只要通过就行!”

目标是让刚才那个失败的测试跑通,哪怕代码写得非常“粗糙”也无所谓。

在上面的例子里,我们知道输入是 `[3, 1, 4, 1, 5, 9, 2, 6]`,期望输出是 `6`。为了让这个测试通过,我们可以直接写一个“硬编码”的函数:

```python
def find_second_largest(arr):
这是一个非常糟糕的实现,但它能让第一个测试通过!
if arr == [3, 1, 4, 1, 5, 9, 2, 6]:
return 6
后面还需要处理其他情况,先就这样
return None 或者抛个错
```

现在,再运行刚才的测试,它应该会通过了。这就是 GREEN 阶段。

第四步:思考下一个测试——“还有哪些情况没考虑到?”

刚才我们只解决了 `[3, 1, 4, 1, 5, 9, 2, 6]` 的情况。TDD 的精髓在于不断地增加测试用例,覆盖更多的场景,并且在每次添加测试后,都遵循 RED > GREEN 的循环。

我们前面拆解的需求里,还有很多边界条件没覆盖。比如:

空数组: `test_find_second_largest_empty()`
只有一个元素的数组: `test_find_second_largest_single_element()`
所有元素都相同的数组: `test_find_second_largest_all_same()`
包含重复元素但第二大不重复: `test_find_second_largest_duplicates_second_max()`
数组本身就是有序的: `test_find_second_largest_sorted_ascending()`
数组本身就是逆序的: `test_find_second_largest_sorted_descending()`

我们先选择一个简单的,比如“空数组”。

第五步:编写测试,让它失败(RED)

```python
def test_find_second_largest_empty():
input_array = []
假设我们的算法在空数组时抛出 ValueError
with pytest.raises(ValueError): 或者根据你的设计来选择断言方式
find_second_largest(input_array)
```

运行这个测试,`find_second_largest` 现在的实现(那个硬编码的)肯定会失败(可能返回 `None`,不抛 `ValueError`)。RED。

第六步:修改代码,让新测试通过(GREEN)

现在,我们需要修改 `find_second_largest`,让它能处理空数组的情况。

```python
def find_second_largest(arr):
if not arr: 处理空数组
raise ValueError("Input array cannot be empty")
if arr == [3, 1, 4, 1, 5, 9, 2, 6]:
return 6
... 后面还需要处理其他情况
return None
```

现在,再运行所有测试(包括旧的和新的),它们都应该通过。GREEN。

第七步:重构(REFACTOR)——“让代码更优雅、更高效!”

在 TDD 的流程里,重构是至关重要的一环,但它必须在所有测试都通过的情况下进行。

观察一下我们现在的 `find_second_largest`:

```python
def find_second_largest(arr):
if not arr:
raise ValueError("Input array cannot be empty")
if arr == [3, 1, 4, 1, 5, 9, 2, 6]: 这个硬编码的条件太傻了!
return 6
return None
```

这个 `if arr == [...]` 的判断简直是明晃晃的 bug 预警。我们需要一个通用、健壮的算法来实现这个功能。

怎么找第二大的元素?一个直观的想法是:
1. 找到最大的元素。
2. 再找到剩下的元素中最大的那个。

但这有个问题,如果最大元素出现多次呢?比如 `[5, 5, 3, 1]`,最大的 `5` 出现了两次,我们第二次找最大时,还是会找到 `5`。

所以,一个更健壮的思路是:
1. 维护两个变量:`largest` 和 `second_largest`。
2. 遍历数组。
3. 对于当前元素 `num`:
如果 `num > largest`:说明找到了新的最大值。原来的 `largest` 变成 `second_largest`,`num` 变成新的 `largest`。
如果 `num > second_largest` 且 `num < largest`:说明找到了新的第二大值,更新 `second_largest`。

初始值怎么设?
`largest` 和 `second_largest` 可以先用负无穷大(或者一个比数组中任何可能值都小的值)初始化。
或者,我们可以用数组的前两个元素来初始化(但要注意处理数组元素个数少于 2 的情况,这在我们之前的测试里已经考虑到了)。

让我们尝试用这种方法来重构(同时删除那个恶心的硬编码):

```python
import sys 假设我们用 sys.float_info.min 来表示负无穷

def find_second_largest(arr):
if not arr:
raise ValueError("Input array cannot be empty")

处理数组元素个数小于 2 的情况
if len(arr) < 2:
raise ValueError("Input array must contain at least two elements")

用数组的前两个元素来初始化(更优雅)
if arr[0] > arr[1]:
largest = arr[0]
second_largest = arr[1]
else:
largest = arr[1]
second_largest = arr[0]

从第三个元素开始遍历
for i in range(2, len(arr)):
num = arr[i]
if num > largest:
second_largest = largest 原来的 largest 变成 second_largest
largest = num num 成为新的 largest
elif num > second_largest and num < largest: 注意这里 num < largest 是为了处理重复最大值的情况
second_largest = num

如果所有元素都一样,second_largest 会等于 largest,这不符合“第二大”的定义
比如 [5, 5, 5],largest=5, second_largest=5。我们应该返回一个错误或者特定值。
这就需要我们在设计测试时就考虑到。
假设需求是:如果不存在第二大值(比如所有元素都一样),则抛错。
if largest == second_largest:
raise ValueError("No distinct second largest element found")

return second_largest
```

现在,我们需要添加新的测试来验证这个重构后的逻辑。

测试所有元素相同的场景: `test_find_second_largest_all_same()` > 应该抛出 `ValueError`。
测试包含重复最大值的场景: `test_find_second_largest_duplicate_max()`,输入 `[10, 5, 10, 2, 8]`,期望输出 `8`。

重要提示:

1. 小步快跑: TDD 的核心就是一次只解决一个小问题,写一个测试,让它通过,然后重构。不要试图一次性写出完美的算法。
2. 清晰的测试命名: 每个测试的名称都应该清晰地表达它在测试什么。
3. 测试隔离: 每个测试都应该是独立的,不依赖于其他测试的执行顺序或状态。
4. 回归测试: 每次修改代码后,一定要重新运行所有测试,以确保你没有破坏之前已经通过的功能。
5. 重构的勇气: 当所有测试都通过后,要勇敢地改进代码,使其更易读、更高效、更易于维护。但重构的目标是“改善代码结构”,而不是“增加新功能”或“修复bug”。
6. 不要跳过 RED 阶段: 故意让测试失败是 TDD 的起点,这迫使你思考如何解决问题,而不是凭感觉写代码。
7. 算法本身也是代码: TDD 对算法同样适用。算法的正确性、鲁棒性,都可以通过测试来保证。

总结一下 TDD 的循环:

RED: 写一个失败的测试。
GREEN: 写最小的、能让测试通过的代码。
REFACTOR: 在所有测试通过的情况下,改进代码。

重复这个循环,直到算法的每一个方面都被充分测试和验证。你会发现,通过这种方式实现的算法,不仅能正确工作,而且代码的结构也更加清晰,易于理解和维护。它更像是一种“编程对话”,你和你的测试在不断地沟通,确保最终的代码符合预期。

网友意见

user avatar
给我一个快排的实现。


你要搞明白,这个不是需求。

如果所有的需求都这样简洁精确高效……

那是是不需要程序员这个职业的,因为指不定哪天你给Cortana说一句,给我一个快排的实现,Cortana都可以给你……


而且你对算法的理解也未免太狭隘,君不见现在大部分人工智能、机器学习各种高大上的岗位,就是整天写测试用例和人肉来测试算法,修正算法。换个高大上的词就叫做拟合


TDD是测试驱动开发,说你要先把需求写成测试,再面向测试去开发。给我一个快排的实现这压根儿不是需求,真正的需求长这样:

明天我们要上线一个微信一样的App,你今天打开微信好好研究下。

类似的话题

  • 回答
    抛开那些生硬的列表式“最佳实践”,让我们来聊聊怎么实打实地用测试驱动开发(TDD)来搞定一个算法,从零开始,讲得透彻点,保证你读完能立刻上手。核心思路:写测试,让测试失败,然后写代码让它通过,最后再重构。听起来简单,但真正用起来,你会发现里面的门道不少。TDD 之于算法,就像是给你的思维加上了一个精.............
  • 回答
    .......
  • 回答
    生活中,我们都可能遇到“高不成,低不就”的困境,就像站在一个不上不下的岔路口,既不甘心现状,又对前方充满迷茫。当你感到自己似乎总是在一个不上不下的尴尬境地时,这并不罕见,也并非意味着你不够好。关键在于,我们如何调整心态,找到属于自己的那条路。一、 理解“高不成,低不就”背后的多重解读首先,我们需要明.............
  • 回答
    深入了解「实验室轮转」:在未知中寻觅真知在科研探索的漫漫长路上,「实验室轮转」(lab rotation)犹如一个精彩的“探索者手册”,为那些初涉科研门径的学子们提供了一个绝佳的机会,让他们可以在不同的研究领域、不同的课题组中“试水”,去感受科研的脉搏,去发现自己的兴趣所在。简单来说,实验室轮转就是.............
  • 回答
    .......
  • 回答
    .......
  • 回答
    .......
  • 回答
    快手 CEO 宿华发文称将用“正确的价值观”指导算法,这一表态在当下引发了广泛的关注和讨论。要深入理解这一表态的含义和影响,需要从多个维度进行剖析。一、 表态的背景与动机:首先,我们需要理解宿华发出这一表态的背景和可能的动机。1. 社会责任感与行业监管压力: 算法在内容平台扮演着核心角色,其推荐逻.............
  • 回答
    给发烧友建立正确的听音观,这可不是一件拍脑袋就能搞定的事,得有理有据,娓娓道来,让他们真心信服,而不是死记硬背。咱们得从根子上把这个问题捋顺了,用科学的态度,把那些形而上的“玄学”抽丝剥茧,留下实实在在的“真金”。第一步:打破“玄学”迷雾,树立“科学实证”基石很多发烧友对音质的评判,往往停留在一种“.............
  • 回答
    .......
  • 回答
    这篇报道确实挺引人深思的,特别是那句“近30万吨废金属,重量相当于5艘航母用钢”。咱们来掰扯掰扯这事儿,看看这说法有没有点儿夸张,背后又折射出什么问题。首先,咱们得捋清楚这30万吨废金属是怎么来的。共享单车这玩意儿,说是方便了出行,但走到哪儿看到那堆积如山的报废车,心里总不是滋味。这些车子,从设计到.............
  • 回答
    正确地对商业公司提出质疑是一项需要策略、专业性和法律意识的复杂任务。无论你是作为员工、投资者、消费者还是监管机构成员,提出质疑时都应遵循以下原则,以确保问题得到妥善处理,同时避免不必要的冲突或法律风险。 一、明确质疑的动机与目标1. 确定质疑的合法性 确保质疑内容符合法律法规(如《反不正当.............
  • 回答
    “为曹丞相盖被子”这个说法本身非常有趣,因为曹操在历史上是一位叱咤风云的政治家和军事家,他的人生充满了传奇和复杂性。在那个时代,为君主或重要人物盖被子是一项需要极其谨慎和讲究的礼仪性事务,绝非寻常之事。如果我们要“为曹丞相盖被子”,这更多的是一种象征性的、历史性的解读,涉及到对当时礼仪、社会等级以及.............
  • 回答
    毛文龙是一位在中国明朝末年具有争议的历史人物,对他的评价至今仍是史学界和民间讨论的热点。要正确认识毛文龙的是非功过,需要我们超越简单的“忠臣”或“奸臣”标签,从更宏观的历史背景、具体的军事和政治行为以及长期影响等多个维度进行分析。一、 毛文龙的背景与崛起: 时代背景: 明朝末年,朝政腐败,宦官专.............
  • 回答
    关于皮蛋瘦肉粥,这绝对是一道让人胃口大开又充满温暖的家常粥品。别看它简单,里面可是藏着不少门道呢!今天咱们就来聊聊,怎么把这碗粥做得既有颜值又有灵魂,让人吃一口就忘不掉。备料,是成功的一半咱们得先把这些宝贝们凑齐了: 米: 大米是主角,口感很重要。我个人比较喜欢用东北大米或者丝苗米,它们煮出来的.............
  • 回答
    哈喽!想知道怎么跟女生聊得开心,让对方觉得跟你聊天很有意思,甚至有点上头?这事儿说起来可不是一门玄学,更像是一门需要点技巧和真诚的艺术。别担心,咱们今天就来好好聊聊,让你成为那个让女生忍不住想多聊几句的有趣灵魂!开场白:别让沉默成为第一道坎很多人卡在第一步,不知道怎么开口。其实,想一个别出心裁的开场.............
  • 回答
    改变内向敏感的性格,不是要变成外向八面玲珑的人,也不是要磨平你那颗细腻的心,而是让你能够更好地驾驭这份特质,让它成为你的优势,而不是阻碍你前进的绊脚石。这更像是一种“精修”,而不是“大改”。咱们一步一步来聊,让你有个清晰的思路,而且我尽量不说那些干巴巴的理论,更贴近咱们的生活体验。第一步:理解你的“.............
  • 回答
    好的,咱们来聊聊怎么从自然和健康的方式入手,给大脑“充充电”,对抗那些让人提不起劲的抑郁情绪。请记住,这里说的“补充多巴胺”并非指直接吃什么药片就能立竿见影,而更多的是通过生活方式的调整,让身体自身分泌更多对情绪有益的神经递质,其中多巴胺就是一个重要的“快乐因子”。首先,咱们得明白,多巴胺不是万能的.............
  • 回答
    刷牙这事儿,看似简单,但要真说起来,里面门道可不少。别以为随便拿牙刷使劲刷几下就万事大吉了,那样不仅清洁不到位,还可能伤了牙龈和牙釉质。今天咱们就来掰扯掰扯,怎么把这刷牙的小事儿做得又好又到位,让你的牙齿健康亮白,口气清新自然。一、工欲善其事,必先利其器首先,得选对你的“战友”——牙刷。 刷头大.............
  • 回答
    怎么喝水,这听起来像是小学生才会问的问题。但说实话,咱们大多数人,包括我自己,其实都并没有真正“喝对”过水。不是说喝了会怎么样,而是,你有没有想过,怎样才能让这件每天无数次的小事,变得更有效,更滋养你的身体?今天,咱就来掰扯掰扯这喝水里的门道。一、 时机很重要,别等口渴了才想起喝水咱们身体有个小小的.............

本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度google,bing,sogou

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有