Faisabilité de la liste chaînée ou du tableau pour les données triées ou non?

StackOverflow https://stackoverflow.com/questions/276278

  •  07-07-2019
  •  | 
  •  

Question

Comparer les LinkedLists et les tableaux tout en comparant leurs différences avec des données triées et non triées

  • Ajout
  • Supprimer
  • Récupération
  • Tri
  • Vitesse globale
  • Utilisation globale de la mémoire

Questions actuelles

  

Discutez de la faisabilité d'implémenter un ensemble de données non trié sous forme de liste chaînée plutôt que de tableau. Quels seraient les compromis en termes d’insertion, de suppression, de récupération, de mémoire informatique et de rapidité de l’application?

     

Discutez de la faisabilité d'implémenter un jeu de données trié sous forme de liste chaînée plutôt que de tableau. Quels seraient les compromis en termes d'insertion, de suppression, de récupération, de mémoire informatique et de rapidité de l'application?

     

Sur la base de vos réponses aux questions précédentes, récapitulez les coûts et les avantages de l’utilisation de listes chaînées dans une application.

Mes réponses / entrée:

  

Les LinkedLists doivent allouer de la mémoire chaque fois qu'un nouveau nœud est ajouté, ce qui est utile lorsque vous ajoutez de nombreux nœuds et que la taille change constamment, mais généralement plus lentement lorsque vous ajoutez quelques éléments

     

Les tableaux alloués en mémoire au début du programme, liste de redimensionnement lente (ajout de nombreux éléments lents s’il faut redimensionner)

     

La récupération est plus rapide dans un tableau en raison de l'indexation

     

Ajout / suppression plus rapide dans LinkedList en raison des pointeurs

Était-ce utile?

La solution

Sur non trié ou trié. Je vais en faire un, alors vous devez vraiment faire vos devoirs

Le balisage Stackoverflow a vraiment besoin de tables pour faire celle-ci. Vous voulez dire à quel point "cher" l'opération concerne les éléments non triés / tableau, triés / tableau, non triés / liste-liée, triés / liste-liée

Un dernier point: "Vitesse de l'application" est un indice à considérer plus que la vitesse des opérations individuelles. 

* Adding

Non trié: L'ajout de tableau est O (1) sauf si le redimensionnement est nécessaire - ajoutez-le simplement à la fin. Vous voudrez peut-être discuter d’une stratégie de redimensionnement qui minimise les frais généraux (indice: ne vous contentez pas d’augmenter la taille d’une unité)

Sorted: L'addition de tableau est O (n) - trouver l'endroit où l'ajouter est O (log (n)), mais vous devez déplacer la moitié des éléments vers le haut (en moyenne) pour créer le nom commun du nouveau

Non trié: la liste liée est O (1) - ajoutez-la au début ou à la fin de la liste.

Trié: la liste chaînée est O (n) - bien que vous puissiez à nouveau ajouter l'élément dans O (1), vous devez parcourir la moitié de la liste en moyenne pour trouver l'emplacement où le placer.

Alors, à vous pour le reste. Postez une réponse et nous la critiquerons, mais pour tirer le meilleur parti de votre (probablement) coûteuse éducation, vous devez vraiment travailler un peu là-dessus:) 

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

Autres conseils

Vous n'êtes pas sûr de la classe à laquelle cela s'adresse, mais pour un programme CS, vous devrez faire mieux que "is slow". et "est rapide". Essayez de quantifier cela, en termes de nombre d'opérations nécessaires. Vous devez être familiarisé avec une machine généralement utilisée pour une telle quantification, utilisez cette machine. 

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.

// programme CPP pour démontrer le traitement // heure du tableau trié et non trié 

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

// Sortie du code 

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

  
      
  • Supprimer
    •   

Non trié & amp; trié: la suppression de matrice est O (n) - il faut déplacer tous les éléments pour remplir le "trou"

Non trié & amp; trié: la liste chaînée est O (1) - Change les pointeurs au besoin

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top