Pythonでリストを逆順にすると、私は通常、逆転のために配列[:: - 1]を使います。リストの2つの側面。しかし、私は、時間の複雑さや空間の複雑さなど、これらの2つのソリューションの違いがわかりません。以下、この二つの方法のために配列[:: - 1]の複雑さと空間の複雑さは何ですか
コード：CのPythonで
def reverse(array):
array[:] = array[::-1]
def reverse(array):
start, end = 0, len(array)-1
while start < end:
array[start], array[end] = array[end], array[start]
start += 1
end -= 1
、配列リストであると仮定すると、式array[::-1]は に機能list_subscript()に見出される以下のアルゴリズムをトリガするソースファイルlistobject.c
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 += (size_t)step, i++) {
it = src[cur];
Py_INCREF(it);
dest[i] = it;
}
このコードの時間と空間の両方の複雑さは、O(n)です。ここで、nはリストの長さです。もちろんここには驚きはありません。
あなたの機能reverse()もO(n)時間の複雑さを持っていますが、それは一時的なリストを使用しないという違いがあります。
組み込みのC関数は、純粋なpythonループよりもはるかに高速です（100要素リストの場合、コンピュータで約10倍）。
トピックの外ですが、 '[:: - 1]ではなく[' reversed（） ']（https://docs.python.org/2/library/functions.html#reversed）組み込み関数を使用することができます] 'を使用して逆のリストを反復処理します。 –
['timeit']（https://docs.python.org/2/library/timeit.html）を使ってどの方法がより高速かをテストし、[' dis']（https：// docs。 Python.org/2/library/dis.html）モジュールを使用して、作成した各関数のバイトコードを表示します。経験則として、カスタム関数ではなく配列を逆にするには 'array [:: - 1]'または 'list（reversed（array））'にしてください。組み込み関数は 'CPython'を使って実装されているため、非常に最適化されています。ここでソースを見つけることができます：[github組み込み関数CPython]（https://github.com/python/cpython） –
ありがとう。たぶん私はそれを非常に明確に説明していないかもしれません。はい、私はリストを逆転させるために 'reversed'関数を使うことができますが、時には文字列のようなものを逆にする必要があり、' reverse'関数が文字列に対して機能しません。このような状況では、私は通常 'string [:: - 1]'を使用しますが、どのように動作し、そのパフォーマンスがわかりません。 – JoshuaW1990