折りたたみを展開する

おぼえ書き、まとめ、発表など

担当者探しゲームをした

以下のような問題があった。

 

あなたは、ある要件Xを尋ねるために役所Aにいった。要件Xの担当者が役所Aにいるのは間違いない。ただし、とても大きな役所だ、部署は何百とあるし、従業員は何千といる。その市役所では、要件がある人は入り口にある受付で訪ねる習わしだ。効率化ってやつ。

 

あなたは、要件Xの担当者を受付で尋ねる。

 

f:id:Rlan:20170603212929p:plain

 

ただし、受付の担当者も忙しい。役所すべての人を知ることはできない。とても大きな役所なのだ。だが、彼・彼女達は適切な案内をしてくれる。要件Xについて話すと、どの担当部署に行けばいいかを教えてくれる。「それは2Fの人事課2係ですね」とか、「別館3Fの安全課ですね」、とかだ。

  

あなたは、要件Xの担当部署がY課であると教えてもらった。Y課を訪れると、机がズラッと並んでいて従業員が仕事をしていた。ここで、大声を出して、要件Xの担当者を探すのも気が引ける。

 

f:id:Rlan:20170603213134j:plain 

 そこで、あなたは一人ひとりに話かけることにした、「Xの担当者はあなたですか?」と。さて、この時、担当者を見つけるまでの期待平均時間はいくつだろうか?ただし、問題を解くために以下に詳しい追加の設定を書いておく。

 

  • 従業員の数はn、部署の数はm
  • 部署1つあたりの従業員の数\alphaは一様分布で\alpha = n/m
  • ある従業員ijが一緒になる確率は1/m
  • 受付→部署に行く時間は単位時間1
  • 部署の従業員に担当者かどうか尋ねるのにかかる時間も単位時間1
  • ただし、部署に従業員が1人だけの場合は担当者がだれなのか自明なので0
  • ただし、部署の従業員は1以上
  • 毎回、部署で最後に訪ねた人が担当者

 最後の設定だけ不自然だが勘弁して欲しい。

 

例えば、

  • 受付→部署A→部署Aに10人の従業員

だと、かかる時間は1+10で11単位時間である。

 

また、

  • 受付→部署B→部署Bに1人の従業員

だと、かかる時間は1+0で1単位時間である。

 

さてはて、平均所要時間の期待値はいくつだろうか?

 

もし、各部署に1人しかいない場合は期待平均時間は1であることを確認して、従業員が複数いる場合の期待値平均時間を考える。

 

 

f:id:Rlan:20170605202715p:plain

 

ただし、X_{ij}は従業員ijが同じ部署だった時に1になる。

 

 

ハッシュ関数アルゴリズムの(期待)計算時間の一部のこのように書き換えて計算してみた。毎回、部署で最後に訪ねた人が担当者という不自然な設定もそのため。最初の受付がハッシュ関数である。

 

興味がある方は、以下の本のSection 11を参照して欲しい。

 

 

Introduction to Algorithms (MIT Press)

Introduction to Algorithms (MIT Press)

  • 作者: Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein
  • 出版社/メーカー: The MIT Press
  • 発売日: 2009/07/31
  • メディア: ペーパーバック
  • 購入: 5人 クリック: 90回
  • この商品を含むブログ (19件) を見る