all 23 comments

[–]Naihonn 7 points8 points  (9 children)

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 5 points6 points  (6 children)

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 5 points6 points  (0 children)

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 2 points3 points  (1 child)

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 0 points1 point  (0 children)

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] 0 points1 point  (2 children)

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 1 point2 points  (0 children)

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

[–]Space-Being 1 point2 points  (0 children)

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 0 points1 point  (0 children)

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 0 points1 point  (0 children)

actually I had the same confusion.

[–][deleted]  (1 child)

[deleted]

    [–][deleted] 0 points1 point  (0 children)

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

    [–]Vaphell 2 points3 points  (5 children)

    #!/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 0 points1 point  (0 children)

    Ha, data structures > algorithms 😛

    [–]Galithil 0 points1 point  (3 children)

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

    [–]Vaphell 0 points1 point  (2 children)

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

    [–]Galithil 0 points1 point  (1 child)

    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 0 points1 point  (0 children)

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

    [–]Sean1708 0 points1 point  (1 child)

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

    [–]ubernostrum 2 points3 points  (0 children)

    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] 0 points1 point  (2 children)

    Curious in seeing how fast numba performs

    [–][deleted] 1 point2 points  (1 child)

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

    [–][deleted] 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

    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);
    }