Przy okazji niedawnego code review dostałem pytanie, czemu w skrypcie napisanym w Pythonie nie korzystam z obiektu typu set, tylko z dict. Chodziło o cache na kilka tysięcy elementów, odpytywany kilkaset tysięcy razy. Z przyzerowym hit ratio. Zdziwiłem się, bo kojarzyłem, że czytelna konstrukcja wykorzystująca in dla obiektu typu list
data = [x for x in range(1000)]
y = 1001
if y in data:
print("Hit")jest raczej wolna. Zwłaszcza w porównaniu z nieco mniej czytelnym wariantem z użyciem dict:
data = {x: True for x in range(1000)}
y = 1001
if data.get(y):
print("Hit")Odpisałem o co chodziło i usłyszałem, że przecież set jest szybki. Coś mi zaświtało. Bo niby set jest bardziej podobny w użyciu do listy, ale pod spodem ma parę ciekawych właściwości. Zresztą, gdy poprosimy LLM o optymalizację pod kątem szybkości, otrzymamy coś w stylu[1]:
data = {x for x in range(1000)} # Converted 'data' to a set
y = 1001
if y in data: # Checking membership still works the same way
print("Hit")Różnice w czasie wykonania możemy zgrubnie i niezbyt elegancko sprawdzić w następujący sposób:
| import time | |
| how_many = 1000 | |
| s = set() | |
| d = {} | |
| l = [] | |
| for x in range(1000000): | |
| d[x] = True | |
| s.add(x) | |
| l.append(x) | |
| test = [0, 1, 9999999] | |
| t1=time.time() | |
| for c in range(how_many): | |
| for t in test: | |
| if t in s: | |
| pass | |
| t2=time.time() | |
| print("set", t2-t1) | |
| t1=time.time() | |
| for c in range(how_many): | |
| for t in test: | |
| if d.get(t): | |
| pass | |
| t2=time.time() | |
| print("dict", t2-t1) | |
| t1=time.time() | |
| for c in range(how_many): | |
| for t in test: | |
| if t in l: | |
| pass | |
| t2=time.time() | |
| print("list", t2-t1) |
by Jak już jesteśmy przy tego typu ciekawostkach. A co jeśli mamy w cache ciągi znaków i chcemy sprawdzić, czy nasz ciąg znaków nie kończy się jednym z ciągów z cache? LLM poproszony o optymalizację znowu podpowiada, że lepszy jest set. Ale nieoczekiwanie sugeruje też wykorzystanie regexpów. I co? Ku mojemu zaskoczeniu regexp w stylu
pattern = re.compile("("+"|".join(our_set)+")"$")
return bool(pattern.search(tested_value))okazuje się najszybszym rozwiązaniem! Nie to, że uważam regexpy za szczególnie wolne, co to, to nie. Oczywiście pattern wykonujemy raz, nie dla każdej testowanej wartości.
Dalsza lektura:
O’reily High performance Python Dictionaries and Sets
[1] Tak, różnica niezbyt rzuca się w oczy przy takim zapisie. Mało widać różnicę między dict a set. Kiedyś już o tym wspominałem. Czytelniejszy zapis – którego chyba nikt nie używa – tamże.