Осуществимость LinkedList по сравнениюМассив для отсортированных по сравнениюнесортированные данные?

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

  •  07-07-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

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

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

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

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

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

Добавление / удаление быстрее в LinkedList из-за указателей

Это было полезно?

Решение

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

Разметке Stackoverflow действительно нужны таблицы для выполнения этой задачи.Вы хотите сказать, насколько "дорогостоящей" является операция для несортированного / массива, sorted / array, несортированного / связанного списка, sorted / linked-list

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

* Adding

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

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

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

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

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

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

Другие советы

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

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.

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

  • Удаление

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top