在Python中对列表进行分类

Question

什么是在Python中对列表进行分类的最佳方法？

例如：

totalist is below

totalist[1] = ['A','B','C','D','E']
totalist[2] = ['A','B','X','Y','Z']
totalist[3] = ['A','F','T','U','V']
totalist[4] = ['A','F','M','N','O']

假设我想获取列表中前两个项目为['A','B']的列表，即list[1]和list[2]。有没有一种简单的方法可以不用逐个迭代地获取这些内容？例如：

if ['A','B'] in totalist

我知道那样不起作用。

- user1179317

---

你尝试的代码是什么？ - Annapoornima Koppad

没有办法解决这个问题，除非按照答案所建议的以某种形式迭代它。如果高效检查是一个重要的优先事项，那么您应该重新制定数据表示方式；为了提高速度而牺牲一些空间复杂度。例如，在创建列表时，可以在原地记录哪些行满足属性。 - gowrath

Answer 1

您可以检查每个列表的前两个元素。

for totalist in all_lists:
    if totalist[:2] == ['A', 'B']:
        # Do something.

注意： Kasramvd建议的一行解决方案也非常好。我发现我的解决方案更易读。不过，我应该说，推导式比普通for循环略微快一些。（我亲自测试过。）

- Rockybilly

---

这应该很好用，不确定为什么你被踩了，但我已经帮你反驳了。 - bravosierra99

我认为他的意思是不要循环遍历每个列表中的每个单独项。你必须迭代遍历这些列表，否则你无法检查每一个... - bravosierra99

谢谢，那个if语句就是我要找的。 我基本上有成千上万个路径（以列表形式），并试图将它们分类。 看看路径属于哪个分支。 有点像树形结构。 - user1179317

如果您正在尝试对所有列表进行分类，您应该查看groupby。您可以使用关键字lambda x: x[:2]。 - Rockybilly

@Rockybilly：或者使用operator.itemgetter(slice(2))作为键来减少Python层的工作。但你需要进行排序；itertools.groupby类似于uniq；它只会折叠相邻的元素。因此，可以使用类似于prefixkey = operator.itemgetter(slice(2))的代码，然后使用for prefix, grp in groupby(sorted(totalist, key=prefixkey), key=prefixkey):进行操作。 - ShadowRanger

Answer 2

仅供娱乐，itertools 解决方案可将每个元素的工作推送到C层：

from future_builtins import map  # Py2 only; not needed on Py3
from itertools import compress
from operator import itemgetter

# Generator
prefixes = map(itemgetter(slice(2)), totalist)
selectors = map(['A','B'].__eq__, prefixes)

# If you need them one at a time, just skip list wrapping and iterate
# compress output directly
matches = list(compress(totalist, selectors))

这可以简化为一行代码：

matches = list(compress(totalist, map(['A','B'].__eq__, map(itemgetter(slice(2)), totalist))))

但我不建议这样做。顺便提一句，如果totalist可能是生成器而不是可重复序列，您需要使用itertools.tee将其加倍，添加：

 totalist, forselection = itertools.tee(totalist, 2)

将prefixes的定义更改为在forselection上进行map，而不是totalist；由于compress同时迭代两个迭代器，因此tee不会有有意义的内存开销。

当然，正如其他人所指出的那样，即使转移到C语言，这也是一个线性算法。理想情况下，您可以使用类似于collections.defaultdict(list)的东西，将每个list的两个元素前缀（转换为tuple以使它们成为合法的dict键）映射到具有该前缀的所有list的list中。然后，您只需对N个list进行线性搜索以查找具有匹配前缀的list，而是执行totaldict['A', 'B']，您将获得具有O(1)查找的结果（还有更少的固定工作量;没有常数切片）。

示例预计算工作：

from collections import defaultdict

totaldict = defaultdict(list)
for x in totalist:
    totaldict[tuple(x[:2])].append(x)

# Optionally, to prevent autovivification later:
totaldict = dict(totaldict)

然后，您只需使用以下代码即可立即有效地获取任何两个元素前缀的 matches：

matches = totaldict['A', 'B']

- ShadowRanger

---

真是太有趣了！你因为这个有趣的因素得到了一个赞，但请不要让这成为被接受的答案！ :) - Rolf of Saxony

@RolfofSaxony： :-) 我喜欢 itertools；虽然它几乎肯定不适用于这里，但是一般的模式实际上是如何在其他情况下很好地使用它的一个不错的例子。在 OP 的情况下，我几乎肯定会选择 defaultdict(list) 路线。 - ShadowRanger

@RolfofSaxony 没有必要玩乐，将一些函数组合在一起并进行不必要的操作不是正确的方法，特别是对于可以使用更简单、更快速的方法完成的如此简单的任务。 - Mazdak

@Kasramvd 哎呀，我知道啊，我只是以回答的精神接受了它，如果你看了我的最后一句话，你可能已经能够推断出来了。 - Rolf of Saxony

Answer 3

基本上，您无法在Python中使用嵌套列表来完成此操作。但如果您正在寻找一种优化的方法，以下是一些方法：

使用简单的列表推导式，通过比较预期列表与子列表的前两个项：

>>> [sub for sub in totalist if sub[:2] == ['A', 'B']]
[['A', 'B', 'C', 'D', 'E'], ['A', 'B', 'X', 'Y', 'Z']]

如果您想要索引，请使用enumerate：

>>> [ind for ind, sub in enumerate(totalist) if sub[:2] == ['A', 'B']]
[0, 1]

如果你处理大数据集，这里有一个在Numpy中相当优化的方法：

>>> import numpy as np    
>>> 
>>> totalist = np.array([['A','B','C','D','E'],
...                      ['A','B','X','Y','Z'],
...                      ['A','F','T','U','V'],
...                      ['A','F','M','N','O']])

>>> totalist[(totalist[:,:2]==['A', 'B']).all(axis=1)]
array([['A', 'B', 'C', 'D', 'E'],
       ['A', 'B', 'X', 'Y', 'Z']], 
      dtype='|S1')

如果你不想使用循环，而且想要一种函数式的方式作为python中列表推导式的替代方案，那么你可以使用filter函数。但是需要注意的是，filter函数并不像列表推导式那样优化。

>>> list(filter(lambda x: x[:2]==['A', 'B'], totalist))
[['A', 'B', 'C', 'D', 'E'], ['A', 'B', 'X', 'Y', 'Z']]

- Mazdak

---

请注意，如果你的谓词函数是在 C 中内置实现的（并且输入足够长），那么 filter 函数会被完美优化；在这种情况下，它通常比等效的生成器表达式/列表推导运行更快。如果需要一个无法内联到生成器表达式/列表推导中的 lambda，那么 filter 函数肯定会更慢；如果它正在使用一个不能避免用于生成器表达式/列表推导的 def 函数，则通常在性能上类似（通常略慢，但相差不大）。filter 函数很先进，在仅使用生成器表达式/列表推导也完全可以，但如果你理解其工作原理，它可以为你提供速度提升。 - ShadowRanger

@ShadowRanger 是的，我知道，但还是谢谢你的评论。 - Mazdak

Answer 4

你可以做到这一点。

>>> for i in totalist:
...     if ['A','B']==i[:2]:
...             print i

- Annapoornima Koppad

---

我写了答案，然后看到他已经写了一样的。 :-) - Annapoornima Koppad

都会发生的事情！ - Rolf of Saxony

Answer 5

您似乎关心性能（成本）问题。如果需要这样做，并且您担心性能问题，那么您需要使用不同的数据结构。这将在制作列表时增加一些“成本”，但在筛选它们时可以节省时间。

如果基于前两个元素进行过滤的需求是固定的（不能推广到前n个元素），那么我会将它们添加到字典中，其中键是前两个元素的元组，而项是列表的列表。

然后，您只需通过进行字典查找来检索列表。这很容易做到，并且几乎不会在制作列表时增加内存和时间成本，同时可以带来潜在的大幅加速。

- Tim Richardson

---

它不总是前两个元素，随着您遍历列表，它会不断增加。基本上，这些列表是路径，并且按分支对路径进行分类，有点像树形结构。我将使用上面提到的if语句。 - user1179317