17

ページ付けを使用してHTMLテーブルを作成する必要があります。データは、joined selectステートメントを使用できない2つの異なるソース（1つのOracleともう1つのMySQLのような2つの異なるデータベースからの2つのテーブルである可能性があります）から取得されます。さらに複雑にするために、タイムスタンプ（プロパティの1つはタイムスタンプ）でソートされたデータを昇順で表示する必要があります。

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

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

4

1 に答える 1

4

私が理解しているように、あなたの懸念は記憶です。

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

テーブルがすでにソートされている場合は、 N個のソートされたシーケンスを1つにマージする必要があります。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 * logN）です。ここで、Mはテーブル内のレコードの総数であり、Nはテーブルの数です。このヒープ全体は、Nが十分に大きい場合にのみ面倒な価値があります（私の推測では約100です）。それ以外の場合は、線形探索とO（N * M）を使用します。

于 2012-08-14T15:49:24.057 に答える