読者です 読者をやめる 読者になる 読者になる

つらねの日記

プログラムの進捗やゲームをプレイした感想などを書き連ねる日記。

単語距離を調べるクソプログラムを書いた

前置き

突然ですが,皆さん,Wikipediaである単語からある単語へ出来るだけ短かく到達するゲームとかやったことありますよね.

私はありません

ともかく,如何なる単語に対してもハブのようなものが存在し,7だか14だか以内にはどの単語にも到達することが出来ると聞く.それを本当なのかどうか立証してみようという試みである.

結果論

距離1~2じゃないと運用できないくらいには,思ったより通信で速度が出なかったので,サーバーへの負荷は承知でスレッド化するかなんかしないとだめそう.

続きを読む

uncrustifyが死んだ

本記事は,brew updateをしたらuncrustifyが死んだので,頑張って復活させるまでの奮闘記です.

余談ですが,Atomのエラーウィンドウみたいなのを,キーボードから消す方法を探しています.{}の数がずれていたりすると毎回それが出て,バツボタンポチーするのが面倒でならないの.

序章

死体発見

Atom Beautifyのuncrustifyを多様して適当すぎるインデントやフォーマットを綺麗に整えてもらいながら,C++競技プログラミングをしているわけだが,先日,唐突にUnexpected ')' for 'ANGLE_OPEN'とかいう謎のエラーで死んだ.

ほぼテンプレートの展開しかやっていなかったような状態だったのに唐突に死んだのに,完全に意味が不明😇 ANGEL_OPENってなんだ,天使〜〜〜〜〜😇😇って思ってたけどよくよくみたらangleだった. まぁ,角度開きも十分意味がわからないけれどもさ.

まとめ

眼科にいこう

続きを読む

bindkey -v の一部分を<nop>にしたい

結論

bindkey -M vicmd 'j' undefined-key

bindkey -v はじめました

ターミナルを使っていて,ちょっと不便に思っていたのが,コマンドモードが使えないとこ. 半ばvim教徒の人間にとってデフォルトの操作では不便を感じてしまうのだ.

他のプロのzshrcを眺めていたら,bindkey -vという記述を見掛けた. 調べると,vim bindでターミナルを操作できるらしい.

神だった

端的に感想を述べると神だった.今まで欲っしていたものはこれだ!!!!!これだったんだ!!!!という感じだった.

今まで使ってきて手慣れた操作を別に登録していいとこ取りしてあげることで,素晴しい使い心地となった.

問題点が一つ

ただ唯一,jk ESCに関する問題があった.モードがins,cmdのいづれであるのも関わらす,とりあえず,jkを押すような人間なので,down-line-orhistoryやら,up-line-or-historyが呼ばれて入力しているものがずれることがあって困る. 前の履歴とか調べたいときは,C-PNhistory-beginning-searchを使うのでやめて欲しいのだ.

NOPにしたい

keybindを消してさしあげたかったが,消し方がわからなかった. しかもbindkey -Dで消そうとしてもなんか消えない.bindkey -D 'j'やらbindkey -D -M vicmd 'j'やら試してみたけどだめだった.

しょうがないのでbindkey -M vicmd 'j' undefined-keyをした.

なんか微妙にかっこわるいのでもっと良い方法があると思う.

gunzip 備忘録

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

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

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

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という単語を用いるのはあまりよろしいことではないのかもしれない.

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

はじめに

マンデルブロ集合とは

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_sethttp://azisava.sakura.ne.jp/mandelbrot/を眺め, 無事理解し,processingにて図形を生成することが出来たので,忘れぬように書き記しておく. processingでは他の言語におけるcomplexなどといった便利なクラスは存在しないので, 実数部と虚数部を分けて,それぞれ自分で計算する必要がある.

f:id:turane_gaku:20160206014856p:plain

図形生成のアルゴリズム

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

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

https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:SierpinskiTriangle.PNG

これは三角形の中に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:a2 + b2 > 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));
    }
  }
}

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

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

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 に関しても理解を深めたい💪