¿Viabilidad de la lista vinculada frente a la matriz para datos ordenados frente a datos no clasificados?

Question

Comparar LinkedLists y Arrays al tiempo que compara sus diferencias con datos ordenados y no ordenados

• Agregando
• Eliminando
• Recuperando
• Clasificación
• Velocidad general
• Uso general de memoria

Preguntas reales

  

Discuta la viabilidad de implementar un conjunto de datos sin clasificar como una lista vinculada en lugar de una matriz. ¿Cuáles serían las compensaciones en términos de inserción, eliminación, recuperación, memoria de la computadora y velocidad de la aplicación?

     

Discuta la viabilidad de implementar un conjunto de datos ordenados como una lista vinculada en lugar de una matriz. ¿Cuáles serían las compensaciones en términos de inserción, eliminación, recuperación, memoria de la computadora y velocidad de la aplicación?

     

Con base en sus respuestas a las preguntas anteriores, resuma los costos y beneficios de usar listas vinculadas en una aplicación.

Mis respuestas / aportes:

  

LinkedLists tiene que asignar memoria cada vez que se agrega un nuevo nodo, útil cuando se agregan muchos nodos y el tamaño cambia constantemente, pero generalmente es más lento cuando se agregan pocos elementos

     

Las matrices asignaron memoria al comienzo de la ejecución del programa, redimensionando la lista lentamente (agregando muchos elementos lentos si es necesario cambiar el tamaño)

     

La recuperación es más rápida en la matriz debido a la indexación

     

Agregar / eliminar más rápido en LinkedList debido a punteros

Answer 1

En sin clasificar frente a ordenado. Haré uno, entonces realmente necesitas hacer tu tarea

El marcado de Stackoverflow realmente necesita tablas para hacer esto. Quiere decir qué tan caro es la operación es para la ordenada / ordenada, ordenada / ordenada, ordenada / lista enlazada, ordenada / lista enlazada

Un punto final: " velocidad de la aplicación " es una pista para considerar más que solo la velocidad de las operaciones individuales.

* Adding

Sin clasificar: la adición de matriz es O (1) a menos que sea necesario cambiar el tamaño; simplemente agréguela al final. Es posible que desee analizar una estrategia de cambio de tamaño que minimice los gastos generales (pista: no solo aumente el tamaño en uno)

Ordenado: la suma de matrices es O (n): encontrar el lugar para agregarlo es O (log (n)), pero debe mover la mitad de los elementos hacia arriba (en promedio) para crear romm para el nuevo

Sin clasificar: la lista vinculada es O (1): agréguela al inicio o al final de la lista.

Ordenado: la lista vinculada es O (n), aunque puede volver a agregar el elemento en O (1), debe escanear la mitad de la lista en promedio para encontrar el lugar donde colocarlo.

Entonces, a ti por el resto. Publique una respuesta y la criticaremos, pero para aprovechar al máximo su educación (presumiblemente) costosa, realmente necesita trabajar un poco en esto :)

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

Answer 2

No estoy seguro de para qué clase es, pero para un programa CS, tendrá que hacerlo mejor que "es lento" y "es rápido". Trate de cuantificar eso, en términos de número de operaciones necesarias. Debe estar familiarizado con una maquinaria que normalmente se utiliza para dicha cuantificación: use esa maquinaria.

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.

// Programa CPP para demostrar el procesamiento // hora de la matriz ordenada y no clasificada

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

// Salida del código

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

  

  
• Eliminando
  

Sin clasificar & amp; ordenado: la eliminación de la matriz es O (n): tiene que mover todo el elemento para llenar el 'agujero'

Sin clasificar & amp; ordenado: la lista vinculada es O (1) - Cambiar punteros según sea necesario