複数のソースからページ分割を作成する

Question

ページ設定を含むHTMLテーブルを作成する必要があります。データは2つの異なるソースから得られます（1つのOracleのような2つの異なるデータベースからの2つのテーブルと、もう1つはMySQLです）。これはjoinステートメントを使用できません。より複雑にするために、タイムスタンプでソートされたデータ（タイムスタンプのプロパティの1つ）を昇順で表示する必要があります。

たとえば、ソースAには45レコード、ソースBには55レコードがあります。したがって、テーブルには合計レコード100件が表示されますが、一度に表示できるのは15レコードだけです。だから7ページ（6ページ15レコードと1レコード10レコード）でなければなりません。

上記の例は、合計100個のレコードであり、メモリにロードするのは簡単です。しかし、実際の制作では、数千または数百万のレコードになる可能性があります。誰も私が使用できるアルゴリズムを知っていますか？私が提供できるパラメータは、ページ番号とページあたりのレコード数です。

Answer 1

私が理解するように、あなたの心配は記憶です。

個々のテーブル（AとB）がタイムスタンプでソートされていない場合は、すべてのレコードを1つのファイルにマージしてから、ファイルベースのソートアルゴリズム（MergeSortなど）を使用する必要があります。レコード、第2パスではソートされた4など）。タイムスタンプの昇順にすべてのレコードを含むファイルがある場合は、ページに分割できます。

テーブルが既にソートされている場合は、ソートされたシーケンスを1つにマージする必要があります。私はHeapの何らかの種類を編成して、N個のソースのうちどれがタイムスタンプが最小のアイテムがあるかを把握することをお勧めします。擬似コードでは、次のようになります。

for i=1,N 
{ 
    Add the 1st record from each table to the Heap 
} 
while(Heap not empty) 
{ 
    x = take the smallest item from the heap, noting which table j this record belonged to 
    Add x to output 
    if (the j-th table is not completely processed) 
    { 
    take the next value from the j-th table and insert it into the heap 
    } 
} 

複雑さはO Mは、テーブル内のレコードの総数である（M * logN個）であり、Nは、テーブルの数です。このヒープ全体のことは、Nが十分に大きければ（私の推測は〜100）、面倒だけの価値があります。それ以外の場合、私は線形検索とO（N * M）に行きます。