Осуществимость LinkedList vs. Array для отсортированных и несортированных данных?

Question

Сравнение LinkedLists и Arrays, а также сравнение их различий с отсортированными и несортированными данными

• Добавление
• Удаление
• Получение
• Сортировка
• Общая скорость
• Общее использование памяти

Актуальные вопросы

Обсудить возможность реализации несортированного набора данных в виде связанного списка, а не массива. Каковы будут компромиссы с точки зрения вставки, удаления, поиска, памяти компьютера и скорости приложения?

Обсудить возможность реализации отсортированного набора данных в виде связанного списка, а не массива. Каковы будут компромиссы с точки зрения вставки, удаления, поиска, памяти компьютера и скорости приложения?

На основе ваших ответов на предыдущие вопросы суммируйте затраты и преимущества использования связанных списков в приложении.

Мои ответы / ввод:

Списки LinkedList должны выделять память каждый раз, когда добавляется новый узел, полезно при добавлении множества узлов, и размер продолжает изменяться, но обычно медленнее при добавлении нескольких элементов

Массивы выделяют память в начале выполнения программы, медленно меняя размер списка (добавляя много элементов медленно, если нужно изменить размер)

Из-за индексации поиск выполняется быстрее в массиве

Быстрое добавление / удаление в LinkedList благодаря указателям

Answer 1

Не отсортировано и не отсортировано. Я сделаю один, тогда тебе действительно нужно делать домашнее задание

Разметке Stackoverflow действительно нужны таблицы для этого. Вы хотите сказать, насколько «дорогая» операция для несортированного / массива, отсортированного / массива, несортированного / связанного списка, отсортированного / связанного списка

И последнее замечание: «скорость приложения» - это подсказка для рассмотрения не только скорости отдельных операций.

* Adding

Unsorted: добавление массива равно O (1), если не требуется изменение размера - просто добавьте его в конец. Возможно, вы захотите обсудить стратегию изменения размера, которая минимизирует накладные расходы (подсказка: не просто увеличивайте размер на единицу)

Sorted: Добавление массива - O (n) - поиск места для добавления - O (log (n)), но вам нужно переместить половину элементов вверх (в среднем), чтобы сделать новое для нового

Unsorted: связанный список O (1) - добавьте его в начало или конец списка.

Sorted: Связанный список - O (n) - хотя вы можете снова добавить элемент в O (1), вам нужно в среднем просмотреть половину списка, чтобы найти место для его размещения.

Итак, к вам на отдых. Отправьте ответ, и мы его критикуем, но чтобы извлечь максимальную пользу из вашего (предположительно) дорогого образования, вам действительно нужно поработать над этим:)

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

Answer 2

Не уверен, для какого класса это класс, но для CS-программы вам придется работать лучше, чем «медленно» и «быстро». Попробуйте определить это с точки зрения количества необходимых операций. Вы должны быть знакомы с оборудованием, обычно используемым для такого количественного определения, - использовать это оборудование.

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.

// Программа CPP для демонстрации обработки // время отсортированного и несортированного массива

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

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

@ Пол: Спасибо

• Удаление

Несортировано и отсортировано: удаление массива - O (n) - нужно переместить весь элемент, чтобы заполнить «дыру»

Не отсортировано и не отсортировано: связанный список O (1) - при необходимости измените указатели