Viabilidade de LinkedList vs. Array para classificadas vs. dados não ordenado?

Question

Comparando Linked e matrizes ao mesmo tempo, comparando as suas diferenças com dados ordenados e não ordenados

• Adicionar
• Remover
• Recuperação
• Sorting
• A velocidade geral
• uso geral da memória

perguntas reais

Discutir a viabilidade da implementação de um conjunto de dados não ordenada como uma lista ligada em vez de uma matriz. Quais seriam as vantagens e desvantagens ser em termos de inserção, remoção, recuperação, memória do computador, ea velocidade da aplicação?

Discutir a possibilidade de implementar um conjunto de dados classificados como uma lista ligada em vez de uma matriz. Quais seriam as vantagens e desvantagens ser em termos de inserção, remoção, recuperação, memória do computador, ea velocidade da aplicação?

Com base em suas respostas às perguntas anteriores, resumem os custos e benefícios do uso de listas ligadas em um aplicativo.

As minhas respostas / entrada:

Linked tem que alocar toda a memória de um novo nó é adicionado, útil ao adicionar muitos nós e tamanho continua a mudar, mas geralmente mais lento ao adicionar alguns elementos

Arrays memória alocada no início da execução do programa, lista de redimensionamento lenta (adicionando muitos elementos lento se tem que redimensionar)

A recuperação é mais rápida em ordem devido à indexação

Adicionar / remover mais rapidamente no LinkedList devido a ponteiros

Answer 1

Em vs. indiferenciados ordenados. Eu vou fazer um, então você realmente precisa fazer sua lição de casa

Stackoverflow marcação realmente precisa de tabelas para fazer este. Você quer dizer como "caro" a operação é para a matriz / indiferenciados, classificado / matriz, /-lista ligada indiferenciados, classificado / ligada-list

Um último ponto: "velocidade da aplicação" é uma dica para considerar mais do que apenas a velocidade das operações individuais.

* Adding

Unsorted: Array adicionando é O (1), a menos redimensionamento necessário - basta adicioná-la até o fim. Você pode querer discutir uma estratégia de redimensionamento que minimiza a sobrecarga (dica: não basta aumentar o tamanho por um)

Ordenado: Array adicionando é O (n) - encontrar o lugar para adicionar é O (log (n)), mas você precisa mover metade dos elementos up (em média) para fazer romm para o novo

Unsorted:. Lista ligada é O (1) - adicioná-lo para o início ou fim da lista

Ordenado:. Lista ligada é O (n) - embora você pode adicionar novamente o elemento em O (1), você precisa fazer a varredura através de metade da lista, em média, para encontrar o lugar para colocá-lo

Assim, ao longo de você para o resto. Postar uma resposta, e vamos criticá-lo, mas para obter o máximo de seu (presumivelmente) educatiom caro, você realmente precisa fazer algum trabalho sobre isso:)

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

Answer 2

Não sei o que classe isto é para, mas para um programa de CS, você terá que fazer melhor do que "é lento" e "é rápido". Tentar quantificar que, em termos de número-de-operações necessário. Você deve estar familiarizado com a máquina normalmente utilizada para tal quantificação -uso que as máquinas.

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 demonstrar o processamento // tempo de matriz classificada e não ordenada

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

// saída do 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: Obrigado

• Remover

Unsorted & classificadas: Array remoção é O (n) - tem que mover todos os elementos sobre a preencher 'buraco'

Unsorted & classificadas: lista ligada é O (1) - Alterar ponteiros conforme necessário