可行性与链表阵列，用于排序与未分类的数据？

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

  •  07-07-2019
  •  | 
  •  

题

比较LinkedLists和阵列，同时也比较它们的分歧与排和未分类的数据

  • 加入
  • 除去
  • 检索
  • 排序
  • 总的速度
  • 整体内存使用情况

实际问题

讨论的可行性，实现一个未分类的数据集作为一个链接清单，而不是一个阵列。会是什么样的折衷，是在条款插入，清除、检索、计算机存储器，并且速度的应用程序？

讨论的可行性排序的数据集作为一个链接清单，而不是一个阵列。会是什么样的折衷，是在条款插入，清除、检索、计算机存储器，并且速度的应用程序？

基于你的回答前一个问题，汇总成本和收益的使用链接表中的应用程序。

我的答案/输入：

LinkedLists必须分配存储每次一个新的节点是加，有时加入了许多节点和尺寸不断变化但一般较慢当增加一些元素

阵列分配的存在开始的程序的运行，调整缓慢表(加上许多因素慢，如果需要调整)

检索速度更快阵列，因为索引

加入/消除更快链表由于指针

有帮助吗？

解决方案

在未分类的对排序。我会做一个，那么你真的不需要做家庭作业

计算器的标记真的需要表要做到这一点。你想说如何"高昂"的操作的未经分类整理/阵列，排/阵列，未排/连接，排/连名单

最后一点："快速的应用程序"是一个暗示要考虑的不仅仅是速度的个人的行动。 

* Adding

未分类:阵列加是O(1)除非调整需要-只是添加到最后。你可能会想要讨论的一个调整战略，最大限度地减少开销(暗示:不只是增加通过一个)

排序：阵列加是O(n)-找到的地方增加它是O(日志(n))，但是你需要将一半的元素(月平均)让罗姆新的

未分类:链表是O(1)-加它的开始或结束的清单。

排序：链表是O(n)虽然你可以再添加元O(1)，需要扫描通过一半的列表上平均查找地方把它。

所以，在你的休息。后一个答案，我们批评它，但获得最大(据推测)昂贵的educatiom，你真的需要做一些工作在这个:)

* 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