デレステキャラソートのソートの仕組みに関する質問があったので、大したものではないですがソートのアルゴリズムについて書きます。

ソートの説明

データの構造に木構造を使った仕組みになってます。

次の3つの処理を繰り返し行うことで順位を確定します。

  • 木を作る
  • ソートする
  • 確定したノードを取り除く

説明しにくいので例を使って説明していきます。

例では簡易的に28個のノード(01番~28番)を最終的に01,02,03,…,27,28とソートすることを目指します。

#1. 「木を作る」

rootノード(構造上のノード)の下に最大5つの子ノード(01番~28番)がぶら下がるように複数の木を作ります。
※それぞれの木にぶら下げるノードはランダムで決定します

例:6つの木ができました(深さ1なのでイメージしにくいですが)

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
32
33
─┬16
05
28
23
17
─┬24
07
27
08
14
─┬10
12
22
09
02
─┬20
03
19
04
21
─┬15
25
01
26
─┬18
06
13
11

#2. 「ソートする」(ユーザによる順位付け)

上位が親ノード、下位が子ノードになるようにノードを付け替えます。

例:
1つ目の木では05,16,17,23,28の順番に付け替えます。
rootノードの子ノードが05で、05の子ノードが16で、16の子ノードが17で、17の子ノードが23で、23の子ノードが28です

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
──05
16
17
23
28
──07
08
14
24
27
──02
09
10
12
21
──03
04
19
20
22
──01
15
25
26
──06
11
13
18

#3. 再び「木を作る」

深さ1のノードを使って、#1と同様に新しく木を作ります。今回も深さ1の子ノードは最大5つです。

例:深さ1のノードは6つあるので2つの木を作ります。(本来はランダムで決めますが今回は元の並び通り)

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
─┬05
│ └16
│ └17
│ └23
│ └28
07
│ └08
│ └14
│ └24
│ └27
02
09
10
12
21
─┬03
│ └04
│ └19
│ └20
│ └22
01
│ └15
│ └25
│ └26
06
11
13
18

#4. 再び「ソートする」(ユーザによる順位付け)

#2と同じ処理です。上位が親ノード、下位が子ノードになるようにノードを付け替えます。

例:
1つ目の木では02,05,07の順番に付け替えます(他の構造は維持します)。
rootノードの子ノードが02で、02の子ノードが05で、05の子ノードが07です

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
──02
09
│ └10
│ └12
│ └21
05
16
│ └17
│ └23
│ └28
07
08
14
24
27
──01
15
│ └25
│ └26
03
04
│ └19
│ └20
│ └22
06
11
13
18

#5. 再び「木を作る」→「ソートする」

今までと同じ手順です。ソートまで進めます。

例:深さ1のノード(01,02)は2つなので1つの木になります。

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
──01
15
│ └25
│ └26
03
│ ├04
│ │ └19
│ │ └20
│ │ └22
│ └06
│ └11
│ └13
│ └18
02
09
│ └10
│ └12
│ └21
05
16
│ └17
│ └23
│ └28
07
08
14
24
27

#6. 「確定したノードを取り除く」

木が1つ&深さ1の子ノードが1つになった場合、その子ノードの順位が確定します。
確定したノードは木から取り除きます。順位は取り除いた順番です。
深さ2だったノードはそれぞれ別の木になります。

例:
深さ1の子ノード(01)が1つなので、01の順位が確定します。
深さ2だったノード(15,03,02)は新しい木になります。

確定したノード[01,]

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
──15
25
26
──03
04
│ └19
│ └20
│ └22
06
11
13
18
──02
09
│ └10
│ └12
│ └21
05
16
│ └17
│ └23
│ └28
07
08
14
24
27

#7. 「木を作る」、「ソートする」、「確定したノードを取り除く」を繰り返し行う

これらの操作を繰り返すことで最終的にすべてのノードの順位を確定します。

末文

思い出しながら書いたので細部の違いはありますが、基本はこんな感じです。

キャラソート画面.jpg

みなさん。キャラソートってやったことありますか?
キャラソートというのは、アニメやゲームなどのキャラクターを2択で選択していき、好きなキャラクターを順番付けするアプリケーションです。簡単な操作で手軽にできるのが特徴なのですが、アイドルマスターシンデレラガールズのようにキャラクタ数が多いコンテンツだと、最後までソートするのに多くの時間がかかってしまします。また、これはあえてこういう仕様にしていると思われますが、最後に上位を決めるものが多く、途中で止めることができません。
そこで、選択数を増やし、上位から順位を決めていって好きな時に止められるキャラソートを作りました。全ての順位を決定する場合は所要時間はほとんど変わりませんが、上位30位程度まで決めたい場合は、かなりの時間短縮になっているはずです。
上位30位までの結果をツイッターで呟けるようになってるので、ぜひやってみてください。

デレステキャラソート

私の結果

また、おまけの機能として上位30位までの結果をグラフ化して表示する機能を設けました。d3.jsというライブラリを使ってぐりぐり作ってみたのですが、簡単に綺麗で見栄えの良いグラフが作れるので便利になったものですね。

キャラソートグラフ.jpg

また何か思いつけばグラフ機能を追加していこうと思います。

あけましておめでとうございます。年1回の生存報告でございます。
今年はやる気出して、ブログを引っ越してみました。ちょっとナウい感じの見た目になってませんか?
hexoという名前の静的サイトジェネレータを使って、github pagesにアップロードしています。今までは有料のレンタルサーバーを使っていたので、無駄に維持費がかかっていましたが、これからはドメイン代だけです。ドメインは割と気に入っているので、無理やりでも続けますよ。

例年通り去年を振り返ってみます。

折りたたみ自転車「ブロンプトン」

結構よさげな自転車を買っちゃいました。折り畳みでとてもコンパクトなんですが、割とよく走ります。製品名は”Brompton S2L”です。同じラインナップには変速機が6段のものと2段のものがあるんですが、軽くてメンテしやすいということで2段のものを選びました。でも2段で十分です。別に速く走りたいわけではないので、基本的には重い方のギアで走って、走り出しや坂道で軽い方のギアという使い分けで不満はありません。

brompton_ise.jpg

上の写真は2015年のF1日本グランプリの後に、伊勢神宮に行ったときの写真です。
F1グランプリ開催中は、津市内のホテルから鈴鹿サーキットまでブロンプトンで通いました。片道16km程で1時間程度でしたが、混雑知らずなので気持ち的に非常に楽でした。ただ今回観戦した場所が西コースなので、スプーンコーナー入り口までの坂が結構きつかったです。
決勝の次の日は津駅から伊勢市駅まで輪行して、伊勢神宮にお参りに行きました。外宮から内宮までの移動も楽々でしたね。

アイドルマスターシンデレラガールズ スターライトステージ

友人に誘われて始めてしまいました。始めは少し遊んですぐに辞めるつもりだったのですが、気が付いたらアニメ版を全話見て、ライブに行って、アニメのブルーレイDISCまで揃え始めてしまいました。

スターライトステージでSSR(最高レア)の”前川みく”を手に入れてしまったのがすべての始まりだった・・・

スターライトステージに誘われる

遊んでみると結構面白い

面白いものには課金しようと、毎日引けるお得なガチャをする

SSR前川みくが手に入る

どんなキャラだろうと調べる

なんかこの子めっちゃかわいくない?

アニメ見る

シンデレラプロジェクト(アニメのアイドルメンバー達の意)のみんな大好きだああああ!!
みくりーな尊い!(アニメで*(アスタリスク)という名前のユニットを組んだ多田李衣菜と前川みくの二人の組み合わせがマジ最高すぎる様子)

ライブ(シンデレラの舞踏会)のライブビューイングに参加

シンデレラガールズ最高かよ

抜け出せない沼

いやもう、SSR前川みくを手に入れたのは運命でしたね。

ゲームの方は、いわゆる音ゲーでして、今までほとんど経験のないジャンルです。今は練習してそこそこ上達してきました。Master全部フルコンを目指していますが、まだまだ先は長そうです。というか一部無理そうな曲もあるしなあ。ぐぬぬ。

Screenshot_20160104-234913.jpg Screenshot_20160104-235659.jpg

2枚目の画像は今のマイルームの状態です。マイルームというのは、家具アイテムを設置したり、お気に入りのアイドルを配置したりできる箱庭のような、おまけ機能です。部屋の真ん中に、*(アスタリスク)に見えるように座布団を配置してみました。赤と青(紫だけど)はみくと、りーなのイメージカラーです。壁にはSSRを手に入れると一緒にもらえるポスターを貼ってます。・・・結構、集めてしまったなあ。うん。まあ。無(理のない)課金で頑張りますよ!

後書き

ブログを引っ越しして、更新しやすい環境になったので少しは頻度増えるといいですね!
ではまた!(来年かな)

どーもどーも。おひさです。今年もバシバシ更新していきますよ!

いや、はい。1年ぶりです。今年こそは少なからず更新したいです。いやね、去年も何回か旅行に行きましてね。舞鶴とか大湊とか行ってたんですよ。もちろん艦これ関連の場所ですよ。舞鶴は私の鎮守府ですからね!気合、入れて、行ってきましたよ。そりゃもちろん写真も撮ってきました。うん、更新したいね。更新したいなー。めっちゃ更新したいわー。

はい、すみません。今日はなんとなくテーマを変更したかっただけです。最近ちょっとWEB周りを触る機会あったので、少しだけやる気になったんです。しかし、テーマ変えただけで力尽きました。

また、いい風が吹いたら更新します。では!今年もよろしくお願いします!

おひさデス。何かの気まぐれで更新します。

前回の更新から1年以上空いてしまいました。特に何も無かったですが、ここ1年ぐらいのことでも書いておきます。

艦これ

「艦これ」ブームですよね。私も去年の7月頃から「舞鶴鎮守府」で提督業を営んでおります。9月には広島県の「呉」に聖地巡礼に行ってきまして、護衛艦に乗ったり、江田島にある旧海軍兵学校を見学したりと、充実した旅ができました。艦これが無ければ、呉に行こうとも思わなかったでしょうから、こうした出会いを提供してくれたことについても、「艦これ」を企画運営されている方には感謝ですね。

呉の旅行については気が向いたら書きたいのですが、少しだけ写真とともに紹介します。

呉港(天龍)

呉港で、護衛艦「うみぎり」に乗る前に撮った写真です。真ん中が「天龍」、右に「阿武隈」、奥に「伊勢」と、艦これで馴染みのある名前の護衛艦が停泊していました。

しまなみ海道

多々羅大橋

呉のついでに行ってきた、広島の尾道と愛媛の今治の間の島々を結ぶ「しまなみ海道」。自転車専用レーンが用意されていて、自転車乗りが多いです。レンタルサイクルとフェリーを利用して回ってきましたが、瀬戸内の海と島の風景が美しく、自転車で走っていて気持ちが良かったです。

ミラーレス一眼

そういえば、これも去年のことでしたが、ミラーレス一眼を買っちゃいました。機種はSONYの「NEX-6」。上の写真はシグマの単焦点レンズ「30mm F2.8 DN」で撮影したものです。カメラがあると撮影するのが楽しいですね。ただ、ミラーレスとはいえ、持ち運ぶのはやっぱり面倒。本体が小さくてもレンズは小さくならないですからね。ここぞと言うときぐらいしか出番が無いです。

F1

あと去年の出来事と言えば、初めてF1GPの観戦に行ってきました。金曜日のフリー走行から、決勝後のコース内を歩ける「コースウォーク」まで、3日間F1と鈴鹿を満喫してきました。今年は日本人選手が参戦しているので、去年以上に盛り上がりそうです。是非また行きたいですね。

鈴鹿サーキット

それでは今回はこんなところで。また1年後にならないように頑張ります。