Pythonの文字リストで文字列を作成できるかどうかを調べる最速の方法

Question

文字列で文字列を作成し、TrueまたはFalseを返すかどうかを確認する必要があります。

私はlist.countまたはcollections.Counterでさまざまなソリューションを使用しています。

また、私は文字のリストを通読する必要はいけない、このソリューションを使用しています：

def check(message, characters): 
    try: 
     [list(characters).remove(m) for m in message] 
     return True 
    except: 
     return False 

は最速の方法はありますか？文字の非常に非常に大きなリストのために。カウンターとリストの数が遅いようです。これを行うための高速なpythonic方法があるかどうか知らない。

例：= "hello" を

Answer 1

あなたはcollections.Counter()を使用することができ

message = "hello" 
characters = "hheellooasdadsfgfdgfdhgfdlkgkfd" 

check(message, characters) # this should return True or False 
# characters can be a veeeeery long string 

重複が問題はその一例文字= "hheloo" のメッセージのために動作しないでしょう。ただ、二つのカウンタを構築し、任意の負のカウントそこにいるかどうかを確認するためにsubtract()メソッドを使用します。

>>> c1 = Counter(characters) 
>>> c2 = Counter(message) 
>>> c1.subtract(c2) 
>>> all(v >= 0 for v in c1.values()) 
False 

これは線形時間で動作するはずです。

Answer 2

これは、両方の文字列の長さが重要であり、文字ごとに繰り返す必要があるため、線形時間では実行できません。実際の実装を確認することなく、私はremove()が対数であると仮定します。

def check(msg, chars): 
    c = list(chars) # Creates a copy 
    try: 
     for m in msg: 
      c.remove(m) 
    except ValueError: 
     return False 
    return True 

if __name__ == '__main__': 
    print(check('hello', 'ehlo')) 
    print(check('hello', 'ehlol')) 
    print(check('hello', 'ehloijin2oinscubnosinal')) 

Answer 3

これは、ユージンのソリューションとjbndlrのソリューションと比較した別の解決策です。

def test1(input_word, alphabet): 
    alp_set = set(list(alphabet)) 
    in_set = set(list(input_word)) 
    return in_set.issubset(alp_set) 

def test2(input_word, alphabet): 
    c1 = collections.Counter(alphabet) 
    c2 = collections.Counter(input_word) 
    c1.subtract(c2) 
    return all(v >= 0 for v in c1.values()) 

def check(msg, chars): 
    c = list(chars) # Creates a copy 
    try: 
     for m in msg: 
      c.remove(m) 
    except ValueError: 
     return False 
    return True 

input_word = "hello" 
alphabet = "hheellooasdadsfgfdgfdhgfdlkgkfd" 


start_time = time.time() 
for i in range(10000): 
    test1(input_word,alphabet) 
print("--- %s seconds ---" % (time.time() - start_time)) 

start_time = time.time() 
for i in range(10000): 
    test2(input_word,alphabet) 
print("--- %s seconds ---" % (time.time() - start_time)) 

start_time = time.time() 
    for i in range(10000): 
     check(input_word,alphabet) 
    print("--- %s seconds ---" % (time.time() - start_time)) 

>> --- 0.03100299835205078 seconds --- 
>> --- 0.24402451515197754 seconds --- 
>> --- 0.022002220153808594 seconds --- 

⇒jbndlrのソリューションは、このテストケースで最も高速です。

別のテストケース：

input_word = "hellohellohellohellohellohellohellohellohellohellohellohellohello" 
alphabet = 

は

"hheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfd"

>> --- 0.21964788436889648 seconds --- 
>> --- 0.518169641494751 seconds --- 
>> --- 1.3148927688598633 seconds --- 

⇒test1には、これを行うためのより高速な方法は多分あり、最速

Answer 4

で明らかに起因するすべての（）ジェネレータ（Why is Python's 'all' function so slow?）を作成するコストにおそらくforループ@eugene Yさんに拡大し、より高速であります答え：

from collections import Counter 
import time 

message = "hello" 
characters = "hheeooasdadsfgfdgfdhgfdlkgkfd" 

def check1(message,characters): 
    c1 = Counter(characters) 
    c2 = Counter(message) 
    c1.subtract(c2) 
    return all(v > -1 for v in c1.values()) 

def check2(message,characters): 
    c1 = Counter(characters) 
    c2 = Counter(message) 
    c1.subtract(c2) 
    for v in c1.values(): 
     if v < 0: 
      return False 
    return True 

st = time.time() 
for i in range(350000): 
    check1(message,characters) 
end = time.time() 
print ("all(): "+str(end-st)) 

st = time.time() 
for i in range(350000): 
    check2(message,characters) 
end = time.time() 
print ("for loop: "+str(end-st)) 

結果：

all(): 5.201688051223755 
for loop: 4.864434719085693