python - 算法设计——何时使用字典与列表来跟踪值

Question

对于以下问题，我使用字典来跟踪值，而提供的答案使用列表。有没有一种快速的方法可以为这些问题确定最有效的数据结构？

A robot moves in a plane starting from the original point (0,0). The robot can move toward UP, DOWN, LEFT and RIGHT with a given steps. The trace of robot movement is shown as the following: UP 5 DOWN 3 LEFT 3 RIGHT 2.­ The numbers after the direction are steps. Please write a program to compute the distance from current position after a sequence of movement and original point. If the distance is a float, then just print the nearest integer. Example: If the following tuples are given as input to the program: UP 5 DOWN 3 LEFT 3 RIGHT 2 Then, the output of the program should be: 2

我的答案使用字典(origin["y"] 表示 y，origin["x"] 表示 x):

direction = 0
steps = 0
command = (direction, steps)
command_list = []
origin = {"x": 0, "y": 0}
while direction is not '':
    direction = input("Direction (U, D, L, R):")
    steps = input("Number of steps:")
    command = (direction, steps)
    command_list.append(command)
print(command_list)

while len(command_list) > 0:
    current = command_list[-1]
    if current[0] == 'U':
        origin["y"] += int(current[1])
    elif current[0] == 'D':
        origin["y"] -= int(current[1])
    elif current[0] == 'L':
        origin["x"] -= int(current[1])
    elif current[0] == 'R':
        origin["x"] += int(current[1])
    command_list.pop()
distance = ((origin["x"])**2 + (origin["y"])**2)**0.5
print(distance)

提供的答案使用列表(pos[0] 代表 y，pos[1] 代表 x):

import math
pos = [0,0]
while True:
    s = raw_input()
    if not s:
        break
    movement = s.split(" ")
    direction = movement[0]
    steps = int(movement[1])
    if direction=="UP":
        pos[0]+=steps
    elif direction=="DOWN":
        pos[0]-=steps
    elif direction=="LEFT":
        pos[1]-=steps
    elif direction=="RIGHT":
        pos[1]+=steps
    else:
        pass

print int(round(math.sqrt(pos[1]**2+pos[0]**2)))

Answer 1

我将就您的问题提出几点意见，因为我强烈反对关闭建议。你的问题中有很多不是意见。

总的来说，您选择的词典不合适。对于像这样的玩具程序，它没有太大区别，但我假设您对严肃程序的最佳实践感兴趣。在生产软件中，您不会做出这种选择。为什么？

• 容易出错。 future 代码中的错字，例如origin["t"] = 3 当你的意思是 origin["y"] = 3 是一个讨厌的错误，可能很难找到。 t = 3 更有可能导致“快速失败”。 (在 C++ 或 Java 等静态类型语言中，这肯定是编译时错误。)

• 空间开销。一个简单的标量变量基本上不需要超出值本身的空间。数组对于跟踪其位置、当前和最大大小的“掺杂向量”有固定的开销。字典需要更多额外空间用于开放寻址、未使用的哈希桶和填充跟踪。

• 速度。

  • 访问标量变量非常快:只需几条处理器指令。
  • 在知道其索引时访问元组或数组元素也非常快，尽管不如变量访问快。需要额外的指令来检查数组边界。将一个元素添加到数组可能需要 O(当前数组大小)才能将当前内容复制到更大的内存块中。元组和数组的优点是您可以根据计算出的整数索引快速访问元素。标量变量不会这样做。当您需要整数索引访问时，请选择一个数组/元组。当您知道确切的大小并且不太可能更改时，请使用元组。它们的不变性往往使代码更易于理解(并且线程安全)。
  • 访问字典元素的成本仍然更高，因为必须计算散列值并使用可能的冲突解决方案遍历存储桶。添加单个元素也可以触发表重组，这是 O(table size)，常数因子比列表重组大得多，因为所有元素都必须重新散列。字典的一大优势是访问所有存储的对可能需要相同的时间。只有当你需要这种能力时，你才应该选择字典:存储从键到值的“映射”。

从以上所有内容得出结论，原点坐标的最佳选择应该是简单变量。如果您稍后以需要将 (x, y) 对传入/传出方法的方式增强程序，那么您会考虑使用 Point 类。