Pomiędzy bitami

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.