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:
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.