偏移量/页数限制/大小转换
偏移量/页数限制/大小转换
提问于 2014-07-02 14:03:27
这应该是一个相互交织的挑战。我正在寻找一个还不存在的算法(据我所知)
- 我们有一个数据库访问函数，它可以一次读取记录的页面，使用页码和页面大小作为参数。让我们将此函数称为
getFromDatabase(int page, int size)。 - 我们希望提供一个REST，它应该根据偏移量和限制返回记录。让我们将其封装在函数
getRecords(int offset, int limit)中。
无论如何，我们必须使用给定的offset和limit来检索匹配的数据库记录，这些记录只能由page和size访问。显然，偏移量/限制并不总是映射到单个页面/大小。面临的挑战是找到一个算法，使“理想”数量的getFromDatabase调用来检索所有记录。该算法应考虑以下几个因素：
- 对
getFromDatabase的每个调用都有一定的开销；将调用保持在最低限度。 - 检索到的每条记录都会增加附加开销；检索尽可能少的记录(如果减少总开销，可以检索“浪费”)。
- 该算法本身也有开销成本；显然，它们不应超过任何好处。
我提出了以下算法：http://jsfiddle.net/mwvdlee/A7J9C/ (JS代码，但该算法与语言无关)。本质上，它是以下伪码：
do {
do {
try to convert (offset,limit) to (page,size)
if too much waste
lower limit by some amount
else
call `getDatabaseRecords()`
filter out waste records
increase offset to first record not yet retrieved
lower limit to last records not yet retrieved
} until some records were retrieved
} until all records are retrieved from database该算法的关键是确定too much waste和some amount。但是这个算法不是最优的，也不能保证它是完整的(它很可能是，我只是不能证明它)。
还有更好的吗？算法，还是我能做的改进？有没有人对如何解决这个问题有好的想法？
回答 3
Stack Overflow用户
发布于 2018-01-12 20:34:49
正如@usr所指出的，在这个问题的大多数变体中(无论是查询数据库、API还是其他实体)，最好尽可能减少调用的数量，因为返回几个额外的行几乎总是比发出单独的调用便宜。下面的PageSizeConversion算法将始终找到返回最少记录的单个调用(这正是它执行搜索的方式)。在数据集的开头(headWaste)或结束(tailWaste)可能会返回一些额外的记录，这是在单个页面中匹配数据集所必需的。该算法是在Javascript中实现的，但很容易移植到任何语言中。
function PageSizeConversion(offset, limit) {
var window, leftShift;
for (window = limit; window <= offset + limit; window++) {
for (leftShift = 0; leftShift <= window - limit; leftShift++) {
if ((offset - leftShift) % window == 0) {
this.pageSize = window;
this.page = (offset - leftShift) / this.pageSize;
this.headWaste = leftShift;
this.tailWaste = ((this.page + 1) * this.pageSize) - (offset + limit);
return;
}
}
}
}
var testData = [
{"offset": 0,"limit": 10,"expectedPage": 0,"expectedSize": 10,"expectedHeadWaste": 0,"expectedTailWaste": 0},
{"offset": 2,"limit": 1,"expectedPage": 2,"expectedSize": 1,"expectedHeadWaste": 0,"expectedTailWaste": 0},
{"offset": 2,"limit": 2,"expectedPage": 1,"expectedSize": 2,"expectedHeadWaste": 0,"expectedTailWaste": 0},
{"offset": 5,"limit": 3,"expectedPage": 1,"expectedSize": 4,"expectedHeadWaste": 1,"expectedTailWaste": 0},
{"offset": 3,"limit": 5,"expectedPage": 0,"expectedSize": 8,"expectedHeadWaste": 3,"expectedTailWaste": 0},
{"offset": 7,"limit": 3,"expectedPage": 1,"expectedSize": 5,"expectedHeadWaste": 2,"expectedTailWaste": 0},
{"offset": 1030,"limit": 135,"expectedPage": 7,"expectedSize": 146,"expectedHeadWaste": 8,"expectedTailWaste": 3},
];
describe("PageSizeConversion Tests", function() {
testData.forEach(function(testItem) {
it("should return correct conversion for offset " + testItem.offset + " limit " + testItem.limit, function() {
conversion = new PageSizeConversion(testItem.offset, testItem.limit);
expect(conversion.page).toEqual(testItem.expectedPage);
expect(conversion.pageSize).toEqual(testItem.expectedSize);
expect(conversion.headWaste).toEqual(testItem.expectedHeadWaste);
expect(conversion.tailWaste).toEqual(testItem.expectedTailWaste);
});
});
});
// load jasmine htmlReporter
(function() {
var env = jasmine.getEnv();
env.addReporter(new jasmine.HtmlReporter());
env.execute();
}());<script src="https://cdn.jsdelivr.net/jasmine/1.3.1/jasmine.js"></script>
<script src="https://cdn.jsdelivr.net/jasmine/1.3.1/jasmine-html.js"></script>
<link href="https://cdn.jsdelivr.net/jasmine/1.3.1/jasmine.css" rel="stylesheet" />
<title>Jasmine Spec Runner</title>
这也许不是@Martijn所想要的，因为它偶尔会产生大量浪费的结果。但在大多数情况下，这似乎是一个很好的解决一般问题的办法。
Stack Overflow用户
发布于 2020-05-04 20:09:06
偏移/页数限制原则-页码分页(精确，不浪费)
如果页面大小==限制或(偏移百分比限制) == 0，则页== (整数)其他页== (浮点数)。
在命令行中运行“节点convertOffsetToPage.js”类型
function convertOffsetToPage(offset, limit) {
const precision = 1000000;
const pageSize = limit;
let page = (offset + limit) / limit;
page = Math.round(page * precision) / precision;
return { page, pageSize };
}
function dbServiceSimulation(page, pageSize, items) {
const start = Math.round((page - 1) * pageSize);
const end = Math.round(page * pageSize);
return items.slice(start, end);
}
function getDataItems(itemCount) {
return Array.from(Array(itemCount), (_, x) => x);
}
const dataItems = getDataItems(1000000);
console.log('\ndata items: ', dataItems);
let offset = parseInt(process.argv[2], 10) || 0;
let limit = parseInt(process.argv[3], 10) || 1;
console.log('\ninput offset: ', offset);
console.log('\ninput limit: ', limit);
const { page, pageSize } = convertOffsetToPage(offset, limit);
console.log('\npage = ', page);
console.log('\npageSize = ', pageSize);
const result = dbServiceSimulation(page, pageSize, dataItems);
console.log('\nresult after core Service call');
console.log('\nresult: ', result)
console.log('\n');
Stack Overflow用户
发布于 2021-05-06 18:31:44
我也遇到了这个问题。以下是我的解决方案(用java)。首先，不重要的情况被关闭，然后是棘手的部分:)。它试图找到最优的页面大小、页码，并从页面的开头计算新的偏移量。保留的原始界限：
public static PageSizeOffsetLimit toPageSize(int offset, int limit) {
if (offset < limit) {
return new PageSizeOffsetLimit(0, offset + limit, offset, limit);
}
if (offset == limit) {
return new PageSizeOffsetLimit(1, limit, 0, limit);
}
for (int size = limit; size < 2 * limit; size++) {
int newOffset = offset % size;
if ((size - limit) >= newOffset) {
return new PageSizeOffsetLimit(offset / size, size, newOffset, limit);
}
}
throw new RuntimeException(String.format(
"Cannot determinate page and size from offset and limit (offset: %s, limit: %s)",
offset,
limit));
}玩得开心:)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24533203
复制相关文章
相似问题
腾讯云开发者
