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

17

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.

data-structures

— Fanatyk 23
źródło

Napisane przez innych, czy przez nas samych?

Moim pierwotnym zamiarem było to, co się rozwijało, ale myślę, że nadaje ciekawy wymiar temu pytaniu. Edytowane oryginalne pytanie.

— Fanatic23,

Złożenie go nie oznacza, że jest wyrafinowane. Prostsze = zawsze lepsze.

— tp1

Najbardziej złożone były zawsze dostępne w STL. Złożoność zazwyczaj wynika z zagnieżdżonych struktur danych, a nie z ich typu. Prosta struktura = dobra, chyba że profiler narzeka.

— Koder

-1 dla niepotrzebnej oceny wartości. Mógłbym tak samo powiedzieć: w dzisiejszych czasach, jeśli sam wdrażasz struktury danych, jesteś głupi i uparty. Nie bądź kolejnym mądrym dzieciakiem, który myśli, że może niewłaściwie zaimplementować strukturę danych.

— Pieter B

7

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.

— aufather
źródło

7

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 :)

— 远声远 Shengyuan Lu
źródło

4

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.

— bit-twiddler
źródło

5

Radzę każdemu, kto oddał głos „w dół”, że należy dodać komentarz wyjaśniający, dlaczego oddano głos „w dół”. Mogę poradzić sobie z kimś, kto ma inne zdanie. Jednak nie mogę znieść tchórzostwa.

— bit-twiddler

2

@ bit-twiddler Nauczyłem się twierdzenia De Morgana na studiach filozoficznych. Teraz robię CS, nie zostało wspomniane. Szczerze mówiąc, widzę tego rodzaju rzeczy jako stenografię, która najlepiej wiąże się z doświadczeniem. Czy naprawdę musisz pamiętać zasady (i z nazwy!), Które stosujesz, kiedy rozkładasz równanie na inne? Nie wiem o tobie, ale wypracowuję to na podstawie tego, co przede mną, a nie na pamięć. To samo dotyczy modyfikacji wyrażeń logicznych.

— Rupert Madden-Abbott,

2

@Rupert: Twierdzenie De Morgana jest zwykle ujęte w dyskretnej matematyce i organizacji komputerowej (obie są wymagane na studiach licencjackich w USA). Jako licencjat skoncentrowałem się na architekturze komputerowej / oprogramowaniu systemowym. Twierdzenie De Morgana jest szeroko stosowane w cyfrowej logice. Istnieją obszary rozwoju oprogramowania na niskim poziomie, w których znajomość twierdzenia De Morgana staje się krytyczna. Na przykład istnieją minimalne komputery z zestawem instrukcji, które nie zawierają pełnego zestawu instrukcji boolowskich; dlatego trzeba umieć wyprowadzić jedną operację logiczną z innej.

— bit-twiddler,

1

(ciąg dalszy) Oto test, na którym większość ocen nieinformatycznych / inżynierii komputerowej / elektrotechniki (koncentracja inżynierii komputerowej) albo całkowicie zawodzi, albo bardzo długo zajmuje odpowiedź. Biorąc pod uwagę tylko operację NAND (ujemną), uzyskaj następujące operacje boolowskie: NOT, AND, OR, NOR, XOR i XNOR. Znajomość twierdzenia De Morgana znacznie ułatwia wyprowadzenie tych sześciu operacji logicznych. Twierdzenie De Morgana jest z pewnością najważniejszym twierdzeniem w cyfrowym projektowaniu logiki.

— bit-twiddler

1

..... choć uczciwie, w branży, w której DUŻO pracy zajmuje się pisaniem aplikacji RoR na wpół ocenianych dla małej firmy, prawdopodobnie jest około 1 raz na 1000000000, gdzie trzeba by było SŁUCHAĆ koncepcja bramek logicznych i algebry logicznej, zamiast po prostu znać znaczenie angielskich słów „lub” oraz „i”. nie mówiąc, że te rzeczy nie mają znaczenia, jeśli wykonujesz pracę z CS, skomplikowane algorytmy lub optymalizacje lub programowanie na niskim poziomie, ale dla większości osób pracujących jako programistów jest to rodzaj bezużytecznych drobiazgów.

— sara,

2

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.

— Peter Taylor
źródło

2

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.

— dbasnett
źródło

1

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.

w C ++ to jest std::listi naprawdę nie ma w tym nic skomplikowanego: / Uważam, że czerwono-czarne drzewo / drzewo AVL jest znacznie bardziej skomplikowane, z tymi wszystkimi warunkami przywracania równowagi!

— Matthieu M.

@Mathieu std :: map, a najprawdopodobniej otrzymasz drzewo rb.

— sierpnia

1

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

— Scant Roger
źródło

usuwa okulary „Drogi Boże”.

— Len Joseph

1

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.

— ProdigySim
źródło

1

Brzmi to jak przesada w rozwiązaniu Sudoku, ponieważ algorytm cofania brutalnej siły rozwiązuje zagadkę szybciej niż można wprowadzić dane.

— kevin cline

3

@kevin, tańczące linki to algorytm cofania brutalnej siły - ale z wiarygodną heurystyką.

— Peter Taylor

Potrzebujesz heurystyki, jeśli chcesz robić takie rzeczy, jak wyliczanie całkowitej liczby rozwiązań i twierdzenie, że Sudoku ma tylko 1 unikalne rozwiązanie.

— ProdigySim

1

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.

— TMN
źródło

0

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.

Moim zamiarem nie było narzucanie jakiejś egzotycznej struktury danych. Ale to smutna sytuacja, gdy potrzebujesz czegoś od razu i musisz poradzić sobie z tym, co jest już dostępne, tylko dlatego, że tak nakazuje polityka korporacyjna.

— Fanatic23,

0

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.

— Old Pro
źródło