-4

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

  • 添加
  • 移除
  • 检索
  • 排序
  • 整体速度
  • 总体内存使用情况

实际问题

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

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

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

我的答案/输入：

每次添加新节点时，LinkedLists 都必须分配内存，这在添加许多节点并且大小不断变化时很有用，但在添加少量元素时通常会变慢

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

由于索引，在数组中检索速度更快

由于指针，在 LinkedList 中添加/删除更快

4

4 回答 4

2

不确定这是针对哪个课程的，但是对于 CS 程序，您必须比“慢”和“快”做得更好。尝试根据需要的操作数来量化它。您应该熟悉通常用于此类量化的机器 - 使用该机器。

于 2008-11-09T18:59:19.300 回答
2

关于未排序与排序。我会做一个，然后你真的需要做你的功课

Stackoverflow 标记确实需要表格来执行此操作。您想说对于未排序/数组、已排序/数组、未排序/链表、已排序/链表的操作有多“昂贵”

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

* Adding

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

排序：数组添加是 O(n) - 找到添加它的位置是 O(log(n))，但是您需要（平均）向上移动一半元素以为新元素创建 romm

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

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

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

* Removing
* Retrieving
* Sorting
* Overall speed
* Overall memory usage
于 2008-11-09T19:34:46.373 回答
1 
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.
于 2018-05-04T06:18:38.547 回答
0

@保罗：谢谢

  • 移除

未排序和已排序：数组删除是 O(n) - 必须将所有元素移动以填充“洞”

未排序和排序：链表是 O(1) - 根据需要更改指针

于 2008-11-09T19:45:32.793 回答