0

我想知道是否有人知道一种简单的算法来执行列表的洗牌，该算法允许权重偏差，以便列表中的每个项目同时朝着列表的顶部工作。

我正在一个网站上使用分页目录中的企业列表，并且列表需要公平显示，因此一个企业不能总是高于/低于另一个列表。目录的纯粹洗牌是不够的，因为它的随机性可能会导致任何给定的企业在很长一段时间内随机洗牌到列表中的相似位置，所以我想提供一些权重，以便每个列表被慢慢地推到列表中，以便随着时间的推移，它们有相当平等的机会显示在目录的第一页上。

编辑：

在凯文的感谢下 - 我正在尝试将这些规则正式化：

1）对于 n 个列表，每个列表必须在 n 个“准随机播放”中显示在位置一）

2）（模糊）列表的平均（？）位置应该随着时间的推移而增加，直到它到达位置 1

3) 对于任意两个业务（A 和 B），在 n 次洗牌迭代中，A 不能超过 B 超过 50% 的时间？

我还应该补充一点，我为一家拥有极其复杂和令人费解的“洗牌器”的企业工作，这对于安抚大量付费客户而言是必要的，这些客户坚持在我们目录中的各个业务类别中公平分配。客户的投诉是一个“真正的”问题，因为用户通常从前几个分页页面中选择项目，按字母顺序（默认情况下）对客户进行排序是不公平的，并且鉴于用户从上到下阅读，这不是公平的是，一项业务始终高于另一项业务。

我很想知道是否有人对他们以前可能已经实施过的这个问题有一个整洁的解决方案。

编辑：

我有一个想法，考虑到这些项目存储在数据库中，我可以有一个列，它是每个列表位置随时间推移的总和，当一个项目到达第一个位置时，我可以使用它来排序（降序）然后我可以将列表设置为 0，这意味着列表中的每个项目最终都会排在列表的顶部。问题是，对于大量列表，随着时间的推移，这个数字可能会变得相当大......

编辑：

我不想猛击数据库，我需要在用户浏览时保持一致性，因此我只会每晚（每天一次）执行“伪随机播放”，而不是在目录的每次显示上

4

2 回答 2

0

对于有 X 个公司的数据库，创建一个 X x X 网格，并用公司名称填充每个单元格。任何给定的公司名称都应该在每一行和每一列中出现一次。例如，对于一个包含十家公司的数据库，每家公司都有一个字符名称，一个这样的网格将如下所示：

ABCDEFGHIJ
BCDEFGHIJA
CDEFGHIJAB
DEFGHIJABC
EFGHIJABCD
FGHIJABCDE
GHIJABCDEF
HIJABCDEFG
IJABCDEFGH
JABCDEFGHI

第 x 行第 y 列的公司将在第 y 天从列表顶部出现 x 个单位。换句话说，每天您都会参考不同的行来对公司名称进行排序。此方案满足您的两个标准：每个元素必须每 X 天至少出现一次 #1 插槽，并且任何特定元素不应长时间停滞在同一位置。但是仍然存在B公司总是出现在A公司下面的问题，所以还需要做一些额外的工作。

随机选择两列并交换它们。重复此过程，直到列充分随机化（有关执行此操作的线性时间方法，请参阅Fisher-Yates Shuffle ）。一个这样的结果可能如下所示：

HIDEJBGCAF
IJEFACHDBG
JAFGBDIECH
ABGHCEJFDI
BCHIDFAGEJ
CDIJEGBHFA
DEJAFHCIGB
EFABGIDJHC
FGBCHJEAID
GHCDIAFBJE

现在，平均而言，A 将有 50% 的时间在 B 前面。实际百分比会有所不同，但会落在以 50% 为中心的钟形曲线上，而且很少会达到非常不均匀的比例。

公司 B 可能会抱怨它总是在公司 A 出现在 #1 之后的第二天出现在 #1 插槽中。如果这是一个问题，那么也对行执行洗牌：

GCDHBIFEAJ
HDEICJGFBA
BHICGDAJFE
JFGAEBIHDC
IEFJDAHGCB
AGHBFCJIED
CIJDHEBAGF
EABFJGDCIH
FBCGAHEDJI
DJAEIFCBHG

现在您有一个具有以下属性的排序方案：

优点

  • 在一个 X 天的周期中，所有 X 公司都出现在 #1 位置。
  • 在 X 天的周期中，没有一家公司会停滞在同一个时段。一旦它占据了槽 K，它将在循环的剩余时间内不会返回到该槽。（在最坏的情况下，它仍然可能在同一区域“徘徊”一段时间，但最终它会在列表中的任何地方出现）
  • 没有一家公司出现在另一家公司的时间超过 50%。你拥有的公司越多，它就越接近 50%。
  • 哪家公司将出现在排名第一的位置是不可预测的，因此没有人可以根据公司何时受到关注而合理地声称存在偏见。

缺点

  • 对于 N 个公司的数据库，生成网格需要 O(N^2) 时间和内存。您只需要每 N 天生成一个，并且可以提前完成，因此您可以将成本摊销到 O(N) 时间。
  • 公司不会随着时间的推移而“冒泡”。我认为这个约束与“任何公司都不应该出现在另一个太多”约束相冲突；如果所有公司都以大致相同的速度向上冒泡，那么起步较高的公司通常会高于起步较低的公司。我给出的方法是放弃一个要求以满足另一个互斥要求的结果。
  • 对于任何 X 天的时间段，公司有 1/N 的机会连续两天出现在 #1 位置。例如，当 A 公司在周期的最后一天位于 #1 槽时，当您生成新网格时，A 公司在周期的第一天位于 #1 槽时，就会发生这种情况。如果这是不可取的，您可以执行另一次随机播放，直到 A 不在第一个插槽中。
于 2012-09-17T15:03:19.523 回答
0

我想到的最简单的答案是使用最近最少使用 (LRU) 方法。

更新首页中显示的每个元素的时间戳，并呈现从“最近最少使用/显示”最先到“最近使用/显示”最后排序的所有元素。

这应该可以解决问题，并且涉及更新仅显示在首页中的元素的时间戳。

随着新元素的添加，旧元素从列表中删除，这应该保持优雅地循环项目。

您可以通过允许项目在返回到堆的底部之前粘附到首页进行几次迭代来微调这一点。这将取决于数据库中的项目数量、新元素的添加率、旧元素的删除率。

我希望这会有所帮助，劳伦特。

于 2012-09-17T12:04:12.923 回答