Message Boards Message Boards

2
|
2146 Views
|
1 Reply
|
5 Total Likes
View groups...
Share
Share this post:

Why ListConvolve beats a compiled version

Posted 11 years ago
Hey there, 

I wrote a short code to mimic the build-in ListConvolve function. I compiled the code into "c" with the Compile function. I would like to know why ListConvolve is still so much faster on large list.  (You should have a proper C compiler installed to run this code, otherwise wolfram virtural machine is used)
 Clear[cf]
 cf = Compile[{{x, _Real, 1}, {n, _Integer}},
   Module[{l = {}, temp = 0.},
    Do[
     (Do[temp = temp + x[[i]];,
       {i, k, k + n - 1}]);
     l = Append[l, 1/n*temp];
     temp = 0.;,
     {k, 1, Length[x] - n + 1}
    ];
   Return[l]
   ], CompilationTarget -> "C"
  ]
I compare the time required to run these two codes:
data = RandomReal[{1, 10}, 100000];
cf[data, 3];
ListConvolve[1/3.*{1, 1, 1}, data];
No need to use timing function, the difference is definitely noticeable as the length of data is greater than 10^4. 
I am curious about what is behind the ListConvolve function.
POSTED BY: Shenghui Yang
Aha, I can answer this by myself. The issue with the first version is that the variable "l" is with dynamic length, it is very costly to create a new array as the dimension gets bigger along with time. If we simply use a static length of array for "l", the speed-up is significant. 
Clear[cf]
cf = Compile[{{x, _Real, 1}, {n, _Integer}},
  Module[{l = x, temp = 0.},
   Do[(Do[temp = temp + x[[i]];, {i, k, k + n - 1}]);
    l[[k]] = 1/n*temp;
    temp = 0.;, {k, 1, Length[x] - n + 1}];
   Return[l]], CompilationTarget -> "C"]
To get the correct result, I just simply drop the last "n-1" terms, for instance, this piece of code is good for computing the convolution with the length of kernel equal to 3
data = RandomReal[{1, 10}, 10000000];
cf[data, #][[;; -(# - 1)]] &[3];
The modified code gives me the correct results in fraction of a second
POSTED BY: Shenghui Yang
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract