Machbarkeit von LinkedList vs. Array für vs. unsortierte Daten sortiert?

Question

Im Vergleich LinkedLists und Arrays, während auch ihre Differenzen mit sortierten und unsortierten Daten

Vergleich

• Hinzufügen
• Entfernen
• Suchen
• Sortieren
• Gesamtgeschwindigkeit
• Gesamtspeicherauslastung

Die tatsächlichen Fragen

  

Diskutieren Sie die Machbarkeit eines unsortierten Datensatzes als eine verknüpfte Liste Implementierung anstatt eines Arrays. Was wären die Vor- und Nachteile in Bezug auf die Insertion, Entfernung, Retrieval, Computerspeicher, und die Geschwindigkeit der Anwendung?

     

Diskutieren Sie die Machbarkeit eines sortierten Daten Implementierung als eine verknüpfte Liste gesetzt, anstatt ein Array. Was wären die Vor- und Nachteile in Bezug auf die Insertion, Entfernung, Retrieval, Computerspeicher, und die Geschwindigkeit der Anwendung?

     

Auf der Grundlage Ihrer Antworten auf die vorangegangenen Fragen, fassen die Kosten und Nutzen der in einer Anwendung verkettete Listen verwendet wird.

Meine Antworten / Eingang:

  

LinkedLists haben zuzuteilen Speicher jedes Mal ein neuer Knoten hinzugefügt wird, nützlich, wenn viele Knoten hinzufügen und Größe ständig ändert aber in der Regel langsamer, wenn das Hinzufügen einige Elemente

     

Arrays Speicher sich am Anfang des Programmablaufs zugeordnet, Ändern der Größe Liste langsam (das Hinzufügen viele Elemente langsam, wenn die Größe müssen)

     

Retrieval ist schneller in Array aufgrund Indizierung

     

Hinzufügen / Entfernen in LinkedList schneller durch Zeiger

Answer 1

Auf unsortiert vs. sortiert. Ich werde man tun, dann sind Sie wirklich Ihre Hausaufgaben brauchen zu tun

Stackoverflow Markup wirklich braucht, Tabellen, dies zu tun. Sie wollen sagen, wie „teuer“ der Betrieb für die unsortierte / Array, sortiert / array, unsortiert / verknüpften Liste, sortiert / verknüpften Liste

Ein letzter Punkt: „Geschwindigkeit der Anwendung“ ist ein Hinweis mehr zu berücksichtigen als nur die Geschwindigkeit der einzelnen Operationen.

* Adding

unsortiert: Array Zugabe ist O (1), sofern nicht benötigt resizing - fügen Sie es nur bis zum Ende. Vielleicht möchten Sie eine Redimensionierung Strategie diskutieren, die den Overhead (Tipp: Sie erhöhen nicht nur die Größe von einem) minimiert

Sortiert: Array Zugabe ist O (n) - das Hotel zu finden, um es hinzuzufügen ist O (log (n)), aber Sie müssen die Hälfte der Elemente bewegen (im Durchschnitt) romm für die neue machen

unsortiert. Verlinkte Liste ist O (1) - fügen Sie es zum Anfang oder Ende der Liste

Sortiert:. Verlinkte Liste ist O (n) - obwohl Sie wieder das Element in O hinzufügen können (1), müssen Sie im Durchschnitt die Hälfte der Liste scannen durch den Ort zu finden, sie setzen

Also, zurück zu dir für den Rest. eine Antwort veröffentlichen, und wir werden es Kritik, aber das Beste aus Ihrem (vermutlich) teuer educatiom zu bekommen, müssen Sie wirklich etwas Arbeit auf, dies zu tun:)

* Removing
* Retrieving
* Sorting
* Overall speed
* Overall memory usage

Answer 2

Nicht sicher, welche Klasse dieser für ist, aber für ein CS-Programm, werden Sie tun müssen, besser als „langsam“ und „schnell“. Versuchen Sie, das zu quantifizieren, in Bezug auf die Anzahl von-Operationen benötigte. Sie sollten in der Regel für eine solche Quantifizierung -use dieser Maschinen verwendet mit Maschinen vertraut sein.

Answer 3

Here is a C++ code that illustrates that sorting the data miraculously makes the code faster than the unsorted version. Let’s try out a sample C++ program to understand the problem statement better.

// CPP-Programm Verarbeitung demonstrieren // Zeit von sortierten und unsortierten Array

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

const int N = 100001;

int main()
{
    int arr[N];

    // Assign random values to array
    for (int i=0; i<N; i++)
        arr[i] = rand()%N;

    // for loop for unsorted array
    int count = 0;
    double start = clock();
    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    double end = clock();
    cout << "Time for unsorted array :: "
         << ((end - start)/CLOCKS_PER_SEC)
         << endl;
    sort(arr, arr+N);

    // for loop for sorted array
    count = 0;
    start = clock();

    for (int i=0; i<N; i++)
        if (arr[i] < N/2)
            count++;

    end = clock();
    cout << "Time for sorted array :: "
         << ((end - start)/CLOCKS_PER_SEC)
         << endl;

    return 0;
}

// Ausgabe des Codes

Output :

Execution 1:
Time for an unsorted array: 0.00108
Time for a sorted array: 0.00053

Execution 2:
Time for an unsorted array: 0.001101
Time for a sorted array: 0.000593

Execution 3:
Time for an unsorted array: 0.0011
Time for a sorted array: 0.000418
Observe that time taken for processing a sorted array is less as compared to an unsorted array. The reason for this optimization for a sorted array is branch prediction.

Answer 4

@ Paul: Danke

  

  
• Entfernen
  

Unsorted & sortiert: Array zu entfernen, ist O (n) - müssen alle Element bewegen sich über 'Loch'

füllen

Unsorted & sortiert: verlinkte Liste ist O (1) - Änderungszeiger nach Bedarf