ソートされたサブセクションで複数のリンクリストをソートおよびマージする

Question

私はnumlistsリンクリストの配列を持っています。リスト内のノードの形式は次のとおりです。

struct Edge 
{ 
    int64_t blocknum; 
    int64_t location; 
    struct Edge *next; 
}; 
typedef struct Edge edge; 

私は昇順でlocationによってソートされ、単一リンクリストにすべてのリストをマージする必要があります。各リストはノードがblocknumに等しいブロックで構成され、これらのブロックはそれぞれ既にソートされています。 blocknumの大きい値を持つリストブロックは、すべて小さい値のblocknumのブロックよりも大きい位置の値を持ちます。サブリストのブロックはすでにローカルにblocknumの順にソートされています。これは実質的に、これがブロックを昇順で並べ替えることになるということを意味します。それはあまり気にする必要はありません。locationそれはそれ自身の面倒を見るからです。配列のnextメンバーが有効で割り当てられているか、明示的にNULLが宣言されていると仮定してもかまいません。ここで

は私が

edge *sort_edges(edge **unsorted, int numlists) 
{ 
    edge *sorted_head = NULL; 
    edge *sorted_current = NULL; 
    edge *current_edge = NULL; 
    edge *temp = NULL; 
    int64_t blocknum; 

    int i; 
    int64_t minblock; 
    int remaining = numlists; 
    int first = 1; 
    int minblock_index; 
    while(remaining) //while there are still more lists to process 
    { 
     minblock = LLONG_MAX; 
     temp = NULL; 
     minblock_index = INT_MAX; 
     remaining = numlists; 
     for (i=0; i<numlists; i++) //loop over the list of head nodes to find the one with the smallest blocknum 
     { 
      if (!unsorted[i]) //when a lists is exhausted the lead node becomes NULL, and we decrement the counter 
      { 
       remaining--; 
      } 
      else //a simple minimum finding algorithm 
      { 
       current_edge = unsorted[i]; 
       if (current_edge->blocknum < minblock) 
       { 
        temp = current_edge; 
        minblock = current_edge->blocknum; 
        minblock_index = i; 
       } 
      } 
     } 
     if (remaining == 0) 
     { 
      break; 
     } 
     if (first) //if we have not yet set up the head of the list, we have to save a pointer to the head 
     { 
      sorted_head = temp; 
      sorted_current = sorted_head; 
      first = 0; 
     } 
     else 
     { 
      sorted_current->next = temp; 
     } 
     blocknum = sorted_current->blocknum; 
     while (sorted_current->blocknum == blocknum && sorted_current->next) //skip through to the end of the block so that the next section we append will go on the end 
     { 
      sorted_current = sorted_current->next; 
     } 
     unsorted[minblock_index] = sorted_current->next; //reset the head of the unsorted list to the node after the block 
    } 
    return sorted_head; 
} 

この作品を思い付いた機能です。私の質問は次のとおりです：

効率的な並べ替えアルゴリズムの点で私は良くできますか？ （ほとんど確かにはい、私はちょうど人々が与えられた前提のソート問題のために思い付くものが不思議です）。

Answer 1

上記の「ブロック」あなたはポインタ配列内の各ポインタからぶら下がっリストを意味し、その後、

int compare_edge_blocknum(const void *e1, const void *e2) 
{ 
    if (!e1 && !e2) 
     return 0; 
    else 
    if (!e1) 
     return +1; 
    else 
    if (!e2) 
     return -1; 
    else { 
     const int64_t b1 = ((edge *)e1)->blocknum; 
     const int64_t b2 = ((edge *)e2)->blocknum; 
     return (b1 < b2) ? -1 : 
       (b1 > b2) ? +1 : 0; 
    } 
} 

edge *last_in_list(edge *list) 
{ 
    if (list) 
     while (list->next) 
      list = list->next; 
    return list; 
} 

edge *sort_edges(edge **array, size_t count) 
{ 
    edge root = { 0, 0, NULL }; 
    edge *tail = &root; 
    size_t i; 

    if (!array || count < 1) 
     return NULL; 
    if (count == 1) 
     return array[0]; 

    qsort(array, count, sizeof *array, compare_edge_blocknum); 

    for (i = 0; i < count; i++) 
     if (array[i]) { 
      tail->next = array[i]; 
      tail = last_in_list(array[i]); 
     } 

    return root->next; 
} 

たかはblocknumによると、ポインタの配列をソートするqsort()を使用しています。結果のリストへのハンドルとしてrootを使用します。ポインタの配列をループし、結果リストのtailにNULL以外の各ポインタを追加します。リストの最後の要素を指すように常に更新されます。tail

テール要素を見つけるために各リストをトラバースするのはおそらく遅い部分ですが、残念ながらそれを避ける方法はありません。 （リスト要素がメモリ内で連続していない場合、リストトラバーサルはRAMから多くのキャッシュロードを必要としがちですが、配列がソートされるときのアクセスパターンはCPUが予測することがより簡単ですおそらく最も遅い一部ではありません - 。もちろん、あなたが実用的なデータセットにコードを分析し、あなたがCライブラリqsort()よりも速くソートの実装を必要とするかどうかを検討することができます）

---

OPは、個々のことを明らかにポインタ配列にポインタを掛けるリストは、1つ以上の「ブロック」、すなわち連続したソートされたランを含むことができる。これらはブロック番号の変更によって検出できます。

追加のメモリ使用が問題でない場合、私はその後、blocknumによってソートされ、最終的に連鎖します

typedef struct { 
    int64_t blocknum; 
    edge *head; 
    edge *tail; 
} edge_block; 

の配列を作成したいです。最初の（head）要素と最後の（tail）要素の両方へのポインタを保存するということは、リストを1回だけスキャンすることを意味します。 edge_block配列がソートされた後、単純な線形のパスにより、すべてのサブリストを最終リストにまとめることができます。例えば

（コンパイルのみテスト済み）：

#include <stdlib.h> 
#include <stdint.h> 
#include <errno.h> 

typedef struct Edge edge; 
struct Edge { 
    int64_t  blocknum; 
    int64_t  location; 
    struct Edge *next; 
}; 

typedef struct { 
    int64_t  blocknum; 
    struct Edge *head; 
    struct Edge *tail; 
} edge_block; 

static int cmp_edge_block(const void *ptr1, const void *ptr2) 
{ 
    const int64_t b1 = ((const edge_block *)ptr1)->blocknum; 
    const int64_t b2 = ((const edge_block *)ptr2)->blocknum; 
    return (b1 < b2) ? -1 : 
      (b1 > b2) ? +1 : 0; 
} 

edge *sort_edges(edge **array, size_t count) 
{ 
    edge_block *block = NULL; 
    size_t  blocks = 0; 
    size_t  blocks_max = 0; 
    edge  *root, *curr; 
    size_t  i; 

    if (count < 1) { 
     errno = 0; 
     return NULL; 
    } 

    if (!array) { 
     errno = EINVAL; 
     return NULL; 
    } 

    for (i = 0; i < count; i++) { 
     curr = array[i]; 

     while (curr) { 

      if (blocks >= blocks_max) { 
       edge_block *old = block; 

       if (blocks < 512) 
        blocks_max = 1024; 
       else 
       if (blocks < 1048576) 
        blocks_max = ((blocks * 3/2) | 1023) + 1; 
       else 
        blocks_max = (blocks | 1048575) + 1048577; 

       block = realloc(block, blocks_max * sizeof block[0]); 
       if (!block) { 
        free(old); 
        errno = ENOMEM; 
        return NULL; 
       } 
      } 

      block[blocks].blocknum = curr->blocknum; 
      block[blocks].head = curr; 

      while (curr->next && curr->next->blocknum == block[blocks].blocknum) 
       curr = curr->next; 

      block[blocks].tail = curr; 
      blocks++; 
      curr = curr->next; 
     } 
    } 

    if (blocks < 1) { 
     /* Note: block==NULL here, so no free(block) needed. */ 
     errno = 0; 
     return NULL; 
    } 

    qsort(block, blocks, sizeof block[0], cmp_edge_block); 

    root = block[0].head; 
    curr = block[0].tail; 
    for (i = 1; i < blocks; i++) { 
     curr->next = block[i].head; 
     curr = block[i].tail; 
    } 

    free(block); 

    errno = 0; 
    return root; 
} 

---

が非常に多くblocknumsが潜在的にある、またはあなたが使用するメモリの量を制限する必要がある場合は、その後、私は小さな分を使用したいですcountをキー

typedef struct { 
    size_t count; 
    edge *head; 
    edge *tail; 
} edge_block; 

要素の-heap、そのサブリスト内の要素の数。

考えられるのは、入力からブロックを抽出するときは、余裕があればそれをミニヒープに追加するという考えです。それ以外の場合は、min-heapのルートリストとマージします。 OPのルールによれば、この「マージ」は実際には単一のインサートであり、各ブロックは連続しているので注意してください。最初に挿入ポイントのみを検索する必要があります。 countは、ルートリストの要素数を反映するように更新されます。したがって、最小ヒープを再生成します。

ヒープの目的は、2つの最短ブロックをマージして、リストを走査して挿入ポイントを最小限にすることです。

すべてのブロックが挿入されたら、ルートを取得してそのリストを新しいルートリストとマージし、ヒープのサイズを毎回1減らしてからリストを1つ残します。それが最終結果リストです。

Answer 2

私が理解しているように、複数のソートリストがあり、それらをまとめて1つのソートリストを作成したいとします。

一般的な方法は、リストのキューを作成し、ペアを継続的にマージし、結果をキューに追加し、リストが1つだけ残るまで繰り返すことです。例：

listQueue = queue of lists to be merged 
while listQueue.count > 1 
{ 
    list1 = listQueue.dequeue 
    list2 = listQueue.dequeue 
    newList = new list 
    // do standard merge here 
    while (list1 != null && list2 != null) 
    { 
     if (list1.item <= list2.item) 
     { 
      newList.append(list1.item) 
      list1 = list1.next 
     } 
     else 
     { 
      newList.append(list2.item) 
      list2 = list2.next 
     } 
    } 
    // clean up the stragglers, if any 
    while (list1 != null) 
    { 
     newList.append(list1.item) 
     list1 = list1.next 
    } 
    while (list2 != null) 
    { 
     newList.append(list2.item) 
     list2 = list2.next 
    } 
    listQueue.enqueue(newList) 
} 
mergedList = listQueue.dequeue 

これはシンプルで追加メモリをほとんど必要としないため、魅力的なオプションです。効率的です。

メモリが少し必要です（O（log k）、kはリストの数です）、少し速い方法があり、もう少しコーディングする必要があります。これには、各リストの最初の項目を含むmin-heapの作成が含まれます。ヒープから最下位アイテムを削除し、新しいリストに追加してから、最も低いアイテムがあったリストから次のアイテムを取り出し、ヒープに挿入します。

これらのアルゴリズムは両方ともO（n log k）の複雑さですが、2番目のアルゴリズムはデータをあまり移動させないため、おそらく高速です。どのアルゴリズムを使用するかは、リストの大きさとマージの頻度によって異なります。