Как эффективно фильтровать повторяющиеся строки в Python?

Question

Мой вопрос выглядит как классический, но я не могу найти точно такой же вопрос в stackoverflow. Надеюсь, мой вопрос не является дубликатом.

У меня большой файл. Файл имеет много строк и фиксированных столбцов. Меня интересуют столбцы А и В среди всех столбцов. Цель состоит в том, чтобы я хотел получить строки, где (1) значение в столбце A в строке также отображается в других строках, и (2) существует более одной строки, которая имеет такое же значение столбца A, но различное значение столбца B.

Рассмотрим следующую таблицу. Меня интересуют строки 1,3 и 5, потому что «а» появляется в 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

p.s. Я добавлю некоторые ограничения, чтобы уточнить.

1. Я использую Python 2.7
2. Мне нужны "все интересные строки": duplicate имеет "некоторые" интересные "a" s.
3. Порядок важен
4. Фактически, данные являются обращениями к памяти при выполнении программы. Столбец A имеет доступ к памяти, а столбец B имеет некоторые интересующие меня условия. Если доступ к памяти имеет несколько условий во время выполнения, я хотел бы изучить последовательность доступа к памяти.

Answer 1

Создание объектов из различных элементов в вашем списке может вызвать некоторое замедление. Здесь я просто использую модуль коллекций для создания мультимножества и позволяю самому контейнеру сортировать ненужные элементы. Посмотрите, как это работает для вас. Я предполагаю точный формат файла, который вы указали выше.

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 2

Ну, две итерации по элементам в 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) там, где это необходимо.Также обратите внимание, что он потребляет немного больше памяти, чем первый алгоритм, из-за диктов a_to_b, которые теперь содержат списки.

Answer 3

Ваша сложность уже довольно хороша. Вы просто ищете линейное ускорение здесь.

Есть ли причина, по которой вы не можете просто вернуть duplicate вместо выполнения второго цикла?

Если вы добавите else, вы можете избежать повторной вставки a_to_b[a] = b, когда он уже есть.

Кроме того, дисковый ввод / вывод медленный и имеет много времени, когда ЦП доступен для других вещей в ожидании чтения. Поскольку у вас много таких действий, вы, вероятно, сможете значительно ускорить процесс, если один поток найдет дубликаты, а другой поток читает следующий файл.

Answer 4

Следующее чрезвычайно просто.Это дает значение A интересных строк;изменить его для получения строк будет просто:

def isInteresting(rows):
    avals = {}
    for row in rows:
        bvals = avals.get(row.getA()) or set()
        bvals.add(rowgetB())
        avals[row.getA()] = bvals

    return [ aval
             for aval in avals.keys()
             if avals[aval] and len(avals[aval]) > 1 ]

Answer 5

Нужно ли сохранять первоначальный заказ?Если нет, то это похоже на то, что делает 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)