Jak najprościej zaimplementować obsługę słownika w C?

W pewnym momencie mojej radosnej twórczości w języku C okazało się, że trzeba mi zaimplementować obsługę słownika – rozumianego jako lista par klucz-wartość.

Ustaliłem, że potrzebuję, by każdy element słownika był reprezentowany przez parę (ciąg znaków, liczba zmiennoprzecinkowa). Słownik będzie wielokrotnie wykorzystywany, więc zamierzam przechowywać go w pliku.

Nie wiem, jak to najprościej zrobić w C. Przyszły mi do głowy następujące cztery pomysły:

• zaimplementowanie własnej obsługi własnej struktury słownika w pliku tekstowym (opcja "hardest");
• zaimplementowanie własnej obsługi struktury w jakimś popularnym formacie (np. JSON);
• skorzystanie z biblioteki do obsługi jakiegoś popularnego formatu (np. JSON);
• skorzystanie z biblioteki do obsługi słowników (o ile taka w ogóle jest dla C) (opcja "softest").

Być-może-istotne-szczegóły-projektowe: przewiduję, że ciąg znaków będzie zawierać następujące znaki: a-z, A-Z, 0-9, łącznik (-) i apostrof. Na razie nie planuję, by zawierał białe znaki; jestem jednak przewidujący, więc pomyślałem, że fajnie by było, gdyby przy implementacji od razu uwzględnić taką możliwość. Przewiduję, że liczba zmiennoprzecinkowa powinna mieć co najmniej dwa miejsca po przecinku; będzie z zakresu (0; 1].

Który z tych pomysłów jest najlepszy (głównie: najprostszy)? Może ktoś zna jakieś biblioteki? Najbardziej chciałbym takie, które są powszechne w repozytoriach dystrybucji Linuksa.

PS. Zapomniałem o dość ważnej rzeczy: jakie operacje przewiduję na słowniku. Otóż:

1. wyszukiwanie par po kluczu, tj. po ciągu znaków;
2. dodawanie par;
3. usuwanie par;
4. modyfikowanie wartości; ostatecznie mogę to zaimplementować za pomocą usuwania i dodawania, tylko martwię się o wydajność.

Jeszcze jedna uwaga, właśnie co do wydajności: przewiduję, że słownik będzie zawierać co najmniej kilka tysięcy par, a być może i kilkadziesiąt tysięcy (chyba że wcześniej porzucę ten projekt – tak, uwzględniam taką możliwość). Nie wiem, czy to ma znaczenie przy wyborze rozwiązania.

PS2. Fajnie będzie, jeśli będzie łatwo sortować słownik, aczkolwiek to mogę zrobić także jakoś zewnętrznie (może w Bashu?).

Jeszcze przyszło mi do głowy: nie musi to być nawet w języku C. Jednak z uwagi na to, że aktualnie po prostu w nim piszę, oraz z uwagi na wydajność wybrałem go. W przypadku innej technologii wolałbym, by była to taka, którą się posługuję; jako więc alternatywę rozpatruję aktualnie Bash i JavaScript.

Podstawowe pytanie, jaki ma być ten słownik, dynamiczny? To wtedy, Masz do zaimplementowania strukturę key: value, jako tree lub hash table, jak nie to, to wystarczy prosta tablica.

Co to jest struktura dynamiczna, słownik dynamiczny?

Silv napisał(a):

Co to jest struktura dynamiczna, słownik dynamiczny?

To jest struktura, do której możesz dodawać elementy już po utworzeniu. Najpewniej potrzebujesz właśnie czegoś takiego.
Prosty pomysł, to zaimplementowanie tablicy haszującej z otwartym adresowaniem (poszukaj tylko tego terminu).

Tak, właśnie tak – potrzebuję wykonywać wszystkie cztery wymienione operacje po utworzeniu słownika. Rozumiem więc, @lion137, @enedil, że proponujecie mi wybór pierwszej opcji.

Jeszcze pytanie, jaka złożoność Cię interesuje, bo hash table, jak pisze @enedil daje Coi aproksymowaną stałą złożoność stałą (i to jest opcja najprostsza - w sensie kodowania), ale z sortowaniem to już może być gorzej. Z drugiej strony, drzewo(~logn), jak napisałem łatwo posortować.

Może po prostu zacznij używać C++? Nie musisz wcale korzystać z obiektów, wyjątków, polimorfizmu, szablonów i całego tego dobrodziejstwa, cały kod zostaje jaki był, kompiluje się tak samo (C++ to generalnie mówiąc wstecznie kompatybilny nadzbiór C), a słownikiem będzie std::map lub std::unordered_map. A jak nie to przykładem gotowej implementacji kolekcji w C jest https://github.com/srdja/Collections-C, albo możesz od razu postawić redisa i użyć C API.

Dodaj język skryptowy do Twojego projektu:

• https://www.lua.org/pil/24.html
• https://docs.python.org/3/extending/embedding.html

lion137 napisał(a):

Jeszcze pytanie, jaka złożoność Cię interesuje (…)

To jest jeszcze do dokładnego ustalenia, nie myślałem nad tym za wiele. Ale na szybko: nowe elementy najpewniej będą dodawane rzadko; podczas dodawania często będzie wykonywana modyfikacja; usuwać na razie nie planuję – poza przypadkami implementacji modyfikacji pary jako usunięcie-dodanie; wyszukiwanie będzie najczęstsze i powinno być najszybsze.

Spearhead napisał(a):

Może po prostu zacznij używać C++?

To jest do przemyślenia, tak. ;) No ale żebym zmieniał technologię z projektu na projekt, to chyba nie ja…

A jak nie to przykładem gotowej implementacji kolekcji w C jest https://github.com/srdja/Collections-C, albo możesz od razu postawić redisa i użyć C API.

A tego nie znałem; zobaczę, co to.

Spine napisał(a):

Dodaj język skryptowy do Twojego projektu:

• https://www.lua.org/pil/24.html
• https://docs.python.org/3/extending/embedding.html

Nie mówię definitywnego "nie", ale… jak wykorzystanie technologii, której nie znam, może mi ułatwić projekt? Przez "ułatwienie" rozumiem w szczególności ułatwienie wykonania go tak, by posiadał jak najmniej błędów.

PS. @Spine: chyba że masz na myśli też Bash lub JavaScript. To wtedy OK. Ale przy nich pozostaje to samo pytanie, co do C.

Silv napisał(a):

To jest do przemyślenia, tak. ;) No ale żebym zmieniał technologię z projektu na projekt, to chyba nie ja…

Zależy chyba jaki jest cel tego projektu. Edukacja? Jak tak, to żaden problem, nauczysz się czegoś nowego, wpłyniesz na szerokie wody C++, olbrzymia i groźna to kraina, ale właśnie w mojej opinii najlepiej zacząć właśnie od poznania C - sam tak zrobiłem i IMHO to najlepsza droga. Bo właśnie po to w C się walczy z zarządzaniem pamięci żeby potem odkryć dobrodziejstwa takie jak wektor. A jeżeli robisz projekt by coś konkretnego dla ciebie robił, to co za różnica w czym jest napisany... przechodząc zaś na C++ (początkowo raczej "C z klasami") nie będziesz musiał kodu przepisywać, bo kompilator C++ radzi sobie z kodem C (po to cały język stworzono).

Silv napisał(a):

Spine napisał(a):

Dodaj język skryptowy do Twojego projektu:

• https://www.lua.org/pil/24.html
• https://docs.python.org/3/extending/embedding.html

Nie mówię definitywnego "nie", ale… jak wykorzystanie technologii, której nie znam, może mi ułatwić projekt? Przez "ułatwienie" rozumiem w szczególności ułatwienie wykonania go tak, by posiadał jak najmniej błędów.

Reszta projektu dalej będzie w C. Ale dzięki dołączonemu Pythonowi, słownik obsłużysz bezbłędnie, eliminując boilerplate :]

Silv napisał(a):

PS. @Spine: chyba że masz na myśli też Bash lub JavaScript. To wtedy OK. Ale przy nich pozostaje to samo pytanie, co do C.

W sumie głównie Python jako język osadzony w Twojej aplikacji załatwiałby sprawę. No i tak jak pisałem, C by służył do odpalania części aplikacji napisanych w języku Python. Zapis tego dictionary do pliku mógłbyś zrobić jako serializację do pickle => https://wiki.python.org/moin/UsingPickle

o jest jeszcze do dokładnego ustalenia, nie myślałem nad tym za wiele. Ale na szybko: nowe elementy najpewniej będą dodawane rzadko; podczas dodawania często będzie wykonywana modyfikacja; >usuwać na razie nie planuję – poza przypadkami implementacji modyfikacji pary jako usunięcie-dodanie; wyszukiwanie będzie najczęstsze i powinno być najszybsze.

Tak, najprościej, to chyba najlepiej zaimplementować hash table, tu dobry wykład:
https://runestone.academy/runestone/books/published/pythonds/SortSearch/Hashing.html#implementing-the-map-abstract-data-type

Moja propozycja:

• slownik zapisywany w formacie *.properties
• w pamieci trzymasz hashmape, tzn. dla klucza liczysz hashcode, wg niego wybierasz kubelek, w kubelku masz liste par klucz-wartosc.(taka podstawowa implementacja)

C nie sluzy do pisania "aplikacji", tak moze bylo z 50 lat temu. Obecnie to tool do programowania systemowego (drivery, kernel, protokoly sieciowe).
Jesli piszesz cos wiekszego to wez C++, tak samo szybkie a mniej meki z problemami schylku XX w.

@Silv ja Ci już mówiłem: chcesz napisać swój słownik/hashmapę/cokolwiek w ramach nauki - zrób to. W C, C++, w czym chcesz. Ale jeśli realizujesz jakiś projekt a nie piszesz RTOSa i nie masz ograniczeń co do wyboru języka to bierzesz przynajmniej C++ w wersji 11, bo zwyczajnie szkoda się mordować z ubogą biblioteką standardową. Chyba, że chcesz wszystko przy okazji tego projektu poznać od bebechów, to ok. Ale skończy się na zaimplementowaniu pełnej obiektowości i RAII z C++ w C przy użyciu setjmp/longjmp ;)

Standardowa biblioteka do C jest faktycznie uboga, dlatego nie wyobrażam sobie pracy w C bez GLiba. Wszystko to co w normalnych bibliotekach standardowych jest, m. in. Drzewa i Tablice Hashujące. A GLib jest dobrze przetestowany bo jest podstawą do środowiska graficznego GNOME

Silv napisał(a):

Co to jest struktura dynamiczna, słownik dynamiczny?

O chłopie, Ty żartujesz? :)

(Trochę powtórzę po kolegach, ale wybaczcie, to w celu resume...)

• Jeśli chcesz się uczyć, to bardzo dobrze, ale sensownie tego nie zrobisz, jeśli jesteś na poziomie pytań powyższych... :)
• Jeśli to jest zewnętrzne zlecenie, a możesz zmienić język/technologię -- to koledzy pisali o C++11...
• Jeśli to jest zewnętrzne zlecenie, a nie możesz zmienić języka/technologii -- to GLib...
• Jeśli to jest zewnętrzne zlecenie, a nie możesz zmienić języka/technologii ani użyć GLib (czy innej gotowej biblioteki), a dodatkowo nie masz czasu na naukę struktur dynamicznych (a w C sprowadza się to do mieszania wskaźnikami), to OSTATECZNIE możesz zrobić coś takiego:

#define MAX_KEYS 100
struct Dict {
    int size;
    KEY_TYPE kt[MAX_KEYS];
    VAL_TYPE vt[MAX_KEYS];
};

i do tego dopisać odpowiednie funkcje (oczywiście musisz też zdefiniować i odpowiednio obsłużyć typy KEY_TYPE oraz VAL_TYPE)...

koszalek-opalek napisał(a):

Silv napisał(a):

Co to jest struktura dynamiczna, słownik dynamiczny?

O chłopie, Ty żartujesz? :)

(Trochę powtórzę po kolegach, ale wybaczcie, to w celu resume...)

• Jeśli chcesz się uczyć, to bardzo dobrze, ale sensownie tego nie zrobisz, jeśli jesteś na poziomie pytań powyższych... :)

Wyróżnienie moje
Dla mnie nazwa słownik dynamiczny też jest dziwna, nowa i niezrozumiała. Szybciej powiedziałbym słownik mutowalny/zmienny w przeciwieństwie do słownika niemutowalnego/niezmiennego

Kamil Żabiński napisał(a):

koszalek-opalek napisał(a):

Silv napisał(a):

Co to jest struktura dynamiczna, słownik dynamiczny?

O chłopie, Ty żartujesz? :)

(Trochę powtórzę po kolegach, ale wybaczcie, to w celu resume...)

• Jeśli chcesz się uczyć, to bardzo dobrze, ale sensownie tego nie zrobisz, jeśli jesteś na poziomie pytań powyższych... :)

Wyróżnienie moje
Dla mnie nazwa słownik dynamiczny też jest dziwna, nowa i niezrozumiała. Szybciej powiedziałbym słownik mutowalny/zmienny w przeciwieństwie do słownika niemutowalnego/niezmiennego

Dynamiczny znaczy coś innego niż mutowalny. W niemutowalnym nie można nic zmieniać, a w niedynamicznym (statycznym) można np. zmieniać wartość pod kluczem, o ile taki istnieje. Chodzi tutaj nie o określenie zewnętrznych interakcji z obiektem, a o jego "zdolności". Przykładowo, może być nieco łatwiej zaimplementować słownik oparty na drzewie, jeśli klucze nie będą zmieniane - wystarczy wziąć zbiór kluczy, posortować go, i zbudować w ten sposób zbalansowane drzewo binarne, którego nie trzeba dodatkowo balansować w kolejnych operacjach.

Dla mnie nazwa słownik dynamiczny też jest dziwna, nowa i niezrozumiała

Dynamiczna struktura, słownik, lista, to taka, do której możemy, dodawać elementy, dopóki nam pamięci nie zabraknie, w przecieństwie od niej statyczna, to taka, która ma, podczas działania programu, stały rozmiar: tablica, czy hash table z dwóch tablic. Typowy przykład dynamicznej struktury:
https://en.wikipedia.org/wiki/Dynamic_array

Pozwolę sobie zrobić jeszcze jedno podsumowanie dotychczasowych pomysłów; umieszczam je tu głównie po to, by mieć je w połączeniu z tematem (a nie gdzieś na kartce). Jakbym się pomylił co do intencji niektórych osób, krzyczcie.

1. @lion137 proponuje, bym zaimplementował prostą tablicę, drzewo lub tablicę haszującą (np. przy pomocy tego).
2. @Spearhead proponuje trzy rzeczy: 1) bym odszedł od pomysłu wykonania całości w C i zaczął używać C++, i względem tego wykorzystał albo std::map, albo std::unordered_map; dodaje później, że mogę nawet skompilować go [słownik std::map] jako dzieloną bibliotekę .so z wyeksponowanym API i dołączyć do reszty projektu żeby zachować "czystość"; 2) jeśli wolę wykonać całość w C, to mogę wykorzystać https://github.com/srdja/Collections-C; 3) mogę też skorzystać z C API Redisa.
3. @Spine proponuje, bym, nie porzucając C, wykorzystał język skryptowy – Lua lub Python. Dodaje później, że w przypadku Pythona mógłbym pomyśleć o formacie danych pickle.
4. @Kamil Żabiński również proponuje, bym wykorzystał język skryptowy, ale – Scheme; wspomina też o "Embedded Scheme" i "CHICKEN Scheme" (nie wiem jeszcze, czym one są). Później dodaje, że jeśli wykorzystuję bibliotekę standardową w C, to do pary mógłbym wziąć bibliotekę GLib.
5. @vpiotr proponuje, by słownik zapisywać w formacie .properties i skorzystać z tablicy haszującej. I także radzi odejść od C na rzecz C++.
6. @alagner także radzi odejść od C na rzecz C++ (przynajmniej w wersji 11).
7. @koszalek-opalek wspomina o C++, GLib, a jeśli nie mógłbym ich użyć, to w ostateczności mogę wykorzystać statyczną "kolekcję" w C.

Ogólnie najwięcej problemów mam z wymyśleniem, jak sprawnie obsłużyć plik. Ale jeszcze żadnego powyższego pomysłu nie rozważałem dogłębnie, więc może niektóre z nich to uwzględniają. Będę nad tym myślał.

Wszelkie jeszcze inne propozycje mile widziane.

@Silv: To jakiś żart? https://github.com/lion137/Python-Data-Structures

@lion137: Ale co ma być żartem?

UPDATE:

Po pobieżnym zastanowieniu się nad zaproponowanymi rozwiązaniami doszedłem do wniosku, że jedynie dwa z nich opisują najtrudniejszą rzecz, czyli obsługę plików: moduł pickle oraz Redis. Rozwiązania dotyczące tej kwestii opiszę więc najpierw; o pozostałych rozwiązaniach wspominam niżej.

Dokumentacja Pythona zaznacza, że moduł pickle nie jest bezpieczny (cokolwiek to znaczy). Uznałem więc, że dla tak niewielkich potrzeb jak moje nie ma sensu: 1) na tyle zmniejszać zaufania do programu, lub: 2) zużywać czas/energię na dodatkowe zabezpieczanie się tam, gdzie nie oczekiwałem, że będę musiał dodatkowo się zabezpieczać.

Redis wydaje się więc lepszym wyborem z tej dwójki. Niemniej chcę umożliwić innym osobom w miarę bezproblemową instalację programu, który będzie wykorzystywał słownik (idealnie: brak potrzeby instalacji i minimalny proces make). A domyślam się, po pobieżnym poczytaniu o Redisie, że użytkownik programu będzie musiał mieć go zainstalowanego. Nie jestem przekonany, czy taka zależność nie będzie zbytnim obciążeniem – skutkującym niechęcią do używania programu. Na razie więc wstrzymam się z okazywaniem entuzjazmu co do używania Redisa. — Ale od razu zaznaczę, @Spearhead, że wygląda on całkiem-całkiem (i w ogóle dzięki za pokazanie go!). Jeśli nie użyję go teraz, to jeśli tylko nie porzucę projektu, a okaże się przydatny (projekt, nie Redis), zastanowię się, czy Redisa jednak nie użyć.

Podsumowując więc obsługę plików: brakuje mi nadal wiedzy, jak to zrobić. Leży mi wykorzystanie pliku tekstowego, więc co do formatu danych, to skłaniam się do użycia JSON-a, XML-a lub wymienionego przez @vpiotr formatu .properties. Ogólnie: jakiegoś formatu szeroko używanego i możliwego do czytania przez człowieka (choć człowiek nie jest głównym celem).

Co do rozwiązań dotyczących samej struktury danych: skłaniam się ku jakiejś szeroko używanej bibliotece, którą większość przyszłych użytkowników programu powinna mieć (vide wcześniejszy akapit o Redisie: pożądana minimalizacja zależności).

Nie mam prawie żadnych informacji o popularności GLib, ale z racji na jej wiek i przeznaczenie myślę, że nie powinna być mała. Jest to opcja.

Jeszcze mniej wiem o popularności Collections-C. Choć widać, że ma wiele gwiazdek na GitHubie, to ja na przykład o tym wcześniej nie słyszałem (albo słyszałem, ale nie było mi potrzebne i zapomniałem).

Podsumowując więc strukturę danych: potrzeba by mi było informacji o popularności obu wymienionych rozwiązań.

Wszelkie inne rozwiązania nadal mile widziane przeze mnie – choć nie ukrywam, że w tym momencie już wolałbym się skoncentrować na czymś.

PS. Jeśli przeoczyłem jakąś informację, która moje powyższe spostrzeżenia może zmienić – piszcie.

To się trochę problem XY zaczyna robić. Może tak: co ten słownik i plik mają zawierać? Konfigurację? Dane wejściowe? Jakie wartości (inty/stringi czy wartości będą jakieś bardziej skomplikowane?)? Bo może zwykły libconf się nada.

alagner napisał(a):

To się trochę problem XY zaczyna robić. Może tak: co ten słownik i plik mają zawierać? Konfigurację? Dane wejściowe? Jakie wartości (inty/stringi czy wartości będą jakieś bardziej skomplikowane?)? Bo może zwykły libconf się nada.

Jak najbardzie zgadzam się z @alagner. @Silv Redis służy do innych celów. Jeśli potrzebujesz lokalnie w programie słownika to użyj po prostu którejś biblioteki. Na 90% będzie to prostsze niż stawianie Redisa. Redis miałby sens jeśli miałbyś swój program w wielu instancjach i chciał, żeby działał bez stanowo. Wtedy cały stan jest trzymany w Redisie.
Ewentualnie jeśli by twoja aplikacja składała się z wielu niezależnie wdrażanych elementów. Wtedy Redis może służyć jako prosta szyna wymiany informacji. Dokładnie kolejka Pub/Sub.
Dla programu desktopowego Redis to overengineering. I mówię to jako fan Redisa :)

alagner napisał(a):

To się trochę problem XY zaczyna robić. Może tak: co ten słownik i plik mają zawierać? Konfigurację? Dane wejściowe? Jakie wartości (inty/stringi czy wartości będą jakieś bardziej skomplikowane?)?

Napisałem w pierwszym poście:

Ustaliłem, że potrzebuję, by każdy element słownika był reprezentowany przez parę (ciąg znaków, liczba zmiennoprzecinkowa). (…) przewiduję, że ciąg znaków będzie zawierać następujące znaki: a-z, A-Z, 0-9, łącznik (-) i apostrof. Na razie nie planuję, by zawierał białe znaki; jestem jednak przewidujący, więc pomyślałem, że fajnie by było, gdyby przy implementacji od razu uwzględnić taką możliwość. Przewiduję, że liczba zmiennoprzecinkowa powinna mieć co najmniej dwa miejsca po przecinku; będzie z zakresu (0; 1].

@Kamil Żabiński: właśnie się zorientowałem. ;) Ale, jak napisałem, jeszcze może się przydać – gdybym program kiedyś rozwijał.

Popieram przedmówców, za mało tu kontekstu jest. Teraz na przykład się dowiadujemy, że to nie jest to program do jakichś twoich prywatnych celów, który to sobie będzie hulał na twojej maszynie, lecz będzie dystrybuowany do jakichś "użytkowników", więc lepiej rugować z niego nadmiarowe zależności. Im mniej wiemy tym trudniej się doradza

@Spearhead: ach, może i tak. Jest tak, że front-end programu (na początek CLI) ma umożliwić określenie języka tekstu podanego jako parametr – a w plikach ze słownikami będę przechowywać… cóż, słowniki. ;)

Czyli to jednak jest problem XY, bo nie doczytaliśmy.
Nie potrzebujesz słowników dynamiczny, statyczny czy jako zewnętrzna aplikacja jak Redis.
Potrzebujesz Internationalization and localization

W najprostszej wersji zamiast słownika możesz użyć zwykłej struktury z C z milionem pól. I dla Języka polskiego mieć ją wypełnioną stringami po polsku, a dla angielskiego po angielsku.
I potem zamiast pisać

printf("Hello World!");

piszesz

printf(strukturaZTlumaczeniami.helloWorld)

Następnym krokiem może być czytanie struktury z plików, ale to dopiero jak stwierdzisz że nie chce ci się utrzymywać tłumaczenia w kodzie.
Jako format pliku do trzymania tłumaczeń polecam pliki .properties bo to znam z Javy i tam działa.
Ale można użyć cokolwiek np Minimal Mistake (theme do Jekylla) trzyma wszystkie tłumaczenia w jednym pliku yaml

Kamil Żabiński napisał(a):

Czyli to jednak jest problem XY

Nie zgadzam się ;); ja się tłumaczę dobrze, jasno, szczerze…

Potrzebujesz Internationalization and localization

Może, może; na razie mnie interesują inne kwestie. Pomyślę na pewno o tej uwadze później.

PS. @Kamil Żabiński: ale nadal nie wiem, jak bezproblemowo obsłużyć dodawanie, modyfikację, usuwanie i wyszukiwanie w pliku, choćby z poziomu C.