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

Odpowiedz Nowy wątek
2020-01-12 23:45
0

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.


edytowany 10x, ostatnio: Silv, 2020-01-13 00:02

Pozostało 580 znaków

2020-01-12 23:59
0

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.


Nie wiem, czy doczytałeś moje dwie aktualizacje postu? Może odpowiadam na Twoje pytanie. - Silv 2020-01-13 00:00
Widzę, dalej nie wiem, czy to ma być struktura dynamiczna czy nie; jeśli chodzi o sortowanie, to drzewo można łatwo posortować - zwracając inorder - lion137 2020-01-13 00:03

Pozostało 580 znaków

2020-01-13 00:04
0

Co to jest struktura dynamiczna, słownik dynamiczny?


Pozostało 580 znaków

2020-01-13 00:08
1
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).

Pozostało 580 znaków

2020-01-13 00:13
0

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.


Pozostało 580 znaków

2020-01-13 00:19
1

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


edytowany 1x, ostatnio: lion137, 2020-01-13 00:20

Pozostało 580 znaków

2020-01-13 00:21
2

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.

PS: regexy też są w C++, raczej lepiej udokumentowane niż te POSIX-a - Spearhead 2020-01-13 00:22

Pozostało 580 znaków

2020-01-13 00:25
1

Dodaj język skryptowy do Twojego projektu:

Jeśli język skryptowy to tylko Scheme, a jeśli Embedded Scheme to tylko CHICKEN Scheme - Kamil Żabiński 2020-01-13 09:23

Pozostało 580 znaków

2020-01-13 00:30
0
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:

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.


edytowany 1x, ostatnio: Silv, 2020-01-13 00:30

Pozostało 580 znaków

2020-01-13 00:32
0

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.


Pozostało 580 znaków

2020-01-13 00:39
0
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).

Pokaż pozostałe 2 komentarze
Jak pisałem nie musisz poznawać całego C++ żeby to działało, wystarczy dodać sam std::map. Możesz nawet skompilować go jako dzieloną bibliotekę .so z wyeksponowanym API i dołączyć do reszty projektu żeby zachować "czystość". Ale jak pisałem, to tylko propozycje. - Spearhead 2020-01-13 00:51
Może C nie był najlepszym wyborem, zgadzam się; ale wciąż sądzę, że była to najlepsza decyzja, jaką mogłem podjąć w taki krótkim czasie, w jakim ją podjąłem. Myślałem kilka razy nad tym, by opracować całość w Bashu – i tak z niego korzystam – ale oszacowałem, że nie znam go na tyle, by sprawnie rozwiązać ewentualne problemy z wydajnością. W przypadku C oszacowałem, że po prostu żadnych problemów z wydajnością nie będzie. cd. - Silv 2020-01-13 00:56
Wydajność zależy od wielu czynników, jak używasz algorytmów o złożoności wykładniczej dla dużych zbiorów danych to i C nie pomoże. - Spearhead 2020-01-13 00:58
Cd. Nie lubię uczyć się technologii na potrzeby jednej struktury danych, jeszcze bardziej nie lubię przepisywać czegoś, co już działa. — Tak, wiem, zobaczymy, co z tego wątku wyjdzie… może nawet zmienię na C++, bo nie uśmiecha mi się pobierać i konfigurować nowe środowiska, gdy mam już np. kompilator i IDE do C++. - Silv 2020-01-13 01:01
Hm, pewnie powinienem przestawić się na myślenie w kategoriach algorytmów, a nie technologii. - Silv 2020-01-13 01:07

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0