时间戳

首页 > 解决方案 > Python检查列表中是否存在用于检测循环的列表

python - Python检查列表中是否存在用于检测循环的列表

问题描述

我有一个大约 60000 个数据点的样本，并且在迭代算法中，在每个步骤中，根据某些标准，我要么“删除”（设置为 NaN）其中一个数据点，要么“添加”一个先前删除的数据点回到样本中（设置回其原始值）。为了避免算法陷入死循环，每次迭代的样本应该总是不同的。因此，我跟踪当前在每次迭代中删除的数据点，并将元素索引存储在列表中，如下所示：

现在在当前迭代 7 中，算法建议删除数组索引为 4 的元素，因此新状态data_state_temp将是 [2,1,3]。目前它检查它是否已经通过

flag_cycle = (data_state_temp in data_state_list)

该算法检查新状态以添加/删除不同的数组元素，直到flag_cycleis False，然后继续。

除此之外，它还没有完全工作，因为迭代 7 中的状态 [2,1,3] 和迭代 3 中的 [2,3,1] 是相同的，但列表不同（需要对它们进行排序或更好将新删除的数组元素插入到它们应该属于排序列表的位置），问题是算法变得非常慢。在实践中，例如data_state_temp长度为 15000，并且data_state_list有 40000 个列表，通常长度增加到 15000。

问题：

标签： pythonlist

解决方案

保留历史记录（固定查找）

如果你不关心过去状态的顺序——只是它曾经被访问过——那么让我们收集set所有过去的状态。这给了我们一个固定的查找而不是线性查找in（例如for needle in haystack）

要使 aset发挥其魔力，它必须使用可散列类型。简而言之，atuple是不可变的，因此是可散列的，因此可以与 . 一起使用set。

from itertools import chain

# let's say we already have state that is 15000 long
data_states = set()
data_state = tuple(range(15000))
data_states.add(data_state)

# we loop until we decide on a new state
while data_state in data_states:
    # either you decide to remove an element, say 42
    # (can skip sort because the previous tuple was already sorted)
    new_data_state = tuple(x for x in data_state if x != 42)

    # or you decide to add an element, 9000
    new_data_state = tuple(sorted(x for x in chain(data_state, [9000])))

    data_state = new_data_state

# now commit this state to your history
data_states.add(new_data_state)

请注意，元组是不可变的，因此我们必须在创建元组之前先进行排序。另请注意，sorted(_)表单创建一个副本，而_.sort()执行就地排序。由于我们将先前的状态解析为生成器，因此后一种排序是不可能的，因为我们没有内存。所以选择前者。然后将其输入tuple()构造函数。

运行时复杂性

给定len(state) = n：

new_data_state = tuple(sorted(x for x in chain(data_state, [9000])))
  1. x for x in ...: 带有n操作的生成器
  2. sorted(...)：创建一个列表，填充n条目
  3. tuple(...)：创建一个元组，填充n条目

步骤 1+2 发生在一次传递中n。然后重复n第 3 步。总运行时复杂度O{2n}为state.

问：如何加速？

我上面列出的。如果您对记忆感到束手无策，您可能会考虑使用更紧凑的表示形式state。

例如，您可能会分块state成3由5000连续数字组成的块。然后使用嵌套字典。例如data_states[(x for x in range(5000)][(x for x in range(5000)] == <all the remaining digits>

通过这种方式，空间成本被摊销，使得带有15777数字的元素的增量空间成本仅为15777 - 5000 - 5000 = 5777数字。这本质上就是字典的作用。

问：它是否按长度比较列表元素？

是的，它执行长度匹配作为短路 a 的第一个检查False。但是不，它仍然处理每一个元素。

推荐阅读