17

我需要创建一个带有分页的 HTML 表格。数据来自 2 个不同的来源（可能是来自 2 个不同数据库的 2 个表，比如一个 Oracle，另一个是 MySQL），您不能使用 join select 语句。为了使它更复杂，我需要以升序显示按时间戳（属性之一是时间戳）排序的数据。

例如，源 A 有 45 条记录，源 B 有 55 条记录。所以该表将显示 100 条记录，但一次只显示 15 条记录。所以必须有 7 页（6 页有 15 条记录，1 页有 10 条记录）。

上面的例子总共只有 100 条记录，内存可能很容易将它们全部加载。但在实际生产中，可能是数千或数百万条记录。有谁知道我可以使用的任何算法？我可以提供的参数是页码和每页的记录数。

4

1 回答 1

4

据我了解，您关心的是记忆。

如果单个表（A 和 B）没有按时间戳排序，那么您需要将它们的所有记录合并到一个文件中，然后使用一些基于文件的排序算法（类似于 MergeSort，在一次通过中，您会得到排序的记录对，在第二遍你得到排序4s等）。当您有一个所有记录按时间戳升序排列的文件时，您可以将其分成页面。

如果表已经排序，则需要将N 个排序序列合并为一个。我建议您组织某种堆来跟踪 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 回答