python 列表搜索和串联性能

Question

我是 Python 的新手，正在寻找对我编写的简单 DFS 代码的一些批评：

def depthFirstSearch(problem):
    return depthFirstSearchRec(problem.getStartState(), problem)

def depthFirstSearchRec(currentState, problem, visited=[]):
    if currentState in visited:
        return None
    else:
        visited.append(currentState)

    if problem.isGoalState(currentState):
        return []

    for successor, action, _ in problem.getSuccessors(currentState):
        actions = depthFirstSearchRec(successor, problem)

        if actions is not None:
            return [action] + actions

    return None

问题：

使用 "in" 关键字搜索列表是否为 Python 中的 O(n) 操作？如果是这样，最好的方法是什么？
添加到列表的头部是 O(1)，就像添加到链表的头部，还是 O(n)，就像添加到数组的头部？如果是 O(n)，最好的方法是什么？
请随时指出任何 "bad" 编码实践，如果有的话

Answer 1

A Python list 是一个在内存中紧凑的数组，例如 C++ 的 std::vector。因此，in 运算符是 O(N) 并且添加到 list 末尾以外的任何地方也是 O(N)。解决办法是使用不同的数据结构——有lot！ -- 取决于你想要完成什么。

假设您的 states 是可散列的（如果您希望获得良好的性能，最好是！），visited 应该是 set -- 添加到集合中并且在其上使用 in 运算符都是 O(1)（因为该集合在内部实现为散列 table）。

至于 actions，最简单的想法可能是使用 collections.deque 而不是列表——双端队列是 O(1) 用于在任一端添加或删除（虽然列表要快得多，而且 O(1)，如果所有添加和删除都在右端）。

python 列表搜索和串联性能

python list search and concatenation performance

python

performance

coding-style