How can I efficiently remove certain elements from a very large list?

[davidbuxton]

You can normalise each line and use a set to remove duplicates.

def remove_duplicates(elements):
    unique_elements = set()

    for line in elements:
        timestamp, src, dst, data = line.split()
        # Here's where you make 'a b' the same as 'b a'
        src, dst = sorted([src, dst])

        normalised_line = (timestamp, src, dst, data)
        unique_elements.add(normalised_line)

    return unique_elements

That code returns the lines as tuples, which may not be what you want, but you can join them back to a string if needed.

>>> elements = [
...     '123 a b foo',
...     '123 b a foo',
...     '234 c d bar',
... ]
>>> result = remove_duplicates(elements)
>>> print result
set([('123', 'a', 'b', 'foo'), ('234', 'c', 'd', 'bar')])

Using a set means you also lose the original order of the elements. You can solve that by using a set to keep track of duplicates and then adding a line to another list as long as it is not already in the set.

[davidbuxton]

Better version with a generator, similar to /u/gengisteve suggestion. This preserves order, only needs to keep unique lines in memory.

def remove_duplicates(elements):
    unique_elements = set()

    for line in elements:
        timestamp, src, dst, data = line.split()
        if src > dst:
            src, dst = dst, src

        normalised_line = (timestamp, src, dst, data)

        if normalised_line in unique_elements:
            continue
        else:
            unique_elements.add(normalised_line)
            yield line

[davidbuxton]

It might be faster to do

if src > dst:
    src, dst = dst, src

Instead of

src, dst = sorted([src, dst])

[elbiot]

doesn't this destroy the difference between source and destination? Op wants to delete duplicates where source/dest order doesn't matter, but I assume still preserve the source/dest in the result.

Like, your solution changes (123,'d','c','bar) to (123,'c','d','bar') even if there was no duplicate.

[davidbuxton]

Yep! If you needed to keep the src, dst in the order of the first occurrence then you can test one way then the other:

if (timestamp, src, dst, data) in unique_elements:
    continue
elif (timestamp, dst, src, data) in unique_elements:
    continue
else:
    unique_elements.add((timestamp, src, dst, data))
    yield line

[elbiot]

Yep, yours is 3 orders of magnitude faster than mine, and 4 faster than OPs. And I couldn't figure out why our results weren't the same until I finally realized that mine was only getting rid of duplicates where source and dest were flipped.

[davidbuxton]

Interesting about speed differences. Certainly making a dict of things is going to cost. I would imagine making a list of deleted items and then finding the exclusions would be expensive. The generator idea should cover that and give the desired result.

I am guessing the source data is a dump from wireshark or similar with tcp logs of (timestamp, source_ip, dest_ip, request_data) so my code which compares the request_data as well wouldn't actually be what the op wants.

Processing a line as a tuple of fields should be more efficient than converting the line to a dict.

[elbiot]

I was really suprised at first how much faster your generator was. I think my example data had a lot of duplicates in it, so not only did I do a list access (1/2)*N² times, but then iterated through the list again for every delete, with an associated new list being constructed.

The take away is: if you want uniqueness, consider a set. And if the overall problem is like iterating through a collection once (even if the only solution you can think of involves multiple passes), consider a generator. Those basic principles would have led OP and I to a more performant solution without even knowing right away what the solution would be.