javascript - 分页算法 : display ranked search results for unique eCommerce merchants

Question

嗨 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

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

key - MerchantId, 
value - PriorityQueue of type MerchantListingDetails

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

MerchantListingDetails 类包含以下内容-
商户编号, 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 分钟内可以想到的粗略算法。让我知道您是如何实现的。