Fattibilità di LinkedList vs. Array per dati ordinati o non ordinati?

Question

Confronto di liste collegate e matrici confrontando anche le loro differenze con dati ordinati e non ordinati

• Aggiunta
• La rimozione
• Recupero
• Ordinamento
• Velocità complessiva
• Utilizzo complessivo della memoria

Domande reali

  

Discutere la fattibilità dell'implementazione di un set di dati non ordinati come elenco collegato anziché come matrice. Quali sarebbero i compromessi in termini di inserimento, rimozione, recupero, memoria del computer e velocità dell'applicazione?

     

Discutere la fattibilità dell'implementazione di un set di dati ordinati come un elenco collegato anziché come un array. Quali sarebbero i compromessi in termini di inserimento, rimozione, recupero, memoria del computer e velocità dell'applicazione?

     

In base alle risposte alle domande precedenti, riepilogare i costi e i vantaggi dell'utilizzo degli elenchi collegati in un'applicazione.

Le mie risposte / input:

  

Le liste collegate devono allocare memoria ogni volta che viene aggiunto un nuovo nodo, utile quando si aggiungono molti nodi e le dimensioni continuano a cambiare ma generalmente più lente quando si aggiungono pochi elementi

     

Matrici di memoria allocata all'inizio del programma in esecuzione, ridimensionamento dell'elenco lento (aggiunta di molti elementi lenti se è necessario ridimensionare)

     

Il recupero è più veloce nell'array grazie all'indicizzazione

     

Aggiunta / rimozione più rapida in LinkedList a causa di puntatori

Answer 1

Su non ordinate vs. ordinate. Ne farò una, quindi dovrai davvero fare i compiti

Il markup StackOverflow ha davvero bisogno di tabelle per fare questo. Vuoi dire come " costoso " l'operazione è per la lista non ordinata / matrice, ordinata / matrice, lista non ordinata / collegata, lista ordinata / collegata

Un ultimo punto: "velocità dell'applicazione" è un suggerimento da considerare oltre alla velocità delle singole operazioni.

* Adding

Unsorted: l'aggiunta di array è O (1) a meno che non sia necessario il ridimensionamento, basta aggiungerlo alla fine. Potresti voler discutere di una strategia di ridimensionamento che riduca al minimo il sovraccarico (suggerimento: non solo aumentare le dimensioni di uno)

Ordinati: l'aggiunta di array è O (n) - trovare il posto dove aggiungerlo è O (log (n)), ma è necessario spostare la metà degli elementi verso l'alto (in media) per creare un nuovo comando

Unsorted: l'elenco collegato è O (1) - aggiungilo all'inizio o alla fine dell'elenco.

Ordinati: l'elenco collegato è O (n) - sebbene sia possibile aggiungere nuovamente l'elemento in O (1), è necessario eseguire la scansione di metà dell'elenco in media per trovare il posto dove inserirlo.

Quindi, spetta a te per il resto. Pubblica una risposta e la criticheremo, ma per ottenere il massimo dalla tua educazione (presumibilmente) costosa, devi davvero lavorare su questo :)

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

Answer 2

Non sei sicuro di quale classe sia, ma per un programma CS, dovrai fare di meglio che "quotare è lento" e "è veloce". Cerca di quantificare ciò, in termini di numero di operazioni necessarie. Dovresti avere familiarità con un macchinario tipicamente utilizzato per tale quantificazione - usa quel macchinario.

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.

// Programma CPP per dimostrare l'elaborazione // ora dell'array ordinato e non ordinato

#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;
}

// Output del codice

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

  

  
• La rimozione
  

Non ordinato & amp; ordinato: la rimozione dell'array è O (n) - è necessario spostare tutto l'elemento per riempire 'buco'

Non ordinato & amp; ordinato: l'elenco collegato è O (1) - Modificare i puntatori in base alle esigenze