カテゴリー: テクノロジー

プログラマーに欠かせない、配列の処理を最適化する方法

こんにちは。開発担当のマットです。
プログラムし始めたときのことを振り返ってみました。

バイナリヒープとの出会い・・・

何か面白いアプリケーションを作ろうと思って、プログラミングを勉強している方が多くいると思います。
特にゲームを作ろうと思っている方…

私もプログラミングの勉強を始めたころ、いずれゲーム作成に挑戦しようかと思っていました。
最初に作ったプログラムはJavascriptの”Hello World”でしたが、その後とても簡単なシミュレーション・ゲームを作ることに挑戦しました。

ランダムに生成された世界地図上で、多くの国や部族が戦いあって敵を全て倒すと勝つというごく一般的なゲームでしたが、作ることはとても楽しかったです。

世界地図のランダム生成アルゴリズムが完成し、次は敵の国を作ることに挑戦しました。
敵国の動きがあまりにも読みやすかったら困るので、AIのコーディングに結構時間をかけてしまいました。

ある程度できあがって、実行しようと思ったら、、、
ガタガタと重くなりました。
処理が重くて、敵の駒が動くのに数秒かかるようになってしまいました。

まだJavascriptの世界から卒業していなかったため、重くなっていることをブラウザのせいにし「ブラウザに頼らない言語で書いていたら問題はなかった」と信じて一旦ゲームを忘れました。

その後ある日、Javaでゲームを開発しているYoutubeシリーズを見て前に作ったゲームを思い出し、再びゲーム作成に挑戦しようと決めました〜 でも今回はJavaで！

今回は全く違うゲームですが、AIを同様に作ってみました。

「今回は速い！」
「今回は問題無い！」
と思いきや、またガタガタ重くなってしまいました。。。

ブラウザのせいにしていたのは大間違いで問題は私が書いたコードにありました。

コードを必死に読んで、デバッギングをして、問題を特定できました！
一つのものすごい重いファンクションのせいでした。

そのファンクションはある配列の中の一番少ない値を返してくれるものでした。
なお、そのファンクションは一秒間に何度も呼び出される。

つまり、もし配列に1000個の値が入っているとしてその処理を一秒間に1000回読んでしまえば、毎秒毎秒100万の比較処理となってしまいます。

恐ろしいループの中のループでした。

配列の最小値、(または最大値)を取得する軽い方法はないか？と悩んで、調べたらバイナリヒープに出会いました。

バイナリヒープとは？

バイナリヒープは「二分ヒープ」とも呼ばれますが、簡単に説明するとバイナリヒープは、
必ず、最小値（または最大値）が常に最初のキーに入るよう管理をきちんとされている配列です。

つまり、配列がarrayとしたら、arrayの最小値（または最大値）は必ずarray[0]にあります。
これがあると、ループをしなくても最小値・最大値をすぐ取得することができ負荷を減少するものとなります。

でも、まさか配列をソートすることになってしまうと余計処理時間がかかりそうので具体的にどうやってするのでしょうか？

配列に潜んでいる特徴

通常、配列をこのように想像します。
0から数えるキーがありそれぞれのキーに値が当てはまります。

しかし、形を変えて想像すると配列に潜んでいた面白い特徴を見ることができます。
それぞれのキーに親子関係を作ることができるのです。

このように並ぶと、
array[0] の子供は array[1]とarray[2]
array[3] の子供は array[7]とarray[8]
array[5] の親は array[2]
array[4] の親は array[1]
などなど・・・

パターンは既に見られているかもしれませんが、
親から見た場合、
親 = n としたら
左の子供 = n*2+1
右の子供 = n*2+2

子供から見た場合、
子供 = n としたら
親 = (n-1)/2   *分数を捨てる

バイナリヒープでできること

このバイナリヒープに値を入れる時、
または、バイナリヒープから値を削除する時、
その値の親と子供の上下関係さえ守れば、最小値・最大値は必ず、array[0]になります。

詳しく、説明します。
*説明では、「最小値」を返すバイナリヒープを紹介しますが、最大値を返すヒープは同様な動きです。

バイナリヒープにINSERT

バイナリヒープに新しい値を挿入する時、その値を配列の一番後ろに付け加えます。
次、新しく入れた値をその親と比較します。
もし新しい値の方が大きい場合、何もしません。
けれども新しい値の方が小さい場合、親と場所を交換し動作を繰り返します。

これをきちんとすると、最小値が必ず、「ルート」(array[0])の位置に上がってきます。

先ほどの配列に「3」を挿入してみましょう。

バイナリヒープからPOP

最小値を配列から取って削除したい場合、動作が反対となります。
まずは最小値（array[0]にあるもの）を消し、配列の一番最後の値をarray[0]に持ってくる。
その新しくなったarray[0]を子供達と比較し、大きければ一番小さい子供と場所を交換し動作を繰り返します。

バイナリヒープの特長

通常1000個の値を持っている配列の最小値を取得しようと思ったら、1000回ループしなければなりません。

でもデータをバイナリヒープの形で管理したら、最小値をループせずに取得でき最大でも9回の比較だけでヒープを整え直すことができます。
(1,000 <　2^10)

配列が大きければ大きほど最適化の効果が見られます。
例えば、1,000,000個の値を持っている配列でも最大でも、たったの19回の比較で整え直すことができます。1,000,000回ループするより速いでしょう。
(1,000,000 <　2^20)

実際のコード

私は最近Sportareの開発に関わり、Swift言語でのプログラミングが好きになりました。

そこでSwiftで書いたバイナリヒープのコードを紹介したいと思います。

通常ならばもっとコード整理しますが、以下のコードはバイナリヒープを把握するために作ったのでそのままベタ書きしました。
Swiftに慣れていない方でも、すぐわかると思います〜

これからも、頑張りましょう！

雨の音ってずっと聴いていられますよね。（って言ったらモテそう。。）
マエダです。

「VR!VR!VR!・・・・・」

社内ではウォーボーイズばりにみんな叫んでいる今日この頃です。
（出典：マッドマックス 怒りのデス・ロード）

で、行ってきましたソニーストア。
PlayStation®VR体験。

大阪は店舗前通路にも体験ブースを設置しおねえさんが使い方を案内してくれました。
僕を含めて体験予約者はおじさんの群れ。
客観的にみると近未来感のあるアレに見えました。（ご想像にお任せします。。）

はい、口あいてます。
あきますとも。

体験させていただいたのは深海に潜っていくコンテンツ。
「気分が悪くなったら手を挙げてお知らせくださいね」とおねえさんにご案内いただきました。

で、なんかちょっとしてから絶望的に怖いサメさんがこっちに向かってきちゃいます。

完全に気分悪くなるに決まってるじゃないですか。
コワいよ。
フツーにコワい。

でも手を挙げることなんてできません。

だっておねえさんにショボいおっさんって思われるじゃないですか。。。

そんなこんなであっという間のPS VR体験は終了しました。

「気分は大丈夫ですか？」
おねえさんは僕に優しく声をかけてくれました。

「はい、大丈夫です。楽しめました。」
平静を装った僕は汗びっしょりで説得力ゼロでした。。

Oculus Riftを体験していたからそんなに驚かないだろうと思ってましたが超コワかったし超楽しめました。（震え声）

で、VRのスゴさを知った僕はもっとVRの魅力が知りたくて以下のイベントに参加。
http://googlevrgame.peatix.com/

そこで聞いたお話では今買いのVRデバイスはRiftでもPS VRでもないとのこと。

これです。
『htc Vive』
https://www.htcvive.com/jp/

ルームスケールVRという体験。
マジパネェ。
体験したヒトにしかわからないスゴさがあるとのことでこちらでは多くは語りません。。。

VR楽しい＼(^o^)／

iOSアプリを開発すると、UIPickerViewはとても便利なものです。
指のフリックだけで、ユーザに多くのデータを提示することができるため、沢山のアプリで使われていています。

UIPickerViewを使うには、以下のステップが必要です。

1. UIPickerViewのインスタンスを作成する
2. データ自体を用意する
3. UIPickerViewのデータを扱うオブジェクト（DataSource)を定義
4. UIPickerViewの表示などを扱うオブジェクト（Delegate)を定義
5. DataSourceでComponent(区切り)数やRow(行)数を返すファンクションを用意する
6. Delegateで各項目のタイトルを返すファンクションを用意する
7. UIPickerViewのデータをロードする

簡単な実例を以下に貼り付けいたしました。
生物のリストをUIPickerViewで表示させる簡単なアプリだけです。

ご覧の通り、
生物の順番が作成した順番となって、生物の種類（Kingdom(哺乳類、鳥類、昆虫類、など))を見分けられないのはあまりよくないと思います。
以下の改善に取り組みましょう！

1. 生物を種類にまとめる
2. 生物の種類によって文字色を設定する

生物を種類にまとめる

これは一行でできることです！
データで使われるArrayにsortInPlaceファンクションを掛けて、Animalのkingdom値で順番を変更する。

Animal.Species.sortInPlace { $0.kingdom.hashValue < $1.kingdom.hashValue }

生物の種類によって文字色を設定する

これを実現するには、UIPickerViewDelegateの”titleForRow”のファンクションを消去し、”attributedTitleForRow”のファンクションを設置する必要があります。

例は以下に貼り付けています。

Swiftの基本のルールですが、Extensionで
・Method （メソッド、即ちファンクション）
・Computed Properties（計算型変数）
は定義できまるのに対して、
・Stored Property（保持型変数）
は定義することができません。

保持型変数と計算型変数の違いを簡単に説明しますと、保持型プロパティとは、データを保持してくれる、とても一般的な変数です。
計算型プロパティとは、すでに定義されている保持型プロパティを操る、getとsetのある、ファンクションに近い変数です。新たなデータを保持することはできません。

つまり、普通の保持型変数をクラスに追加したい場合、Extensionでではなく、クラスの中で定義しなければなりません。

けれども、Appleのライブラリのクラス(UIViewなど)のコードはアクセスできないため、そのようなクラスに新たな変数を定義することはできません。

もちろん、こういうようなクラスにサブクラスを作って、変数をサブクラスで定義できますので、問題はありません。
例えば、UIView の背景色が何回変わったかを記録する変数を付け加えようと思ったら、ColorChangingUIViewというSubclassを作って、そのクラスに変数を入れたら、解決されます。

SubclassでUIViewに変数を加える方法

 
上記の例では、単純に３つのColorChangingUIViewを作りましたので、問題はありませんでしたが、同じように、背景色が何回変わったかを記録する変数を持つUITableViewやUIButtonやUILabelなどを用意しようと思ったら、それぞれ、ColorChangingUITableView、ColorChangingUIButton、ColorChangingUILabelをつくる必要があります。
 
なお、同じ変数名を定義しても、ColorChangingUIViewとColorChangingUITableViewとColorChangingUILabelなどをループで取り扱う際、if is でそれぞれのタイプを確認しないと、colorChangesの変数がアクセスできないため、コードは複雑になり、大混乱になりやすい状態です。
 
それぞれのUIViewのSubclassにSubclassを作る場合のカオス

やっぱり、全てのクラスが親クラスとして共有しているUIViewのコードに変数入れることができたら、解決されますね。
それで、以下は、UIViewに保持型変数を入れる方法となります。

UIViewに保持型変数を入れる場合

わかりやすい上、重複を防げた簡潔なコードになりましたね。
これからも、Swiftの開発、頑張りましょう！