Python如何實現str [:: - 1]？

Question

考慮蟒蛇行：

str[::-1] 

我看到它的速度非常快，而且方式比一些爲O（n）解決方案，也節省內存更快捷。 Python在這種情況下使用什麼算法？

Answer 1

嗯，你有沒有嘗試過任何快速和骯髒的測試？這是第一遍：

In [1]: import time 

In [2]: def reverse_list_time(my_list): 
    ...:  start = time.time() 
    ...:  reversed = my_list[::-1] 
    ...:  stop = time.time() 
    ...:  return stop - start 
    ...: 

In [3]: reverse_list_time(list(range(1000))) 
Out[3]: 1.33514404296875e-05 

In [4]: testing_lists = (list(range(n)) for n in range(1000,100000,500)) 

In [5]: testing_lists 
Out[5]: <generator object <genexpr> at 0x7f7786bd97d8> 

In [6]: results = list(map(reverse_list_time,testing_lists)) 

這裏是我的結果

這看起來大致爲O（n）給我。

如果這不能說服你，這裏是 the implementation。它看起來像一個非常簡單的O（n）解決方案給我。這是它的肉：

else { 
     result = PyList_New(slicelength); 
     if (!result) return NULL; 

     src = self->ob_item; 
     dest = ((PyListObject *)result)->ob_item; 
     for (cur = start, i = 0; i < slicelength; 
      cur += step, i++) { 
      it = src[cur]; 
      Py_INCREF(it); 
      dest[i] = it; 
     } 

     return result; 

Answer 2

您可以使用Python的dis.dis模塊拆卸str[::-1]：

>>> import dis 
>>> def reverse_(str_): 
...  return str_[::-1] 
... 
>>> dis.dis(reverse_) 
    6   0 LOAD_FAST    0 (str_) 
       3 LOAD_CONST    0 (None) 
       6 LOAD_CONST    0 (None) 
       9 LOAD_CONST    1 (-1) 
      12 BUILD_SLICE    3 
      15 BINARY_SUBSCR  
      16 RETURN_VALUE  

你可以看到每個指令在documentation手段。對於LOAD_FAST文檔說：

推到本地co_varnames[var_num]參考壓入堆棧。

co_varnames是一種始終與代碼對象一起出現的結構。在這種情況下，它是str_：

>>> reverse_.__code__.co_varnames 
('str_',) 

下一條指令，LOAD_CONST，被這樣描述：

推co_consts[consti]壓入堆棧。

推入堆棧的值爲None（dis很有幫助，併爲您查找）。接下來的兩條指令是LOAD_CONST指令，將值None和-1推送到堆棧上。

下一條指令，BUILD_SLICE，被描述爲：

推棧上切片對象。 argc必須是2或3.如果是2，slice(TOS1, TOS)被推入;如果是3，則推入slice(TOS2, TOS1, TOS)。有關更多信息，請參閱slice()內置函數。

TOS2, TOS1, TOS表示堆棧None, None, -1，其從堆棧（對象變得slice(None, None, -1)）被推到slice()對象上的數值。

BINARY_SUBSCR被描述爲：

實現TOS = TOS1[TOS]。

這意味着Python的計算str_[sli]其中sli是slice()對象推到堆棧中的前一指令。它的

>>> str_[slice(None, None, -1)] 

最後，RETURN_VALUE相當於：

返回與TOS的函數的調用者。

最後的指令返回上一步的結果，這是反轉的str_。

摘要

我看到它的速度非常快，而且方式比一些O（N）解決方案的更多更快，也節省內存。

事實上，通過切片來逆轉列表涉及比Python中的一些其他逆轉方法更多的內存開銷。長話短說（沒有長時間的兔子洞），更大的內存開銷會發生，因爲切片操作會返回整個列表。

一種替代方法可能是：使用reversed()生成迭代器，這通常對於內存和時間更具性能（儘管從此迭代器生成列表非常耗時）。

Python在這種情況下使用什麼算法？

爲了使長話短說：Python中加載變量str，構建了一個slice(None, None, -1)對象，實現str[slice(None, None, -1)]（source code），並返回逆轉str。