[Numpy-discussion] Optimisation of a Numpy set intersection function
tchur at optushome.com.au
Sun Apr 8 17:32:09 EDT 2001
I have been trying to optimise a simple set intersection function
for a Numpy-based application on which I am working. The function needs
find the common elements (i.e the intersection) of two or more
Numpy rank-1 arrays of integers passed to it as arguments - call them
array A, array B etc. My first attempt used searchsorted() to see where
in array A each element of array B would fit and then check if the
element in array A at that position equalled the element in array B - if
then that element was part of the intersection:
c = searchsorted(A,B)
d = compress(less(c,len(A)),B)
This works OK but it requires the arrays to be stored in sorted order
(which is what
we did) or to be sorted by the function (not shown).
I should add that the arrays passed to the function may have up to a few
million elements each.
Ole Nielsen at ANU (Australian National University), who gave a paper on
mining using Python at IPC9, suggested an improvement, shown below.
Provided the arrays are pre-sorted, Ole's function is about 40% faster
than my attempt, and about the same speed if the arrays aren't
However, Ole's function can be generalised to find the intersection of
two arrays at a time. Most of the time is spent sorting the arrays, and
increases as N.log(N) as the total size of the concatenated arrays (N)
(I checked this empirically).
C = sort(concatenate(Arraylist))
D = subtract(C[0:-n], C[n:]) #or
# D = convolve(C,[n,-n])
return compress(equal(D,0),C) #or
# return take(C,nonzero(equal(D,0)))
Paul Dubois suggested the following elegant alternative:
Unfortunately, perhaps due to the overhead of creating the rank-2 array
hold the results of the subtract.outer() method call, it turns out to be
slower than Ole's function, as well as using huge tracts of memory.
My questions for the list, are:
a) can anyone suggest any further optimisation of Ole's function, or
b) how much do you think would be gained by re-implementing this
function in C using the Numpy C API? If such an effort would be
are there any things we should consider while tackling this task?
More information about the NumPy-Discussion