分页算法:显示唯一电子商务商家的排名搜索结果

Question

Hi Stack Overflow社区，

我正在为电子商务网站构建搜索功能，并寻找满足多种要求的最佳分页算法。

当用户在我们的网站上提交搜索产品查询时，我们会返回根据其指定偏好评分的产品列表。然后，搜索结果将显示在多个网页上。由于多个商家信息可以属于同一商家，因此我们希望确保商家不会在单个网页中主导搜索结果。

1. 结果按分数降序排序。
2. 给定每个页面的结果数量，我们将结果集划分为单独的页面(分页)，同时让商家在每个页面上最多出现一次。
3. 如果页面不能只填充唯一商家，则页面将填充剩余的产品条目，同时保留初始排序。

例如： 每页显示的结果 设 numPerPage = 4;

// results array of csv, comma-delimited strings with format:
// merchant_id,listing_id,score,description
let results = [
"5,90,500.1,description text",  
"4,51,495.8,description text",  
"8,72,490,description text",  
"5,89,485.4,description text",
"5,80,480,description text",
"9,18,478.1,description text",  
"6,50,475.9,description text",  
"5,56,472,description text",  
"7,12,470.5,description text",  
"5,5,465,description text",
"6,10,450,description text"
]
// Paginate function output: array of strings representing paginated results, 
// with an empty String separator after each page, except the last page.
let output = [
"5,90,500.1,description text",  
"4,51,495.8,description text",  
"8,72,490,description text", 
"9,18,478.1,description text",
"", // this is a page separator
"5,89,485.4,description text",
"6,50,475.9,description text",  
"7,12,470.5,description text",
"6,10,450,description text",
"", // this is a page separator
"5,80,480,description text",
"5,56,472,description text",  
"5,5,465,description text"]

到目前为止，已经编写了以下代码：

function paginate(numPerPage, results) {
// first map : transform into array of arrays
// second map : transform into array of objects w/ key-value pairs
let hash = {};
let output = [];
output = results.map(listing => listing.split(',')).map((listing, i) => {
return {
"index": i,
"merchant_id": listing[0],
"listing_id": listing[1],
"score": listing[2],
"description": listing[3]
}
});
// sort the listings by descending score.
output = output.sort((a,b) => b.score-a.score);
console.log(output);
// next, create a hash of merchant: array of listings
// while results per page < numPerPage ...
// ... optimal pagination algorithm in progress..
}

我正在考虑创建一个"merchant": [array of that merchant's listings]哈希，并在我们前进的过程中shift()商家数组的第一个值。但是，当考虑到每页独特的商家偏好要求时，该算法变得有趣。此外，我想出的算法不是很理想。

真的很感激任何帮助！

Answer 1

我认为这可以通过集合和 Map 的组合来解决

key - MerchantId, 
value - PriorityQueue of type MerchantListingDetails

这里的优先级队列是基于分数的最大堆。

商家列表详细信息类由以下
merchant_id组成， listing_id， 得分 描述

1. Initially your Set & Map is empty. 
2. for each MerchantListingDetails // from input line 
check if merchantID is present in set, 
if not then add it to set and append to page1.
if merchantId present in set, then add the merchantId and corresponding object to Map.
3. Continue till your page is full.
Now for page2 :
1. Delete all the entries from set.
2. copy the keys(merchantId's) from Map to set.
3. for each entry from Map,
get the first entry for each merchant and display it on page.
if the merchant has no entries left in map , delete its key from map and set.
4. If the page has required list of output, then again go to step 1 for new page and continue.

注意：这只是我在 10 分钟内能想到的粗略算法。让我知道你是如何实现它的。