スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ジャンプ13号感想

●トリコ
省略されていた、小松奪還時の様子ですが、
どうも小松と三虎しかいなかった模様。

そういえば、料理人は「上手い料理を作れたら帰っていいぞ」と言われてた筈ですが、
良く考えたら帰れないですね。

建物も傾いてて、人間界の都市からも離れている場所から
どうやって帰れ
と。(多分、途中で死ぬ)

とりあえず、
-----------------------------------
① スタージュンが料理人たちを乗せて行った
(人間界に帰した?)
② その後、竹ちゃんとスタージュンがコンビを組んで旅へ

-----------------------------------
こんな感じかな。


●i・ショウジョ
「願いを叶えるアプリ」についてですが、
「3サイズを入力したらアンインストールで出来る」って、
願いは全く叶ってないですよね。

※自力で調べないといけないから、意味なし。

おまけに、今回
3サイズを知る事無く消滅しましたからね。
これ、一体どうするんだ。

多分、"説明書"さんから、
---------------------------------------
「あなたの願いを叶えられなかったから、
  もう一度あなたの望むアプリを与えます」

---------------------------------------
という提案があるかなーと思ってる。

しかし、テンポが速いので、
どうやって話を続けていくのかなー
とか思ってます。

ワンピースで例えるなら、
1話目で"ワンピース"を発見、
2話目で"ワンピース"が消滅
する様なものですからね。

「PSYCHO+」(藤崎竜という方の漫画。)みたいに、
どんどん課題が与えられていく感じになるのかな?
(もし"説明書"さんから新アプリの提供があった場合)


●暗殺教室
そういえば鷹岡はどうなったんだろう。

もう2度も負けたので、次に登場する時は
殺戮マシーン:TA・KA・O・KA ぐらいに進化してもらわないと困る。

もし、"強くなって再登場"しない場合は、
"死神"の様な上位互換の敵キャラに、噛ませ犬として使われる未来しか見えないなぁ。

あと、理事長が完全にキレてたので、
E組に対してエグイ対抗処置を採るんじゃないかと不安。

殺先生の暗殺どころではない、何かを行いそうな気がする。
その"何か"というのは現状想像がつかないけども。


●ワンピース
トレーボル意外と早くて強かった!

気絶させるミッションですが、
トレーボルが投げつけた船で気絶してたら笑う。
(流石にそんな自滅する様な展開は無いと思いますが)

とりあえず、トレーボルが戻ってきたら
トンタッタ族 VS 人形軍団
トレーボル VS ウソップ
 になりそうと思った。





●食戟のソーマ

<追記予定!>
スポンサーサイト

テーマ : 週刊少年ジャンプ全般 - ジャンル : アニメ・コミック

動的計画法による、最長共通部分列(LCS)算出、差分ファイルを作る方法!


現在、差分ファイル作成、ゲームパッチ適用プログラムを作っており、
その差分ファイルをエディットグラフで実装してみたのですが、

エディットグラフよりも、簡単なアルゴリズムがある様なので、
それもちょっと試してみました。


今回やるのは、
動的計画法による、
最長共通部分列(LCS)算出
です。


まず、最長共通部分算出についてですが、
これは、2つの文字列において、一番長い、共通の順番で出現する文字列の事です。

例えば下記の文字列があるとします。
----------------------------------
旧文字列:ABCDEFGHI
新文字列:ABZCDEZFGI

----------------------------------

この文字列の場合、LCSは「ABCDEFGI」となります。
----------------------------------
旧文字列:ABCDEFGHI
新文字列:ABZCDEZFGI

----------------------------------


で、LCSが見つかった際、
「LCSは固定で、LCS以外の文字列を追加/削除すれば
(最小コストの)差分が出る!」
という事らしい。

なので、(今回の例の)旧文字列→新文字列への変換は、
「H」を削除、2つの「Z」を追加するのが最小コストという訳です。
----------------------------------
旧文字列:ABCDEFGHI
新文字列:ABZCDEZFGI

----------------------------------


では、肝心の動的計画法のやり方を記載してみます。

■やり方
-----------------------------------------------------
【1】文字列+1の2次元配列を用意
【2】下記の条件で、要素番号[1][1]から右下へ、順に走査。
   条件1:一致文字の場合は、左斜め上の要素+1の値を入れる
   条件2:不一致文字の場合は、上と左で大きい方の値を入れる

【3】2次元配列に格納された各値の中で、最も左上にあるものを
   一致文字とする

-----------------------------------------------------

文章だけだと分かりづらいので、
図を用いてやってみましょう。

【1】文字列+1の2次元配列を用意
-----------------------------
旧文字列:ADBCFZ
新文字列:ABDCZFZ

-----------------------------
上記の文字列があるとします。

それぞれ6文字と7文字なので、
横7×縦8の二次元配列を定義します。

【参考画像】
Sample_20140217_1.jpg



【2】要素番号[1][1]から右下へ、順に走査。
---------------------------------------------
条件1:一致文字の場合は、左斜め上の要素+1の値を入れる
条件2:不一致文字の場合は、上と左で大きい方の値を入れる

---------------------------------------------
次に、上記条件に基づいて値を入れていきます。
※二次元配列のすべての要素は、「0」で初期化しておきます。


具体的に書くと、下記になります。
・[1][1]…どちらも「A」なので、[0][0]に1を足した値を[1][1]に入れる
・[1][2]…一致しないので、[0][2]と[1][1]を比較し
    、大きい方の値を[1][2]に入れる
・[1][3]…一致しないので、[0][3]と[1][2]を比較し
    、大きい方の値を[1][3]に入れる
・[1][4]…一致しないので、[0][4]と[1][3]を比較し
    、大きい方の値を[1][4]に入れる

//以下略

【参考画像】
Sample_20140217_2.jpg



【3】各値の中で、最も左上にあるものを共通文字とする
後は共通文字を出すだけなのですが、ここで注意点。

"最も左上"が存在しない場合があります。
今回で言うと、重みが「2」の場合です。


とりあえず、共通文字の算出をやってみましょう。
各値の"最も左上"を見つけるには、下記の手順を行います。
--------------------------------
【1】最も重みの値が大きい場所を現在位置とする
【2】重みが異なる値が出る直前まで上方向に移動
   重みが異なる値が出る直前まで左方向に移動
【3】現在位置を左へ1、上へ1(左斜め上に)変更
【4】値が0の場合は終了。そうでない場合は【2】~【3】を実施。

--------------------------------


具体的に過程を書くと、下記になります。
※下記の過程を読むよりも、図を見て、
各値で、最も左上の場所を見て行った方が分かり易いかもしれません。

--------------------------------
[7][6]を現在位置に設定(重みは5)
上/左へ移動不可。
現在位置を[6][5]に設定(重みは4)
上/左へ移動不可。
現在位置を[5][4]に設定(重みは3)
左へ移動不可。上へ1移動。
現在位置を[3][3]に設定(重みは2)
左へ1移動。上へ移動不可。
現在位置を[2][1]に設定(重みは1)
左へ移動不可。上へ1移動。
現在位置を[0][0]に設定(重みは0)
0なので終了。
--------------------------------

【参考画像】
Sample_20140217_4.jpg
※各値で"最も左上"と判定された場所に色を塗った図。


上記の図を見ると分かるかと思いますが、
LCSは「ADCFZ」になります。簡単ですね!


また、先ほど述べた「左上が無い」パターンについて。
左上が無いパターンは、下記の様に左上が欠けた様な状態になっています。

※"最も左上"があるパターン
■■■
■■■
■■■

※"最も左上"が無いパターン
□■■
■■■
■■■


この左上が欠けた場合はどうすれば良いか、というと
----------------------
・欠けた場所の1つ右
・欠けた場所の1つ下
----------------------
上記2つの内、どちらか好きな方を選べば良いです。
何故なら、書き換えるコストは変わらないからです。


■欠けた部分の1つ下を選択した場合 (LCS … 「ADCFZ」 )
Sample_20140217_4.jpg
旧文字列:ADBCFZ
新文字列:ABDCZFZ

「B」削除、「B」追加、「Z」追加 … コスト3。


■欠けた部分の1つ右を選択した場合 (LCS … 「ABCFZ」 )
Sample_20140217_3.jpg
旧文字列:ADBCFZ
新文字列:ABDCZFZ

「D」削除、「D」追加、「Z」追加 … コスト3。

上記の通り、どちらもコスト3で変わりません。


【補足】
コストは変わりませんが、書き出す差分情報は当然変わってきます。
コストを低く、かつ差分情報のファイルサイズも小さくしたい場合は、
どの文字列をLCSにするか?は考えないといけないと思われます。
(圧縮アルゴリズムとの兼ね合いにより。)


とりあえず、以上が動的計画法によるLCS算出の流れです!



あと、どうして下記の条件でLCSが求められるのか?(証明)についてですが、
----------------------------------------------
条件1:一致文字の場合は、左斜め上の要素+1の値を入れる
条件2:不一致文字の場合は、上と左で大きい方の値を入れる
----------------------------------------------
これは、LCSが求まる際の法則をもとに、
漸化式を再帰的に解く事で答えが得られる事を証明
する必要があります。

ちょっとややこしいかもしれませんが、
証明する方法まで理解したい、という方は下記が参考になるかと思われます(_ _)
【参考URL】最長共通部分列問題 (Longest Common Subsequence)Add Star

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

ジャンプ11号感想

●ILLEGAL RARE
凄い面白そうです!

多分、ジャンプの漫画家の中では、
不可思議な存在(生命体)や、世界観などを描かせたら一番ではなかろうか。

とりあえず、主人公たちの活動と、
宣戦布告(?)を受けたコレクター側がどう動いていくか、ですね。

狼男、鵺、エルフ、ドライアド、夢魔とか、
そこら辺は出て来そうな気がする。


●トリコ
謎の技術で次々と食糧をピンポイント射出するトリコ。
これが"食義"か。凄い。(たぶん違う)

とりあえず、マンサムの所へ行き、
仲間と共にグルメ界へ向かう展開になるのかな?

というか、人間界は作物が育たないような状態になってるっぽいので、
定期的にグルメ界から食料を人間界へ調達しつつ、
第三勢力と戦わなければならない
ような気がする。

栄養カプセルだけだと、理性が崩壊してるっぽいですし。


●磯部磯兵衛物語
連載初期は、春画ネタの後、冬に布団の中で妄想を繰り広げ、
大ゴマでページ数を稼いでるかのような状態だったので、

これ、大丈夫なのか(連載的に)とか思ってたんですが、
普通に安定して面白くなってるような気がする。

例えるならば、「メゾン・ド・ペンギン」の頃の大石先生が、
「いぬまるだしっ」の頃の大石先生になった
様な感じ。
安定してる。


~本編感想~
試食のチョコ団子すらもらえず、
解説がウザイという理由でしばかれた
中島が磯兵衛より悲惨ではないかと思った。

そういえば、大ぱっつぁんは、
「殺してくれ…」と言っている磯兵衛は放置したのだろうか?


●恋のキューピッド焼野原塵
恐らく、塵が魔界に帰り、
吉丸は人間界で恋を成就させるのだろう。

もしかしたら、一気に「10年後 -」みたいに時間軸が飛んで
恋愛が成就した姿が描かれるかもしれん。
(※ただし、下根を除く。)

ゴルゴンさんは…あの人はもう駄目だ。助からない…!
人間界で餓死しそうになりながら生活するイメージしか湧かない。

とりあえず、一部のキャラを除いて、
それぞれの恋愛成就した幸せな姿が描かれる
と思ってる。


●食戟のソーマ
アリス 95点
アリスのお付き 93点
新戸緋沙子 92点

個人的に気になっているのが、アリス側とえりな様側の攻勢。

えりな様は点数が出ませんが、これを見るに、
--------------------------------------------------------
緋沙子 < アリスのお付き < アリス < えりな様
--------------------------------------------------------
こんな感じの力量関係になりそうな気がする。

また、水戸郁魅さんは力量が足りない様なイメージが付いてしまった。
登場初期は、えりな様が評価していたので、実力的に上位だと思っていたのですが…。
(周りの料理人の技量が凄すぎて、埋もれてるのかもしれないけども)

そういえば、うわっくさカレー ラクサカレーを作った貞塚ナオ
アリス様勢に加わったりするのかな?

アリス VS えりな様 の展開は今後も引っ張って行きそうですし、
そこら辺の動きが気になる。


とりあえず、ソーマは何点かは分かりませんが、
1位か同率1位ぐらいで通過するんじゃないかな。
落選したらある意味衝撃。

テーマ : 週刊少年ジャンプ全般 - ジャンル : アニメ・コミック

巨大文字列の場合の、差分ファイル作成プログラム実装完了!

前回、文字列が長すぎると、
エディットグラフを分割しないといけない
→分割したら正常に差分が取れない

という問題が発生していたのですが、

■例
AAAABBBB
BBBB

4文字ずつに区切ってエディットグラフを生成すると、
「AAAA」を削除。
「BBBB」を追加。
「BBBB」を追加。
という結果が出る。

最大8文字までのエディットグラフを生成する場合は、
「AAAA」だけを削除、という正しい結果が得られる。



(非効率かもしれませんが)
解決方法を見つけました。


やり方は簡単で、
例えば1000文字ずつエディットグラフを生成する場合、
後半3分の1程度の結果を破棄します。

例えば下記の文字列があるとします。
AABCDEFGHIJKLMN
AABCZZDEFGHZZMNIJKLMN

15文字ずつに区切った場合は、下記の結果が得られます。
AABCDEFGHIJKLMN
AABCZZDEFGHZZMN  IJKLMN

一致した文字は「AABCDEFGHMN」の11個なのですが、
約3分の1程度後退した所までを確定結果とします。(11 - (11 / 3) = 8文字)

つまり、「M」「N」まで一致した(11文字一致した)という結果が出たものの、
8文字目の「G」の所まで巻き戻り、「G」以降は未確定扱いにします。

AABCDEFG    HIJKLMN
AABCZZDEFG  HZZMNIJKLMN

で、未確定扱いになった「H」より後ろの文字列を
また等間隔(今回は最大15文字)でエディットグラフを生成します。

すると下記の結果が得られます。
AABCDEFG    HIJKLMN
AABCZZDEFG  HZZMNIJKLMN


3分の1後退しなかった場合と比べて、
精度の良い結果が出ている事が分かると思います。

■後退しない場合
AABCDEFGHIJKLMN
AABCZZDEFGHZZMNIJKLMN

■後退した場合
AABCDEFGHIJKLMN
AABCZZDEFGHZZMNIJKLMN



この"3分の1程度"というのが、何とも
論理的ではなく
スマートじゃないなとは思ってる
んですが、
現状では、この実装で行こうと思っています。

※一致部分を検出した際、下記の様になる理由は一応あります。
-------------------------------------------
始端 … ほぼ確定でOK
終端 … 未確定にした方が良い場合が多い。
-------------------------------------------
始端の方は、言わば
何百、何千も先の文字列まで確認して出した結論であり、
これが覆る事は確率的にまずないのです。

具体的にいうと、
下記の場合、1000文字以降に新文字列と一致する「ABC」があったとしても、
一致させる場合は、ABCZZZZZZZZ…の1000文字を削除しないといけません。

旧:ABCZZZZZZZZZZZZZZZZZZ… // 中略(1000文字程度) //… ABC
新:ABC

つまり、削除する1000文字の中に、一致する文字が3つ以上あった時点で、
非効率である事が確定
します。
(今回の場合は、旧文字列の初っ端に「ABC」が存在するので、
その時点で1000文字先の「ABC」と一致させるのは非効率である事が確定。)

"似通ったファイルを比較している"場合は、
1000文字の中に全く
一致する文字が出現しない可能性は極めて低くなる
為、
始端の文字列はほぼ確定して良いのです。

(むしろ、「1000文字先まで確認しても、似た文字の並びが全く出現しない」場合は、
 それは"似通ったファイル"ではないと思う。)


逆に終端の場合を考えてみます。
下記の様に、「AAAAAA」を削除、「DDDDDD」を追加という結果が出ており、
「Z」と、終端の「B」が一致しているとします。
※「DDDDDD」「EEEEEE」は、まだ一致検出の対象になっていない領域とする。

ZAAAAAAB DDDDDD
ZDDDDDDB EEEEEE



この場合、
・「AAAAAA」6文字の中に、2文字以上一致する箇所が、次の領域の近くにある
・「DDDDDD」6文字の中に、2文字以上一致する箇所が、次の領域の近くにある


どちらか一方を満たしていれば、
「AAAAAA」「DDDDDD」を追加/削除するのは非効率
である事が確定します。
(今回は近くに「DDDDDD」(6文字一致)があるので、非効率である事が確定。)


要は、一致する文字を確定する場合も、
一致した文字を未確定の状態に戻す場合も、
-------------------------------------------------------
・追加/削除を確定した文字の内、一致する文字が存在する確率
・その一致した文字が、現在の一致文字よりも多くなる確率
  (一致させるために行う追加/削除のコストが低くなる確率)

-------------------------------------------------------
この2つの確率を見比べている訳です。

(で、その確率からして、
始端 … ほぼ確定でOK
終端 … 未確定にした方が良い可能性高

という傾向が出て来る。)


この確率(期待値?)を上手く算出する計算式を作ることが出来れば、
「無条件で、とりあえず終端近くの3分の1くらいを未確定にする」という、
あやふやな対処法から脱却出来そうな気はする。

改良出来たら、改良してみようと思う。
ひとまず、2月中の公開には何とか間に合いそうな感じ。



~今日のひとこと~
無免許で車を運転しても、
罪に問われない場合ってあるらしい
ですね。


そもそも、「運転免許」というのが、
-------------------------------------------------------------------
"公道において"、自動車および原動機付自転車の運転を認める許可のこと。
-------------------------------------------------------------------
らしく、

言い換えれば、
"公道ではない所"(周囲から隔絶された私有地内 / 敷地内など)の運転に関しては、
特に効力を持って無い
ようなのである。


なので、第三者が全く入って来れないような、
隔離された広大な私有地
がある場合、その私有地内で車を運転しても問題無いらしい。

それで運転の練習をして、教習所では実技をらくらく突破する人も居るんだとか。
なるほど…。法律の穴というか、盲点?みたいな話で面白いと思いました。

テーマ : ゲーム製作 関連 - ジャンル : ゲーム

ジャンプ10号感想

●トリコ
人間界編完結!グルメ界編 開始!
…という感じだった筈なのですが、

いつの間にか小松は救出した事になっており、
更に食材を持って人間界に帰ろうとしているのですが、これは一体?

人間界でのゴタゴタを解決する展開になるのであれば、
全然"グルメ界編"ではない様な気がする。

とりあえず人間界は荒廃してそうな気がした。


●暗殺教室
竹林君がE組を脱出したところで、
E組が成績でTOP争いをしたという事実は変わらない
(=E組は見下せる存在ではない)と思うんですが、

理事長もE組以外のクラスも、
何故、余裕な態度を取っている
のだろう。

もう、E組見下しシステムは崩壊しているというのに。


あと思ったんですが、「理事長の手を打つ」発言は、
竹林君へのE組脱出の打診だったのかな?

ん~そうだとすると、大した戦略では無いなーという印象。

例年やっているそうですが、特に今回の場合は
「殺せんせーがいる事により、E組の成績が上がった」のですから、
殺せんせーに対する措置を取らないと、
次のテストでまたE組が大躍進するだけ
なんじゃないかな。

そうなると、理事長の方針は崩壊しそうな気がする。
竹林君への打診だけで良かったのか理事長。


●ジェントル君
おい!!画力!!
画・力・!!

明らかにまだ週刊誌に載せる段階では無いと思ったんですが、どうだろう。
詳しくは分からんですが、ペンの使い分けもして無さそうな気がする。

漫画の内容はシュールで投げやりなラストで、
それ自体は良いかなーとは思ったんですけども。

絵の方は、要・努力かなと。


<追記予定!>

テーマ : 週刊少年ジャンプ全般 - ジャンル : アニメ・コミック

エディットグラフの実装完了!

エディットグラフの実装が完了しました!
※やはり、一部バグがあって修正→バグ発見→修正を幾度か繰り返しました。


ただ、致命的な欠陥があって、
長すぎる文字列の差分が取れない。


文字列A(5文字)と、
文字列B(10文字)があるとして、
それに必要なエディットグラフの生成は5×10=50のサイズの2次元配列が必要です。

これぐらいなら問題ないんですが、
差分を取るファイルのサイズは300万とかあるのです。

簡単に計算すると…
300万×200万 = 6兆

6兆の要素数を持つ2次元配列を用意する
必要があります。

うわーなんだコレ。
桁外れすぎて、ギャグの領域。  無理。


なので、「じゃあ10×10のエディットグラフを繰り返し作成して、差分取ればいいや」
と思ったんですが、これだと差分が取れない。

例えば下記の文字列があるとします。
-------------------------------------------
旧文字列:TTTTUUUUPP
新文字列:AAAAAAAAAATTTTUUUUPP

-------------------------------------------

それぞれの最初の10文字を比較すると、
「TTTTUUUUPP」を削除、「AAAAAAAAAA」を追加という結果がでます。

そして、旧文字列は後続の文字が無いので比較を終了し、
新文字列の余った「TTTTUUUUPP」は追加するものとします。

するとどうなるかというと、最終的に
-----------------------------------
旧文字列:「TTTTUUUUPP」を削除
新文字列:「AAAAAAAAAA」を追加
新文字列:「TTTTUUUUPP」を追加
-----------------------------------
という結果が出ます。

これ、間違っています。
旧文字列に「AAAAAAAAAA」を追加するだけ、が正解です。


エディットグラフのサンプルが記載されているサイト見てみたのですが、
大抵、短い文字列の比較ばかりで、巨大な文字列の場合の対処法が書いてない。
(自分が見落としている可能性もありますが)

うーむ。
"一致する可能性が高い、短めの範囲"を見つけて、
その範囲でエディットグラフを生成
すればいいのかな…?

難しいとは思っていましたが、想定を超える難易度。

とりあえず、対処法が見つかり次第、
エディットグラフ含め、全般のアルゴリズムの解説記事を書く予定。
目途が立つまで、アクションゲーム制作を進めよう!


~今日のひとこと~
ドラマとかでは、緊急手術で「メス!」とか物々しい雰囲気で言ったりしてますが、
実際は、クラシック音楽などのBGMを流したりして、
リラックス出来る状態にして手術する事が多かったりするらしい。

へー知らなかった!

テーマ : ゲーム製作 関連 - ジャンル : ゲーム



上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。