将偏移分页转换为页码分页的算法

Question

我有一项服务必须接收偏移量格式的分页查询，接收 offset 和 limit 参数。例如，如果我收到 offset=5&limit=10，我希望能收到第 5-14 项。我能够针对这些参数强制执行一些验证，例如设置限制的最大值。

我的数据源必须接收页码格式的分页请求，接收 page_number 和 page_size 参数。例如，如果我发送 page_number=0&page_size=20，我将收到项目 0-19。数据源最大 page_size 为 100。

我需要能够获取我收到的偏移分页参数并使用它们来确定 page_number 和 page_size 参数的适当值，以便 return 一个范围来自包含我需要的所有项目的数据源。可以 return 填充其他项目以填充范围的开始 and/or 结束，然后可以将其过滤掉以生成请求的范围。

如果可能，我应该只向数据源发出一次请求。或者，可以通过最小化从数据源请求的范围大小来提高性能（即获取 10 个项目来满足对 8 个项目的请求比请求 100 个项目更有效）。

感觉实现起来应该相对简单，但我对简单数学解决方案的尝试并没有解决所有边缘情况，而且我对更稳健解决方案的尝试已经开始转向更复杂的问题 space 计算和迭代因子等

有没有简单的方法来计算合适的值？

I've put together a test harness REPL with a set of example test cases that makes it easy to trial different implementations here.

Answer 1

一个合适的实现是从 page_size=limit 开始，然后递增 page_size，直到有一个页面包含从 offset 到 offset+limit 的整个范围。

如果你不想浪费时间在迭代上，那么考虑这个方法所花费的时间至多与结果集的大小成正比，完全与您自己读取、编组、解组和处理结果的时间相比，微不足道。

我已经用 offset+limit <= 100000 测试了所有组合。在所有情况下，page_size <= 2*limit+20。对于较大的限制，最坏情况的开销总是发生在 limit=offset+1 时。在某些时候，发出 2 个请求会变得更有效率。你应该检查一下。

Answer 2

这个怎么样？

if (limit > 100) { 
// return error for exceeding limit...
}

mod_offset = (offset % limit)
page_number = (offset / limit) ;
page_size = limit;

// Sample test cases ..

// offset=25, limit=20 .. mod_offset = 5

(a) page_number = 1, page_size = 20  // skip first 'n' values equal to 'mod_offset'
(b) page_number = 1+1 = 2, page_size = 20 // include only first 'n' values equal to 'mod_offset'


// offset=50, limit=25 .. mod_offset = 0
(a) page_number = 2, page_size = 25  // if offset is multiple of limit, no need to fetch twice...

// offset=125, limit=20  .. mod_offset = 5

(a) page_number = 6, page_size = 20  // skip first 'n' values equal to 'mod_offset'
(b) page_number = 6+1 = 7, page_size = 20 // include only first 'n' values equal to 'mod_offset'

将偏移分页转换为页码分页的算法

Algorithm to convert offset pagination to page number pagination

algorithm

pagination