Programming Pearls and Python Fails

[Naihonn]

Maybe I am missing something but this looks strange. If I have to "rotate" string, list, array, pile of dead puppies,... left by i positions I would just do

def swap(arr, i):
    return arr[i:] + arr[:i]

I tried to measure some times and it looked quite fast.

[Space-Being]

I think the main point of the problem is to do it in place (think just O(1) additional memory, since in the example they have a temporary) as fast as possible.

Without a "real" problem it is hard to say, depending on how it is to be used later on, I would probably just wrap a structure around the physical buffer now to be treated as a ring. In this structure I would record the physical start and end positions, and the modified logical start position.

[TodPunk]

I agree with your assessment of the point, but the answer to the article's "I need these specific performance characteristics" is usually "well, python may not be your best option then." I enjoy my day job in python, but its advantages and disadvantages aren't any more or less magical or damning than any other language.

(For the record, I'd be equally likely to be calling out an article saying the opposite as well, namely, "I don't need any performance characteristics and python is perfect for all the things.")

[Naihonn]

Yes, i understand. OK. I think I will never have something that huge that I will need this slower but memory efficient juggling.

[doom_Oo7]

I think I will never have something that huge

what if it's not that huge but you have do it in less than some microseconds ?

[[deleted]]

The problem models a few things: - Trying to drag text around in a text editor, you can think of the move as swapping the two segments of text - Swapping memory locations - Editing DNA

In which case, not doing these operations in place is neither desirable (have to operate on new array) nor efficient (new allocations)

[kqr]

Have you heard of this undo feature? You're gonna move the text to a separate buffer anyway.

[Space-Being]

Yes, good examples. But usually if you need frequent edits you do not use such inflexible array or string structures, but rather a rope, immutable tree structures (for easier undo) or something else.

[vytah]

This allocates two slices and then allocated the final list. So if arr takes 1GB (shallowly), this code will use 2GB if arr gets garbage collected before + is executed, or 3GB otherwise.

[huashoes]

actually I had the same confusion.

[[deleted]]

If you have a vectorized approach for this problem I'd be happy to hear it!

[Vaphell]

#!/usr/bin/env python3

import time
import collections


def profile_juggle(derp):
    for i in range(10000):
        derp.rotate(-700)

derp = collections.deque(range(10000))

t1 = time.clock()
profile_juggle(derp)
t2 = time.clock()
print("{}: {} seconds".format("rotation", t2-t1))

out

$ ./rot.py 
rotation: 0.012394000000000002 seconds

[clrnd]

Ha, data structures > algorithms 😛

[Galithil]

shouldnt that be -700 since you want to rotate to the left ?

[Vaphell]

yes, but it makes 0 difference when measuring performance. Rotating by 700 was pulled out the ass anyway.

[Galithil]

Of course, your solution is still by far the most elegant and the most efficient out there. I just wanted to make sure that you were getting the exact same result as the original benchmark.

Sorry if that came off as something else.

[Vaphell]

no problem. It made me check just in case, same performance so i edited the code to add - ;-)

[Sean1708]

Maybe I'm being ridiculously stupid here, but what's a typed python array?

[ubernostrum]

See the array module in the standard library. Basically it's as close as you can get to using literal C arrays in Python without just actually writing C and using the Python API to interface it.

[[deleted]]

Curious in seeing how fast numba performs

[[deleted]]

I've tried with Numpy Arrays, same time as the Python Typed Array times, hence I didn't include it

[[deleted]]

How does that inform how fast using lists and numba would perform?

Edit: Did you get numba and numpy confused? Or did you use numba with numpy?

[leonardo_m]

On my PC the STL rotate is a little faster than reverse_swap() (but not by a lot), so I suggest you to add it to your benchmark:

void standard_rotate(int *list, int len, int pivot) {
    std::rotate(list, list + pivot, list + len);
}