並べ替えられたデータと並べ替えられていないデータのリンクリストと配列の実現可能性

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

  •  07-07-2019
  •  | 
  •  

質問

LinkedListsとArraysの比較、およびそれらの違いをソート済みデータと未ソートデータとの比較

  • 追加
  • 削除中
  • 取得中
  • 並べ替え
  • 全体の速度
  • 総メモリ使用量

実際の質問

  

未ソートのデータセットを配列ではなくリンクリストとして実装する可能性について説明します。挿入、削除、取得、コンピューターのメモリ、アプリケーションの速度に関して、トレードオフはどうなりますか？

     

並べ替えられたデータセットを配列ではなくリンクリストとして実装する可能性について説明します。挿入、削除、取得、コンピューターのメモリ、およびアプリケーションの速度に関して、トレードオフはどうなりますか？

     

前の質問への回答に基づいて、アプリケーションでリンクリストを使用することのコストと利点を要約します。

私の回答/入力：

  

LinkedListsは、新しいノードが追加されるたびにメモリを割り当てる必要があります。多くのノードを追加する場合に便利で、サイズが変化し続けますが、要素を追加する場合は一般に遅くなります

     

プログラム実行の開始時に配列にメモリが割り当てられ、リストのサイズ変更が遅くなりました（サイズ変更が必要な場合、多くの要素を追加すると遅くなります）

     

インデックス作成のため、配列での取得が高速化

     

ポインターが原因でLinkedListでの追加/削除が速くなりました

役に立ちましたか？

解決

未ソートとソート済みの場合。私はそれをします、そしてあなたは本当にあなたの宿題をする必要があります

Stackoverflowマークアップには、これを行うためのテーブルが本当に必要です。 「高価」とは操作は、未ソート/配列、ソート済み/配列、未ソート/リンクリスト、ソート/リンクリスト用です

最後のポイント：「アプリケーションの速度」は、個々の操作の速度以上のものを考慮するためのヒントです。 

* Adding

未ソート：サイズ変更が必要でない限り、配列の追加はO（1）です-最後に追加するだけです。オーバーヘッドを最小限に抑えるサイズ変更戦略について話し合うこともできます（ヒント：サイズを1つずつ増やすだけではいけません）

並べ替え：配列の追加はO（n）-追加する場所を見つけることはO（log（n））ですが、新しい要素のロムを作成するには要素の半分を上に移動する必要があります

未ソート：リンクリストは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.

@Paul：ありがとう

  
      
  • 削除中
    •   

未ソート＆amp;ソート済み：配列の削除はO（n）です-すべての要素を移動して「穴」を埋める必要があります

未ソート＆amp;ソート済み：リンクリストはO（1）-必要に応じてポインターを変更します

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top