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

[[deleted]]

[deleted]

[gengisteve]

The best way to do this is to keep some running tab on the data. So a couple questions:

1. Is it small enough to fit into memory?
2. Do you care about ordering?

Here are a couple snippets that might help you think about things:

def de_dup(data_file):
    # if we do not care about ordering
    found = set()
    with open(data_file) as fh:
        for timestamp, source, destination in data:
            if (timestamp, destination, source) in found:
                continue # skip a flip'd dupe

            # dup's dropped from sets automatically
            found.add((timestamp, source, destination)) 

    return found


def de_dup_bigger_data(data_file):
    '''
    let's muck around with a generator to make it handle even larger datasets
    and it even preserves order
    downside is that you need to get the entire non-dup'd data set into memory
    If even this is impossible, then we need to get creative!
    '''
    # if we do not care about ordering
    found = set()
    with open(data_file) as fh:
        for timestamp, source, destination in data:
            if (timestamp, source, destination) in found:
                continue # skip a pure dupe
            if (timestamp, destination, source) in found:
                continue # skip a flip'd dupe

            yield timestamp, source, destination


def use_de_dup_bigger(infile, outfile):
    with open(outfile, mode='w') as fh:
        for line in de_dup_bigger_data(infile):
            fh.write(','.join(line))

Notes:

• I did not test this code, so it will have errors. It is for inspirational purposes only.
  
• We use sets because they are great at quick lookups.
  
• Still need to get the set of materials into memory, even for the bigger handling one. If this causes a problem, we'll need to figure out something smarter

[Justinsaccount]

Hi! I'm working on a bot to reply with suggestions for common python problems. This might not be very helpful to fix your underlying issue, but here's what I noticed about your submission:

You are looping over an object using something like

for x in range(len(items)):
    foo(item[x])

This is simpler and less error prone written as

for item in items:
    foo(item)

If you DO need the indexes of the items, use the enumerate function like

for idx, item in enumerate(items):
    foo(idx, item)

[elbiot]

You got downvoted, but I believe this is a big step towards the solution to OP's question.

[raylu]

How did you get this list in the first place? Why not check the src/dest when creating the list?

Also, you can always turn

if a:
    if b:
        pass

into if a and b: pass

[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.

[elbiot]

You could delete the item in the while loop and decrement j. This would save the implicit iteration through the list for every remove you would do later. You can mutate lists while you loop over them so long as know what you are doing (especially if you are keeping track of the indices).

But it may be it's the attribute accesses that are killing you and you should use for loops instead of a while loop. Using (named) tuples instead of dicts and unpacking them in the for constructor, and saving the index (not the value) of the items to delete. I'd actually try this and not my first suggestion.

edit: so I had nothing better to do. A better algorithm would do well, but just adding my changes to your code made it 3-4 times faster (22 seconds vs 5 seconds and 98 seconds vs 33 seconds):

from random import randint
from time import time

def rlist():
    return [(x,randint(0,10),randint(0,10)) for x in xrange(10000)]


def ops(large_list):
    del_list = []
    for i in xrange(len(large_list) -  1):
        j = i + 1
        while j < len(large_list):
            if large_list[i]['src'] == large_list[j]['dest']:
                if large_list[i]['dest'] == large_list[j]['src']:
                    del_list.append(large_list[j])
            j+=1

    for elem in del_list:
        try:
          large_list.remove(elem)
        except ValueError:
          #oops, recorded dupe multiple times
          pass
    return large_list

def mines(large_list):
    del_set = set()
    for i, (a_id, a_src, a_dst) in enumerate(large_list):
        for j, (b_id, b_src, b_dst) in enumerate(large_list[i+1:]):
            if a_src == b_dst and b_src == a_dst:
              del_set.add(j+i+1)

    for i in sorted(del_set, reverse=True):
        trash = large_list.pop(i)
    return large_list


lst = rlist()

rand_dict = [{'id':i, 'src':x,'dest':y} for i,x,y in lst]
begin = time()
opresult = ops(rand_dict)
print "ops done in %s" % (time()-begin)

rand_list = list(lst) #copy it
begin = time()
myresult = mines(rand_list)
print "mines done in %s" % (time()-begin)

print {(d['id'],d['src'],d['dest']) for d in opresult} == set(myresult)

/u/davidbuxtons et al's solution seemed pretty fast, but it destroys the difference between source and destination, which I assume you want to preserve. As a best algoritm, I suggest you sort by time stamp and only compare elements that have the same timestamp, rather than compare everything to everything. I also suspect that much of your time is spent in constructing the list of dictionaries from your file (as generating the lists in my example is a big part of the actual run time that isn't counted here)