classification
Title: list.reverse(): slow sublist reverse
Type: Stage: resolved
Components: C API, Interpreter Core Versions: Python 3.9
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: Yury, rhettinger, terry.reedy, xtreak
Priority: normal Keywords:

Created on 2020-03-27 12:35 by Yury, last changed 2020-03-29 01:57 by rhettinger. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 19181 Yury, 2020-03-27 12:35
Messages (4)
msg365147 - (view) Author: Yury Norov (Yury) * Date: 2020-03-27 12:35
Hi all,

In Python, I need a tool to reverse part of a list (tail) quickly.
I expected that

        nums[start:end].reverse()

would do it inplace with the performance similar to nums.reverse().
However, it doesn't work at all. The fastest way to reverse a part of
the list that I found is like this:

nums[start:end] = nums[end:start-1:-1]

But it is 30 times slower than pure reverse(). The patch below adds
a region support for the reverse(). It works as fast as I expect.

The test results and script are like this:

            exec(open('test.py').read())
            nums.reverse() 0.006764888763427734
            nums = nums[::-1] 0.10066413879394531
            nums.reverse(-L/2) 0.003548145294189453
            nums.reverse(L/2, L) 0.003538370132446289
            nums = nums[:L/2] + nums[L:L/2-1:-1] 0.19934582710266113
            nums[L/2:L] = nums[L:L/2-1:-1] 0.11419057846069336

import time

nums = list(range(10000000))
L = len(nums)
LL = int(L/2)

t = time.time()
nums.reverse()
print('nums.reverse()\t\t\t\t', str(time.time() - t))

t = time.time()
nums = nums[::-1]
print('nums = nums[::-1]\t\t\t', str(time.time() - t))

t = time.time()
nums.reverse(-LL)
print('nums.reverse(-L/2)\t\t\t', time.time() - t)

t = time.time()
nums.reverse(LL, L)
print('nums.reverse(L/2, L)\t\t\t', time.time() - t)

t = time.time()
nums = nums[:LL] + nums[L : LL - 1 : -1]
print('nums = nums[:L/2] + nums[L:L/2-1:-1]\t', time.time() - t)

t = time.time()
nums[LL:L] = nums[L:LL-1:-1]
print('nums[L/2:L] = nums[L:L/2-1:-1]\t\t', time.time() - t)

If there is better way to reverse lists, can someone point me at the right direction? If not, I'll be happy to fix all existing issues and upstream
this approach.

PR: https://github.com/python/cpython/pull/19181

Thanks,
Yury
msg365150 - (view) Author: Karthikeyan Singaravelan (xtreak) * (Python committer) Date: 2020-03-27 14:08
This looks like a duplicate of https://bugs.python.org/issue1491804
msg365236 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2020-03-28 23:02
The previous issue was also about .sort and Raymond's rejection was mostly about .sort.  I will let him comment about whether the speedup moves him at all.

Yury, please say something about your use case.
msg365240 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2020-03-29 01:57
Thanks for the suggestion, but the need isn't common enough to warrant an API expansion.  If this were a popular operation, it might be worth optimizing, the need almost never arises.
History
Date User Action Args
2020-03-29 01:57:43rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg365240

stage: resolved
2020-03-28 23:02:10terry.reedysetnosy: + terry.reedy
messages: + msg365236
2020-03-27 14:08:35xtreaksetnosy: + rhettinger, xtreak
messages: + msg365150
2020-03-27 12:35:37Yurycreate