6

先日、食料品を買いに出かけていたので、財布の中を検索して、クレジット カード、顧客特典 (ロイヤルティ) カード、写真付き ID を見つける必要がありました。私の財布には他にも数十枚のカード (仕事用 ID、他のクレジット カードなど) が入っているので、すべてを見つけるのに時間がかかりました。

私の財布には、カードを入れることができる 6 つのスロットがあり、各スロットの最初のカードだけが一度に最初に表示されます。特定のカードを見つけたい場合は、それがどのスロットに入っているかを覚えてから、そのスロットにあるすべてのカードを 1 つずつ見て見つけなければなりません。スロットの前面に近いほど、見つけやすくなります。

これはほとんどデータ構造の問題だと思いました。それぞれが任意の数の要素を格納できる k 個のリンクされたリストで構成されるデータ構造があるとします。検索を最小限に抑える方法で、リンクされたリストに要素を配布したいと考えています。要素をさまざまなリストに分散するために必要なシステムを使用でき、いつでもリストを並べ替えることができます。この設定が与えられた場合、次のいずれかの仮定の下で、リストを並べ替える最適な方法はありますか?

  1. 各要素にアクセスする確率が事前に与えられており、アクセスが独立している、または
  2. どの要素がいつアクセスされるかを事前に知りませんか?

私がウォレットで使用している非公式のシステムは、カードをユース ケース (ID、クレジット カード、ロイヤルティ カードなど) に基づいて異なるスロットに「ハッシュ」し、各スロット内の要素をアクセス頻度で大まかに分類することです。ただし、これを行うためのより良い方法があるかもしれません (たとえば、ユースケースに関係なく、各スロットの先頭に最も頻繁に使用される k 個の要素を格納するなど)。

この問題を解決する既知のシステムはありますか? これはデータ構造のよく知られた問題ですか? もしそうなら、最適な解決策は何ですか？

(これがプログラミングに関連していないように思われる場合: ユーザーがよく使用されるアイテムのドロップダウン リストをいくつか持っていて、それらのアイテムを見つけるのに必要な時間を最小限に抑える方法で並べ替えたいアプリケーションを想像できます。特定のアイテム。）

4

3 に答える 3

3

一般的な k に対する完全な回答ではありませんが、Sleator と Tarjan によるこの 1985 年の論文では、k=1 の場合のいくつかの動的リスト更新アルゴリズムの償却後の複雑さについて役立つ分析が提供されています。move-to-front は非常に優れていることがわかります。各アイテムのアクセス確率が固定されていると仮定すると、最適な (静的) アルゴリズムで必要とされるステップ数 (移動とスワップ) の 2 倍を超えることはありません。すべての要素は、確率の昇順でリストされていません。

興味深いことに、他のいくつかのもっともらしいヒューリスティック (つまり、目的の要素を見つけた後に前の要素と交換すること、および明示的な頻度カウントに従って順序を維持すること) は、この望ましい特性を共有していません。OTOH、p。2 彼らは、Rivest による以前の論文が、swap-with-previous の下でのアクセスの予想償却コストが <= move-to-front の下での対応するコストであることを示したと述べています。

最初の数ページしか読んでいませんが、私には関係がありそうです。それが役に立てば幸い！

于 2013-01-07T03:25:31.743 に答える
0

スキップリストを見る必要があります。急行列車と普通列車が混在する電車システムの駅配置にも同様の問題があります。急行列車は急行駅のみに停車しますが、普通列車は普通駅と急行駅に停車します。始発駅から任意の駅まで移動する際の平均停車回数を最小限に抑えるには、急行停車駅をどこに配置する必要がありますか。

解決策は、ステーションを 3 進数 (つまり、1、3、6、10 など、T_n = n * (n + 1) / 2) で使用することです。

これは、すべてのストップ (またはカード) がアクセスされる可能性が等しいと仮定しています。

于 2013-01-07T02:56:01.523 に答える
0

n枚のカードのアクセス確率が事前にわかっていて、k個のウォレットスロットがあり、アクセスが独立している場合、貪欲なソリューションが最適であることは明らかではありませんか? つまり、最も頻繁にアクセスされる k 個のカードがポケットの前に配置され、次に頻繁にアクセスされる k 個のカードがすぐ後ろに配置されます。(確率の高いカードの前に確率の低いカードをランク​​付けする必要はありません。)

アクセス確率がわからないが、それらが存在し、カードアクセスが独立していることは知っている場合、同様にカードを並べ替えると思いますが、代わりに、これまでに見られたアクセス数で並べ替えるのが漸近的に最適です。(Move-to-front もクールですが、ここで使用する明白な理由はわかりません。)

カードの移動にもペナルティを課すと、おそらく何か面白いことが得られます。独立しているかどうかに関係なく、カード アクセスの既知の確率分布がある場合、アクセスするたびに貪欲にカードを並べ替えます。

于 2013-01-07T06:08:29.853 に答える