プログラミング

駆け出しハッカー部の仲間たち {素数との戦い}

お正月からあそんでいる駆け出しハッカー部。きょうはどんな問題をといているのかな?のぞいてみましょう。

Project Euler #10: Summation of primes

The sum of the primes below  10 is 2+3+5+7=17 .Find the sum of all the primes not greater than given N.

source: https://www.hackerrank.com/contests/projecteuler/challenges/euler010

先生
先生
問題を先生が日本語で解説してあげる
先生
先生
10以下の素数は 2,3,5,7 です。その和は17になります。与えられたNより小さい素数の和を求めなさい

先生
先生
簡単ね。チョチョイのチョイよね。部員たちよ。でもこの子たち11日からこんなことしててもしかして非モテかしらwww

学士
学士
エラトステネスの篩(改)完成だぜ。まだ#10解いてないけどね。

平井
平井
エラトステネスの篩。初めて聞いた。なるほどなるほど。

億ラビット
億ラビット
僕はpythonlistの効率を追求した結果こうなりました。エラトステネスの過程で無駄な処理を一切省いたつもりです。そしてやってることは上のディスカッションと同じw104729が10000番目の素数と事前に調べてずるしましたw

先生
先生
ちょっと解説してあげようかしら。エラトステネスのふるい(篩)ってのはね、大昔の人が見つけた素数を特定する方法よ。今でも素数を見つける方法としてこの方法の改良版が利用されているわね。絶対覚えておいて。
先生
先生
考え方は簡単よ。自然数を2からあがって行くの。たとえば100までの素数を求めるとするわね。そのときに、2の倍数を排除していくのよ。だって割り切れるってことはその数字は素数の要件満たさないわよね。これが終わったら3。そうやって100まで見ていけば素数だけが残るってわけ。forループでそれぞれの数字が割り切れるか総当たりを使ったりしたらタイムアウトになるわよ。
先生
先生
まあさすがだわね。駆け出しハッカー部員たちは
億ラビット
億ラビット
学士さんのエラトステネスの篩(改)のコードで再帰する度に新しいlistを作るのってその分負荷がかかるんですかね?この行で古いnumsを毎回新しいlist作って上書きしてますよね?

学士
学士
ぬぬ?
億ラビット
億ラビット
iでインデックスしてwhileループでlist.pop(i)ってやりました。インデックスでpopだと軽いとおもうんですよね。C++とかで処理するとArrayの全書き換え的な処理は重くなりそう。。。ただ、実はわかりませんw。が、このささいな違いで上級とかだと引っ掛かるんですよね。なのでC++とかうまい書き方ができない言語が実は最強説w
学士
学士
リスト内包表記神話を盲信してました。特に根拠はないですけどちょっと弄ってみますー
学士
学士
リスト内包表記のほうが早いですよー
億ラビット
億ラビット
確かにlist作るなら内包表記のが速そうです。が、そもそも毎再帰lisitを作らなくてよい説?学士さんのコードだと再帰毎にその処理繰り返してますよね?
学士
学士
あー。なるほど。まってでもこれって Whileの中でWhileまわしてるだけ。あまり遅くない説
億ラビット
億ラビット
内包表記でlist全書き換えの方が全然速いってことですかね?ふーむ。Pythonは奥が深い。中でなにしてるんだろう。ちょっと研究しておきます。
学士
学士
なかなか。でもこれはできたけど#10解いてないんですよ。テヘペロ。n未満の素数の個数がわかんなくて、結局forで探すしかないのかなー、ってところで思考停止してました。
億ラビット
億ラビット
あ~僕素数求めたあとに1から1000000までforで回してlist作りました
平井
平井
> 言語仕様の裏にアルゴリズム隠れるIDE使えばコーディングしながらでも簡単に見れますよw pythonだとpycharmが便利。GoとかJava,Scala,KotlinとかIntelliJ使うとサクサク
億ラビット
億ラビット
アルゴリズムが見えるってどういうことだろう?こういうやつですか?w
Pythonの内包表記はなぜ速い? : DSAS開発者の部屋
先生
先生
Pythonの内包表記はすごいみたいね。これはみんなちゃんとマスターしておいてね。この記事がいいと思うよ。
pythonの内包表記を少し詳しく

数時間後

学士
学士
ガッテムー。解けたけどタイムアウト。全然おせええー

 

億ラビット
億ラビット
solveの中でprimesをループしてる部分を問題毎にやらなければクリアできると思います。最初に一回だけループしてすべてのパターンを先にlistに格納してsloveはそれを参照するだけというのはどうでしょう?
学士
学士
素数出すループと答え作るループを回すとタイムアウトになっちゃったんで、このやり方でガッテムしてました。1回のループで答え作れそうな気もしますが、なんだか複雑になりそうだったんで後回にしちゃいました。気が向けばリトライ!
億ラビット
億ラビット
むしろeratosthenesの中に和を求める部分も組み込んだらさらに速そうです。僕そっちで書き直して見ます。
億ラビット
億ラビット
わかりました。timeitでテストしてみたのですが。。。 まず昨日僕が書いたlistをpopするコードは論外でしたw。10 ** 6に至っては多分時間かかりすぎで求められない。多分リストの操作自体してはいけないとの結論。popremoveappendとか。。。 それから、学士さんのエラトステネスもやはりループ毎にlistを書き換えてるので内包表記といえど遅いです。 で僕が上で書いた効率悪いコードなんですが、listを最初に一回だけ作って、あとはboolの値を変えてるだけなのでループのロジックは効率悪いですが、それよりもlist自体を操作してないので学士さんのエラトステネスの5倍速い処理速度でしたw
10回ループで10 ** 6を求めるのにかかった平均時間
getPrimeArr(10 ** 6)   0.684
エラトステネス(10 ** 6)   3.798
学士
学士
エラトステネスを弄らなくてもクリアできました。凡ミス疑惑。記録を残してないので真相は闇の中ですが。
億ラビット
億ラビット
僕エラトステネスの中に和を求める処理を組み込んで、これで全問秒殺(1秒以内?)でした。

学士
学士
億ラビットくんの回答はみないぞ。みない!!
はるか
はるか
とけん。何かリスト操作でオーバーヘッドがあるのかな。。。涙
学士
学士
要素書き換えにしたらいいですよ
億ラビット
億ラビット
多分詰まりどころは2つあって、まず前提として素数を求めるのにエラトステネスの篩っていうのを使って効率化しないと時間切れになるのと、これを使っても問題毎に素数を求め直してると間に合わないので最初に一回だけ計算してキャッシュしないと6、7でT<=10**4が響いて時間切れになりますね。
それから上で学士さんと話し合ってたのは素数を求める過程でなんらかの形でリストを操作すると凄く時間がかかるということですね。popremoveappendやlist全体の置き換えも遅延のもとになります。要素を上書きするだけの方法であれば全問1秒以内にクリアできました!エラトステネスの篩に和を求めるプロセスもドッキングできると今のところ最速です。

 

clearNB
clearNB
今日は素数の問題らしいので、余談。 素数の存在は無限にあるので、現在も素数を出しているそうです。 (どんだけ暇人なのか・・・) 学術研究によると、2018年で桁数は24,862,048桁に及んだそうです。
先生
先生
ClearNB君こんにちは。 読者のみなさん、彼は現役高校生。海外で仕事がしたいらしいわね。最近の高校生はどうなってるのかしら。
clearNB
clearNB
解けました!入力後の計算ではタイムアウトしてしまうといったことを想定して、事前計算を取り入れました。 問題の制約通りに作ったので、あまり参考になれないと思いますが、このコードでは、最大0.69秒で全て完了します。

先生
先生
ClearNB君はJava使いだわね。これは懐かしい。C系の言語は読みやすいわね。booleanを使うのは賢いわね。エラトステネスのふるいを使ってるわね。
億ラビット
億ラビット
おおっ!僕の解答より速いですね。やはりboolのリストにするのがポイントな気がします!

 

clearNB
clearNB
boolean は true or false ですから、それで効率よく出せるかなと予想しました:grin: まぁ、今回の難易度がMedium なのは、10^6と制約にあった時点で察しました(笑)でも、Python の構文のシンプルさはいいですね。
先生
先生
平井君、いつもめっちゃ早いのに、今日は提出遅いわね。
平井
平井
Elixirで解いてみるので時間かかりそう 今外なので戻ったらチャレンジ。
先生
先生
まあ。新しい言語で遊んでいるのね。平井さんはすきだわねw。
3時間後
はるか
はるか
泣きそうです。最初のコードで問題なかったのに半日無駄にしてしまった。Nの長さを 10**5 で計算していた。だからずーーーと #6 #7 通らなかった涙。泣きながらめちゃチューンしたCのコードみてください。これが僕の最速です… 0.01秒記録しました

 

億ラビット
億ラビット
おおっ!Cだと爆速ですね!pythonだと#7が0.55sでした。奇数だけループしてるところと、arrayをひとつしか使わず1でマークしてるところがうまいですね:laughing: お疲れさまです!普通にベストアンサー過ぎてこれ以上の思いつかないです

 

clearNB
clearNB
C言語・・・Javaの前者・・・先輩、さすがです! Javaの場合は、#7 は0.54s ですね。
平井
平井
Elixirで解いてみたw めがチカチカする
先生
先生
わお。 do end がならんでるわ。原色いっぱいね。

今日の学び

  1. 素数を求める時はエラトステネスの篩(ふるい)を使おう
  2. Pythonの内包表記は早い。でも何度もリストを作り直す構造は見直そう
  3. 必要に応じて、Booleanを使って効率化を
  4. C言語は爆速
  5. Elixirはカラフル

ということで、駆け出しハッカー部の1日が終わった。どうやらこれはフィクションではなく実話のようだ。覗きたいかたはこちらに行くと見えるらしいよ。プログラミングの腕あげるにはいい場所ではないかな?

 

 

では