algorithm - 确定最后 "record"的最快方法 .. 理想情况下是并行的...(有间隙)

Question

我有一个数据挖掘应用程序，它访问一个网站以检索个人记录 [另一个网站仍由我的公司运营，但没有用于访问它的 API]。我知道第一条记录是“1”但是(没有人为干预)我不知道最后一条记录。按顺序处理数据可能需要一段时间(例如 4000 条记录 = 大约 45 分钟)。为了改善用户体验，我想快速确定完成百分比。

理想情况下，我会实现类似于二进制搜索的方法来确定从服务器中提取最少的最后一条记录。我碰巧知道这些记录是由人类创造的，所以如果今天总共有 4000 条记录，明天可能会在 4000-4020 之间，但我想避免引入假设到我的数据收集应用程序，因为这需要用户进行某种管理。

1. 确定“最后一条记录”的最快方法是什么
2. 使问题复杂化的是，删除的记录看起来与尚未创建的记录完全相同!虽然这些非常罕见，但确实会发生。我已确定在最后一次成功后检索五次连续失败的规则，以指示最后一条记录。
3. 我已经有了一个很好的顺序实现，但由于处理记录的成本，我决定并行检索它们是可能的/更快的(例如一次 8 个)

这种“最后索引”搜索(间隙有限)是否有既定的模式/算法？虽然我可以积极地(在一定程度上)使现有应用程序并行(例如，可能快 8 倍)，但我如何才能快速确定用户等待持续时间？

1. 我可以让用户只需等待他们目前等待时间的 1/8。
2. 我可以花费最初的精力找到最后一条记录，然后回填内容以完成操作。

特定于实现的信息，我正在用 C# 实现它并可以访问 LINQ，但我认为这是一种独立于语言的算法。

编辑 我已经为大多数用户提供了缓存机制，但是现有数据可能会非常频繁地更改(每天 5%-10%)，因此缓存机制很快就会过时.我想避免需要 central-cache 这样所有用户都不会受到这些更改的影响，此外还有多个项目和缓存可能需要访问“网站”我什至可能无法访问或我开发的服务 - 我希望它保留在“用户域”内。因此，有时需要尽快进行“全面更新”。

Answer 1

好吧，正如您所说，您可以使用类似二分查找的方法。您正在尝试找到有效记录索引 (n) 的最小上限。从 n = 1 开始，然后加倍直到结束。 n 现在是上限。现在在 n/2 和 n 之间进行二进制搜索，以将其减少到最小上限。

很明显，这可以被调整为一次拉下 8 条或更多记录(如果你发现你已经结束的唯一方法是看到足够多的相邻记录，这听起来无论如何都是必要的空条目)。