Pythonはどのようにstr [:: - 1]を実装していますか？私はそれが非常に速く、そしていくつかの<strong>O（n）の</strong>ソリューションと、メモリの節約よりも道より高速です参照</p> <pre><code>str[::-1] </code></pre> <p>：

Question

はPythonのラインを考えてみましょう。この場合、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

あなたはstr[::-1]を分解するためにPythonのdis.disモジュールを使用することができます。

>>> 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が役に立ちます）。次の2つの命令は、命令であり、値Noneと-1をスタックにプッシュします。

がスタックにスライスオブジェクトをプッシュ：として

次の命令、BUILD_SLICEは、記載されています。 argcは2または3でなければなりません.2の場合はslice(TOS1, TOS)がプッシュされます。 3の場合はslice(TOS2, TOS1, TOS)が押されます。詳細については、slice()ビルトイン関数を参照してください。

TOS2, TOS1, TOSは、（オブジェクトがslice(None, None, -1)なる）スタックからslice()オブジェクトにプッシュされたスタックNone, None, -1、上の値を表します。

BINARY_SUBSCRは、以下のように記載されている：

はTOS = TOS1[TOS]を実装します。

これは、Pythonは、前の命令でスタックにプッシュsliがslice()オブジェクトであるstr_[sli]を計算することを意味します。関数の呼び出し元へTOSと

戻り値：それは最後に

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

、RETURN_VALUEのと同等です。

最後の命令は前のステップの結果を返します。これは逆のstr_です。私はそれが非常に速く、そしていくつかのO（n）のソリューションと、メモリの節約よりも道より高速です参照

概要

。

実際、スライスによるリストの逆転は、Pythonの他の逆転メソッドよりも多くのメモリオーバーヘッドを伴います。長いストーリーは短く（長いウサギの穴を通らずに）、スライス操作によってリスト全体が返されるため、メモリオーバーヘッドが大きくなります。

代わりに、reversed()を使用してイテレーターを生成することもできます（通常、このイテレーターからリストを生成するには時間がかかります）。

この場合、Pythonはどのアルゴリズムを使用しますか？

長い話を短くする：Pythonは、変数strをロードslice(None, None, -1)オブジェクトを構築し、str[slice(None, None, -1)]（source code）を実装して、逆strを返します。