gpt4 book ai didi

database - 偏移/限制页面/大小转换

转载 作者:太空狗 更新时间:2023-10-30 01:56:28 24 4
gpt4 key购买 nike

这应该是一个有趣的挑战。我正在寻找一种尚不存在的算法(据我所知)

  • 我们有一个数据库访问函数,可以使用页码和页大小作为参数一次读取记录页。让我们调用此函数 getFromDatabase(int page, int size)
  • 我们想提供一个 REST API,它应该根据偏移量和限制返回记录。让我们将其包装在函数 getRecords(int offset, int limit) 中。

不知何故,我们必须使用给定的offsetlimit 来检索只能由page 访问的匹配数据库记录尺寸。显然,偏移量/限制不会总是映射到单个页面/大小。挑战在于找到一种算法,使 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

该算法的关键在于确定太多浪费一些数量。但是这个算法不是最优的,也不能保证是完整的(很可能是,我只是无法证明)。

有没有更好的(已知的?)算法,或者我可以做的改进?有人对如何解决这个问题有好的想法吗?

最佳答案

正如@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 正在寻找的正是,因为它偶尔会产生大量浪费的结果。但在大多数情况下,这似乎是解决一般问题的好方法。

关于database - 偏移/限制页面/大小转换,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24533203/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com