LinkedList与Array的排序与未排序数据的可行性？

Comparing LinkedLists and Arrays while also comparing their differences with sorted and unsorted data

比较LinkedLists和Arrays,同时还比较它们与已排序和未排序数据的差异

Adding
Removing
Retrieving
Sorting
Overall speed
Overall memory usage

总内存使用情况

Actual questions

Discuss the feasibility of implementing an unsorted data set as a linked list rather than an array. What would the tradeoffs be in terms of insertion, removal, retrieval, computer memory, and speed of the application?

讨论将未排序的数据集实现为链表而不是数组的可行性。在插入,删除,检索,计算机内存和应用程序的速度方面会有什么权衡?

Discuss the feasibility of implementing a sorted data set as a linked list rather than an array. What would the tradeoffs be in terms of insertion, removal, retrieval, computer memory, and speed of the application?

讨论将排序数据集实现为链表而不是数组的可行性。在插入,删除,检索,计算机内存和应用程序的速度方面会有什么权衡?

Based on your answers to the previous questions, summarize the costs and benefits of using linked lists in an application.

根据您对先前问题的回答,总结在应用程序中使用链接列表的成本和收益。

My answers/input:

LinkedLists have to allocate memory everytime a new Node is added, useful when adding many Nodes and size keeps changing but generally slower when adding few elements

LinkedLists必须在每次添加新节点时分配内存,在添加许多节点和大小不断变化时很有用,但在添加少量元素时通常较慢

Arrays allocated memory at the beggining of the program run, resizing list slow (adding many elements slow if have to resize)

数组在程序运行的开始时分配内存,调整列表速度很慢(如果必须调整大小,则添加很多元素)

Retrieval is faster in array due to indexing

由于索引,检索在数组中更快

Adding/removing faster in LinkedList due to pointers

由于指针,在LinkedList中添加/删除速度更快

4 个解决方案

#1

On unsorted vs. sorted. I'll do one, then you really do need to do your homework

在未排序与排序。我会做一个,那你真的需要做你的功课

* markup really needs tables to do this one. You want to say how "expensive" the operation is for the unsorted/array, sorted/array, unsorted/linked-list, sorted/linked-list

*标记确实需要表来执行此操作。你想说的是对于未排序/数组,排序/数组,未排序/链接列表,排序/链接列表的操作是多么“昂贵”

One final point: "speed of the application" is a hint to consider more than just the speed of the individual operations.

最后一点:“应用程序的速度”是一个提示,不仅要考虑单个操作的速度。

* Adding

Unsorted: Array adding is O(1) unless resizing needed - just add it to the end. You might want to discuss a resizing strategy that minimises the overhead (hint: don't just increase the size by one)

未排序:除非需要调整大小,否则添加数组为O(1) - 只需将其添加到结尾。您可能想要讨论一个最小化开销的调整大小策略(提示:不要只是将大小增加一个)

Sorted: Array adding is O(n) - finding the place to add it is O(log(n)), but you need to move half the elements up (on average) to make romm for the new one

排序:数组添加是O(n) - 找到添加它的地方是O(log(n)),但你需要将一半的元素向上移动(平均)以使新的元素成为romm

Unsorted: Linked list is O(1) - add it to the start or end of the list.

未排序:链接列表为O(1) - 将其添加到列表的开头或结尾。

Sorted: Linked list is O(n) - although you can again add the element in O(1), you need to scan through half the list on average to find the place to put it.

排序:链接列表为O(n) - 尽管您可以再次在O(1)中添加元素,但您需要平均扫描列表的一半以找到放置它的位置。

So, over to you for the rest. Post an answer, and we'll critique it, but to get the most from your (presumably) expensive educatiom, you really need to do some work on this :)

所以,剩下的就交给你了。发表一个答案,我们会批评它,但为了从你的(大概)昂贵的教育中获得最大收益,你真的需要做一些工作:)

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

#2

Not sure what class this is for, but for a CS program, you will have to do better than "is slow" and "is fast". Try to quantify that, in terms of number-of-operations-needed. You should be familiar with a machinery typically used for such quantification -use that machinery.

不确定这是什么类,但对于CS程序,你必须做得比“慢”和“快”做得更好。尝试根据所需的操作次数来量化。您应该熟悉通常用于此类量化的机器 - 使用该机器。

#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 program to demonstrate processing // time of sorted and unsorted array

// 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 of the 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.

#4

@Paul: Thanks

Removing

Unsorted & sorted: Array removing is O(n) - have to move all element over to fill 'hole'

未排序和排序:数组删除是O(n) - 必须移动所有元素以填充'空洞'

Unsorted & sorted: Linked list is O(1) - Change pointers as needed

未排序和排序:链接列表为O(1) - 根据需要更改指针

#1