ひしだまの変更履歴

ひしだまHPの更新履歴。
主にTRPGリプレイの元ネタ集、プログラミング技術メモと自作ソフト、好きなゲームや音楽です。

1から「10のn乗」までの合計を算出するプログラム

2012-03-28 21:18:14 | PG(Scala)

Hadoopで1~100の合計を算出するプログラムを考えてみた訳だが、冷静に考え直すまでもなく、Hadoopの出番じゃないんだよな(爆)
しかし100程度だからいけないのであって、もっと桁数が大きくなればHadoop向きのサイズになるんじゃないか? intの上限(Javaなら32bit)を超える程度だと「longを使えばー?」と言われてしまうので、longは十進数だと18桁まで入るから、19桁の数、つまり「1から10の19乗」までの合計を出すなら、いける!?
JavaならBigIntegerというクラスがあるので、メモリーの許す限りの桁数の整数は扱えるし。

とは言え、1つのMapTaskで10億回(10の9乗)の加算をやるとしても、10の10乗(つまり100億)個のMapTaskが必要となる計算。1000ノードのHadoopクラスターで、1ノード当たり1千万回のタスクを実行か。10コアのCPUだとして、1コア当たり百万タスク。
やっぱり現実的じゃないかもなー(汗)


同じく現実的ではないが、Scalaなら、BigIntegerに相当するBigIntというクラスがあるので、Intでのプログラムと同様にシンプルに書ける。

//Int版
def f0(n: Int) = (1 to math.pow(10, n).toInt).par.sum

//BigInt版

def f1(n: Int) = (BigInt(1) to BigInt("1" + "0"*n)).par.sum

BigIntには初期値としてStringを渡せる。"0"*nは、"0"をn個並べた文字列になるので、10のn乗を作れる。これでばっちり!
と思いきや、toメソッドにはIntの限界があるようで、エラーになってしまった…。

scala> f1(19)
java.lang.IllegalArgumentException: 1 to 10000000000000000000 by 1: seqs cannot contain more than Int.MaxValue elements.

ちなみに、もっと少ない数でもOutOfMemoryになったよ。何故だー?orz

scala> f1(7)
java.lang.OutOfMemoryError: Java heap space


仕方ないので等差数列の和の公式にしてみたら、ちゃんと出来た。
BigIntはIntと同じく*や+が使えるので、コーディングもしやすい。 

def f2(n: Int) = { val m = BigInt("1" + "0"*n); (m * (m+1)) / 2 }


しかし最も短くシンプルなプログラムは、これだと思うw
(自分の中では半端な証明しか出来てないけど、たぶん合ってると思う)

def f3(n: Int) = ("5" + "0"*(n-1)) * 2

この件では、Hadoop君はScalaちゃんに敵わないようだ(笑)


コメント    この記事についてブログを書く
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする
« 1~100を合算するHadoopプロ... | トップ | 特定バージョンのCDHのインス... »
最新の画像もっと見る

コメントを投稿

PG(Scala)」カテゴリの最新記事