image

  • フォト Amazonギフト券
    ※この時計の時刻は、閲覧しているパソコンのものであり、必ずしも正確な時間とは限りません

検索

最近のトラックバック

無料ブログはココログ

« ピックアップ:今こそiPhone版Evernoteをマスターしよう, 2010年本屋大賞を集合知を使って予想してみる, etc... | トップページ | ピックアップ:twitter経由のみで新卒採用, 民主党政府「両親いない子」は子ども手当の対象外に, etc... »

2010-01-23

Scala + remote actor で魔法陣を

魔法陣で試すべき組合せを 複数マシンに割り振り、 解を返させる例を Scala で作った。
 http://go.2ch2.net/u/8NAJtZ

3 x 3 魔法陣の解を数え上げるには、 9! 通りの組み合わせをすべてチェックすればよい。
9! 程度なら1 CPU でもなんとかなるかもしれないが、25! とかは無理。
そこで、複数マシンで分散処理させることを考える。

まず  [0 ... 9!] の範囲の数字と、順列を 1 対1に対応させることを考える。
これができると 複数マシンへのタスク割り振りは、(チェック開始の整数値、チェック終了整数値) を決める事で済ませられる。

順列 n! 通り と 数字の対応は次のようにする。
順列の作り方は、 (1,2,...., n) のリストから 何番目の要素を取ってきて並べたか で表現することができる。(最初の要素を0と数える)
3!の順列の場合で説明する。
取り方が (0,0,0) なら 順列 (1,2,3) ができる
取り方が (2,1,0) なら 順列 (3,2,1) ができる。(最後の取り方は、残りは1つだから常に0)

この取り方の数字列 (a, b, 0) に対して 3*a + 2 * b という数値を対応させる。
これは すべての順列から (0 ... 3! -1 の数字) への対応となる。

逆に (0...3!-1) の数字に対して、
数値を 2!, で割った商、その余りを2 で割った商、0 の3つの数字 でつくられる3つの数字の組は、リストの何番目の要素を取っていくかの操作に対応させることができる。

順列          取り方     整数
---------------------------------
1 2 3        0 0 0        0
1 3 2        0 1 0        1  // 2 * 0 + 1
2 1 3        1 0 0        2  // 2 * 1 + 0
2 3 2        1 1 0        3  // 2 * 1 + 1
3 1 2        2 0 0        4  // 2 * 2 + 0
3 2 1        2 1 0        5  // 2 * 2 + 1
---------------------------------

類似の方法で 組み合わせ (n の n乗 通り) の場合分けも 数字へマップすることが可能。

« ピックアップ:今こそiPhone版Evernoteをマスターしよう, 2010年本屋大賞を集合知を使って予想してみる, etc... | トップページ | ピックアップ:twitter経由のみで新卒採用, 民主党政府「両親いない子」は子ども手当の対象外に, etc... »

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/184434/47371773

この記事へのトラックバック一覧です: Scala + remote actor で魔法陣を:

« ピックアップ:今こそiPhone版Evernoteをマスターしよう, 2010年本屋大賞を集合知を使って予想してみる, etc... | トップページ | ピックアップ:twitter経由のみで新卒採用, 民主党政府「両親いない子」は子ども手当の対象外に, etc... »

mokuji

2013年12月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

google

  • twitter
  • __
  • _
    Googleボットチェッカー

合わせて読む

  • 合わせて読む
    フィードメーター - katoy: cocolog あわせて読みたい

リンク