Muszę sprawdzić, czy ciąg może być utworzony z listą znaków i zwrócić prawdziwe lub fałszywe.

Używam różnych rozwiązań z listą. Count lub Collections.Counter.

Używam tego rozwiązania, którego nie muszę czytać przez listę znaków:

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

Czy jest najszybszy sposób? Na bardzo dużą listę znaków. Licznik i liczba listy wydaje się wolniej. Nie wiem, czy jest szybki sposób, aby to zrobić.

Przykład:

message = "hello"
characters = "hheellooasdadsfgfdgfdhgfdlkgkfd"

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

duplikaty mają znaczenie , więc na przykład znaki = "HHOLOO" nie działałby na wiadomość = "cześć"

3
lapinkoira 26 czerwiec 2017, 12:16

4 odpowiedzi

Najlepsza odpowiedź

Możesz użyć collections.Counter(). Wystarczy zbudować dwa liczniki i użyj subtract() Metoda do sprawdzenia, czy jest jakieś negatywne liczenia:

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

Powinno to działać w linii liniowej.

7
Eugene Yarmash 26 czerwiec 2017, 09:24

Może być szybszy sposób robienia tego, najwyraźniej ze względu na koszty tworzenia generatora wszystkich () (Dlaczego funkcja Pythona" All "tak wolna?) Być może A do pętli jest szybsza, rozszerzająca się na odpowiedź @eugenena 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))

Wyniki:

all(): 5.201688051223755
for loop: 4.864434719085693
1
ragardner 26 czerwiec 2017, 10:42

Oto kolejne rozwiązanie w porównaniu do rozwiązania Eugene'a i rozwiązanie 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 ---

⇒ Rozwiązanie JBNdlr jest najszybsze - dla tego przypadku testowego.

Kolejna testowa:

input_word = "hellohellohellohellohellohellohellohellohellohellohellohellohello"
alphabet =   

" Hheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfdhheellooasdadsfgfdgfdhgfdlkgkfd "

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

⇒ Test1 jest najszybszy

1
P. Siehr 26 czerwiec 2017, 10:03

Nie jest to możliwe w czasie liniowym, jako długość obu strun ma znaczenie i muszą być iterowane dla każdej postaci. Bez sprawdzania rzeczywistej implementacji, zakładam remove() jest logarytmiczny.

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'))
1
jbndlr 26 czerwiec 2017, 09:32