如何在Python中高效地过滤重复行？

Question

我的问题看起来像是一个经典的问题，但我在StackOverflow上找不到完全相同的问题。希望我的问题不是重复的。

我有一个很大的文件。这个文件有很多行和固定的列。我对所有列中的A列和B列感兴趣。我的目标是找出那些行，满足以下两个条件：(1) 该行的A列的值在其他行中也出现过，并且 (2) 有多于一行的A列值相同，但B列的值不同。

考虑下面的表格。我对第1、3和5行感兴趣，因为"a"在3行中出现，而且B列的值是不同的。相反，我对第2和4行不感兴趣，因为"b"出现了两次，但对应的B列值始终是"1"。同样，我也对第6行不感兴趣，因为"c"只出现了一次。

# A B C D
=========
1 a 0 x x
2 b 1 x x
3 a 2 x x
4 b 1 x x
5 a 3 x x
6 c 1 x x

为了找到这样的列，我读取文件中的所有行，把每一行转换成一个对象，创建一个对象的列表，然后用以下算法找到有趣的列。这个算法是有效的，但对于我的数据集来说，运行时间比较长。你有什么建议可以让这个算法更高效吗？

def getDuplicateList(oldlist):
    # find duplicate elements
    duplicate = set()
    a_to_b = {}
    for elements in oldlist:
        a = elements.getA()
        b = elements.getB()
        if a in a_to_b:
            if b != a_to_b[a]:
                duplicate.add(a)
        a_to_b[a] = b 

    # get duplicate list
    newlist = []
    for elements in oldlist:
        a = elements.getA()
        if a in duplicate:
            newlist.append(a)

    return newlist

附注：我添加了一些限制条件以便更清楚。

1. 我使用的是Python 2.7
2. 我需要“所有有趣的行”：duplicate有“某些”有趣的“a”。
3. 顺序很重要
4. 实际上，这些数据是一个程序执行过程中的内存访问。A列是内存访问，B列是我感兴趣的一些条件。如果一个内存访问在运行时有多个条件，那么我想研究内存访问的顺序。

Answer 1

原来的顺序需要保持吗？如果不需要的话，这看起来和groupby做的事情很像，使用内置的方法可能会让你的程序运行得更快。

也许可以试试下面这样的写法（未经测试！）：

s = sorted(oldlist, key=lambda e: (e.getA(), e.getB()))
interesting = (g for k,g in itertools.groupby(s, lambda e: e.getA())
               if len(g) > 1)

Answer 2

从你列表中的不同项目创建对象可能会导致一些速度变慢。在这里，我只是使用了collections模块来创建一个多重集合，让这个容器自己处理那些不相关的项目。你可以试试看这个方法对你是否有效。我假设你提供的文件格式是完全一样的。

import collections

def get_interesting_items(filename):
    multiset = collections.defaultdict(set)

    with open(filename) as f:
        # skip header lines
        f.readline()
        f.readline()

        # add all B items to Bset, indexed by A
        for line in f:
            _, a, b, _ = line.split(' ', 3)
            multiset[a].add(int(b))

        # generate all A, Bset pairs where Bset contains at least 2 items.
        for a, bset in multiset.iteritems():
            if len(bset) >= 2:
                yield a, bset

def main():
    for a, bset in get_interesting_items('myfile.txt'):
        print a, bset

Answer 3

其实，你在oldlist上进行的两次循环，可以用一次循环来替代。我觉得这样做在大多数情况下会让你的算法更高效，特别是对于很长的列表来说。

如果你不在意newlist的顺序，我建议用一个循环来替代，这样也能得到和你原来算法一样的结果。我已经用随机生成的百万元素列表测试过，结果总是大约只需要一半的时间：

def new_getDuplicateList(oldlist):
    # find duplicate elements
    newlist = []
    duplicate = set()
    a_to_b = {}
    for elements in oldlist:
        a = elements[0]
        b = elements[1]
        if a in duplicate:
            newlist.append(a)
        else:
            if a in a_to_b.keys():
                if not b in a_to_b[a]:
                    a_to_b[a].append(b)
                    duplicate.add(a)
                    extension = [a for i in a_to_b[a]]
                    newlist.extend(extension)
                else:
                    a_to_b[a].append(b)
            else:
                a_to_b[a] = [b]

    return newlist

（可能条件判断的部分可以写得更好看一些。）如果你想输出整行数据而不仅仅是a的值，修改起来也很简单，只需要把a换成(a, b)就可以了。另外要注意，这个方法比第一个算法稍微多占用一点内存，因为现在的字典里存的是列表。