パイソン：直接セット

Question

にカンマ区切りの文字列を分割し、私のようなものありませんいくつかのコードがあります。

if string in comma_delimited_string.split(','): 
    return True 

This websiteはセットとdictsとメンバーシップのテストは非常に速く、そのリストやタプルであると述べています。 set(comma_delimited_string.split(','))を実行すると、リストがセットに変換される前にリストが作成されているため、スピードが向上しないことがわかります（少なくとも、タイムアウトすると遅くなるようです）。

私は（私のコードへの真のメリットよりも、主に好奇心から）、その後、思っていた、comma_delimited_string.split(',')のと同じ効果を達成するための方法があるが、直接セットを作成し、リストの代わりに、スピードアップのつもりで上記の操作は？

Answer 1

いいえ、str.split操作は常にリストを返し、それをsetに変換しようとすると時間がかかります。 str.splitはCでimplementeがあるため、また、直接生成し、独自の手作りsplitを書くことセットは、遅くなりますが

ノート（ソースコードはObjects/stringlib/split.h下でなければなりません）があなたのstringは、カンマが含まれているとしない場合

if string in comma_delimited_string: 

stringにカンマが含まれている場合は、あなたのテストは常にのでデフで（失敗します：あなたはstringその後、あなただけ行うことができ、splitによって返される要素の部分文字列ではないことを期待します要素text.split(',')は決して1つを含んでいません。

あなたが何か持っている時には、上記の条件が失敗する場合がある。この場合には"a" in ["aaa", "bb", "c"]が失敗したので

if "a" in "aaa,bb,c".split(',') 

を。

別の方法としては、正規表現を使用することができます。

import re 
if re.search(r'(^{0},)|(,{0},)|(,{0}$)|(^{0}$)'.format(re.escape(string)), comma_delimited_string): 

私はこれがより速くなるかどうかわかりませんが、それはおそらくあなたの入力に依存します。

Answer 2

何かをセットに変換するには、それを反復する必要があるという事実を無視しています。その繰り返しは元のリストを検索するために既に行っているのとまったく同じです。だから、オーバーヘッドだけでこれを行うことに利点はありません。

あなたが変換のコストを償却することができるので、あなたがそれを何度もやっているならば、セットに対する検索はより効率的です。しかし、変換自体は常にリニアスキャンになります。それを避ける方法はありません。

Answer 3

既存のセットのメンバシップテストはリスト（O（n））より速く（O（1））、文字列からセットを作成する必要があります。 n）。時間の複雑さについては何もできません。

あなただけの代わりに、中間データ構造を構築する文字列をスキャンすることによって、しかし一定の係数でテストをスピードアップすることができます：あなたは本当に良い理由がない限り

(',%s,' % string) in (',%s,' % comma_delimited_string) 

はこれを使用しないでください。