Jaka jest najbardziej skomplikowana struktura danych, której użyłeś w praktycznej sytuacji? [Zamknięte]

Zarodek tego pytania powstał w wyniku dyskusji, którą prowadziłem z kilkoma innymi programistami z branży.

Okazuje się, że w wielu miejscach kierownicy projektów obawiają się złożonych struktur danych i generalnie nalegają na wszystko, co istnieje od razu po wyjęciu z pudełka ze standardowej biblioteki / pakietów. Ogólny pomysł wydaje się być kombinacją tego, co jest już dostępne, chyba że wydajność jest poważnie ograniczona. Pomaga to w utrzymaniu prostoty bazy kodu, co dla osób niebędących dyplomatami oznaczałoby „mamy duże zużycie, a nowsze, które zatrudniamy, mogą nie być tak dobre”.

Więc nie ma filtru kwitnienia, list pomijania lub drzew rozrzuconych dla ćpunów CS. Oto pytanie (jeszcze raz): Jaką najbardziej skomplikowaną strukturę danych zrobiłeś lub wykorzystałeś w biurze?

Pomaga zrozumieć, jak dobre / wyrafinowane jest oprogramowanie z prawdziwego świata.

Użyłem list pomijania do wyszukiwania. Tam, gdzie pracuję, istnieje standardowa implementacja i wszyscy są zachęcani do korzystania z niej. Użyłem Patricia próbuje do skutecznego przechowywania i pobierania adresów IP. Ponownie wdrożenie było już obecne.

Jestem programistą Java. Java Collection Framework może rozwiązać moje 90% problemy ze strukturą danych, pozostałe 10% wymaga wysiłku. Myślę, że jeśli naprawdę rozumiesz wyrafinowane standardowe lib napisane przez ekspertów, w większości przypadków znajdziesz pomoc.

Złożone struktury danych są trudne do utrzymania w prawdziwym świecie. Aby uniknąć bałaganu w kodzie, podzielę problem na kilka mniejszych. Każdy mały problem można rozwiązać za pomocą Java Collection Framework . Być może rozwiązanie nie jest najmądrzejsze (wymaga więcej pamięci i wolniej), ale działa i jest łatwe w utrzymaniu. To jest kompromis.

Jeśli muszę napisać złożoną strukturę danych, wybiorę podręcznik :)

Najbardziej skomplikowaną strukturą danych, z której korzystałem w pracy, była trie. Było to jednak dwadzieścia lat temu.

Problem z tworzeniem oprogramowania przemysłowego polega na tym, że większość programistów przemysłowych nie jest absolwentami informatyki (CompSci); dlatego techniki, które przeciętny grad CompSci przyjmuje za pewnik, są uważane za zbyt trudne dla programistów chleba i masła.

Brak ogólnej wiedzy CompSci w branży jest poważnym problemem. Na przykład straciłem liczbę programistów, których spotkałem i którzy nie rozumieją takich wyrażeń, jak! (A! = 5 i&b! = 3) i a == 5 || b == 3 są logicznie równoważne. Każdy, kto wie, jak zastosować Twierdzenie DeMorgan, może rozpoznać, że te wyrażenia są logicznie równoważne. Większość absolwentów spoza CompSci nigdy nie słyszała o twierdzeniu DeMorgan. Jeśli zbadamy jakąkolwiek znaczącą bazę kodu, znajdziemy wiele wystąpień wyrażeń, które negują negatywne podwyrażenia logiczne. Czytelność kodu zawierającego zanegowane negatywne podwyrażenia logiczne jest prawie zawsze poprawiana przez przekształcenie tych wyrażeń w ich niez negowane formy.

Kiedyś napisałem kolejkę kalendarza (kolejka priorytetowa O (1)) dla symulacji opartej na zdarzeniach, w której profilowanie wykazało, że istniejąca sterta była wąskim gardłem.

Wydałem również produkt, który zawiera maszynę skończoną z około 80000 stanów - kod do jej wygenerowania był co najmniej trochę skomplikowany.

Dawno, dawno temu, w galaktyce ... Pracowałem w zespole, który używał „buforów przyjaciół” Knutha w RTOS w asemblerze.

Gra Conwaya z 256 pokoleniami dla świata 1024 x 1024.

Naprawdę nie użyłem niczego specjalnego, od zera byłaby to podwójnie połączona lista .

Niezbyt ekscytujące, użyłem innych struktur. Ale twoje pytanie zostało zadane od zera.

Drzewo tablic skrótów zawierające ogólne listy danych finansowych - nawet nie pytaj. Czasami chciałbym być kowbojem. Ach, proste życie pod gwiazdami ...

Musiałem napisać od podstaw strukturę Circular Double-Linked-List dla Algorytmu Dancing Links dla solvera Sudoku. To było jak projektowanie kostki Rubika. Cała struktura była w zasadzie listą list - każdy węzeł wskazywał cztery inne.

Kiedyś użyłem drzewa o ważonej długości ścieżki do specjalnej pamięci podręcznej. To było zabawne. Napisałem również własne procedury zarządzania stertami w celu malloc()wymiany, ale wiele osób to zrobiło.

Po przemyśleniu najbardziej „skomplikowaną” strukturą danych, którą zrobiłem od zera, jest modelowanie sieci elementów opartej na podwójnie powiązanych listach. Ale to było lata temu, kiedy programowałem na poziomie systemu.

Obecnie prawie nie tworzę żadnych fantazyjnych struktur danych. Większość dzieje się w bazie danych, w której decydujesz, co wstawisz do tabeli, być może jakąś wstępnie obliczoną wartość, być może identyfikator powiązanego rekordu do szybkiego wyszukiwania, aby uniknąć niepotrzebnego wyszukiwania.

Osobiście uważam, że dane zadanie określa środki. Po co dążyć do korzystania z jakiejś egzotycznej struktury danych, jeśli nie ma z niej pożytku? I jeśli mogę powiedzieć w większości praktycznych programów stosowanych, prawdopodobnie nie ma potrzeby wymyślania nowego koła.

Czy kolejka priorytetowa się liczy? To pojawia się w prawie każdej aplikacji napisanej w czasie rzeczywistym. Niedawno stał się częścią standardowej biblioteki Java (Java 1.5).

Poza tym nie mogę wymyślić nic skomplikowanego, czego tak naprawdę chciałem, że nie byłem w stanie wyciągnąć biblioteki. Nie pozwoliłbym, żeby mnie to powstrzymało, ale zadałbym pytanie, dlaczego potrzebuję zbyt egzotycznej struktury danych, aby biblioteki mogły ją uwzględnić. Zdecydowanie poszukałbym istniejącej implementacji typu trie lub filtru kwitnienia lub listy pominięć, zanim spróbowałem napisać jedną z nich.

Ogólnie zgadzam się z twoim kierownikiem, że koszt budowy i utrzymania niestandardowej struktury danych zbyt ezoterycznej, aby nie istniała żadna wersja biblioteki, prawdopodobnie przeważy nad korzyściami wynikającymi z tej wydajności. Chciałbym, abyś wykazał, poprzez profilowanie, że zwykłe struktury bibliotek powodują znaczną utratę wydajności, zanim pozwolę Ci przejść dalej i zoptymalizować je za pomocą czegoś wymyślnego. Ponieważ z reguły tańsze jest kupowanie cykli procesora niż cykli inżynierskich.