-1

Suppose a 1-dimensional numpy array. I want to make a new array that contains every n elements. What is the computationally fastest way to do this?

Example: 

a = numpy.arange(1,10)
b = numpy.fancytricks(a,?)
# b is now [2,4,6,8] if n = 2.

Edit: bolded important part of the question.

d0rmLife
  • 4,112
  • 7
  • 24
  • 33
  • @jme That provides a way to accomplish the sampling goal, but makes no guarantees about speed. – d0rmLife Nov 14 '15 at 22:02
  • 2
    What sort of guarantees about speed do you expect? Slicing in such a way returns a view of the data in `a` with a doubled stride length, so it takes constant time and incurs very little overhead. – jme Nov 14 '15 at 22:05
  • @jme I am simply curious what the fastest protocol is, since I am working on a time-constrained problem that involves sampling large data. – d0rmLife Nov 14 '15 at 22:06
  • Have you profiled your code and found this sort of operation to be the bottleneck? – jme Nov 14 '15 at 22:07
  • @jme No, but saving time at this stage would allow more time for more complex operations. I'm not expecting a miracle, just making sure I'm not missing out on any easy gains. – d0rmLife Nov 14 '15 at 22:10
  • Time saved on the quick things is capped at the amount of time taken by the quick things. This probably won't save a second over the course of your whole program. – user2357112 Nov 14 '15 at 22:19
  • @jme you edited your comment well after writing it. And presumably downvoted a clear question. Can you prove your stride length claim? Afterall, the question you link to says it is not a constant time operation. Confusing. – d0rmLife Nov 14 '15 at 22:20
  • 1
    @d0rmLife: No, slicing is constant time. Copying a slice isn't constant time, but you usually don't need to make a copy. – user2357112 Nov 14 '15 at 22:22
  • 1
    Nope, no downvote from me. The question linked to says "This creates a view of the the original data, so it's constant time." Below it talks about copying the slice, which is linear time. But if you don't copy, no linear time is needed. You can easily verify the claim with a simple `%%timeit`. – jme Nov 14 '15 at 22:23
  • @jme Gotchya, thank you for clarifying. I guess the key to saving time in a case like this is to determine how essential the copy is. Thanks again. – d0rmLife Nov 14 '15 at 22:24
  • @d0rmLife While many questions ask for **[fastest | lowest-latency]** a well prepared **quantitatively based experiment definition shall be a part of the StackOverflow MCVE convention**. Saying this, one may sketch a ***Cost Function:: 150.000$ x ManYearsInAlgoDevAlphaBetaTestTqmProdRelease + ( 60$ + 0.15$ x kWatts) x HoursDeltaSavedInProduction +...*** This will show real metrics' difference between smart solution and nonsensical proposals alike to develop language-X extension & finally get same,if not worse performance as other,read smarter,approaches. **Big-O's say why CostFunction $ave$** – user3666197 Nov 14 '15 at 22:49
  • Without context this question is close to meaningless. What are you going to do with this new array? For some purposes a `view` just delays the inevitable iteration and copy. – hpaulj Nov 15 '15 at 00:11

2 Answers2

2

The absolute fastest way to do this is to write an extension module in pure C and use the buffer protocol to access the data directly. If you use Cython or another such tool to write the C for you, you may see small amounts of performance lost in automatic reference counting. Since you still have to do manual reference counting in handwritten C, the difference is likely to be negligible to nonexistent.

This will have marginally less overhead than the slicing syntax NumPy provides out of the box. However, assuming you use NumPy correctly, the overall performance gain is likely to be small and constant, so it's not clear to me that this is worth the extra effort in any reasonable situation.

Kevin
  • 28,963
  • 9
  • 62
  • 81
2
b = a[1::step]

n = length(a)

Computational cost is O(n), you are "making" a loop with length(a)/step

UPDATE:
Computational cost is O(1), there is no numpy.array object re-arrangement, just one constant ... in access-method... is set / changed. Once deployed, the access-speed is the same as with a value stored there before an update.

user3666197
  • 1
  • 6
  • 50
  • 92
juankirr
  • 323
  • 2
  • 13
  • It is not Omega(n/step)? – d0rmLife Nov 14 '15 at 22:08
  • 4
    Computational cost is `O(1)`. Basic slicing returns a view with altered stride length. There is no need to look through the array at all. – jme Nov 14 '15 at 22:09
  • return a view with altered stride length has O(1) cost? – juankirr Nov 14 '15 at 22:26
  • 1
    @juankirr Yes. Returning a view is just making a pointer, which is `O(1)`. Changing the stride length is also `O(1)`, since it's just updating a single number. You can time it to be sure... On my machine, `b = a[::2]` takes about 280 nanoseconds whether `a` has 100 entries or 100 million. – jme Nov 14 '15 at 22:32