3

I would like to implement the fastest possible convolution of two very short vectors (1d) in Python (or in C with a Python interface). The convolution results are reported only for non-zero values of the first vector.

Example:

main_vector = [0,0,0,1,1,1,0,0,0] # usually < 250 elements long
mask = [1,1,1]                    # usually 31 elements long
result = [0,0,0,2,3,2,0,0,0]      # result of convolution

The result is the convolution of the main_vector with the mask, however the result is reported only on non-zero values of the main_vector.

My fastest solution until now:

result = numpy.convolve(main_vector, mask, "same")
result = numpy.multiply(main_vector, result)

Would there be a faster way to implement this in Cython or some other interface? Any ideas very much appreciated. I am using this to do motif searches in bioinformatics, and i perform many of these convolutions.

grexor
  • 109
  • 1
  • 5
  • Is mask always all ones? – Divakar Jan 04 '17 at 15:18
  • yes, the mask is always all ones – grexor Jan 04 '17 at 15:18
  • And main_vector always has 0s and 1s only? – Divakar Jan 04 '17 at 15:35
  • yes exactly, main_vector has only 0 or 1 at any position – grexor Jan 04 '17 at 15:37
  • Do you need this for the entire length with `"same"` or something like `"valid"` be okay too? – Divakar Jan 04 '17 at 15:54
  • In-place multiplication is a bit faster than using `numpy.multiply`: `result *= main_vector` (memory allocation!). Note that masking (`result[main_vector != 0]`) is slower than multiplication. – a_guest Jan 04 '17 at 15:56
  • ideal would be "same", however "valid" would also be of great help – grexor Jan 04 '17 at 15:56
  • You can use [`1D uniform filter`](https://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.ndimage.filters.uniform_filter1d.html). But, with such short vectors, it doesn't seem to provide any noticeable speedup. – Divakar Jan 04 '17 at 19:58
  • Thank you for all the replies, i will try the in-place multiplication and 1D uniform filter and see if the timings are improved. – grexor Jan 05 '17 at 10:30
  • Since the mask is all ones, this is more like a rolling sum. See this anwer: http://stackoverflow.com/a/28884909 – user7138814 Jan 05 '17 at 19:32

0 Answers0