关于数据结构权衡利弊的举例可能不合适？ about hello-algo HOT 5 CLOSED

谢谢反馈！

“链表牺牲数据访问速度”的说法可能并不准确，应该说牺牲了随机访问的速度

这句话并没有错误，随机访问更慢是因为时间复杂度不同，顺序访问更慢是因为缓存机制。

链表顺序访问存在一定的性能损失但是我认为一般情况下都可以忽略不计。

是的，顺序访问的损失相对更少。我们可以做一下实际测试，在以下测试中，遍历数组比遍历链表快约 2 倍。在某些场景下，我们是需要考虑到这个问题的，例如数据访问频率远高于数据增删的场景。

import time


class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next


# Create a linked list and an array with the same elements
size = 10000

array = list(range(size))

head = ListNode(0)
cur = head
for i in range(1, size):
    cur.next = ListNode(i)
    cur = cur.next


# Time the traversal of the array
start_time = time.time()
for num in array:
    pass
array_time = time.time() - start_time

# Time the traversal of the linked list
start_time = time.time()
cur = head
while cur:
    cur = cur.next
linked_list_time = time.time() - start_time

print("Array traversal time: {:.4f} s".format(array_time))
print("Linked list traversal time: {:.4f} s".format(linked_list_time))
# Array traversal time: 0.0003s
# Linked list traversal time: 0.0006s

此处应该选用两个存储内容相同的数据结构进行对比，比如用键值数组实现 Map 和使用哈希表实现 Map，后者空间利用率一般低于前者，但性能更好，这样对比才有意义。

你介绍的示例很好，指出了在数据结构设计中，时间使用与空间占用是一个 trade-off 的过程。但这个例子不太适合出现在这一节，因为这是第一章中的内容，介绍的是非常 general 的内容，相当一部分读者此时对哈希表的实现是没有概念的。

原文想要表达的是更一般性的结论，即 如果想在某方面取得提升，往往需要在另一方面作出妥协 ，并举出尽可能简单的例子：一条“链”和一张“图”。

使用两个存储内容完全不同的数据结构对比内存占用是没有意义的，就像存储世界地图的数据结构一定比存储一个二进制位的数据结构占用内存一样。

原文没有想要对比“存储内容完全不同的数据结构”，而是想要表达当存储数据的“复杂性”增加时，往往会导致占用空间的增加。而数据结构的设计者需要考虑，如何让这个增加尽可能的小，尽量不影响数据操作的效率等等。我们知道的是，存储世界地图和存储二进制数的数据结构一定是达到了信息量、空间占用、效率等方面的上佳平衡。

from hello-algo.

确实链表因为地址跳转的原因遍历性能会受到影响，这里是我疏忽了。

我仍然认为表达“如果想在某方面取得提升，往往需要在另一方面作出妥协”时使用这个示例并不妥当。图相较于链表存储了更多的信息，所以图的内存占用高于链表，这只是由于需要存储这些信息而导致的数据结构体积膨胀，也就是说是一种必然性的膨胀，而不是由于我需要在内存占用和性能上取舍导致的内存占用膨胀。

如果需要在这里说明数据结构的取舍，我认为可以使用一些生活中可以接触到的事务进行类比。比如世界地图有平面纸张的存储形式，也有地球仪这样的存储形式，地球仪在尽可能完美地复现了真实地图，而使用平面纸张存储虽然会导致地图部分失真，但可以极大地降低存储成本；纸质书和电子书，两者阅读体验、存储成本也可以进行类比；购买商品时价格和功能地取舍等等。

from hello-algo.

我理解你的看法，我同意时间效率和时间效率的权衡是最常见的。

我更愿意将将数据结构的“信息表示能力”、“时间效率”和“空间效率”视为同一层面的概念，即将“信息表示能力”单独看作一种考虑因素。

拿地球仪 vs. 地图来举例。我们因为想要获取更完整的信息（不失真），需要设计选取一个信息表示能力更强的数据结构（即地球仪），那么代价就是空间效率降低（地球仪材料成本、存储成本更高）。

from hello-algo.

我明白您的意思了，但是我还是觉得这个示例的描述不是特别合理，至少在计算机领域，只有满足最低需求的方案才能参加到权衡的过程中，使用图是需求导致的必然选择，权衡应该发生在选择使用何种方式存储图上。

也就是说在图和链表之间选择并不是在权衡不同的数据结构，只是说这个权衡的过程也考虑到了数据结构相关的问题，其本质是在权衡需求。这个权衡并不是发生在数据结构的设计过程中，而是在其之前，这与本段开头的“数据结构设计是一个充满权衡的过程”想违背，容易引起读者误解。

如果想要表明“想要表达更多信息，难免导致空间膨胀”的话，我觉得还是舍弃这个例子另起一段单独说比较好，或者修改段落开头，使得两者不再相互冲突。

from hello-algo.

看你如何定义“权衡”了，权衡并非仅出现于性能优化。（当然，性能优化的确是权衡最重要的体现方面）

就比如你提到的“最低需求的方案”，有些问题链表可以满足“最低需求”，图可以满足“高级需求”，此时就需要做权衡：是花更多的空间来达到更好的效果，还是节省空间接受一般的结果。

举个例子，n 个星球排成一条线，计算每个星球所受的万有引力。你可以：

1. 设计一个链表存储每个星球与最近星球的距离，然后计算一个近似解；
2. 也可以设计一个图存储星球两两之间的距离，然后计算精确解；

至于选择哪个，那是我们需要权衡的问题。我会去评估近似解是否够用，以及内存资源够不够存储图（当 n 较大时，方案 1 能节省巨大的空间），再做决定。

在实际问题中，花更多的资源达到更优的结果，还是设计一个简单方案只求次优的结果，是一个常见的权衡问题。完全固定住目标，优化特定场景下的全局性能，又是一种权衡。

咱们不要纠结这个啦，我们只是对这些咬文嚼字的问题的定义不太一样。

from hello-algo.