0

リスト内の各項目が同時にリストの一番上に向かって機能するように、重みバイアスを許可するリストのシャッフルを実行するための単純なアルゴリズムを誰かが知っているかどうか疑問に思っています。

ページ分割されたディレクトリにビジネス リスティングがあるサイトで作業しています。リスティングを公平に表示する必要があるため、あるビジネスが常に別のリスティングの上/下にあるとは限りません。ディレクトリの純粋なシャッフルは実際には十分ではありません。これのランダムな性質により、特定のビジネスがリスト内の同様の場所に長期間にわたってランダムにシャッフルされる可能性があるためです。リストはゆっくりとリストを上に移動し、時間の経過とともにディレクトリの最初のページに表示される機会が合理的に均等になるようにします。

編集：

Kevin からの感謝を込めて - 私はこれらのルールを形式化しようとしています:

1) n 個のリストの場合、各リストは n 回の「準シャッフル」で 1 番目の位置に表示する必要があります)

2) (あいまい) リストの平均 (?) 順位は、順位 1 に達するまで時間の経過とともに増加するはずです。

3) 任意の 2 つのビジネス (A と B) について、n 回のシャッフルの繰り返しで、A が 50% を超えて B を上回ってはなりませんか?

また、私は非常に複雑で入り組んだ「シャッフラー」を持つビジネスで働いていることも付け加えておく必要があります。これは、ディレクトリ内のビジネスのそれぞれのカテゴリに公平に分散することを主張する多数の有料クライアントをなだめるために必要です。顧客からの苦情は「本当の」問題です。ユーザーは通常、ページ分割されたページの最初の数ページからアイテムを選択するため、クライアントをアルファベット順 (デフォルト) で注文するのは公平ではなく、ユーザーが上から下に読むことを考えると、そうではありません。あるビジネスが常に他のビジネスよりも優れていることを公正に示します。

以前に実装した可能性のある、この問題に対する適切な解決策を誰かが持っているかどうかを知りたいです。

編集：

これらのアイテムがデータベースに保存されていることを考えると、アイテムが最初の位置に達したときに、順序付け (降順) に使用できる、時間の経過に伴う各リストの位置の合計である列を作成できます。リストを 0 に設定すると、リスト内のすべての項目が最終的にリストの一番上に表示されます。問題は、多数のリストの場合、時間の経過とともに、この数がかなり大きくなる可能性があることです...

編集：

データベースをバタンと閉めたくないので、ユーザーがブラウジングしている間は一貫性が必要なので、ディレクトリのすべての表示ではなく、毎晩（1日1回）「疑似シャッフル」を実行するだけです

4

2 に答える 2

0

私が思いつく最も簡単な答えは、Least-Recently-Used (LRU) アプローチを使用することです。

トップページに表示される各要素のタイムスタンプを更新し、「最近使用/表示されていないもの」から「最近使用/表示されたもの」の順に並べ替えられたすべての要素をレンダリングします。

トップページに表示されている要素だけのタイムスタンプを更新する必要があります。

新しい要素が追加され、古い要素がリストから削除されると、アイテムが適切に循環し続けるはずです。

これを微調整するには、アイテムを最初のページに数回貼り付けてから、山の一番下に戻すようにします。これは、データベース内の項目数、新しい要素の追加率、古い要素の削除率によって異なります。

これがお役に立てば幸いです、ローラン。

于 2012-09-17T12:04:12.923 に答える
0

X 社を含むデータベースの場合、X x X グリッドを作成し、各セルに会社名を入力します。特定の会社名は、各行と列に 1 回だけ表示する必要があります。たとえば、それぞれ 1 文字の名前を持つ 10 社のデータベースの場合、そのようなグリッドの 1 つは次のようになります。

ABCDEFGHIJ
BCDEFGHIJA
CDEFGHIJAB
DEFGHIJABC
EFGHIJABCD
FGHIJABCDE
GHIJABCDEF
HIJABCDEFG
IJABCDEFGH
JABCDEFGHI

x 行 y 列の会社は、y 日目にリストの上から x ユニットの位置に表示されます。つまり、会社名の順序付けのために、毎日異なる行を参照します。このスキームは、各要素が少なくとも X 日に 1 回は #1 スロットにある必要があること、および特定の要素が同じ位置に長時間停滞してはならないことの 2 つの基準を満たします。しかし、B社は常にA社の下に表示されるという問題があるため、追加の作業が必要です。

ランダムに 2 つの列を選択し、それらを入れ替えます。列が十分にランダム化されるまで、このプロセスを繰り返します (これを行う線形時間の方法については、Fisher-Yates Shuffleを参照してください)。そのような結果の 1 つが次のようになります。

HIDEJBGCAF
IJEFACHDBG
JAFGBDIECH
ABGHCEJFDI
BCHIDFAGEJ
CDIJEGBHFA
DEJAFHCIGB
EFABGIDJHC
FGBCHJEAID
GHCDIAFBJE

現在、平均して、A は 50% の確率で B の前にいます。実際のパーセンテージは変動しますが、50% を中心としたベル カーブ上にあり、非常に不均一な比率になることはめったにありません。

会社 B は、会社 A が 1 位になったちょうど 1 日後に、常に 1 位のスロットに表示されると文句を言うかもしれません。これが問題になる場合は、行に対してもシャッフルを実行します。

GCDHBIFEAJ
HDEICJGFBA
BHICGDAJFE
JFGAEBIHDC
IEFJDAHGCB
AGHBFCJIED
CIJDHEBAGF
EABFJGDCIH
FBCGAHEDJI
DJAEIFCBHG

これで、次のプロパティを持つ順序付けスキームができました。

長所

  • X 日間のサイクルの過程で、すべての X 社が 1 番目のスロットに表示されます。
  • X 日間のサイクルの過程で、どの企業も同じスロットで停滞することはありません。スロット K を占有すると、残りのサイクルではそのスロットに戻りません。(最悪の場合、しばらくの間は同じエリアを「ホバリング」することもありますが、最終的にはリストのどこにでも行きます)
  • ある企業が別の企業よりも 50% 以上の確率で登場することはありません。所有する企業が多いほど、50% に近づきます。
  • どの企業が 1 位のスロットに表示されるかは予測できないため、企業がスポットライトを浴びた時期に基づいてバイアスを正当に主張することはできません。

短所

  • N 社のデータベースの場合、グリッドの生成には O(N^2) 時間とメモリが必要です。N 日ごとに 1 つだけ生成する必要があり、事前に生成できるため、コストを O(N) 時間まで償却できます。
  • 企業は時間の経過とともに「バブルアップ」しません。この制約は、「どの会社も他の会社よりも上に表示されるべきではない」という制約と矛盾すると思います。すべての企業がほぼ同じ速度で上向きに泡立つ場合、通常、高くスタートした企業は低くスタートした企業よりも上になります。私が示した方法は、相互に排他的な別の要件を満たすために、1 つの要件を破棄した結果です。
  • X 日間の任意の期間で、1/N の確率で企業が 2 日連続で 1 位のスロットに表示されます。これは、たとえば、会社 A がサイクルの最終日に #1 スロットにあり、新しいグリッドを生成すると、会社 A がサイクルの初日に #1 スロットにある場合に発生します。これが望ましくない場合は、A が最初のスロットになくなるまで、別のシャッフルを実行できます。
于 2012-09-17T15:03:19.523 に答える