## Intersection of sorted numpy arrays

Question

I have a list of sorted numpy arrays. What is the most efficient way to compute the sorted intersection of these arrays?

In my application, I expect the number of arrays to be less than 10^4, I expect the individual arrays to be of length less than 10^7, and I expect the length of the intersection to be close to p*N, where N is the length of the largest array and where 0.99 < p <= 1.0. The arrays are loaded from disk and can be loaded in batches if they won't all fit in memory at once.

A quick and dirty approach is to repeatedly invoke `numpy.intersect1d()`

. That seems inefficient though as `intersect1d()`

does not take advantage of the fact that the arrays are sorted.

Show source

## Answers to Intersection of sorted numpy arrays ( 1 )

Since

`intersect1d`

sort arrays each time, it's effectively inefficient.Here you have to sweep intersection and each sample together to build the new intersection, which can be done in linear time, maintaining order.

Such task must often be tuned by hand with low level routines.

Here a way to do that with

`numba`

:Now the samples :

And a run for 10 samples

This way it seems that the job can be done in about 5 minutes , beyond loading time.