Invoering

Algoritmen en datastructuren zijn de fundamentele elementen die ook het softwareontwikkelingsproces in programmeren efficiënt kunnen ondersteunen. Python, een eenvoudig te coderen taal, heeft veel functies zoals een lijst, woordenboek en set, die ingebouwde datastructuren zijn voor de Python-taal. De wizards worden echter ontketend door de algoritmen in deze structuren toe te passen. Algoritmen zijn instructies of een set regels of een wiskundig proces en bewerkingen waarmee men tot een oplossing komt. Wanneer ze samen worden gebruikt, kunnen ze een onbewerkt script omzetten in een zeer geoptimaliseerde toepassing, afhankelijk van de datastructuren waarover de programmeur beschikt. Dit artikel bekijkt de top 7 algoritmen voor datastructuren in Python.

Waarom zijn algoritmen belangrijk voor datastructuren in Python?

• Geoptimaliseerde prestaties: Mensen creëren algoritmen voor entiteiten die van plan zijn deze werken onder ideale omstandigheden uit te voeren. Het gebruik van de juiste datastructuren helpt tijd en ruimte te minimaliseren, waardoor programma’s efficiënter worden uitgevoerd. Dus, als het wordt gebruikt met een datastructuur zoals de binaire zoekboom, minimaliseert het juiste zoekalgoritme de tijd die wordt besteed aan zoeken aanzienlijk.
• Omgaan met grote hoeveelheden data: Gegevens op grote schaal moeten in de kortst mogelijke tijd worden verwerkt. Daarom vereist informatie efficiënte algoritmen. Als er geen goede algoritmen worden gebruikt, zullen verschillende bewerkingen met gegevensstructuren tijdrovend zijn en veel bronnen verbruiken of zelfs beperkingen voor de prestaties vormen.
• Gegevensorganisatie: Technieken helpen bij het beheren van gegevens in de datastructuren van computersystemen. Sorteeralgoritmen zoals Quicksort en Mergesort gebruiken bijvoorbeeld elementen in array-vorm of gekoppelde lijsten om zoeken en verwerken eenvoudiger te maken.
• Geoptimaliseerde opslag: Het kan ook weten hoe data zo efficiënt mogelijk in een structuur opgeslagen kan worden, waarbij zo min mogelijk geheugen gebruikt wordt. Hash-functies in hashing-algoritmen zorgen er bijvoorbeeld voor dat verschillende datasets waarschijnlijk worden toegewezen aan andere locaties in een hash-tabel. Zo wordt de tijd die nodig is om naar dergelijke data te zoeken, verkort.
• Bibliotheekoptimalisatie:De meeste Python-bibliotheken zoals NumPy, Pandas en TensorFlow zijn afhankelijk van structurele algoritmen om de gegevensstructuur te analyseren. Kennis van deze algoritmen stelt ontwikkelaars in staat om deze bibliotheken optimaal te benutten en deel te nemen aan het evolutieproces van dergelijke bibliotheken.

Top 7 algoritmen voor datastructuren in Python

Laten we nu eens kijken naar de top 7 algoritmen voor datastructuren in Python.

1. Binaire zoekopdracht

Sorteren organiseert records in een bepaalde volgorde, waardoor ze snel en zo snel mogelijk toegankelijk zijn. Binair zoekalgoritme zoekt naar een item in een gesorteerd bestand met items. Het werkt volgens het concept van het steeds opnieuw halveren van het zoekinterval. Als de waarde van de zoeksleutel namelijk kleiner is dan het item in het midden van het interval, moet het interval worden verkleind tot de onderste helft. Anders verkleint het tot de bovenste helft. Bovendien kan elke vorm worden uitgedrukt als het verschil tussen twee vormen, die elk niet complexer zijn dan het origineel.

Algoritme stappen

Variabelen initialiseren:

• Set left naar 0 (de beginindex van de array).
• Set right naar n - 1 (de eindindex van de array, waarbij n is de lengte van de array).

Herhaal totdat left is groter dan right:

• Bereken de mid index als de vloerwaarde van (left + right) / 2.

Controleer het middelste element:

• Als arr(mid) is gelijk aan de streefwaarde:
  • Geef de index terug mid (doel is gevonden).
• Als arr(mid) is kleiner dan de streefwaarde:
  • Set left naar mid + 1 (negeer de linkerhelft).
• Als arr(mid) is groter dan de streefwaarde:
  • Set right naar mid - 1 (negeer de rechterhelft).

Als de lus eindigt zonder dat het doel is gevonden:

• Opbrengst -1 (doel is niet aanwezig in de array).

Code-implementatie

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left 

Lineair zoeken vormt de basis van binair zoeken, omdat het de tijdcomplexiteit veel efficiënter maakt door het te configureren als een functie van log n. Wordt meestal gebruikt in gevallen waarin de zoekfunctie in applicaties moet worden ingeschakeld, bijvoorbeeld bij het indexeren van databases.

2. Samenvoegen Sorteren

Merge Sort is een verdeel-en-heersalgoritme dat een ongesorteerde lijst krijgt. Het maakt n sublijsten, elk met één element. De sublijsten worden gevraagd om te worden samengevoegd om andere gesorteerde sublijsten te ontwikkelen totdat ze één enkele sublijst krijgen. Het is stabiel en de algoritmen in deze categorie werken binnen de tijdcomplexiteit van O(n log n). Merge Sort is over het algemeen geschikt voor grote werkvolumes en wordt gebruikt wanneer een stabiele sortering vereist is. Het sorteert gekoppelde lijsten effectief en splitst uitgebreide gegevens die niet in het geheugen passen op in kleinere componenten.

Algoritme stappen

Verdeling:

• Als de array meer dan één element bevat, verdeelt u de array in twee helften:
  • Vind het middelpunt mid om de array in twee helften te verdelen: left = arr(:mid) En right = arr(mid:).

Veroveren:

• Pas recursief samenvoegsortering toe op beide helften:
  • Sorteer de left half.
  • Sorteer de right half.

Samenvoegen:

• Voeg de twee gesorteerde helften samen tot één gesorteerde array:
  • Vergelijk de elementen van left En right één voor één en plaats het kleinste element in de oorspronkelijke matrix.
  • Ga door totdat alle elementen uit beide helften weer in de oorspronkelijke matrix zijn samengevoegd.

Basisgeval:

• Als de array slechts één element bevat, is deze al gesorteerd en wordt deze onmiddellijk geretourneerd.

Code-implementatie

def merge_sort(arr):
    if len(arr) > 1:
        # Find the middle point
        mid = len(arr) // 2
        
        # Divide the array elements into 2 halves
        left_half = arr(:mid)
        right_half = arr(mid:)
        
        # Recursively sort the first half
        merge_sort(left_half)
        
        # Recursively sort the second half
        merge_sort(right_half)
        
        # Initialize pointers for left_half, right_half and merged array
        i = j = k = 0
        
        # Merge the sorted halves
        while i 

3. Snel sorteren

Snel sorteren is een efficiënte sorteertechniek die gebruikmaakt van de verdeel-en-heerstechniek. Deze methode sorteert door een pivot uit de array te selecteren en de andere elementen in twee arrays te verdelen: één voor elementen kleiner dan de pivot en een andere voor elementen groter dan de pivot. Quick Sort presteert echter beter dan Merge Sort en Heap Sort in de echte wereld en wordt uitgevoerd in een gemiddeld geval van O(n log n). Als we deze kenmerken analyseren, kunnen we concluderen dat het populair is in verschillende bibliotheken en frameworks. Wordt vaak toegepast in commerciële computing, waarbij grote matrices moeten worden gemanipuleerd en gesorteerd.

Algoritme stappen

Kies een draaipunt:

• Selecteer een pivot-element uit de array. Dit kan het eerste element, het laatste element, het middelste element of een willekeurig element zijn.

Partitioneren:

• Herschik de elementen in de array zodat alle elementen kleiner dan de pivot aan de linkerkant staan ​​en alle elementen groter dan de pivot aan de rechterkant. Het pivot-element wordt op de juiste positie in de gesorteerde array geplaatst.

Snel sorteren recursief toepassen:

• Pas de bovenstaande stappen recursief toe op de linker- en rechtersubarrays.

Basisgeval:

• Als de array slechts één element bevat of leeg is, is deze al gesorteerd en eindigt de recursie.

Code-implementatie

def quick_sort(arr):
    # Base case: if the array is empty or has one element, it's already sorted
    if len(arr)  pivot)
    
    # Recursively apply quick_sort to the left and right sub-arrays
    return quick_sort(left) + (pivot) + quick_sort(right)

# Example usage:
arr = (10, 7, 8, 9, 1, 5)
sorted_arr = quick_sort(arr)
print(f"Sorted array: {sorted_arr}")

4. Dijkstra’s algoritme

Dijkstra’s algoritme helpt de kortste paden tussen punten of knooppunten in het netwerk te verkrijgen. Het idee is om continu het knooppunt met de kleinste voorlopige afstand te kiezen en de verbindingen te versoepelen totdat het bestemmingsknooppunt is gekozen. Dit algoritme voor datastructuren in Python wordt veel gebruikt in computernetwerken, met name in computer mapping systemen die padberekeningen vereisen. Het wordt ook gebruikt in GPS-systemen, routingprotocollen in computernetwerken en als algoritme voor karakter- of objectbeweging in videogames.

Algoritme stappen

Initialiseren:

• Stel de afstand tot het bronknooppunt in op 0 en tot alle andere knooppunten op oneindig (∞).
• Markeer alle knooppunten als onbezocht.
• Stel het bronknooppunt in als het huidige knooppunt.
• Gebruik een prioriteitswachtrij (min-heap) om knooppunten op te slaan, samen met hun voorlopige afstanden.

Ontdek buren:

• Controleer voor het huidige knooppunt alle niet-bezochte buren.
• Bereken voor elke buur de voorlopige afstand tot het bronknooppunt.
• Als de berekende afstand kleiner is dan de bekende afstand, moet u de afstand bijwerken.
• Voeg de buur met de bijgewerkte afstand toe aan de prioriteitswachtrij.

Selecteer het volgende knooppunt:

• Markeer het huidige knooppunt als bezocht (een bezocht knooppunt wordt niet opnieuw gecontroleerd).
• Selecteer het nog niet bezochte knooppunt met de kortste voorlopige afstand als het nieuwe huidige knooppunt.

Herhalen:

• Herhaal stap 2 en 3 totdat alle knooppunten zijn bezocht of de prioriteitswachtrij leeg is.

Uitvoer:

• Het algoritme geeft de kortste afstand van het bronknooppunt naar elk knooppunt in de grafiek weer.

Code-implementatie

import heapq

def dijkstra(graph, start):
    # Initialize distances and priority queue
    distances = {node: float('infinity') for node in graph}
    distances(start) = 0
    priority_queue = ((0, start))  # (distance, node)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # If the popped node's distance is greater than the known shortest distance, skip it
        if current_distance > distances(current_node):
            continue

        # Explore neighbors
        for neighbor, weight in graph(current_node).items():
            distance = current_distance + weight

            # If found a shorter path to the neighbor, update it
            if distance 

5. Breedte-eerst zoeken (BFS)

beste vrienden is een techniek om boom- of grafiekdatastructuren te doorkruisen of te doorzoeken. Dit grafiekalgoritme gebruikt een boomzoekstrategie; het begint met een knooppunt of rootknooppunt en vertakt zich naar alle randknooppunten en vervolgens naar alle knooppunten op het volgende niveau. Dit algoritme voor datastructuren in Python wordt gebruikt voor korte afstanden in ongewogen grafieken. Doorkruisingen zijn gebruikt in levelvolgorde voor elk knooppunt. Het wordt gevonden in peer-to-peernetwerken en zoekmachines, en vindt verbonden componenten in een grafiek.

Algoritme stappen

Initialiseren:

• Maak een lege wachtrij q.
• Zet het startknooppunt in de wachtrij s naar binnen q.
• Markeer het startknooppunt s zoals bezocht.

Herhaal dit totdat de wachtrij leeg is:

• Een knooppunt uit de wachtrij halen v van q.
• Voor elke onbezochte buur n van v:
  • Markering n zoals bezocht.
  • In de wachtrij plaatsen n naar binnen q.

Herhaal stap 2 totdat de wachtrij leeg is.

Beëindig het proces zodra alle knooppunten op alle niveaus zijn bezocht.

Code-implementatie

from collections import deque

def bfs(graph, start):
    # Create a queue for BFS
    queue = deque((start))
    
    # Set to store visited nodes
    visited = set()
    
    # Mark the start node as visited
    visited.add(start)
    
    # Traverse the graph
    while queue:
        # Dequeue a vertex from the queue
        node = queue.popleft()
        print(node, end=" ")
        
        # Get all adjacent vertices of the dequeued node
        # If an adjacent vertex hasn't been visited, mark it as visited and enqueue it
        for neighbor in graph(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Example usage:
graph = {
    'A': ('B', 'C'),
    'B': ('D', 'E'),
    'C': ('F', 'G'),
    'D': (),
    'E': (),
    'F': (),
    'G': ()
}

bfs(graph, 'A')

6. Diepte-eerst zoeken (DFS)

DFS is het andere algoritme voor het navigeren of mogelijk zoeken in boom- of grafiekdatastructuren. Dit begint bij de root (of een willekeurige node) en doorloopt zo ver mogelijk een tak voordat het weer omhoog gaat. DFS wordt op veel gebieden toegepast voor sorteren, cyclusdetectie en het oplossen van puzzels zoals doolhoven. Het is populair in veel AI-toepassingen, zoals in games voor het vinden van het pad, het oplossen van puzzels en compilers voor het parsen van boomstructuren.

Algoritme stappen

Initialisatie:

• Maak een stapel (of gebruik recursie) om bij te houden welke knooppunten bezocht moeten worden.
• Markeer alle knooppunten als onbezocht (of initialiseer een visited set).

Begin bij het bronknooppunt:

• Duw het bronknooppunt naar de stack en markeer het als bezocht.

Verwerk knooppunten totdat de stapel leeg is:

• Een knooppunt uit de stapel halen (huidig ​​knooppunt).
• Verwerk het huidige knooppunt (bijvoorbeeld afdrukken, opslaan, enz.).
• Voor elke niet-bezochte buur van het huidige knooppunt:
  • Markeer de buur als bezocht.
  • Duw de buurman op de stapel.

Herhaal dit totdat de stapel leeg is.

Code-implementatie

def dfs_iterative(graph, start):
    visited = set()  # To keep track of visited nodes
    stack = (start)  # Initialize the stack with the start node

    while stack:
        # Pop the last element from the stack
        node = stack.pop()

        if node not in visited:
            print(node)  # Process the node (e.g., print it)
            visited.add(node)  # Mark the node as visited

            # Add unvisited neighbors to the stack
            for neighbor in graph(node):
                if neighbor not in visited:
                    stack.append(neighbor)

# Example usage:
graph = {
    'A': ('B', 'C'),
    'B': ('D', 'E'),
    'C': ('F'),
    'D': (),
    'E': ('F'),
    'F': ()
}

dfs_iterative(graph, 'A')

7. Hashen

Het geven van een specifieke naam/identiek aan een bepaald object uit een groep vergelijkbare objecten staat bekend als hashing. Twee worden geïmplementeerd met behulp van een hashfunctie die de invoer (bekend als ‘key’) in kaart brengt in een vaste reeks bytes. Hashing maakt efficiënte toegang tot gegevens mogelijk, wat essentieel is wanneer gegevens snel moeten worden benaderd. Databases gebruiken hashing vaak voor indexering, caches en gegevensstructuren zoals hashtabellen voor snelle zoekopdrachten.

Algoritme stappen

Invoer: Een gegevensitem (bijv. een tekenreeks, getal).Kies een hashfunctie: Selecteer een hashfunctie die invoergegevens koppelt aan een hashwaarde (vaak een geheel getal).Bereken hashwaarde:

• Pas de hashfunctie toe op de invoergegevens om de hashwaarde te verkrijgen.

Invoegen of opzoeken:

• Plaatsing: Sla de gegevens op in een hashtabel en gebruik de hashwaarde als index.
• Zoeken: Gebruik de hashwaarde om snel de gegevens in de hashtabel te vinden.

Omgaan met botsingen:

• Als twee verschillende invoeren dezelfde hashwaarde opleveren, gebruikt u een methode voor het oplossen van conflicten, zoals chaining (meerdere items opslaan op dezelfde index) of open addressing (een andere open sleuf vinden).

Code-implementatie

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = (() for _ in range(size))
    
    def hash_function(self, key):
        # A simple hash function
        return hash(key) % self.size
    
    def insert(self, key, value):
        hash_key = self.hash_function(key)
        key_exists = False
        bucket = self.table(hash_key)
        
        for i, kv in enumerate(bucket):
            k, v = kv
            if key == k:
                key_exists = True
                break
        
        if key_exists:
            bucket(i) = (key, value)  # Update the existing key
        else:
            bucket.append((key, value))  # Insert the new key-value pair
    
    def get(self, key):
        hash_key = self.hash_function(key)
        bucket = self.table(hash_key)
        
        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found
    
    def delete(self, key):
        hash_key = self.hash_function(key)
        bucket = self.table(hash_key)
        
        for i, kv in enumerate(bucket):
            k, v = kv
            if k == key:
                del bucket(i)
                return True
        return False  # Key not found

# Example usage:
hash_table = HashTable(size=10)

# Insert data into the hash table
hash_table.insert("apple", 10)
hash_table.insert("banana", 20)
hash_table.insert("orange", 30)

# Retrieve data from the hash table
print(hash_table.get("apple"))   # Output: 10
print(hash_table.get("banana"))  # Output: 20

# Delete data from the hash table
hash_table.delete("apple")
print(hash_table.get("apple"))   # Output: None

Lees ook: Manieren om hashing in een datastructuur te berekenen

Conclusie

Het beheersen van algoritmen in combinatie met datastructuren is essentieel voor elke Python-ontwikkelaar die efficiënte en schaalbare code wil schrijven. Deze algoritmen zijn fundamentele tools die dataverwerking optimaliseren, prestaties verbeteren en complexe problemen in verschillende applicaties oplossen. Door deze algoritmen te begrijpen en te implementeren, kunnen ontwikkelaars het volledige potentieel van Python’s datastructuren ontsluiten, wat leidt tot effectievere en robuustere softwareoplossingen.

Lees ook: Complete gids over sorteertechnieken in Python (editie 2024)