Fattibilità di LinkedList vs. Array per dati ordinati o non ordinati?
-
07-07-2019 - |
Domanda
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
Soluzione
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
Altri suggerimenti
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.
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.
@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