对lis进行排序和筛选

Question

我有这样的清单：

[['Richard', 1, 'Group A'], ['Mark', 3, 'Group A'],
 ['Alan', 4, 'Group B'], ['Dave', 3, 'Group B'],
 ['Gordon', 2, 'Group A']]

我想过滤，以便只保留每组中最低的数字（Richard的数字是1，Mark是3，Alan是4，等等），以便列表如下所示：

[['Richard', 1, 'Group A'], ['Dave', 3, 'Group B']]

我用lambda键排序：

filteredList = sorted(list,key=lambda x: x[2])

但是，当涉及到在每个组内进行排序和清除级别更高的个人时，我就被挡在了后面。你知道吗

在Python中有没有一种简单的方法来实现这一点，或者我应该迭代并测试每一行？你知道吗

Answer 1

这是一个简单的“bin and find min”问题。第一关，我们将：

from collections import defaultdict
bins = defaultdict(list)
for item in input_list:
    bins[item[2]].append(item)

现在我们只需要取每个箱子的最小值：

from operator import itemgetter
get_second = itemgetter(1)
results = [min(group, key=get_second) for group in bins.values()]

到目前为止，我们有一个O（N）算法（对于我们放入dict中的每个N项，装箱在O（1）时间内发生），并且找到min会在每个项上运行一次——所以这也是O（N）。。。你知道吗

---

如果需要，可以按组名对结果排序：

results.sort(key=itemgetter(2))

---

我们可以同时执行min步骤和装箱步骤来节省一点内存（例如，如果输入来自一个生成器并且有很多项）：

from operator import itemgetter
get_second = itemgetter(1)
results = {}
for item in input_stream:
    group = item[2]
    if group not in results:
        results[group] = item
    else:
        results[group] = min(item, results[group], key=get_second)

这实际上是与@wim提供的解决方案相同思想的不同实现。要在完成后排序结果（如果需要）：

 ordered_results = sorted(results.values(), key=itmegetter(2))

这样，我们每个小组只保留一个结果。代价是额外的代码复杂性。你知道吗

Answer 2

重新键入组名的数据。不要给数据命名list，因为它隐藏了一个内置名称。你知道吗

>>> results = {}
>>> for name, number, group in data:
...     key = group
...     value = number, name
...     results[key] = min(value, results.get(key, value))
...     
>>> [[name, number, group] for group, (number, name) in results.items()]
[['Dave', 3, 'Group B'], ['Richard', 1, 'Group A']]

纯python数据结构很好地处理了这个问题，sort/itertools方法是次优的，并且将复杂性从O（n）增加到O（n logn）。你知道吗

Answer 3

您可以使用collections.defaultdict根据第3项对子列表进行分组，然后使用min()函数和列表理解中的适当键来获得预期结果：

In [61]: from operator import itemgetter
In [62]: from collections import defaultdict
In [63]: lst = [['Richard', 1, 'Group A'], ['Mark', 3, 'Group A'], ['Alan', 4, 'Group B'], ['Dave', 3, 'Group B'], ['Gordon', 2, 'Group A']]

In [64]: d = defaultdict(list)

In [65]: for i, j, k in lst:
             d[k].append([i, j, k])
   ....:     

In [66]: [min(sub, key=itemgetter(1)) for sub in d.values()]
Out[66]: [['Dave', 3, 'Group B'], ['Richard', 1, 'Group A']]

通过将自定义对象传递给defaultdict()，您甚至可以以更优化的方式来实现这一点，这样它只会在新项具有较小的第二项时追加新项：

from collections import defaultdict


class MyList(list):

    def __init__(self, *args, **kwargs):
        super(MyList, self).__init__(*args, **kwargs)

    def special_append(self, arg):
        if not self:
            self.append(arg)
        elif arg[1] < self[0][1]:
            self[0] = arg

演示：

lst = [['Richard', 1, 'Group A'], ['Mark', 3, 'Group A'], ['Alan', 4, 'Group B'], ['Dave', 3, 'Group B'], ['Gordon', 2, 'Group A']]

d = defaultdict(MyList)

for i, j, k in lst:
    d[k].special_append([i, j, k])

print(d)

defaultdict(<class '__main__.MyList'>, {'Group B': [['Dave', 3, 'Group B']], 'Group A': [['Richard', 1, 'Group A']]})