Er wordt veel gepraat over datastructuren, maar ik kan geen eenvoudige lijst met datastructuren en hun praktische gebruik vinden. Ik probeer te studeren voor een interview en ik denk dat dit me zou helpen, samen met vele anderen. Ik zoek iets als dit:
Gegevensstructuur – Voorbeeld/gebruikt voor
Hash-tabel – snel gegevens opzoeken …geef dan een voorbeeld
Array – …
Binaire boom – …
Als er ergens een dergelijk hulpmiddel is, laat het me dan weten.
Bedankt!
EDIT: ik bedoel, wikipedia is goed en zo, maar op de meeste pagina’s worden niet echt praktische toepassingen vermeld. Ik ben op zoek naar meer dan dat.
Antwoord 1, autoriteit 100%
Gevonden in een vergelijkbare vraag, eerder op StackOverflow:
Hash-tabel – gebruikt voor snel opzoeken van gegevens – symbooltabel voor compilers,
database-indexering, caches, unieke gegevensweergave.Trie – woordenboek, zoals gevonden op een mobiele telefoon voor
automatische aanvulling en spellingcontrole.Suffixstructuur – snelle zoekopdrachten in volledige tekst die in de meeste tekstverwerkers worden gebruikt.
Stack – bewerking ongedaan maken\opnieuw in tekstverwerkers, evaluatie van expressies
en syntaxis-parsing, veel virtuele machines zoals JVM zijn stapelgericht.Wachtrijen – Transport- en operationeel onderzoek waar verschillende entiteiten zijn
opgeslagen en vastgehouden om later te worden verwerkt, dwz de wachtrij voert de
functie van een buffer.Prioriteitswachtrijen – procesplanning in de kernel
Bomen – Parsers, bestandssysteem
Radix-boom – IP-routeringstabel
BSP-boom – 3D computergraphics
Grafieken – Verbindingen/relaties op sociale netwerksites, Routing
,communicatienetwerken, gegevensorganisatie enz.Heap – Dynamische geheugentoewijzing in lisp
Dit is het antwoord dat oorspronkelijk is gepost door RV Pradeep
Enkele andere, minder nuttige links:
Toepassingen worden alleen vermeld voor sommige gegevensstructuren
Niet toepassingsgericht, door goede samenvatting en relevant
Antwoord 2, autoriteit 15%
Ik zit in hetzelfde schuitje als jij. Ik moet studeren voor technische interviews, maar het onthouden van een lijst is niet echt nuttig. Als je 3-4 uur over hebt en een diepere duik wilt maken, raad ik je aan om een kijkje te nemen
mijncodeschool
Ik heb Coursera en andere bronnen bekeken, zoals blogs en studieboeken,
maar ik vind ze ofwel niet uitgebreid genoeg of aan de andere kant van het spectrum, te dicht op de vereiste computerwetenschappelijke terminologieën.
De gast in de video heeft een aantal lezingen over datastructuren. Let niet op de dwaze tekeningen, of het lichte accent. U moet niet alleen begrijpen welke datastructuur u moet selecteren, maar ook enkele andere punten waarmee u rekening moet houden wanneer mensen nadenken over datastructuren:
- voor- en nadelen van de gemeenschappelijke datastructuren
- waarom elke datastructuur bestaat
- hoe het in het geheugen werkt
- specifieke vragen/oefeningen en beslissen welke structuur te gebruiken voor maximale efficiëntie
- lucide Big 0 uitleg
Ik heb ook opmerkingen op github geplaatst als je geïnteresseerd bent.
Antwoord 3, autoriteit 8%
Volgens mijn begrip zijn datastructuur alle gegevens die zich in het geheugen van elk elektronisch systeem bevinden en die efficiënt kunnen worden beheerd. Vaak is het een spel van geheugen of snellere toegankelijkheid van gegevens. Wat het geheugen betreft, worden er compromissen gesloten met het beheer van gegevens op basis van de kosten voor het bedrijf van dat eindproduct. Efficiënt beheerd vertelt ons hoe de gegevens het beste kunnen worden ontsloten op basis van de primaire behoefte van het eindproduct. Dit is een verklaring op zeer hoog niveau, maar datastructuren zijn een enorm onderwerp. De meeste interviewers duiken in datastructuren die ze zich kunnen veroorloven om in de interviews te bespreken, afhankelijk van de tijd die ze hebben, namelijk gekoppelde lijsten en gerelateerde onderwerpen.
Deze gegevenstypen kunnen nu worden onderverdeeld in primitief, abstract en samengesteld, op basis van de manier waarop ze logisch zijn geconstrueerd en toegankelijk zijn.
- primitieve datastructurenzijn basisbouwstenen voor alle datastructuren, ze hebben er een continu geheugen voor: boolean, char, int, float, double, string.
- samengestelde gegevensstructurenzijn gegevensstructuren die zijn samengesteld uit meer dan één primitieve gegevenstypes.class, structure, union, array/record.
- abstracte datatypeszijn samengestelde datatypes die een manier hebben om ze efficiënt te benaderen, wat een algoritme wordt genoemd. Afhankelijk van de manier waarop de data wordt benaderd, worden datastructuren onderverdeeld in lineaire en niet-lineaire datatypes. Gelinkte lijsten, stapels, wachtrijen, enz. zijn lineaire gegevenstypen. heaps, binaire bomen en hash-tabellen enz. zijn niet-lineaire gegevenstypen.
Ik hoop dat dit je helpt om erin te duiken.
Antwoord 4, autoriteit 6%
Het uitstekende boek “Algorithm Design Manual”van Skienna bevat een enorme opslagplaats van algoritmen en gegevensstructuur.
Voor tal van problemen worden datastructuren en algoritmen beschreven, vergeleken en wordt het praktische gebruik besproken. De auteur geeft ook verwijzingen naar implementaties en de originele onderzoekspapers.
Het is geweldig om het boek op je bureau te hebben als je zoekt naar de beste gegevensstructuur om je probleem op te lossen. Het is ook erg handig voor de voorbereiding van een sollicitatiegesprek.
Een andere geweldige bron is de NIST Dictionary of Data Structures and Algoritmes.
Antwoord 5, autoriteit 4%
Nog enkele praktische toepassingen van datastructuren
Rood-zwarte bomen (gebruikt bij frequent invoegen/verwijderen)
en weinig zoekopdrachten) – K-mean Clustering met behulp van roodzwarte boom, databases, eenvoudige database, zoeken naar woorden in woordenboeken, zoeken op internet
AVL Trees (meer zoeken en minder invoegen/verwijderen) – Data-analyse en datamining en de toepassingen die meer zoekopdrachten met zich meebrengen
Min Heap – Clusteralgoritmen
Antwoord 6, autoriteit 3%
Elke rangschikking van verschillende datastructuren zal op zijn minst gedeeltelijk gebonden zijn aan de probleemcontext. Het zou helpen om te leren hoe tijd- en ruimteprestaties van algoritmen kunnen worden geanalyseerd. Meestal wordt “grote O-notatie” gebruikt, b.v. binair zoeken is in O(log n) tijd, wat betekent dat de tijd om naar een element te zoeken de log (in grondtal 2, impliciet) is van het aantal elementen. Intuïtief, aangezien elke stap de helft van de resterende gegevens weggooit als irrelevant, zal een verdubbeling van het aantal elementen de tijd met 1 stap verlengen. (Binair zoeken schalen redelijk goed.) Ruimteprestaties hebben betrekking op hoe de hoeveelheid geheugen groeit voor grotere datasets. Merk ook op dat de big-O-notatie constante factoren negeert – voor kleinere datasets kan een O(n^2)-algoritme nog steeds sneller zijn dan een O(n * log n)-algoritme met een hogere constante factor. Complexe algoritmen hebben vaak meer werk te doen bij het opstarten.
Naast tijd en ruimte, omvatten andere kenmerken of een gegevensstructuur is gesorteerd (bomen en skiplists worden gesorteerd, hashtabellen niet), persistentie (binaire bomen kunnen pointers uit oudere versies hergebruiken, terwijl hashtabellen ter plaatse worden gewijzigd), enz.
Hoewel je het gedrag van verschillende datastructuren moet leren om ze te kunnen vergelijken, is een manier om een idee te krijgen waarom ze qua prestaties verschillen, door er een paar nauwkeurig te bestuderen. Ik stel voor om enkelvoudig gekoppelde lijsten, binaire zoekbomen en lijsten overslaan, die allemaal relatief eenvoudig zijn, maar heel verschillende kenmerken hebben. Bedenk hoeveel werk het kost om een waarde te vinden, een nieuwe waarde toe te voegen, alle waarden op volgorde te vinden, enz.
Er zijn verschillende teksten over het analyseren van algoritmen/gegevensstructuurprestaties die mensen aanbevelen, maar wat ze echt logisch voor mij maakte, was het leren van OCaml. Omgaan met complexe datastructuren is het sterke punt van ML, en hun gedrag is veel duidelijker wanneer je pointers en geheugenbeheer kunt vermijden zoals in C. (OCaml leren alleen om datastructuren te begrijpen is echter vrijwel zeker de lange weg. 🙂 )