2

I have two sets of numbers, each in a list in my Python script. For each number in the first list, I need to see if any of the numbers in the second are larger than it. I only need the number of times that an n2 was larger than an n1. (For example, if numset1 is [7,2] and numset2 is [6,9], I just need 3) Right now I'm doing this - going through each n1 and checking if each n2 is larger than it:

possibilities = [(n1<n2) for n1 in numset1 for n2 in numset2]
numPossibilities = sum(possibilities)

Currently this is the slowest portion of my script, particularly when dealing with larger datasets (numset1 and numset2 containing thousands of numbers). I'm sure there's some way to make this more efficient, I'm just not sure how.

penguinrob
  • 1,431
  • 3
  • 17
  • 39

3 Answers3

3

Sort numset2 and then iterate over numset1 but use a binary search on numset2, for example using the bisect module: http://docs.python.org/2/library/bisect.html

import bisect
# your code here
numset2.sort()
L = len(numset2)
numPossibilities = sum([bisect.bisect_right(numset2,n1) < L for n1 in numset1])

Also note that your original code does not compute what you have asked for in your second sentence - for each element in numset1, it sums how many elements in numset2 are greater than this element, not whether there is an element that matches the criterion.

To match your original code, do:

numPossibilities = sum([L - bisect.bisect_right(numset2,n1) for n1 in numset1])
YXD
  • 31,741
  • 15
  • 75
  • 115
  • I don't believe you can sort a `set`. – martineau Dec 07 '12 at 00:59
  • I think the chosen variable names are misleading - the questions states "I have two sets of numbers, each in a list in my Python script." ... – YXD Dec 07 '12 at 01:01
  • I don't think this code snippet actually works correctly. At the very least, the `< L` part is suspicious - you probably want to sum the number of entries to the left of the bisection point - i.e. the actual return value of bisect_right – happydave Dec 07 '12 at 01:02
  • @happydave , yes, I have added a note about this. It depends on whether you want the code that matches the result in the question, or the description in the question. – YXD Dec 07 '12 at 01:07
  • @MrE Sorry, I should've worded that differently. The code listed in my question does what I want, so go with what the code does, not what my bad description says. – penguinrob Dec 07 '12 at 01:14
  • That works great, it's >100x as fast! Also, I'm new to this type of stuff, would you happen to know of some resource that would explain/introduce this type of stuff? The Python doc link was great, but I'm still a bit lost as to how it works. – penguinrob Dec 07 '12 at 01:30
  • That's great - what in particular do you need explaining? [This link](http://en.wikipedia.org/wiki/Binary_search_algorithm#Overview) and [this question](http://stackoverflow.com/questions/700241/what-is-the-difference-between-linear-search-and-binary-search) should help with understanding why things are faster, and why I sorted the list. – YXD Dec 07 '12 at 02:00
  • In particular, `bisect_right` [uses a binary search](http://hg.python.org/cpython/file/2.7/Lib/bisect.py) to find the index of the first element greater than `n1`, (returning `len(numset2)` if all the elements are `<= n1`), so the expression `L - bisect_right(numset2,n1)` gives us the number of elements in `numset2` that are greater than `n1`. Here `L` is `len(numset2)`. – YXD Dec 07 '12 at 02:04
2

Your problem is that you have to iterate over each combination of (n1, n2), and there are len(numset1) * len(numset2) combinations, which gets really large when numset1 and numset2 are only fairly large.

Put a different way, the running time of your algorithm is O(n^2) (if len(numset1) is about equal to len(numset2). Let's make that runtime faster. :-)

This becomes a lot easier to do if we sort the lists. So let's sort numset1 and numset2.

>>> numset1.sort()
>>> numset2.sort()

Now, compare the smallest element of numset1 (call it n1) and the smallest element of numset2 (call it n2). If n1 is smaller, then we know that there are len(numset2) elements in numset2 larger than it. If n2 is smaller, we know that no elements in numset1 are smaller than it.

Now, we don't want to actually delete elements from the beginning of the list, because that's an O(n) operation on a Python list. So instead, let's keep track of where we are in each list and iterate through.

>>> n1_idx, n2_idx, accumulator = 0, 0, 0
>>> while n1_idx < len(numset1) and n2_idx < len(numset2):
        if numset1[n1_idx] < numset2[n2_idx]:
            accumulator += len(numset2) - n2_idx
            n1_idx += 1
        else:
            n2_idx += 1

At the end of this operation, we've spent O(nlog(n)) time sorting the lists and O(n) time doing our iteration, so our overall runtime complexity is O(nlog(n)).

That, and accumulator has the number of (n1, n2) pairs where n1 < n2.

Sam Mussmann
  • 5,883
  • 2
  • 29
  • 43
0

Here is what should be a pretty efficient implementation:

def get_possibilities(numset1, numset2):
    sortset1 = sorted(numset1)
    sortset2 = sorted(numset2)
    total = 0
    i2 = 0
    for i1, n1 in enumerate(sortset1, 1):
        while sortset2[i2] <= n1:
            i2 += 1
            if i2 >= len(sortset2):
                # reached end of i2, so just return total now
                return total
            # current from sortset2 is greater than from sortset1 so far
            total += i1
    # all remaining elements of sortset2 greater than all elements of sortset1
    total += (len(sortset2) - i2 - 1) * len(sortset1)
    return total

This iterates over each set only once, which it accomplishes by sorting the sets before running. This allows some improved logic, because if the element in sortset2 at index i2 is greater than an element of sortset1 at index i1, then it is also greater than all elements in sortset1 at earlier indices.

Andrew Clark
  • 202,379
  • 35
  • 273
  • 306