どうも、学校が週一と家族に話したらほぼニート扱いされているfsyuuです。
さて、タイトルの通りですが読み込み速度が遅いサイト･･･嫌ですよね･･･。
自分も検索してて、なっかなか開かないサイトがあるとイライラします！！
そこでGoogleさんが導入したのがこれ！
黄色の！マーク＋Slow to loadと書かれています！
このサイト開くの遅いよ～、という烙印です。
ユーザーからしたら遅いサイトを避けられるので便利ですねー、さすが！！
製作者はユーザーがきてくれなくなっちゃう為、処理時間のかかっている見直さなければなりません。
ただ、この烙印自分の回線速度が遅い場合も表示されるようなので、その点は注意が必要です！
どちらにせよ表示速度が遅いのはユーザーが離れていく原因でもあるので、製作者は気をつけましょう！
参考にさせていただいたサイト：
どうも、fsyuuです。
今日の朝方ブログを始めたのですが6時までやってたせいで寝過ごしてしまい貴重な土曜日を失いました。
かえせ僕の休日うううぅぅぅ！！
さて、タイトルの通りグーグルの新検索機能について話していきたいと思います。
その名もLocation Aware Search！！
Location Aware Searchとは、Googleの新検索技術のことでスマホの位置情報を使い付近の建物や地名、お店、川など名称がわからないものを調べることができる、というものです。
例えば、「カフェの営業時間」や「川の長さ」などですね！
新しい場所に行ったときはあいまいなものを検索したいことが多いと思うので非常に便利そうです！！
まだ日本語には対応していないようですが、今後とても楽しみですね！
特に自分はとてつもない方向音痴でGoogleMapがあっても迷うことができるので重宝することになりそうです･･･。
【追記】7月6日 正解コード例載せました
ネタバレにならないように一番下に載せたので、ソースだけ見たい方は一番下までスクローーーール！！
その上に参考になったコメントも載せたのでぜひ！
ちなみにこれはあくまで一例であって正確な解き方とはまったく違うかもしれませんし、まだまだ甘い部分もあるのでそれを踏まえて見ていただけると助かります･･･！
どうもfsyuuです。
とうとう期限の7月6日10時を迎えましたね！挑戦した人は1000人弱だったようです。
つまり、1000円以上は確定だー！！うひょー！٩( 'ω' )و
「ホリエモンからの挑戦状」の挑戦受付が終了しました！ 最終的に986名の方にご挑戦いただきました！ありがとうございます！ 100万円山分け対象者は何人になるのでしょうか？楽しみですね～うふふ ご案内メールをお待ちくださいね☆うふふふふふふふふ #horiemonchousen
— CodeIQ [コードアイキュー] (@codeiq) 2015, 7月 6
今回はある程度詳しく書きました。
自分で解きたいって人、また
一番下に正解例を載せましたので見たくない人は注意してください。
codeIQの3周年特別企画と言うことでSNS株式会社の堀江貴文さんが問題を出題していました。
【3周年特別企画】ホリエモンからの挑戦状(https://codeiq.jp/q/1618)
なんと！！！解けた人たちで100万円を山分けできるらしいです！！金！！！！金！！！！！
キャンペーン期間は終了しましたが、まだ挑戦は可能なのでぜひ！
処理的にはかなり簡単なものだと思います。
この問題の難しいところは処理時間の制限！
1秒以内に処理するのは何も考えないでやるとかなり厳しいです。
すごい面白かった！勉強にもなりました！(小並感)
ちなみに自分の処理時間結果です！もっと早く出来るよゴミ！って人いたら是非どんな方法でやったかコメントまたは僕のTwitterにリプで教えてください！
自分もこの問題、すっごい苦戦して2,3日は悩みました･･･。
ここからヒントを書いていきますが、自分はJavaで書いたので言語の違いは考慮していただけると助かります。
処理時間の制限がきつい今回の一番重要な部分となります。
まさか小さい順に足していき･･･すべての通りを試したりしていませんよね･･･？ だとするともっといい方法があるはずです！
自分が考えた方法を３つ紹介していきます。
今回の想定「目標値が300で入力される数字の個数は100個の場合とします。また、重複した数字は入力されません。数字はinput[]という配列に格納されます。」
１．入力された値をソートする
やらなきゃ始まらないですね！
どんな言語でも配列をソートする関数はあります。
アルゴリズムとは言えないかもしれませんが、この処理が次以降に重要となってきます。
２．数字の足しかた
これは非常に重要な部分です。
ただ単に昇順（小さい順）に足していけば、{1,2,3},{1,2,4},{1,2,5}･･･{1,2,197}･･･
さすがに無駄な処理が多すぎますよね･･･
降順（大きい順）に足していくと{200,199,}オーバー！次へ,{200,198,}オーバー！･･･
さっきよりは早くできるのかな？ただ、{200,99,1}というところにたどり着くまでに結構かかりそうな予感はします。
じゃあどうすんだよ！！！という話ですけど
1つ目の数字は降順に、2つ目の数字は昇順に足していけばいいのです！
つまり、
{200,1,?},{200,2,?}･･･
という感じです。
こうするとどんなメリットがあるのか？
計算可能な数字のセットから順に見ていけることです！
オーバーしたり、足りなかったりと悩まされなくて済むわけです。
でも{200,1,?}と分かっても「?」を求めるのに2,3,4,･･･と見ていかなきゃいけないから変わんないじゃん！という人は
次へ！
３．配列に含まれる数字で計算をする
２で計算の仕方はお話しました。
実は最後の？を一発で出す方法があります！
{200,1,?}ならば、目標の 300から2つの数字を引いて
300-200-1=99
？が99であればいいですね！
･･･････簡単！！
そして99が配列にあるかを調べます。
･･･あった！！
はい、1つ終わりです。次は{200,2,?}へ。
こうすることで冗長な処理を大幅に減らすことが可能です。
また、1つ目の数字と2つ目の数字も配列内の数字をつかってあげるといいですねー！
処理を書くのがめんどうかもしれませんが確実に時間が縮まる部分なので、頑張って実装してみてください。
４．しきい値を設ける
これは非常に重要です。
具体的に説明していきます。
目標値の1/3+1は 300/3+1 = 101
101が一番大きい数字とすると、300になる組み合わせは {101,99,100}です。
しかし100になるとどうでしょう。
{100,99,?}
？に101が入れば確かに成り立つんですが、この組み合わせってもう一回やってますよね？必要ないです。
つまり、一番大きい数が目標値の1/3+1を下回った場合は処理を終了してよいのです！
また、1番目の数字が201のとき、
{201,1,98},{201,2,97},･･･{201,50,49} です。
{201,49,50}以降は同じ組み合わせになってしまうのでやる必要ないですね。
これは 2番目の数字＝＜3番目の数字 になったときは数える必要がないというものです。
さらに、1番目の数字が一番大きくなくてはなりませんから、
3番目＜1番目
という関係も忘れてはなりません。
{101,1,198}
これを許可しないようにしてください。
まとめると、
目標値の1/3+1を下回った場合、処理を強制終了。
「2番目＜＝3番目」、「3番目＜1番目」
の関係が崩れた場合は数える必要がないので即次へ行くことができる。
この場合はif文でbreakするなどして無駄な処理をしないようにしましょう。
プログラミング言語自由に選べるので自分の得意言語で書いてる人多いと思いますが、言語によって処理速度全然違います！
スクリプト言語(PHPやPythonなど)使っていてギリギリだめだぁ･･･別に言語にこだわりもないから早くしたい･･･って人はCやJavaに書き直してみましょう！
結構短縮できるようです。
このサイトで詳しく説明してくれています。
俺の言語がこんなに遅いわけがない！？〜C, Java, PHP, Python, Rubyによるプログラミング言語 速度比較〜
ここまではやってるわ！けど出来ないって人はここです！
最適化とは「処理効率がよくて見やすいコード」のことです。今回は見やすくなくてもいいんですけどね。
自分もここで10分半かかっていたところを0.3秒まで縮めました。
まずこのコードを見てください。
一見何も問題なさそうですが、かなり無駄な部分が多いです。
まずい点が３つあるので考えてみてください。
・・・・・・・・分かりましたか？
1つ目
1行目の「i<input.size()」です。
forの条件内にこれを入れているということはループのたびに呼び出されるわけです。
毎回配列の大きさを調べてちゃってることになります。
こういう何度も呼び出される部分は最初に変数に代入して使いましょう。
2つ目
3行目のinput[i]の部分です。
1つ目を見たときに勘付いた方は素晴らしいです！
ここは2行目の上で変数に入れてあげればわざわざ何回も配列のi番目を探さなくて済みますよね！
3つ目
これまた3行目の「int sum」という宣言の部分です。
毎回intと宣言する必要･･･ありませんよね･･･？
これはfor文の外で宣言しちゃいましょう！
細かいことかもしれませんが、これも重要な1歩です。
そして修正後がこちら
おい！行増えてるじゃねーか！！とかツッコミもらいそうですが･･･
プログラム的には無駄な部分がなくなり綺麗になりました！
この処理ですが実際にかかった時間を5回計測した平均を比べると
sampleBefore : 152000 * 10^(-9) 秒
sampleAfter : 98000 * 10^(-9) 秒
でした。
これだけで約33％も処理速度が速くなっていることが分かります。
ちなみに計測のやり方は「[言語名] 処理時間 計測」とかで出てきます！
今回は、System.nanoTime()で開始地点と終了地点の時間を引いて計測してます。
10分半から0.3秒まで縮めたのは配列内の数字を探すときcontainsからbinarySearchとかいう関数に乗り換えたからかもしれないです。
まだ早くできるようです！
コメントより
>ybさん
最適化についてですが、まだ少し無駄が有りますね。
言語によりますが、C++では
1.後置インクリメント→前置インクリメント
2.添字アクセス→イテレータ
と置き換えると早くなります。
前置インクリメントはコピーを作らないので、後置インクリメントより早い。
イテレータはポインタ演算に帰着するため、添字アクセスより早い。
最適化まとめ
よく使う配列の呼び出しや、無駄な宣言、不要な変数など書いているうちに色々なものが積み重なっているので出来るだけ楽にしてあげましょう。
もう一度コードを見直してあげてください。
割と詳しく解説をしました。
これまで出来なかった方も是非トライしてみてください。
間違いを発見されたりした場合もご指摘いただけるとうれしいです。
期間が終わったら自分のソースをアップしたいと思います。
アップしました！
まだ挑戦していない方も是非チャレンジしてみてください！
そしてこの記事が役に立った場合は一言コメントかリプくれるとすっごい嬉しいのでぜひぜひ投稿してください！
以後ネタバレ注意
複数のコメント頂きありがとうございます！
一部事情により削除してしまったものもありますが、とても役に立つものもあったので紹介させて頂きます。
>kanitawaさん
３SUM問題と調べてみてください。
なんと、この問題実はもうアルゴリズムがあるようです！
日本語では載ってないので僕は読めませんでした＾＾；
英語できる人はぜひ翻訳してください！！！
>ybさん
最適化についてですが、まだ少し無駄が有りますね。
言語によりますが、C++では
1.後置インクリメント→前置インクリメント
2.添字アクセス→イテレータ
と置き換えると早くなります。
前置インクリメントはコピーを作らないので、後置インクリメントより早い。
イテレータはポインタ演算に帰着するため、添字アクセスより早い。
とても分かりやすく解説してくれました！
僕よりybさんが記事書いたほうがよかったんじゃないか疑惑･･･
今夜にでも最適化の部分に追記しておきます･･･！
学生のてっきとうに書いたコードなので見苦しいと思いますが暖かい目で見てください･･･
期間終わったら載せるとかぬかしてましたが、自分の書いたコード載せるのは思ったより気が重かったです･･･
至らない部分色々あるかと思いますので、もしよければアドバイスなどコメント頂けるとうれしいです！
