Podobieństwo i porównywanie zbiorów

Przy okazji projekciku[1] trafiłem na interesujący problem. Chodzi o porównywanie zbiorów, a dokładnie liczenie ich podobieństwa. Marzyło mi się, by wyrazić je w zakresie 0 do 1, gdzie 0 to zbiory rozłączne, a 1 zbiory identyczne[2].

Popełniłem następujący kawałek kodu, liczący, na ile set2 jest podobny do set1:

def count_similarity_percent(set1, set2):
    base_count = len(set1)
    if base_count == 0:
        base_count = 1
    matching = 0
    for element in set1:
        if element in set2:
            matching += 1
    perc = 100 * matching / base_count
    return perc

Niby działa, ale… Spójrzmy na przykłady.
Przykład 1:

A = [1, 2, 3, 4]
B = [3, 4, 5, 6]

Podobieństwo A do B wynosi 50% (2 z 4 elementów ze zbioru A występują w B).
Podobieństwo B do A także wynosi 50% (2 z 4 elementów ze zbioru B występują w A).
Wszystko fajnie. Podobieństwa są równe, niezależnie z której strony patrzeć.

Niestety, jeśli zbiory będą miały różną ilość elementów, to sprawa się komplikuje i podobieństwo A do B przestaje być równe podobieństwu B do A. Możemy to zobaczyć w kolejnym przykładzie.
Przykład 2:

A = [1, 2, 3, 4]
B = [3, 4]

Podobieństwo B do A to nadal 50%.
Podobieństwo A do B wynosi 100% – 2 z 2 elementów A występują w B.

Nie spodobało mi się to i zastanawiałem się, co można z tym zrobić. Z jednej strony chciałem, by wartości były przechodnie, tj. równe, niezależnie z które strony porównuję.

Przez głowę przeleciało mi szybko liczenie średniej z podobieństw i zapamiętywanie w obu przypadkach tego wyniku. Podobnie mógłbym zapamiętywać w obu wynikach większą – lub mniejszą – z wartości podobieństwa. Z drugiej strony kołatało mi się, że fajnie nie byłoby liczyć dwa razy.

Poszukałem, popytałem i okazało się, że są do tego miary. W tym przypadku miarą podobieństwa zbiorów jest indeks Jaccarda[3] . Jest prosta i „przechodnia”, tj. nie ma znaczenia, który zbiór z którym się porównuje.

Znalazłem taki wpis o indeksie Jaccarda dla Pythona, ale przyznaję, że nie spodobała mi się implementacja. Po pierwsze, bez sensu importowane jest numpy, które w tym przypadku niczego nie robi. Po drugie, implementacja jest poprawna, ale nieco zakręcona. Lepiej implementować na setach, nie listach. I jak najbardziej można skorzystać z wbudowanego union, a następnie liczyć wprost, wg definicji.

def jaccard_index_percent(set1, set2):
    intersection_count = len(set1.intersection(set2))
    union_count = len(set1.union(set2))
    if union_count == 0:
        union_count = 1
    return 100 * intersection_count / union_count

Zapewne użyję ww. wersji do porównywania zbiorów. Chyba, że pokuszę się jeszcze kiedyś o optymalizację pod kątem prędkości działania. O ile zauważę taką potrzebę.

[1] Jeśli coś się z tego wykluje sensownego, to niebawem opiszę dokładniej.
[2] Od 0 do 1, od 0% do 100%, bez znaczenia, wartość jest taka sama. Choć IMO ludzie lepiej rozumieją procenty, a łatwiej kodować na float. Ale to wszystko nieistotny detal.
[3] Linkuję we wpisie polską wersję, która jest lakoniczna, ale prostsza. Jeśli ktoś jest bardziej zainteresowany tematem, to polecam wersję angielską, wraz z see also.

Advent of Code – po latach

Całkiem niedawno M. w mailu zapytał, czy znam Advent of Code. Ano znam. Nawet miałem o tym notkę. Odkąd poznałem, to bawię się regularnie. Z przerwą w 2019 z powodów, których nie pamiętam.

Ponieważ z tego co pamiętam nie robiłem jeszcze zadań „poza konkursem”, to dobry moment na podsumowanie. 2018 – 10 gwiazdek. 2020 – 33 gwiazdki, 2021 – 29 gwiazdek. W tym roku póki co 21 gwiazdek. Oczywiście na ilość gwiazdek rzutuje wiele czynników, z których istotnym jest czas, który mogę poświęcić na zabawę.

Niemniej staram się siąść codziennie rano o szóstej do komputera i porywalizować. Głównie ze znajomymi z pracy. Wspólny dashboard z wynikami to dobry motywator. I AoC ma to rozwiązane bardzo fajnie. W sumie tego najbardziej zabrakło mi w opisywanym rok temu Advent of Cyber.

Czy coś się zmieniło? Wydaje mi się, że tak. Dorobiłem się schematu rozwiązywania zadań. Po pierwsze, wszystko rozwiązuję w Pythonie. Po drugie, standardu dorobiły się struktura katalogów, nazewnictwo plików, nazewnictwo plików z wejściem, czytanie wejścia. Parsowanie wejścia, i debug podczas pisania też. Niekoniecznie zawsze jest przez to wszystko szybciej, ale mam wrażenie, że czas rozwiązywania jest stabilniejszy.

Wydaje mi się, że lepiej radzę sobie ze strukturami danych i podziałem na funkcje. Staram się pisać bardziej pythonowo, ale różnie to wychodzi. Z innych obserwacji – do rozwiązywania niektórych zadań (np. części drugiej dziś) przydaje się zabawa w CTFy.

Ogólnie Advent of Code bardzo mi się spodobał. Na tyle, że wykupuję co roku AoC+. Warto, bo to prawdziwe pay what you want.

Hacktoberfest 2022

W tym roku ponownie uczestniczyłem w Hacktoberfest. Początkowo wydarzenie traktowałem sceptycznie. Zresztą słusznie, bo problem mało istotnych commitów i spamu jak najbardziej istnieje. Potem jednak stwierdziłem, że to fajny motywator, żeby coś zrobić w open source. Zabawę z Hacktoberfest zacząłem więc w 2020, z repozytoriami nie uczestniczącymi oficjalnie w Hacktoberfest.

W zeszłym roku dołączyłem do firmowego wydarzenia. W ramach gry we własną grę, bawiliśmy się w zbieranie jak największej ilości gwiazdek. Czyli robienie commitów do repozytoriów z ich jak największą ilością. W duchu fair play, czyli bez spamu i poprawiania literówek. Trochę taki CTF.

Zatem w pełnym wymiarze uczestniczyłem w Hactoberfest 2021. Mógłbym dodać and all I got was this lousy t-shirt. Bowiem po spełnieniu warunków na odpowiednią liczbę commitów można było wybrać nagrodę – koszulkę lub zasadzenie drzewa. Lubię t-shirty, więc wybrałem koszulkę, mimo średniego koloru. Przy okazji dowiedziałem się, ile kosztuje darmowa koszulka po przejściu przez cło i Pocztę Polską. Otóż w 2021 przy deklarowanej wartości przesyłki $5,95, naliczono 5 zł VAT oraz 8,5 zł opłaty pocztowej. Razem 13,5 zł, czyli mniej więcej połowa wartości paczki. Zaś sama paczka dotarła w marcu 2022. Dowód:

Opłaty za koszulkę Hacktoberfest - Poczta Polska
Opłaty za koszulkę Hacktoberfest. Źródło: fot. własna

Nie powinno zatem dziwić, że w tym roku wybrałem posadzenie drzewa zamiast koszulki. Tegoroczny Hacktoberfest to trochę kontynuacja poprzedniego. Znowu zbieranie gwiazdek z ekipą z firmy. Z drugiej strony jest to powrót do korzeni, bo moje tegoroczne commity to głównie tłumaczenia do tldr. A przecież przygodę z open source zaczynałem od tłumaczeń w ramach Polish Debian Documentation Project, potem tłumaczyłem na polski w ramach GNU Polish Translation Team.

Oczywiście były też commity związane z kodem, oczywiście w Pythonie. I tu spostrzeżenie, że ludzie potrafią znaleźć błąd, zdebugować go, znaleźć miejsce, gdzie powinien być poprawiony i… założyć issue, wszystko pięknie opisując. Nie oceniam bo przyczyny mogą być różne, choć dziwię się, bo nakład pracy na założenie issue na GitHub z pięknym udokumentowaniem błędu i debugiem jest IMVHO większy, niż poprawka w kodzie. W każdym razie widać, że warto commitować i poprawiać takie drobne błędy.