[]がlist()よりも速いのはなぜですか?

724
Augusta 2015-05-14 03:16.

私は最近の処理速度を比較[]し、list()その発見に驚いた[]ランを超える3倍速くよりlist()。私はと同じテストを実行{}し、dict():との結果が実質的に同一であった[]{}しながら、両方は約0.128sec /万サイクルを取ったlist()し、dict()およそ0.428sec /万サイクルごとをしました。

どうしてこれなの?やる[]{}(そしておそらく()''、あまりにも)その明示的に名前のカウンターパートは、(一方で、すぐにいくつかの空の株式リテラルのコピーをバックパスlist()dict()tuple()str())は完全に彼らが実際の要素を持っているかどうか、オブジェクトの作成に取り掛かりますか?

これら2つの方法がどのように異なるのかわかりませんが、知りたいと思います。ドキュメントやSOで答えを見つけることができず、空の角かっこを検索すると、予想よりも問題が多いことがわかりました。

リストと辞書をそれぞれ比較するために、timeit.timeit("[]")timeit.timeit("list()")、とtimeit.timeit("{}")を呼び出してタイミング結果を取得しtimeit.timeit("dict()")ました。Python2.7.9を実行しています。

私は最近、toのパフォーマンスを比較し、同様のリテラル対グローバルのシナリオに触れているように見える「Trueの場合が1の場合よりも遅いのはなぜですか?」を発見しました。おそらくそれも検討する価値があります。if Trueif 1

5 answers

770
Martijn Pieters 2015-05-14 03:21.

[]{}リテラル構文であるためです。Pythonは、リストまたは辞書オブジェクトを作成するためだけにバイトコードを作成できます。

>>> import dis
>>> dis.dis(compile('[]', '', 'eval'))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile('{}', '', 'eval'))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE        

list()dict()は別々のオブジェクトです。それらの名前を解決する必要があり、引数をプッシュするためにスタックを関与させる必要があり、後で取得するためにフレームを格納する必要があり、呼び出しを行う必要があります。それにはもっと時間がかかります。

空の場合は、少なくともa LOAD_NAME(グローバル名前空間とbuiltinsモジュールを検索する必要があります)の後にCALL_FUNCTION、現在のフレームを保持する必要がある、が続くことを意味します。

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile('dict()', '', 'eval'))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        

名前検索の時間を個別に指定できますtimeit

>>> import timeit
>>> timeit.timeit('list', number=10**7)
0.30749011039733887
>>> timeit.timeit('dict', number=10**7)
0.4215109348297119

時間の不一致は、おそらく辞書のハッシュの衝突です。それらのオブジェクトを呼び出す時間からそれらの時間を減算し、その結果をリテラルを使用する時間と比較します。

>>> timeit.timeit('[]', number=10**7)
0.30478692054748535
>>> timeit.timeit('{}', number=10**7)
0.31482696533203125
>>> timeit.timeit('list()', number=10**7)
0.9991960525512695
>>> timeit.timeit('dict()', number=10**7)
1.0200958251953125

したがって、オブジェクトを呼び出す必要がある場合は、1.00 - 0.31 - 0.30 == 0.391,000万回の呼び出しごとにさらに数秒かかります。

グローバル名をローカルとしてエイリアス化することで、グローバルルックアップコストを回避できtimeitます(セットアップを使用すると、名前にバインドするものはすべてローカルになります)。

>>> timeit.timeit('_list', '_list = list', number=10**7)
0.1866450309753418
>>> timeit.timeit('_dict', '_dict = dict', number=10**7)
0.19016098976135254
>>> timeit.timeit('_list()', '_list = list', number=10**7)
0.841480016708374
>>> timeit.timeit('_dict()', '_dict = dict', number=10**7)
0.7233691215515137

しかし、そのCALL_FUNCTIONコストを克服することはできません。

154
Dan D. 2015-05-14 03:22.

list()グローバルルックアップと関数呼び出しが必要ですが[]、単一の命令にコンパイルされます。見る:

Python 2.7.3
>>> import dis
>>> dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
74
Torxed 2015-05-14 03:21.

listは、たとえば文字列をリストオブジェクトに変換する関数であるため、while[]はすぐにリストを作成するために使用されます。これを試してください(あなたにとってより意味があるかもしれません):

x = "wham bam"
a = list(x)
>>> a
["w", "h", "a", "m", ...]

一方

y = ["wham bam"]
>>> y
["wham bam"]

あなたがそれに入れたものを含む実際のリストをあなたに与えます。

23
Dimitris Fasarakis Hilliard 2016-12-03 09:01.

ここでの答えは素晴らしいですが、この質問を完全にカバーしています。興味のある人のために、バイトコードからさらに一歩下がっていきます。私はCPythonの最新のリポジトリを使用しています。古いバージョンはこの点で同様に動作しますが、わずかな変更が加えられている可能性があります。

これらのそれぞれ、BUILD_LISTfor[]およびCALL_FUNCTIONforの実行の内訳は次のとおりですlist()


BUILD_LIST命令:

あなたはただ恐怖を見るべきです:

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

ひどく複雑です、私は知っています。これはとても簡単です:

  • で新しいリストを作成しPyList_New(これは主に新しいリストオブジェクトにメモリを割り当てます)、opargスタック上の引数の数を通知します。ポイントにまっすぐ。
  • に問題がないことを確認しif (list==NULL)ます。
  • PyList_SET_ITEM(マクロ)を使用してスタックにある引数(この場合は実行されません)を追加します。

それが速いのも不思議ではありません!それは新しいリストを作成するためのカスタムメイドであり、他には何もありません:-)

CALL_FUNCTION命令:

コード処理を覗いて最初に目にするのは次のCALL_FUNCTIONとおりです。

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

かなり無害に見えますよね?いいえ、残念ながらそうでcall_functionはありませんが、関数をすぐに呼び出す単純な人ではありません。それはできません。代わりに、スタックからオブジェクトを取得し、スタックのすべての引数を取得してから、オブジェクトのタイプに基づいて切り替えます。それは:

  • PyCFunction_Type?いいえ、そうですlistlistタイプではありませんPyCFunction
  • PyMethodType?いいえ、前を参照してください。
  • PyFunctionType?いいえ、前を参照してください。

list型を呼び出しています。渡される引数call_functionPyList_Typeです。CPythonは、ジェネリック関数を呼び出して、という名前の呼び出し可能なオブジェクトを処理する必要_PyObject_FastCallKeywordsがあります。さらに多くの関数呼び出しが必要です。

この関数は、特定の関数タイプ(理由はわかりません)を再度チェックし、必要に応じてkwargsのdictを作成した後、を呼び出します_PyObject_FastCallDict

_PyObject_FastCallDictついに私たちをどこかに連れて行ってくれます!実行した後、さらにチェックを それはグラブtp_callからスロットtypetype我々はそれがつかむ、あること、に渡されましたtype.tp_call。次に、で渡された引数からタプルを作成し_PyStack_AsTuple、最後に呼び出しを行うことができます。

tp_call一致する、type.__call__が引き継ぎ、最終的にリストオブジェクトを作成します。に__new__対応するリストを呼び出し、PyType_GenericNewそれにメモリを割り当てますPyType_GenericAllocこれは実際にはPyList_New、最後にに追いつく部分です。オブジェクトを一般的な方法で処理するには、前述のすべてが必要です。

最後に、使用可能な引数を使用してリストをtype_call呼び出しlist.__init__て初期化し、その後、元の状態に戻ります。:-)

最後に、覚えておいてくださいLOAD_NAME、それはここで貢献している別の男です。


入力を処理するとき、Pythonは通常C、ジョブを実行するための適切な関数を実際に見つけるためにフープを飛び越えなければならないことは容易に理解できます。それは動的であり、誰かがマスクする可能性がありlistそして男の子は多くの人が行う)、別の道をたどらなければならないので、すぐにそれを呼び出すという呪いはありません。

これはlist()多くを失うところです:Pythonを探索することは、それが何をすべきかを見つけるために行う必要があります。

一方、リテラル構文は、まさに1つのことを意味します。変更することはできず、常に事前に決定された方法で動作します。

脚注:すべての関数名は、リリースごとに変更される可能性があります。重要な点はまだ残っており、将来のバージョンでもおそらく続くでしょう。物事を遅くするのは動的なルックアップです。

14
Aaron Hall 2017-11-28 04:20.

なぜ[]より速いのですlist()か?

最大の理由は、Pythonがlist()ユーザー定義関数と同じように扱われることです。つまり、他の何かをエイリアスして別のことlistを行うことで、Pythonをインターセプトできます(独自のサブクラス化されたリストやおそらく両端キューを使用するなど)。

で組み込みリストの新しいインスタンスをすぐに作成します[]

私の説明はあなたにこれについての直感を与えることを目指しています。

説明

[] 一般にリテラル構文として知られています。

文法では、これは「リスト表示」と呼ばれます。ドキュメントから

リスト表示は、角括弧で囲まれた空の一連の式です。

list_display ::=  "[" [starred_list | comprehension] "]"

リスト表示は新しいリストオブジェクトを生成し、その内容は式のリストまたは理解のいずれかによって指定されます。式のコンマ区切りリストが指定されている場合、その要素は左から右に評価され、その順序でリストオブジェクトに配置されます。理解度が提供されると、リストは理解度から得られた要素から作成されます。

つまり、これはタイプの組み込みオブジェクトlistが作成されることを意味します。

これを回避することはできません。つまり、Pythonは可能な限り迅速にそれを実行できます。

一方、ビルトインリストコンストラクターを使用してビルトインをlist()作成することを傍受することができますlist

たとえば、リストを騒々しく作成したいとします。

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print('List initialized.')

次にlist、モジュールレベルのグローバルスコープで名前をインターセプトし、を作成するときにlist、実際にサブタイプリストを作成します。

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class '__main__.List'>

同様に、グローバル名前空間から削除できます

del list

組み込みの名前空間に配置します。

import builtins
builtins.list = List

そして今:

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class '__main__.List'>

また、リスト表示は無条件にリストを作成することに注意してください。

>>> list_1 = []
>>> type(list_1)
<class 'list'>

おそらくこれは一時的にのみ行うので、変更を元に戻しましょう。まずList、ビルトインから新しいオブジェクトを削除します。

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module 'builtins' has no attribute 'list'
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'list' is not defined

ああ、いや、私たちはオリジナルを見失った。

心配しないでください、私たちはまだ得ることができますlist-それはリストリテラルのタイプです:

>>> builtins.list = type([])
>>> list()
[]

そう...

なぜ[]より速いのですlist()か?

これまで見てきたように、上書きすることはできますlistが、リテラル型の作成を傍受することはできません。を使用するときはlist、何かがあるかどうかを確認するためにルックアップを実行する必要があります。

次に、検索した呼び出し可能オブジェクトを呼び出す必要があります。文法から:

呼び出しは、空の可能性のある一連の引数を使用して、呼び出し可能なオブジェクト(関数など)を呼び出します。

call                 ::=  primary "(" [argument_list [","] | comprehension] ")"

リストだけでなく、どの名前でも同じことをすることがわかります。

>>> import dis
>>> dis.dis('list()')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis('doesnotexist()')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

以下のため[]のPythonバイトコードレベルでの関数呼び出しはありません。

>>> dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

バイトコードレベルでのルックアップや呼び出しを行わずに、リストを作成するだけです。

結論

私たちは、その証明されているlistスコープ規則を使用してユーザーコードを傍受することができ、そのlist()呼び出し可能なためルックスと、それを呼び出します。

一方、[]はリスト表示またはリテラルであるため、名前の検索や関数呼び出しを回避できます。

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

今週のコミックコンですべての素晴らしいものに追いつく方法

今週のコミックコンですべての素晴らしいものに追いつく方法

サンディエゴコミックコンは今週開幕し、オタクのアナウンス、ポスター、予告編、お気に入りの番組や映画のからかいでいっぱいになります。SDCCは、コンベンションフロア全体の多くのパネルで行われているため、すべてに対応するのは難しい場合があります。

Googleの9千万ドルの和解はアプリ開発者にとってもGoogleにとっても勝利ですか?

Googleの9千万ドルの和解はアプリ開発者にとってもGoogleにとっても勝利ですか?

小さなアプリ開発者は金曜日に発表された法的な和解でグーグルから9千万ドルをこじ開けた。アップルとの同様の合意に続いて熱くなった。金曜日のブログ投稿で、Googleは、Androidメーカーが市場での優位性を悪用してPlayストア経由でのアプリ内購入に対して30%の料金を不当に請求したと主張するアプリ開発者との訴訟を解決するために、9千万ドルを支払うことに合意したと述べました。

RadioShackのTwitterはハッキングされていませんでした、それはただの暗号のサクラです

RadioShackのTwitterはハッキングされていませんでした、それはただの暗号のサクラです

今週、RadioShackのTwitterアカウントは、奇妙なものから完全にひどいものになりました。短い順序で、会社のフィード全体が、バイブレーター、「ビッグティット」(スペルミス)、有名人やその他の企業アカウントを荒らしているツイートなど、NSFW素材の真の山になりました。

ヒッグス粒子から10年後、物理学にとって次の大きなものは何ですか?

ヒッグス粒子から10年後、物理学にとって次の大きなものは何ですか?

大型ハドロン衝突型加速器のトンネル内にあるコンパクトミュオンソレノイド(CMS)検出器。2012年7月4日、CERNの科学者たちは、1960年代に最初に提案された素粒子であるヒッグス粒子の観測を確認しました。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

Un breve viaje espacial sobre conceptualizar el diseño

Complicarse la vida, mezclar churros con meninas (nada de ovejas) y encontrar valor en un trastero que adquiriste en una puja.

Un breve viaje espacial sobre conceptualizar el diseño

Bien. Hay un momento en toda salida al espacio exterior en el que de la tensión, la velocidad y las altas temperaturas derivadas del cruce de estratosfera a ionosfera se pasa a un momento de súbita calma, donde se despliega la vista completa del paisaje espacial que nos rodea.

Seguindo Todos os Protocolos (2022), de Fábio Leal

Seguindo Todos os Protocolos (2022), de Fábio Leal

Chico quer transar. Até aí, tudo bem.

多元宇宙—Junø

多元宇宙—Junø

チェーン間アカウントがJunoに登場します。異なるブロックチェーン間でスマートコントラクトの構成可能性と真の相互運用性を提供します。

#brand【ベター・コール・ソール!アメリカのテレビシリーズ「ブレイキング・バッド」に最高のビジネス例が隠されている】・・・ルールクリエイティブ

#brand【ベター・コール・ソール!アメリカのテレビシリーズ「ブレイキング・バッド」に最高のビジネス例が隠されている】・・・ルールクリエイティブ

1.ドラマを見た後、起業する考えはありますか?あなたのビジネスはボトルネックに遭遇しましたか?方向性がなくてわからない場合は、ドラマを追いかけて行くことを心からお勧めします。(?)ブラフではなく、最も完璧なビジネス例を隠すドラマがあります。2.ブレイキング・バッドとその弁護士ドラマ「ブレイキング・バッド」を見た友人たちは、演劇の中で、穏やかな表情で、弁護士のソウル・グッドマンに深く感銘を受けなければなりません。口を開けて、感覚の弱い傭兵の性格を持っています。道徳の面で、サル・グッドマンは無意識のうちに劇に欠かせない役割を果たし、彼自身のシリーズ「絶望的な弁護士」(ベター・コール・ソール)を生み出しました。ウェントウのテキストとビデオは、劇中のソウル・グッドマンのテレビコマーシャルです。製品(サービス)、競争戦略、市場ポジショニング、ブランド名、ターゲット顧客グループ、コミュニケーション軸から広告まで、サル・グッドマンの役割のビジネス設定は、「最低」と見なすことができる超超超超超超完全です。ブランドコミュニケーションのコスト」「変化」のモデル。なぜ?私の分析をご覧ください。3.ソウル・グッドマンの「事業戦略」1.基本情報ブランド名:Saul Goodman製品:法律相談サービス対象顧客:麻薬中毒、飲酒運転、事故など。法律知識の欠如は、一般的に公立弁護士にしか余裕がなく、真面目な弁護士も「特別な法律を持つ消費者」を避けます。恐れてはいけない「​​ニーズ」。コミュニケーションの主軸:この国のすべての男性、女性、子供は有罪判決を受けるまで無実だと思います。地域:アルバカーキ市スローガン:Thrallに電話したほうがいいです!(ベター・コール・ソール)広告:2つの可能性のある犯罪状況をシミュレートします+サウルの主張+サウルのスローガン2をより適切に呼び出します。

Language