5

非常に少数の要素を挿入する必要がある場合、どちらの方法でエンキューとデキューを高速化できますか？配列はリンクリストよりも優れていますか？

いくつかの要素を挿入する必要があり、その削除された要素をキューから削除して読み取る必要があります。配列の場合、要素を削除するたびにインデックスを変更しなければならない場合があります。挿入と削除が同時に発生する場合もあります。

以下のケースからどちらが良いですか？

typedef struct{
    mylist list;
    struct mylistQ *next;
}mylistQ;

配列コード 

 static mylist myListQ[QUEUESIZE+1];
int qLast = 0;

void enqueue_element(mylist qItem)
{
        myListQ[qLast] = qItem;
    qLast++;
}

mylist dequeue_element()
{
 retryq:
   if(qLast >0) {
    mylist qReturn = myListQ[0];  
    int i;
    for (i = 0; i < qLast - 1; i++){
        myListQ[i] = myListQ[i + 1];
    }
    qLast--; 
    return qReturn;
     }
   else {
    goto retryq;
    }
}

リンクリスト 

 int qLast = 0;

mylistQ *headElement = NULL;   
mylistQ *tailElement = NULL;     

void enqueue_element(mylist *List)
{
    mylistQ *newnode;      
    newnode=(mylistQ*)av_malloc(sizeof(mylistQ));
    newnode->next=NULL;
    newnode->list=*List;
    qLast++;
    if(headElement==NULL && tailElement==NULL)
    {
        headElement=newnode;
        tailElement=newnode;
    }
    else
    {
        tailElement->next=newnode;
        tailElement=newnode;
    }
 }

mylist dequeue_element()
{
    mylistQ *delnode;      /* Node to be deleted */
    mylist Dellist;
    if(headElement==NULL && tailElement==NULL){
        LOg( "Queue is empty to delete any element");
        }
    else
    {
       Log("In dequeue_picture queue is not empty");
        delnode=headElement;
        headElement=headElement->next;
    if (!headElement){
        tailElement=NULL;
    }
        Dellist = delnode->list;
        av_free(delnode);
    qLast--;
    }
        return Dellist;
}
4

3 に答える 3

5

これは、実行する操作の数と、配列バージョンがどのように実装されているかによって異なります。

実行する操作が比較的少ない場合、つまり合計で 1000 回未満のエンキュー/デキューの場合、配列はメモリ内で連続しているため高速になります。前へのポインターと後ろへのポインターを維持し、常に後ろで追加し、前でデキューします。

一方、リストが 30 個程度の要素を超えていなくても、これが長期間持続する必要がある場合、配列の潜在的な問題である配列のサイズ変更の問題は発生しません。

リンクされたリストは優れたパフォーマンスが保証されており、配列のサイズ変更には注意が必要です。

編集: @Hans Passant が述べたように、配列は CPU キャッシュの局所性があるため高速です。配列が小さい限り、配列の格納に関連するメモリが L2 に保持されるように、ハードウェアがパフォーマンスを最適化します。インデックスはおそらくレジスターにあります。これは本当に速いです。多くの要素を必要としないという事実から判断すると、この場合は配列が理想的です。はい、要素を移動するときにインデックスを変更する必要がありますが、最適化を使用してコードをビルドすると、インデックスがレジストラーに保存されるため、これは実際には非常に高速な操作です。

ただし、キャッチは次のとおりです。エンキューとデキューの両方を同時に実行する必要があるかもしれないと述べていますが、これは並列、つまり複数のスレッドがメモリにアクセスしていることを意味しますか? この場合、配列は依然として高速ですが、パフォーマンスが 800 倍低下することがわかります。なんで？プロセッサは、ダイ上のキューに関連付けられたメモリをバッファリングできなくなりますが、メイン メモリに格納する必要があります。さらに、スレッド間で競合状態が発生するリスクがあります。あるスレッドがキューから出そうとし、別のスレッドがキューから出ようとしていて、リストに要素が 1 つしかない場合を想像してみてください。いずれにせよ、このアプリケーションが非常にパフォーマンス重視である場合は、必ず NDEBUG および -O3 フラグをオンにしてコンパイルしてください (gcc を想定)。

2番目の編集：コードを見て、他の回答を見て、要素数に上限があるように聞こえるので、配列コードをより効率的にして循環配列に変えることをお勧めします。補足として、現在の配列の実装は非常に非効率的です。削除するたびにキューの残りの部分を転送しますが、これは意味がありません。「最初の」インデックスへの int ポインターをインクリメントするだけです。

疑似コード:

int ciruclarArray[SIZE];
int front = 0;
int back = 0;

void enqueue(int elem)
{
    circularArray[back] = elem;
    if(back < (circularArray.length - 1))
        back++;
    else
        back = 0;
    return elem;
}

int dequeue()
{
    int toReturn = circularArray[front];
    //do same check for incrementing as enqueue
    return toReturn;
}

通常のもののエラーチェックを行うことを忘れないでください。

于 2011-02-24T22:38:45.750 に答える
3

キューに格納する要素の総数に上限がある場合は、循環配列を使用します。これにより、配列の最後に要素を連続的に追加するときに、配列のサイズを変更する必要がなくなります。

于 2011-02-24T23:51:30.090 に答える
1

多くの要素がある場合でも、配列の実装がおそらく最も高速です。インスピレーションを得るために、GCC の C++ デキューを調べました。配列の配列としてキューを格納します。イテレータが循環バッファのようにラップアラウンドするかどうかはわかりません。配列の実装には、後で必要になった場合に備えて、高速ランダム アクセスもあります。

于 2011-02-24T23:55:37.333 に答える