8
\$\begingroup\$

I am implementing a statistical program and have created a performance bottleneck and was hoping that I could obtain some help from the community to possibly point me in the direction of optimization.

I am creating a set for each row in a file and finding the intersection of that set by comparing the set data of each row in the same file. I then use the size of that intersection to filter certain sets from the output. The problem is that I have a nested for loop(\$O(n^2)\$) and the standard size of the files incoming into the program are just over 20,000 lines long. I have timed the algorithm and for under 500 lines it runs in about 20 minutes but for the big files it takes about 8 hours to finish.

I have 16GB of RAM at disposal and a significantly quick 4-core Intel i7 processor. I have noticed no significant difference in memory use by copying the list1 and using a second list for comparison instead of opening the file again(maybe this is because I have an SSD?). I thought the with open mechanism reads/writes directly to the HDD which is slower but noticed no difference when using two lists. In fact, the program rarely uses more than 1GB of RAM during operation.

I am hoping that other people have used a certain datatype or maybe better understands multiprocessing in Python and that they might be able to help me speed things up. I appreciate any help and I hope my code isn't too poorly written.

import ast, sys, os, shutil
list1 = []
filterValue = 3
end = 0

# creates output file with filterValue appended to name
with open(arg2 + arg1 + "/filteredSets" + str(filterValue) , "w") as outfile:
    with open(arg2 + arg1 + "/file", "r") as infile:
        # create a list of sets of rows in file
        for row in infile:
            list1.append(set(ast.literal_eval(row)))

            infile.seek(0)
            for row in infile:
                # if file only has one row, no comparisons need to be made
                if not(len(list1) == 1):
                    # get the first set from the list and...
                    set1 = set(ast.literal_eval(row))
                    # ...find the intersection of every other set in the file
                    for i in range(0, len(list1)):
                        # don't compare the set with itself
                        if not(pos == i):
                            set2 = list1[i]
                            set3 = set1.intersection(set2)
                            # if the two sets have less than 3 items in common
                            if(len(set3) < filterValue):
                                # and you've reached the end of the file
                                if(i == len(list1) - 1):
                                    # append the row in outfile
                                    outfile.write(row)
                                    # increase position in infile
                                    pos += 1
                            else:
                                break
                    else:
                        outfile.write(row)

Sample input would be a file with this format:

[userID1, userID2, userID3]
[userID5, userID3, userID9]
[userID10, userID2, userID3, userID1]
[userID8, userID20, userID11, userID1]

The output file if this were the input file would be:

[userID5, userID3, userID9]
[userID8, userID20, userID11, userID1]

...because the two sets removed contained three or more of the same user IDs.

\$\endgroup\$
  • \$\begingroup\$ Could you add more detail about what you're trying to accomplish, and a few lines of sample input and output, to your question? It's kind of possible to reverse-engineer it from the code, but your actual problem might have weaker constraints, and it would be easier to read. \$\endgroup\$ – David Morris Feb 13 '16 at 10:02
  • \$\begingroup\$ added sample data \$\endgroup\$ – Kenneth Orton Feb 13 '16 at 10:30
  • \$\begingroup\$ i fixed the indentation issue. I apologize for that error, this is my first time posting to this forum. \$\endgroup\$ – Kenneth Orton Feb 13 '16 at 11:07
  • \$\begingroup\$ Is it essential not to read all the data from a file into memory once? In other words, do you need to process files potentially much larger than available RAM? \$\endgroup\$ – Roman Susi Feb 13 '16 at 15:00
  • \$\begingroup\$ The first line will never be output? Please explain why. \$\endgroup\$ – 200_success Feb 13 '16 at 17:06
6
\$\begingroup\$

On reading the file twice

Constructing data structures is costly. You do it once for each line in the file (\$n\$ times) and then do it again \$n^2\$ times. There is absolutely no need as you could only use one list to do so:

>>> a = [[1], [2], [3]]
>>> for i in a:
...     for j in a:
...         print(i, j)
...
[1] [1]
[1] [2]
[1] [3]
[2] [1]
[2] [2]
[2] [3]
[3] [1]
[3] [2]
[3] [3]

That way, with only one list, you avoid spending time converting strings to datastructure and can focus on your algorithm.

So just build the list once and use it any time you want.

Use functions

It lets you reuse your work more easily, by changing parameters. You can also more easily add code to handle command-line arguments and not need to change your code each time you change your input/output file.

A simple layout could look like:

def parse_input(filename):
    ...

def compute_output(output_file, data, filter_value):
    ...

def filter_file(path, filter_value=3, in_name='file', out_name='filteredSets'):
    data = parse_input('{}/{}'.format(path, in_name))
    with open('{}/{}{}'.format(path, out_name, filter_value), 'w') as out_file:
        if len(data) > 1:
            compute_output(out_file, data, filter_value)
        else:
            for datum in data:
                print(datum, file=out_file)


if __name__ == '__main__':
    filter_file(arg2 + arg1)

I’m assuming Python 3 here for the print(datum, file=out_file) line. Change it accordingly if you are using Python 2. It, however, will change your output a bit, but more on that later. I'm also using a for loop in the else just in case there is no rows in data.

Separating concerns with functions let you focus on being efficient for simple tasks. And, if later you want to improve your code thanks to multiprocessing, it will be easier to process it in parallel (using map_async for instance).

Iterate directly over items

Rather than iterating over indices and using these indices to retrieve items. Instead of:

for i in range(0, len(list1)):
    ...
    set2 = list1[i]

You should use:

for set2 in list1:

It's both easier to read and faster. If you truly need the index, you can still use enumerate:

for i, set2 in enumerate(list1):

But as far as eliminating tests against the same line in our product you can test if the object is the same:

for set1 in list1:
    for set2 in list1:
        if set1 is not set2:
            # Do something

Note that I used is instead of == to be sure that we are performing tests on the same line and not on lines with identical values:

>>> a = [[1], [1], [1]]
>>> for i in a:
...     for j in a:
...         print(i, j, i==j, i is j)
...
[1] [1] True True
[1] [1] True False
[1] [1] True False
[1] [1] True False
[1] [1] True True
[1] [1] True False
[1] [1] True False
[1] [1] True False
[1] [1] True True

Managing "stop-early" in loops

Python allows loops (for and while) an optional else clause. This clause executes only if the loop executed entirely without reaching a break (or a return, for what it's worth).

In your case, you could use that at your advantage in the inner for loop: instead of waiting to reach the end of the file for each line, you can break as soon as you find that two lines shares more than 3 items. If you handle writing lines in the else clause of the inner for loop, you can rely on that break to not print a line that has too many items in common with an other one.

Miscellaneous

  • You can use os.path.join to concatenate folders and filenames.
  • You can use set1 & set2 as a shorthand to set1.intersection(set2).
  • You should write each import statement on its own line.

Proposed improvements

import os
from ast import literal_eval

def parse_input(filename):
    with open(filename) as f:
        data = [set(literal_eval(line)) for line in f]
    return data

def compute_output(output_file, data, filter_value):
    for set1 in data:
        for set2 in data:
            if set1 is set2:
                # Do not try to compare a row with itself
                continue
            if len(set1 & set2) >= filter_value:
                # Do not keep lines that have more than a few items
                # in common with any other line
                break
        else:
            # If the second for loop did not break, then keep the line
            print(set1, file=output_file)

def filter_file(path, filter_value=3, in_name='file', out_name='filteredSets'):
    data = parse_input(os.path.join(path, in_name))
    output_filename = os.path.join(path, '{}{}'.format(out_name, filter_value))
    with open(output_filename, 'w') as out_file:
        compute_output(out_file, data, filter_value)


if __name__ == '__main__':
    filter_file(arg2 + arg1)

You should have noticed that I changed the output format a bit. Now each line is a set instead of a list. It's easy to change that by calling print(list(set1), file=output_file) instead. It may change the order, but wont change the content. You could even use sorted(set1).

Beyond ast.literal_eval

I don't know if you can manage the input files of if you have to build around their limitations. But in case you can change them, I suggest you have a look at the pickle module.

Basicaly, when creating your input file, you can pickle.dump a list of all rows (possibly already a list of sets) and then, load them in this script using a simple data = pickle.load(os.path.join(arg2 + arg1, 'file')).

\$\endgroup\$
  • \$\begingroup\$ I appreciate the response. The in file can be manipulated; the rows represent cliques from an undirected graph. At present, in creating the input file, the Python networkx module traverses a file of edges and finds the cliques, storing them in a generator before outputting to file. Order is not an issue with the data as the user id's are unique in the map. With this part of the program I was just trying to eliminate cliques that might possibly be too similar. Unfortunately, I just realized that by removing the cliques that are similar, I lose a certain amount of useful data. \$\endgroup\$ – Kenneth Orton Feb 13 '16 at 16:36
  • \$\begingroup\$ ...because if I remove a clique based on it's intersected similarities then it will omit both of those sets but what if those two sets are the only two sets that contain those certain users? I don't think it would be beneficial at all then to filter the sets unless I was just trying to remove duplicate entries. Sometimes I write a program I think is going to do something useful and then I just never use it. Stranger than fiction. \$\endgroup\$ – Kenneth Orton Feb 13 '16 at 16:42
4
\$\begingroup\$

So I found this quite an interesting problem, and poked at it a little.

I'm mostly going to talk about performance, because that's what you asked about. But along the way, I'll try and make some observations about readability, and answer the other questions you had.

Sample input

You provided some sample data, but to test performance, quite a large volume of sample inputs are needed. The following small program generates those:

#!/usr/bin/env python3

import random, string, sys

def gen(n):
    return ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(n))

names = [gen(5) for _ in range(500)]

for i in range(int(sys.argv[1])):
    print(random.sample(names, random.randrange(3, 6)))

Producing sample output on STDOUT, according to a command-line "count" parameter (this is not nice code, it's just here for reproducibility).

Obviously, the performance of the filtering algorithm will depend not only on the number of sets, but also on the number of possible different names from which the sets are drawn, and the size of the sets. Smaller numbers of names make some approaches pathological; larger sets create more work for most approaches.

Original program

Your original program did not run as-is---it seemed to rely on a few parameters argN provided elsewhere, and a particular directory structure. So I modified it a little to accept a filename as its first argument, and output to STDOUT for easy testing. I also moved around the manipulation of the pos variable, as that seemed to either have the wrong indentation or be in the wrong place.

#!/usr/bin/env python3

import ast, sys, os, shutil
list1 = []
end = 0

filterValue = 3

# creates output file with filterValue appended to name
with open(sys.argv[1], "r") as infile:
    for row in infile:
        list1.append(set(ast.literal_eval(row)))

    pos = 0

    infile.seek(0)
    for row in infile:
        # if file only has one row, no comparisons need to be made
        if not(len(list1) == 1):
            # get the first set from the list and...
            set1 = set(ast.literal_eval(row))
            end = len(list1) - 1
            # ...find the intersection of every other set in the file
            for i in range(0, len(list1)):
                # don't compare the set with itself
                if not(pos == i):
                    set2 = list1[i]
                    set3 = set1.intersection(set2)
                    # if the two sets have less than 3 items in common
                    if(len(set3) < filterValue):
                        end -= 1;
                        # and you've reached the end of the file
                        if(end == 0):
                            # append the row in outfile
                            print(row.strip())
        else:
            print(row.strip())
        # increase position in infile
        pos += 1

A few initial bits of code review on this:

  • There's a lot of state---we seem to be working with lots of temporary variables, many of which are only used once.

  • There's a lot of nesting---by the point we actually print a row, we're inside two for loops and four if statements. This is more than my limited brain can effectively keep track of.

  • We seem to be running back over the file, despite having carefully read it into a data structure. This shouldn't be too expensive in terms of performance, because the OS will be caching the file, but it's unnecessary work. (Throughout, I've taken the assumption that it was necessary to output rows in-order, exactly as they were read (IOW, that we have to reprint the exact string we read, rather than printing out a representation of our data structure for them).

  • We're continuing to do work even for sets we've determined we will never print---even if len(set3) >= filterValue is true on the first line of the file, we will continue happily (and unnecessarily) checking the next hundred thousand lines.

  • We're maintaining our own pos variable to track which loop iteration we're on---Python could do this better and easier using the enumerate construct.

Improved version of original program

To start with, I just applied some polish to the original program, maintaining the approach and spirit of the algorithm while tidying up the code.

Starting immediately after the with open line:

    rows = [row.strip() for row in infile]
    sets = [set(ast.literal_eval(row)) for row in rows]

    for pos, row in enumerate(rows):
        # if file only has one row, no comparisons need to be made
        if len(sets) == 1:
            print(row)
            break

        # find the intersection of all sets in the file
        for i in range(0, len(sets)):
            # don't compare the set with itself
            if (not(pos == i) and
                len(sets[i] & sets[pos]) >= filterValue):
                    break
        else:
            print(row)

Improvements:

  • We use list comprehensions to read the input file, and build the list of sets, emphasising the simplicity of these loops.

  • We only read the file once.

  • We use enumerate(rows) manage both the row and its index in the outer loop.

  • Reversing the sense of the check for single-line files, we take an early exit from the printing loop, saving a level of nesting through the rest of the loop.

  • The multiple temporary setN variables have been crushed down into the expression sets[i] & sets[pos], which gives the intersection of the sets at those two indices.

  • We early-exit from the for loop if a match is found, using the for...else construct to print the row only if no early exit occurred.

  • The lack of intervening bookkeeping means that two nested if statements were stacked on top of each other, so we can just combine the conditions, reducing nesting further.

This is still quadratic (sadly), but the early exits combined with the other improvements does speed things up somewhat (about a factor of two on my machine with my test data).

Using itertools

Whenever I have a problem that looks somewhat like this one (fiddling around with sequences and collections), I wonder whether the itertools standard library module could help. It usually can.

In this case, we can use itertools.combinations to generate all possible pairings of sets (not including pairings with themselves). Then, we can intersect each pairing, and keep both sides; doing this for all pairings gives us the set of sets which we wish to exclude from the output.

The full program looks like this:

#!/usr/bin/env python3

import ast
import sys
import itertools

filterValue = 3

with open(sys.argv[1], "r") as infile:
    rows = [row.strip() for row in infile]
    sets = [frozenset(ast.literal_eval(row)) for row in rows]

    excluded = set(sum(((x, y) for x, y in itertools.combinations(sets, 2) if len(x & y) >= filterValue), ()))

    for i, s in enumerate(sets):
        if s not in excluded:
            print(rows[i])

A few points:

  • We now have to read lines into frozensets (immutable sets) so that we can have sets of sets. This is fine, it's just a little more typing.

  • Almost all of the work is in that slightly horrifying one-liner in the middle. Breaking it down:

    itertools.combinations(sets, 2)
    

    produces all possible pairings;

    ((x, y) for x, y in itertools.combinations(sets, 2) if len(x & y) >= filterValue)
    

    is a generator expression, producing a sequence of those pairs whose intersection is larger than filterValue;

    The slightly horrifying sum(..., ()) thing is just there to flatten the sequence of pairs of sets into a sequence of sets.

  • The slightly awkward loop at the end uses both sets and rows to preserve the aforementioned property of emitting exactly those strings which were given to it.

This is still quadratic, but now the quadratic thing has been moved inside a single generator expression, with the quadratic expansion coming from a part of the standard library; I'd guess that this would be a relatively good place to start if you wanted to use multiprocessing to speed this up.

The greater use of optimised standard functionality also gets us a performance win: about a factor of two (so 4x faster so far than the original).

Indexing

Constant-factor performance improvements don't win us very much for \$O(n)\$ problems with largish \$n\$; some kind of algorithmic improvement is necessary.

My initial thought when trying to come up with an improved approach was that matches were likely to be quite sparse---that is, most sets won't share three items (or whatever filterValue is) with each other; I would expect that most sets will share no items with each other. This is true of my randomly-generated sample data; it may not be true for your real-world data.

If that assumption holds, then the obvious place to start seems to be with a simple index, mapping elements (ids/whatever) to the sets which contain them. Then, we can perform our existing quadratic comparison, but only on sets which we already know share at least one element. If most elements only participate in a small number of sets, we are then doing our quadratic process many times with small \$n\$, rather than once with large \$n\$; this should improve performance.

Starting immediately after the sets = ... line from the previous version (also needs an import collections for the defaultdict):

    # build reverse mapping {element -> [indexes]}
    indexes = collections.defaultdict(list)    
    for i, s in enumerate(sets):
        for e in s:
            indexes[e].append(i)

    # build set of rows to exclude
    excluded = set()

    # do quadratic comparison only for those sets which share at least
    # one member
    for set_indexes in indexes.values():
        # turn indexes back into sets
        cands = [sets[i] for i in set_indexes]
        # normal quadratic intersection
        excluded |= set(sum(((x, y) for x, y in itertools.combinations(cands, 2) if len(x & y) >= filterValue), ()))

    # print all the rows we haven't excluded
    for i, s in enumerate(sets):
        if s not in excluded:
            print(rows[i])

A few points on this:

  • We are using a defaultdict for our index---these are worth reading up on, they make it very easy to do this kind of incremental construction (much nicer than scattering if k not in d: d[k] = [] all over the place) .

  • The core of the program is the same as before: the itertools.combinations et al one-liner is wrapped up in a for loop over the values of the index, so that we do many small quadratic operations rather than one big one.

  • The printing code is exactly the same as before---we're just using a different approach to generate excluded.

  • This approach has some distressing performance variability, in the case that any of the index entries become large. For example, if there were two elements which appeared in every set, with every other element being unique, the program would do the same quadratic operation as the previous version, but it would do it twice. Some clever bookkeeping and early-exiting could mitigate this problem, but I don't think there's a good way to stop the program slanting towards the quadratic.

For most inputs I tested, this approach has both better constants and scales better than the previous programs. But it is possible to generate pathological inputs.

The index built here also introduces the possibility of doing some kind of clever filtering---for example, to avoid filtering out all the sets which mention some element (of which we have a convenient list).

ngram Indexing

Having had some success with indexing, it's reasonable to ask whether there's more to be gained from that approach. The problem with the element-based index was that it could only tell us whether sets had any elements in common; a quadratic-time operation was still necessary to filter the sets with common elements. So a natural question is whether a different kind of index could do more work for us in the data structure.

I can't think of a better way to transition this discussion, so I'll just say: we can get what we want by using ngrams as keys for our index. This requires only a small evolution of the previous approaches: we can use itertools.combinations with filterValue as the length parameter to generate all of the possible filterValue-length subsets of each set. (We need to sort the input to itertools.combinations to get consistent output).

Then, we can just look up each key (unique filterValue-length subset); whenever a key maps to more than one input set, those input sets have at least filterValue elements in common.

The code is straightforward:

#!/usr/bin/env python3

import ast
import sys
import itertools
import collections

filterValue = 3

with open(sys.argv[1], "r") as infile:
    rows = [row.strip() for row in infile]
    sets = [frozenset(ast.literal_eval(row)) for row in rows]

    # build reverse mapping {ngram -> [indexes]}
    index = collections.defaultdict(set)
    for i, s in enumerate(sets):
        ngrams = itertools.combinations(sorted(s), filterValue)
        for ngram in ngrams:
            index[ngram].add(i)

    # build set of excluded indices
    excluded = set()
    for v in index.values():
        # any ngram which maps to more than one set
        # causes that set to fail the filter threshold
        if len(v) > 1:
            excluded |= v

    # print all the rows we haven't excluded
    for i, row in enumerate(rows):
        if i not in excluded:
            print(row)

I think I've previously explained all of the things that go into that final version.

This version seems to have good performance overall; the thing which costs it most performance seems to be increasing the size of the input sets. Increasing the size of filterValue would also cause problems. Playing around with various input-generation parameters, it seems to generally handle inputs of a few hundred thousand sets in a few tens of seconds.

It should also be straightforward to parallelize this version: the expensive operation is generating the index; partial indexes can be generated independently, merging indexes should be quite cheap, so it's a good candidate for multiprocessing.

Having the indexes available would also enable more interesting behaviours, particularly if the element->set index from the previous version was also available. For example, it would be straightforward to keep some filtered sets (say, the single largest filtered set) to avoid dropping elements entirely.

Perhaps I got a little carried away with that, but it was enjoyable to poke at.

\$\endgroup\$
  • \$\begingroup\$ I appreciate the answer. The reason I am using so many nested if's and using variables as enumerators is because I know very little about python. I came to a revealing conclusion the other day, the nested for in my original program would only need to compare sets (pos + 1) -> len(list1) because, for example, if set 1 is compared to set 2 then set 2 would not need to be compared to set 1 again in the next iteration and this would be true for all n in the sets. Your solution is quite helpful, unfortunately I am filtering groups associated in an undirected graph and I think... \$\endgroup\$ – Kenneth Orton Feb 15 '16 at 4:44
  • \$\begingroup\$ ...that filtering the groups by eliminating both sets because they share 3 or more users would prove to be irrationally biased. I would need to save at least one of the groups based on the comparison in order to keep groups who can be analysed in the future. Otherwise, I may be excluding users that specifically only belong to those groups. UserA could be in two groups that share 3 or more users but not in any other groups, thus, UserA gets excluded from the entire output. So, I think filtering these groups on an arbitrary assumption would be useless for analyzing big data. \$\endgroup\$ – Kenneth Orton Feb 15 '16 at 4:49
  • \$\begingroup\$ @KennethOrton ah, I see. You might still be able to do something based on this approach---as mentioned, the indexing approach means that it's quite straightforward to do things like ensuring that each element appears at least once. I guess the problem is mostly one of statistical rigour if you're don't have a consistent basis for excluding sets. Maybe you could calculate some metric of "interestingness" for each set? But that's probably off-topic for Code Review. \$\endgroup\$ – David Morris Feb 15 '16 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.