C/C++>> csearch>> 返回
项目作者： peterfranciscook

项目描述 ：
Fast C-MEX for Array Lookups and Masking
高级语言： MATLAB
项目地址: git://github.com/peterfranciscook/csearch.git
创建时间： 2019-07-29T17:15:27Z
项目社区：https://github.com/peterfranciscook/csearch
开源协议：
下载


csearch

Fast C-MEX for Array Lookups and Masking

Suppose you need to mask indices of a large array

  1. argmin = find(x>=y, 1, 'first');
  2. argmax = find(x<=y, 1, 'last');
  3. maskedArray = x(argmin:argmax);

There is considerable time savings to the masking operation if the array is presorted (e.g. an array of serial timestamps) - the algorithm is now O(log(n)) instead of O(n). For a small array this doesn’t make a big difference, but for a large one it is significant. csearch enables you to take advantage of this property of sorted arrays to quickly mask large arrays. If you use csearch on an unsorted array, the result is undefined. The idea is based on the implementation of bsearch.c in torvalds/linux/lib/bsearch.c.

Syntax

  1. %CSEARCH Fast Lookup and Masking for Sorted Arrays
  2. %
  3. %   argmax = csearch(x, 'lt', y) is equivalent to MATLAB's find(x<y, 1, 'last')
  4. %
  5. %   argmax = csearch(x, 'le', y) is equivalent to MATLAB's find(x<=y, 1, 'last')
  6. %
  7. %   argmin = csearch(x, 'gt', y) is equivalent to MATLAB's find(x>y, 1, 'first')
  8. %
  9. %   argmin = csearch(x, 'ge', y) is equivalent to MATLAB's find(x>=y, 1, 'first')
  10. %
  11. %   Class Support
  12. %   -------------
  13. %   The input array x must be a 1D finite, real, non-sparse array of
  14. %   the following classes: uint8, int8, uint16, int16, uint32, int32,
  15. %   uint64, int64, single or double. 
  16. %
  17. %
  18. %   Notes
  19. %   -----
  20. %   1. If input y is outside the range of the array x, -1 is returned
  21. %
  22. %   2. Input y should be the same class as x
  23. %
  24. %
  25. % Peter Cook 2019

Benchmarks

  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. double precision
  3. num = 100, 1000 repetitions
  4. csearch: 0.01158909 s, MATLAB: 0.00262154 s
  5. num = 1000, 1000 repetitions
  6. csearch: 0.00299610 s, MATLAB: 0.00392571 s
  7. num = 10000, 1000 repetitions
  8. csearch: 0.00293305 s, MATLAB: 0.02520050 s
  9. num = 100000, 1000 repetitions
  10. csearch: 0.00387134 s, MATLAB: 0.13428660 s
  11. num = 1000000, 1000 repetitions
  12. csearch: 0.00318716 s, MATLAB: 1.07517482 s
  13. num = 10000000, 1000 repetitions
  14. csearch: 0.00379733 s, MATLAB: 14.31496315 s
  15. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  16. single precision
  17. num = 100, 1000 repetitions
  18. csearch: 0.00319169 s, MATLAB: 0.00224358 s
  19. num = 1000, 1000 repetitions
  20. csearch: 0.00314525 s, MATLAB: 0.00392495 s
  21. num = 10000, 1000 repetitions
  22. csearch: 0.00310673 s, MATLAB: 0.02433735 s
  23. num = 100000, 1000 repetitions
  24. csearch: 0.00323587 s, MATLAB: 0.12829741 s
  25. num = 1000000, 1000 repetitions
  26. csearch: 0.00358551 s, MATLAB: 0.79688118 s
  27. num = 10000000, 1000 repetitions
  28. csearch: 0.00298553 s, MATLAB: 12.05700865 s
  29. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%