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.

Goodbye Atom

W roku 2014 pojawił się a hackable editor for the 21st century czyli Atom. Od początku mnie zaintrygował. Był to edytor międzyplatformowy, open source, działający w GUI, reklamowany jako rozszerzalny… Samo dobro. Pobrałem i… skasowałem, ze względu na rozmiar. Ważył bowiem grube kilkadziesiąt MB, co wydało mi się sporą przesadą.

Screenshot ze strony projektu
Screenshot ze strony projektu. Źródło: https://atom.io/

Później jednak przekonałem się do Atoma, a nawet go polubiłem. Uzbrojony w pluginy był bardzo przyjemnym narzędziem wspomagającym edycję różnych formatów plików. Więcej, niż edytorem, bardziej traktowałem go jako IDE. Choć z rasowymi IDE nie mam doświadczenia. Czy to Python, Puppet czy zwykłe YAMLe – wszystko edytowało się przyjemnie, ze stosownym kolorowaniem, linterami itp. Pamiętam, że na jednym ze szkoleń z Pythona śmiało współzawodniczył z PyCharm. IIRC wówczas jednej rzeczy nie dało się zrobić w Atomie, i jednej w PyCharmie. W każdym razie, niczego mi w Atomie nie brakowało.

Dlatego w ogłoszeniu o wygaszeniu projektu zdanie Atom has not had significant feature development for the past several years wydaje mi się dwuznaczne. Skoro program ma wszystko, co potrzebne, to co tu rozwijać? No i jeśli oparty jest o wtyczki – a tak było w przypadku Atoma – to ficzery w samym programie też stają się drugorzędne.

Tak czy inaczej, decyzja mnie nie dziwi. Skoro Microsoft ma swoje Visual Studio Code, to będzie je promował, więc po co mu wewnętrzna konkurencja? Artykuł wspomina właśnie VSC jako alternatywę. Zapewne nieprzypadkowo. Z drugiej zaś strony jak robiłem przegląd ewentualnych alternatyw w głowie, to VSC jak najbardziej się pojawiło.

Nie ukrywam, że mam pewien sentyment do Atoma i parę wspomnień z nim związanych. Towarzyszył mi przy nauce Pythona, która zbiegła się ze zmianą pracy. Był nieodłączną częścią DSP2017.

Potem spojrzałem na listę alternatyw i… nie jest wiele lepiej. Nie widzę żadnego następcy czy też zastępcy. Chwilowo najbardziej skłaniam się ku wolnej wersji VSC czyli VSCodium. Ale to bez pośpiechu. W końcu Atom jest open source, więc może jednak okaże się, że będzie utrzymywany.

UPDATE Polecę jeszcze wpis, który właśnie przeczytałem. Nie o edytorze, a o desktopie, ale jest i o edytorach (vim).