2016-04-27

gunzip 備忘録

gunzipするファイルの拡張子は.gzじゃないとだめ

  $ gunzip data2.txt
  gunzip: data2.txt: unknown suffix -- ignored
  $ mv data2.txt data2.gz
  $ gunzip data2.gz

unknown suffixは知らない拡張子ですよってことらしい．

2016-04-06

jqueryで$(window)が使えないとき

解決策

今回の私の例における解決策あるいは，修正すべき問題点を一番最初に記しておく．

function Object() を作ってはいけないということである．

他のページは大丈夫なのに

jqueryを使っていたら，突然$(window)が使えなくなるときがあった．ページのクローズ時に保存処理的なことをしようと思っていたので，JS初心者としては$(window)が使えないと大変に厳しい．

同じようなページを複数を作っていたのだが，そのページだけなぜか使えない．完全に理解不能である．

TypeError: invalid 'in' operand a

コンソールを見ると TypeError: invalid 'in' operand a という謎のエラーがでていた．しかも，自分が書いたプログラムではなく， jqueryの方に．出ていたので完全に謎である．どうしろというのだ．

function Object()に問題があったらしい

幾つかの動物体を配列に挿入して操作しようと思っていたので，その動物体の親クラス的な意味のクラスを作りたかった．

そのため，Objectというクラスを定義していたのだが，それに問題があったらしい．まあ確かに，Javaでも全ての親クラスにObjectが使われていたような気もするし， Objectという単語を用いるのはあまりよろしいことではないのかもしれない．

2016-02-06

マンデルブロ集合の生成に成功した

はじめに

マンデルブロ集合とは

Mandelbrot set - Wikipedia, the free encyclopedia

マンデルブロ集合は以下の漸化式 $z_n$ が無限大に発散しない複素数 $c$ の集合である．

${ \displaystyle z_0 = 0 }$

${ \displaystyle z_{n+1} = z_n ^ 2 + c }$

$c$ の実数部分をx軸，虚数部分をy軸に取ったものがよくみられるフラクタル図形である．

人は日々進化しているんだ

昨日，「マルデンブロ集合」という単語を見かけ，「マンデルブロ」だろと思いながらも一応確認を行うため，調べたところ，恒例の図形が表われた．

その図形を眺めていると，昔フラクタルについて勉強した際に見かけたものの，全く理解することができなかったことを思いだした．その理由として以下の7点を挙げることができる．

他のフラクタル図形と同じノリで，必要な部分だけ計算する感じだと勘違いしていた．
そもそも $c$ の存在を理解しておらず， $z_n$ がマンデルブロ集合だと勘違いしていた．
複素数をJavaで扱うのが面倒だな，，と思った．
実数だけで扱えるというサンプルがWikipediaにあったが，x,yという文言から，勝手に座標系と勘違いしていた．
xn,ynをポインティングしてみて違うじゃんと叫んでいた．
発散だの収束だのどう判断するのか理解できなかった．
記事をしっかりと読んでいなかった．

今回，https://en.wikipedia.org/wiki/Mandelbrot_setや http://azisava.sakura.ne.jp/mandelbrot/を眺め，無事理解し，processingにて図形を生成することが出来たので，忘れぬように書き記しておく． processingでは他の言語におけるcomplexなどといった便利なクラスは存在しないので，実数部と虚数部を分けて，それぞれ自分で計算する必要がある．

f:id:turane_gaku:20160206014856p:plain

図形生成のアルゴリズム

他のフラクタル図形との違い

フラクタル図形で理解が容易く，生成が簡単なものとして，シェルピンスキーのギャスケットが挙げられる．

これは三角形の中に4つの三角形があるという理解が容易い，フラクタル図形である．作る際も普通に再帰や，成分を細かく成長させてゆくだけで事足りる．

対して，マンデルブロ集合は単純に再帰で書くだけ，といったものではなく，ある数学的性質を満す虚数の集合を数直線上にプロットしてみたらフラクタル図形になっているといったもので単純にはいかない．つまり，連続的に次，次と求められるものではなく，虚数を大量に集め，分別するというステップを踏む必要がある．可能な限り，連続な状態になるように分割した虚数全てを，マンデルブロ集合に属すか，属さないかを判断し，それを描画するというステップを取る必要があるようだ．

収束と発散の判断

ある虚数 $c$ がマンデルブロ集合に属すか否かの判断には以下の漸化式が発散するかどうか，を用いる．

${ \displaystyle z_0 = 0 }$

${ \displaystyle z_{n+1} = z_n ^ 2 + c }$

つまりそれぞれの虚数に対して，いちいち面倒な計算を行う必要がある．

この漸化式が収束するか発散するかどうかの判断は http://azisava.sakura.ne.jp/mandelbrot/ に詳しい説明があるが， ${|z_n| > 2}$ を用いれば良いらしい．

複素数を実数部と虚数部に分割する

Javaにはcomplexなどといった便利なクラスはデフォルトでは入っていないので，実数部と虚数部に式を分割する必要がある．ここで，

${ \displaystyle c = A + Bi }$

${ \displaystyle z = a + bi }$

とする．

${ \displaystyle z_{n+1} = z_n ^ 2 + c }$

${ \displaystyle a_{n+1} = a_n ^ 2 - b_n ^ 2 + A }$

${ \displaystyle b_{n+1} = 2 * a_n * b_ni + B }$

と式変形できる．

複素数の絶対値に関しては，複素数 ${z=a+bi}$ とあらわしたとき，

${ \displaystyle |z|^2 = a ^ 2 + b ^ 2 }$

となるため，発散するか否かの判断には[tex:a² + b² > 4]を用いる．

マンデルブロ集合か否か

まとめると，ある虚数 $A+Bi$ が与えられたとき，その数がマンデルブロ集合か否かを判断するためには以下の関数を用いる．

boolean ismandelbrot(double A, double B){
  double a = 0;
  double b = 0;
  for(int i = 0; i < 500; i++) {
    double aa = a * a - b * b + A;
    double bb = 2 * a * b + B;
    a = aa;
    b = bb;
    if (a * a  + b * b >= 4) return false;
  }
  return true;
}

現在は500項目まで求めているが，場合によってはより深い部分まで求める必要がでてくるだろう．

まとめ

A，Bをそれぞれx軸y軸にプロットし，適当な感じで色付けするプログラムが以下の通りになる．

Mandelbrot.pde

double scale = 400;
int div = 20;

void setup() {
  size(1000, 1000);
  noLoop();
}

int ismandelbrot(double A, double B){
  double a = 0;
  double b = 0;
  for(int i = 0; i < 500; i++) {
    double aa = a * a - b * b + A;
    double bb = 2 * a * b + B;
    a = aa;
    b = bb;
    if (a * a  + b * b >= 4) return i;
  }
  return -1;
}

void draw() {
  for(int b = 0; b < height; b++) {
    for(int a = 0; a < width; a++) {
      int m = ismandelbrot((a - width * 7 / 10) / scale, (b - height / 2) / scale);
      if(m == -1)
        set(a, b, color(0));
      else if (m % 3 == 0)
        set(a, b, color(100, m * 255 / div, m * 255 / div));
      else if (m % 3 == 1)
        set(a, b, color(m * 255 / div, m * 255 / div, 100));
      else
        set(a, b, color(m * 255 / div, 100, m * 255 / div));
    }
  }
}

今回は無事マンデルブロ集合を描画することができた．昔は理解が出来なかったこと，実装が不可能だった事柄も，時を経て知識を身に付けることで理解できることが増えていくのだろう．

昔作成した物事を再び作りなおしてみたり，見返してみることも大切なのではないかと気付くことができた．

2016-02-04

pythonでコロン区切りの物理アドレスを取得する

Python

前置き

pythonでコロン区切りのMACアドレスを取得したいと思っていた．すると，

qiita.com

という記事があった．

しかしながら， struct というものを知らなかったので，さっぱり何がおきているのかわからない… そこで， struct を使わない形で書いてみるか，と考えた．

書いた

 ":".join([hex(n >> (5 - i) * 8 & 0xff)[2:].zfill(2)
          for (i, n) in enumerate([uuid.getnode()] * 6)])

uuid.getnodeは48bit区切りの物理アドレスを返すらしいので，それの下位8bitを取ってくる．

速度比較した

from time import time
import uuid
import struct

a = time()
for _ in xrange(1000):
    "-".join([hex(n >> (5 - i) * 8 & 0xff)[2:].zfill(2)
              for (i, n) in enumerate([uuid.getnode()] * 6)])
b = time()
for _ in xrange(1000):
    "-".join([hex(fragment)[2:].zfill(2)
              for fragment in struct.unpack("BBBBBB", struct.pack("!Q", uuid.getnode())[2:])])
c = time()
print b - a
print c - b

自作と本家，それぞれ1000回計測した．

結果

0.0104370117188
0.00326585769653

遅い，遅すぎるぜベイベー… 本家とくらべ，3倍近い時間がかかっている…

だがしかし

落ちついて，ソースコードの長さを見て欲しい．

":".join([hex(fragment >> (5 - i) * 8 & 0xff)[2:].zfill(2) for (i, fragment) in enumerate([uuid.getnode()] * 6)])
"-".join([hex(fragment)[2:].zfill(2) for fragment in struct.unpack("BBBBBB", struct.pack("!Q", uuid.getnode())[2:])])

なんと，4文字の減少が得られた!!すごい!!!

結論

やはり詳しい人のソースコードは素晴しいということが今回の一件から判った．後でstruct に関しても理解を深めたい💪

2016-01-05

Processingで数独の解に光明を

Processing

数独

縦・横の各列と太線の正方形内に同じ数字が入らないように1~9までの数字を各セルに入れていくパズルゲーム

本当はナンプレと呼ぶほうがいいらしい．

デジタルでやりたい

数独を解くにあたり，基本は紙で解くことが多いと思うが，そうすると紙がもったいない&間違えたときの処理がいろいろと面倒くさい．あと終ったときにちゃんとあってるかどうかを確認するのに99+99+9*9のセル確認が必要なので面倒くさい．

ということでパソコン上でできたら紙も無駄にならないし，便利だなと考えた．

欲しい機能

解くときには，確定したセルと同じグループに属するセルから数字を消していくので1~9であとどの数字が残っているかを表示したい
紙でやると1~9を小さく書いて，丸をつけるとかだったので分かりにくい．よって，確定した数字は大きく表示したい．
終了した時にあっているかどうかをシステム側で判断してほしい．

もっと自動化したい

上記の機能を実装したところ，確定したセルと同じグループのセルを判断して一個一個ポチポチ消していくのも面倒になってきた．ならば確定したセルと同じグループのセルからその数字を消して欲しい．というかそれなら消したときにセルが確定したならそのセルについても同様にやって欲しい．

っていうか全部自動化すればよくないか?

完成品

というわけで，問題を入力すると，それの解を求めてくれるプログラムをProcessingで作った．

github.com

問題を数字キーで入力してENTERを押すと解を求めてくれる．一応元来の目的の援助ツールとしても有用な作りにはなっていると思う．

仕組みとか

public class abstract Solve implements Runnable

解いているときに主Theadが止まってしまうと困るのでRunnableに．
解く手法は幾つかあるのでSolveをextendsしてつかえるようにabstract methodを作成
これの子クラスとして消去や二国同盟だとかそれぞれを実装すれば完全分離できてかっこいい

111111111 -> 000000001

データ構造

各セルには9bitの変数を持たせる．1bitごとに1~9の整数が残っているかどうかを表わす．初めは111111111からスタートして段々消していき，000000001などといった，1bitのみが立っている状態になったとき，確定セルといえる．

ex

111111111 = 全て
111111011 = 3ではない
000000011 = 1か2
000000010 = 1で確定

数字の削除

同じグループに属するセルからその数字を消すとき，bitを使うといい感じに書ける．確定セルのbitの反転と&算をとると，綺麗にその数だけが消える．既に消えていた場合には悪影響が全くない．

ex

111011011 = 3と6でない
100000000 = 9を消したい
011111111 = 9のbit反転
1,3式で&算
011011011 = 3,5,9でない

000000001 = 1で確定
011111111 = 9の反転
000000001 = &算をとっても影響しない

エラーがないか

同じグループに属するセルを全て足しあわせたものと，全てから算をとったものが，111111111になるとき，正しいと言える．

ex

000000001
000000010
000000100
...
100000000
これらはorでも+でも111111111になる

000000001
000000001
000000100
...
100000000
あやまって2が1になってしまった場合は111111111にならない

まとめ

数独を解くときの支援ツールを作ろうとしていたら，bit演算で数独の解を求めるプログラムになっていた．でも思ったよりも劇的な効果は得られなかったというのが正直な感想．

最近個人的なブームがsatやsugarあたりなのでJ4Satとかで書いたりしてみたい．

余談ですが，

Sudokuという名前のディレクトリにしているのでcd(省略可能) Sudokuするときにsudo<TAB><ENTER>(kが遠い)とやろうとするため，sudoが意図せず発動してました．

2016-01-05

GitHubとかからJava ProjectをEclipseにimportするときのまとめ

Java

前置き

EclipseのJava Projectで.projectだとか.classpathだとかをignoreしてて，いざEclipseでcloneしたのを使おうとしたときに毎回調べてる気がするので忘れないようにメモ．

Eclipse: Mars.1 Release (4.5.1)

手順

0. File -> import

1. Git -> Projects from Git

f:id:turane_gaku:20160105202103p:plain

2. Clone URI

f:id:turane_gaku:20160105202130p:plain

3. (URIを入力)

f:id:turane_gaku:20160105202134p:plain

4. (Branchを選択)

f:id:turane_gaku:20160105202138p:plain

5_1. (Cloneするディレクトリを指定)

5_2. (ここでDirectoryをコピー)

f:id:turane_gaku:20160105202141p:plain

6. Import using the New Project wizard

f:id:turane_gaku:20160105202144p:plain

7. Java -> Java Project

f:id:turane_gaku:20160105202147p:plain

8_1. (Project nameを適当に付ける)

8_2. (Use default locationのチェックを外す)

8_3. (Locationに先程コピーしたDirectoryを貼りつけ)

f:id:turane_gaku:20160105202155p:plain

9. Finish

f:id:turane_gaku:20160105202154p:plain

その他

Localに既にcloneしてあるのを使うときは手順2でExisting local repositoryを選択するとrepository選択画面ののち手順6に行く．

2015-12-31

c++でto_stringが使えないときの対処法について

c++

前置き

OSXで書いていたときは問題なく動いていたソースコードをWindowsのCygwinで動かそうとしたら，
'to_strin' was not declared in this scope
とかいうエラーでコンパイルに失敗した．
std::to_string()だし，ないってことはないんじゃない?と思ったけど，現に使えなかった．
というわけで，to_string()が使えなかったときの対処法について調べた．

対処

http://stackoverflow.com/questions/12975341/to-string-is-not-a-member-of-std-says-so-g http://stackoverflow.com/questions/12975341/to-string-is-not-a-member-of-std-says-so-g#answer-20861692
この回答をちょっと変更して使った．

    template < typename T > std::string to_string( const T& n )
    {
        std::ostringstream stm ;
        stm << n ;
        return stm.str() ;
    }
}

これを適当なところに記入しておくだけであら不思議．プログラムの方を変えずにto_string()が使えるようになりました．
to_stringが複数定義されているとかにならないのかと思ったが，std::to_stringの引数はintとかfloatみたいに一個一個丁寧に書いてあるため，上手いことオーバーロードになっていて通るらしい．