高效查找Python关联列表中的元素

Question

我有一组列表，长得像这样：

conditions = [
["condition1", ["sample1", "sample2", "sample3"]],
["condition2", ["sample4", "sample5", "sample6"],
...]

我该如何在Python中高效又优雅地完成以下几件事呢？

1. 找到符合某种条件的所有元素？

   比如说，获取所有在condition2中的样本。目前我可以这样做：

   for cond in conditions:
     cond_name, samples = cond
     if cond_name == requested_cond:
       return samples
   

   但这样做太繁琐了。

2. 找到一组条件的有序并集？比如说，ordered_union(["condition1", "condition2"], conditions) 应该返回：

   ["sample1", "sample2", "sample3", "sample4", "sample5", "sample6"]
   

我该如何在Python中高效地做到这一点？可能有一些聪明的单行代码？

Answer 1

关于第一个问题：

>>> dict(conditions)['condition1']
['sample1', 'sample2', 'sample3']

关于第二个问题（你提到的“有序合并”不太清楚，所以我假设你是指“按顺序连接的有序列表”）：

>>> tmpdict = dict(conditions)
>>> sum( map(tmpdict.get, ["condition1", "condition2"]), [] )
['sample1', 'sample2', 'sample3', 'sample4', 'sample5', 'sample6']

另外，示例被修改以回应A.M.的合理批评——因为实现上的问题，sum()在列表大小增加时表现出二次方的行为。因此，我建议使用下面的代码：

>>> import operator
>>> tmpdict = dict(conditions)
>>> reduce(operator.iadd, map(tmpdict.get, ["condition1", "condition2"]), [] )
['sample1', 'sample2', 'sample3', 'sample4', 'sample5', 'sample6']

Answer 2

这看起来更适合用一个 dict 来处理：

conditions = {
"condition1": ["sample1", "sample2", "sample3"],
"condition2": ["sample4", "sample5", "sample6"],
...}

然后你可以通过下面的方式获取“有序的并集”：

>>> conditions["condition1"]+conditions["condition2"]
['sample1', 'sample2', 'sample3', 'sample4', 'sample5', 'sample6']

在 Python 3.1 或 2.7 中，你可以使用 OrderedDict 来保持顺序：

from collections import OrderedDict
conditions = OrderedDict([
["condition1", ["sample1", "sample2", "sample3"]],
["condition2", ["sample4", "sample5", "sample6"]]
])

这样你也可以获取“有序的并集”，同样适用于任意大小的 OrderedDict：

>>> import itertools
>>> [item for item in itertools.chain(*conditions.values())]
['sample1', 'sample2', 'sample3', 'sample4', 'sample5', 'sample6']

Answer 3

哦，如果你不得不使用那个笨重的数据结构，那就别指望能有太好的效果了。你第一个解决方案的简化版大概是这样的：

def samplesof(requested_cond, conditions):
    return next(s for c, s in conditions if c==requested_cond)

而对于第二个，如果你坚持要用一行代码的话，可能会是这样的：

def ordered_union(the_conds, conditions):
    return [s for c in the_conds for s in samplesof(c, conditions)]

其实还有更快的方法来解决第二个问题，但那些方法都是多行代码，比如：

aux_set = set(the_conds)
samples_by_cond = dict((c, s) for c, s in conditions if c in aux_set)
return [s for c in the_conds for s in samples_by_cond[c]]

需要注意的是，这种后面提到的方法之所以更快，是因为它使用了合适的数据结构（一个集合和一个字典）——可惜的是，它必须自己构建这些结构，因为你输入的conditions嵌套列表实际上是个不太合适的数据结构。

你能不能把conditions封装成一个类的成员变量，这样就可以只构建一次那些重要的（合适且快速的）辅助数据结构呢？比如：

class Sensible(object):
  def __init__(self, conditions):
    self.seq = []
    self.dic = {}
    for c, s in conditions:
      self.seq.append(c)
      self.dic[c] = s
  def samplesof(self, requested_condition):
    return self.dic[requested_condition]
  def ordered_union(self, the_conds):
    return [s for c in the_conds for s in self.dic[c]]

现在，这样的做法既快又优雅！

我假设你需要self.seq（条件的序列）来做其他事情（这对于你提到的两个操作来说肯定不是必须的！），而且这个序列和样本中没有重复项（无论你的实际要求是什么，适应起来都不会太难，但如果你什么都不说就盲目猜测，那就会非常困难且毫无意义;-）。