SSブログ
前の10件 | -

rubyをawkのように使うには [プログラミング]

Rubyになれるためには使用機会を増やすことだ、と思い、よく使うawkの代わりにRubyが使えれば良いな、と思いました。

■起動オプション

Rubyの起動オプションによって、awkのような振る舞いにできるようです。

 -n 入力ファイルを1行ずつループして読み込む

 -a 読み込んだ1行を自動でフィールド分割


■shebang

起動オプションが必要となると、shebangを少し工夫しなければなりません。というのは、例えばawkの場合、

#!/bin/awk -f

BEGIN{ 〜 }
/hoge/{
 〜
}


という感じで書きますが、Rubyの場合、環境によってインストール場所が違うことを考慮して、

#!/usr/bin/env ruby

と書くことが多いようです。でもshebangでは引数は1つしか使えない環境があるそうなので、rubyのオプションを続けて書くことができません。そこで、

#!/bin/sh
exec ruby -S -nax $0 "$@"
#! ruby

と書くと良いとのこと。おまじないですな。日常使いなら、使用環境は固定されているから、ここまで凝らずに、

#!/usr/bin/ruby -na

くらいにしておくのが妥当かもしれません。


■awkとの違い

システム変数などは結構違いますが、主なものだけ。rubyの変数名はperlみたいで不気味ですね。「require 'English'」すると、awkと同じ変数名が使えるようになります。

個人的に最大の違いはnext文のふるまい。ちょっと変わったことをする場合にわりとよく使うので。rubyの場合はフラグ変数を使わないと、nextの動きを実現できない気がします。

あとは、awkは変数スコープがグローバルなので、rubyのローカル変数を使っていて変数が見えなくて「あれ?」ということがあります。

 
項目 awk ruby
フィールドセパレータ FS $;
出力フィールドセパレータ OFS $,
レコードセパレータ RS $/
出力レコードセパレータ ORS $\
カレント行番号 NR $.
分割されたフィールド $1, $2,... $F[0],$F[1],...
パターンマッチ $1 ~ /正規表現/ if $F[0] =~ /正規表現/
BEGINブロック内変数のスコープ グローバル
1.8まではBEGINブロック内、
2.0以降はグローバル
next文のふるまい
次の入力行を読み込み、
スクリプトの最初から実行
ループを1個抜けるだけ

nice!(0)  コメント(0) 

rubyでバイナリファイルを読んでみる [プログラミング]

■はじめに

何か新しく言語を勉強したいと思い、オブジェクト指向もいっしょに勉強できそうな ruby を選んでみました。

さっと入門サイトで勉強してみたのですが、文法をいくら教えてもらったところで実践しないと身につかないものです。

題材は何がいいか悩んだのですが、仕事でも関係しているGDSIIフォーマットというバイナリファイルのパーサを作ってみることにしました。

明らかにスクリプト言語には不向きと思われるのですが、ざっと調べるとバイナリファイルの取扱もできそうですし、GDSIIは十数種の可変長レコードの塊で、各レコードが階層構造を構成したりしているので、それらをオブジェクトとして扱えたりするのでは、という期待もありました。


■GDSIIフォーマット

本当にrubyでGDSIIを扱いたいのなら、すでにそういうライブラリが存在するようです。

今回は勉強が目的なので、スクラッチで組み上げます。

GDSIIフォーマットについては、こちらのサイトがまとまってて助かりました。


■パーサ

いちおうGDSIIファイルを読んで、各レコードの情報を取り出せるようになりました。パースするところまでで、その先の各レコードの階層構造を構築するところはできていません。

なにしろruby初心者なので、「rubyらしく」実装できていないと思います。各レコードをクラスにしてはみましたが、オブジェクト指向をほとんど理解していないので、どこまで有効な設計になっているか、はなはだ疑問です。このあたりは一人でやっていても駄目ですね。


#!/usr/bin/env ruby
#
# stream.rb -- GDSII Data Parser
#  "Stream Format" is output format of GDSII data.
#
#  Todo:
#   - do like ruby.
#   - probably bug about upper/lower nibble
#
#  Reference:
#   GDSII Format: http://www7b.biglobe.ne.jp/~garaku/HSGDS/GDSII_p01.html
#
#  History:
#   0.2        change method to class of each record, add Colrow
#   0.1        implement some records will be used usually
#
#  Author:
#   M.Hori   

####################
# Constant
####################

# Variables
MY_VERSION = '0.2'
USAGE_MSG = "Usage: " << $PROGRAM_NAME << " [options] GDSII_File"

####################
# Module
####################

module Util
    # Data Converter
    def int2(input)
        input.unpack("n")[0]
    end

    def int4(input)
        input.reverse.unpack("l*")[0]
    end

    def real4(input)
    end

    def real8(input)
        # S=sign, E=index, M=mantissa
        #  SEEEEEEE MMMMMMMM MMMMMMMM ...(total 7 byte)... MMMMMMMM
        # real8 = (-1)^sign * (0.mantissa)_2 * 16^(index-64)
        sign = (input & 0x8000000000000000)>>63
        index = (input & 0x7F00000000000000)>>56
        mantissa = (input & 0x00FFFFFFFFFFFFFF)/(2.0**56)
        ((-1)**sign)*(mantissa*16**(index-64))
    end

    def ascii(input)
        input.unpack("A*")
    end

    # long print
    def lpr(*var)
        printf(*var) if $long
    end

    module_function :int2, :int4, :real4, :real8, :ascii, :lpr
end

####################
# クラス
####################

class Record
    # 2byte ==> unpack("n")    # convert to big endian (byte order)
    # 1byte ==> unpack("c")
    # +----------------------+
    # |         size         | 2 byte
    # +-----------+----------+               --+
    # |record_type|_data_type| 1 byte + 1 byte |
    # +-----------+----------+                 +-- others
    # |         data         | (size-4) byte   |
    # |           :          |                 |
    # +----------------------+               --+

    # readable instance variables
    attr_reader :record_type, :_data_type, :data

    # Array
    @@record_type_array = [
        "HEADER",   "BGNLIB",   "LIBNAME",   "UNITS",       "ENDLIB",
        "BGNSTR",   "STRNAME",  "ENDSTR",    "BOUNDARY",    "PATH",
        "SREF",     "AREF",     "TEXT",      "LAYER",       "DATATYPE",
        "WIDTH",    "XY",       "ENDEL",     "SNAME",       "COLROW",
        "TEXTNODE", "NODE",     "TEXTTYPE",  "PRESENTATION","SPACING",
        "STRING",   "STRANS",   "MAG",       "ANGLE",       "UNITEGER",
        "USTRING",  "REFLIBS",  "FONTS",     "PATHTYPE",    "GENERATIONS",
        "ATTRTABLE","STYPTABLE","STRTYPE",   "ELFLAGS",     "ELKEY",
        "LINKTYPE", "LINKKEYS", "NODETYPE",  "PROPATTR",    "PROPVALUE",
        "BOX",      "BOXTYPE",  "PLEX",      "BGNEXTN",     "ENDEXTN",
        "TAPENUM",  "TAPECODE", "STRCLASS",  "RESERVED",    "FORMAT",
        "MASK",     "ENDMASKS", "LIBDIRSIZE","SRFNAME",     "LIBSECUR",
    ]
   
    @@data_type_array = [
        "NO_DATA", "BIT_ARRAY", "INT_2", "INT_4", "REAL_4",
        "REAL_8",  "STRING",
    ]

    # Initializer
    def initialize(size, others)
        @size = size
        @record_type, @_data_type = others[0,2].unpack("cc")
        @data = others[2,size-4]    # size=2, record=1, data=1, total=4byte
    end

    # to_s
    def to_s
        return    @@record_type_array[@record_type],
                @@data_type_array[@_data_type]
    end

    # no_operation
    def no_operation
        Util.lpr(" --------------------")
    end

    # Parser
    def parse_data
        case record_type
        when  0    # HEADER
            Util.lpr(" GDSII_Version=%s", Header.new(@data).gds_version)
        when  1    # BGNLIB
            _m, _a = Bgnlib.new(@data).date
            Util.lpr(" Mod=%s Acc=%s", _m, _a)
        when  2 # LIBNAME
            Util.lpr(" LibraryName=%s", Libname.new(@data).name)
        when  3 # UNITS
            #units()
            _uu, _um = Units.new(@data).units
            Util.lpr(" dbUnitByUserUnit=%.1e dbUnitByMeter=%.1e", _uu, _um)
        when  4 # ENDLIB
            no_operation()
        when  5 # BGNSTR
            $log["structures"] += 1
            _m, _a = Bgnstr.new(@data).date
            Util.lpr(" Mod=%s Acc=%s", _m, _a)
        when  6 # STRNAME
            Util.lpr(" StructureName=%s", Strname.new(@data).name)
        when  7 # ENDSTR
            no_operation()
        when  8 # BOUNDARY
            $log["boundaries"] += 1
            no_operation()
        when  9    # PATH
            $log["paths"] += 1
            no_operation()
        when 10    # SREF
            $log["srefs"] += 1
            no_operation()
        when 11    # AREF
            $log["arefs"] += 1
            no_operation()
        when 12    # TEXT
            $log["texts"] += 1
            no_operation()
        when 13 # LAYER
            Util.lpr(" LayerNumber=%d", Layer.new(@data).number)
        when 14 # DATATYPE
            Util.lpr(" DataType=%d", Datatype.new(@data).number)
        when 15    # WIDTH
            Util.lpr(" Width=%.1f", Width.new(@data).width)
        when 16 # XY
            Util.lpr(" %s", Xy.new(@data).xy_list)
        when 17 # ENDEL
            no_operation()
        when 18    # SNAME
            Util.lpr(" StructureName=%s", Sname.new(@data).name)
        when 19    # COLROW
            _col, _row = Colrow.new(@data).colrow
            Util.lpr(" Col=%d, Row=%d", _col, _row)
        when 22    # TEXTTYPE
            Util.lpr(" Text_Type=%d", Texttype.new(@data).number)
        when 23    # PRESENTATION
            _obj = Presentation.new(@data)
            Util.lpr(" Font#=%d Origin=%s", _obj.font, _obj.origin)
        when 25    # STRING
            Util.lpr(" String=%s", Strings.new(@data).name)
        when 26    # STRANS
            _obj = Strans.new(@data)
            Util.lpr(" Mirror=%s Mag=%d Angle=%d",
                _obj.mirror_flag, _obj.mag_flag, _obj.angle_flag)
        when 27    # MAG
            Util.lpr(" Mag=%.1e", Mag.new(@data).value)
        when 28    # ANGLE
            Util.lpr(" Angle=%.1f", Angle.new(@data).value)
        when 33    # PATHTYPE
            Util.lpr(" PathType=%d", Pathtype.new(@data).number)
        when 48    # BGNEXTN
            Util.lpr(" ProjectionSize=%.1f", Bgnextn.new(@data).width)
        when 49    # ENDEXTN
            Util.lpr(" ProjectionSize=%.1f", Endextn.new(@data).width)
        end
    end
end

# HEADER
class Header
    def initialize(data)
        @data = data
    end

    def gds_version
        case @data.unpack("n")[0]
        when 0   then @ver = "v3.0"
        when 3   then @ver = "v3.0"
        when 4   then @ver = "v4.0"
        when 5   then @ver = "v5.0"
        when 600 then @ver = "v6.0"
        else          @ver = "unknown"
        end
        @ver
    end
end

# BGNLIB
class Bgnlib
    def initialize(data)
        @data = data
    end

    def date
        my,mm,md,mh,mn,ms,ay,am,ad,ah,an,as = @data.unpack("n12")
        @last_modify =
            "%4d/%02d/%02d,%02d:%02d:%02d"%([1900+my,mm,md,mh,mn,ms])
        @last_access =
            "%4d/%02d/%02d,%02d:%02d:%02d"%([1900+ay,am,ad,ah,an,as])
        return @last_modify, @last_access
    end
end

# LIBNAME
class Libname
    def initialize(data)
        @data = data
    end

    def name
        Util.ascii(@data)
    end
end

# UNITS
class Units
    def initialize(data)
        @data = data
    end

    def units
        # unpack("H16") H: Hex(upper nibble first)
        @unit_by_uu = Util.real8(@data[0, 8].unpack("H16").join.hex)
        @unit_by_meter = Util.real8(@data[8, 8].unpack("H16").join.hex)
        return @unit_by_uu, @unit_by_meter
    end
end

# BGNSTR
class Bgnstr < Bgnlib
end

# STRNAME
class Strname < Libname
end

# LAYER
class Layer
    def initialize(data)
        @data = data
    end

    def number
        Util.int2(@data)
    end
end

# DATATYPE
class Datatype < Layer
end

# WIDTH
class Width
    def initialize(data)
        @data = data
    end

    def width
        Util.int4(@data)
    end
end

# XY
class Xy
    def initialize(data)
        @data = data
    end

    def xy_list
        # unpack("l*") : long(32bit signed int)
        # reverse : convert endian
        # map(&:to_i) : convert array to int
        xys = @data.reverse.unpack("l*").map(&:to_i)
        @xy_list = ""
        xys.each_slice(2) do |x, y|
            @xy_list <<= "(" << x.to_s << "," << y.to_s << ")"
            # '<<' beter more than '+' for cat strings
        end
        @xy_list
    end
end

# SNAME
class Sname < Libname
end

# COLROW
class Colrow
    def initialize(data)
        @data = data
    end

    def colrow
        @data.unpack("n2")
    end
end

# TEXTTYPE
class Texttype < Layer
end

# PRESENTATION
class Presentation
    def initialize(data)
        @data = data
    end

    def font
        @data.unpack("c2")[0].to_i
    end

    def origin
        text_origin_array = [
            "upperLeft",  "upperCenter",  "upperRight",  nil,
            "centerLeft", "centerCenter", "centerRight", nil,
            "lowerLeft",  "lowerCenter",  "lowerRight",  nil
        ]
        text_origin_array[@data.unpack("c2")[1].to_i]
    end
end

# STRING
class Strings < Libname
end

# STRANS
class Strans
    def initialize(data)
        @data = data
    end

    def mirror_flag
        (@data.unpack("c2")[0] & 0x80)>>7
    end

    def mag_flag
        (@data.unpack("c2")[1] & 0x04)>>2
    end

    def angle_flag
        (@data.unpack("c2")[1] & 0x02)>>1
    end
end

# MAG
class Mag
    def initialize(data)
        @data = data
    end

    def value
        Util.real8(@data[0, 8].unpack("H16").join.hex)
    end
end

# ANGLE
class Angle < Mag
end

# PATHTYPE
class Pathtype < Layer
    # 0=no projection,1=half round projection,
    # 2=half width projection, 4=width is BGNEXTN,ENDEXTN
end

# BGNEXTN
class Bgnextn < Width
end

# ENDEXTN
class Endextn < Width
end

####################
# Main
####################

# Variables
$log = {
    "records"         => 0,
    "structures"    => 0,
    "boundaries"    => 0,
    "paths"            => 0,
    "srefs"            => 0,
    "arefs"            => 0,
    "texts"            => 0,
}

# Method

def usage()
    STDERR.printf("%s\n", USAGE_MSG)
end

def cprint(*var)
    console = open('/dev/tty', "w") do |con|
        con.printf(*var)
    end
end

# Parse Options
require 'optparse'
OptionParser.new do |opt|
    opt.banner = USAGE_MSG
    opt.version = MY_VERSION
    opt.on('-l', 'print long format information') { |v| $long = v }
    begin
        opt.parse!(ARGV)
    rescue OptionParser::InvalidOption => e
        puts e.message
        usage
        exit
    end
end

# Open File then Read and Parse
INPUT_FILE = ARGV[0]
if !INPUT_FILE then usage; exit end

begin
    # not neccesary file.close
    File.open(INPUT_FILE, "rb") do |file|
        record = {}
        c = 0
        $bgnstr = 0; $boundary = 0; $path =0;
        $sref = 0; $aref = 0; $text = 0
        # Display Title
        Util.lpr("%4s %3s %-12s %-9s %s\n",
            "#", "byte", "RecType", "DataType",
            "Contents (XY,WIDTH is dbUnit)")
        # Read File
        while !file.eof
            # Get Record Size
            size = file.read(2).unpack("n")[0]    # to big endian
            if size > 0
                data = file.read(size-2)    # get remain record
                record[c] = Record.new(size, data)
                _record_type, _data_type = record[c].to_s
                Util.lpr("%4d: %3d %-12s %-9s",
                    c, size, _record_type, _data_type)
                record[c].parse_data()
                Util.lpr("\n")
            else
                break
            end
            c += 1
            cprint("\r%d records loaded.", c) if !$long
        end
        cprint("%s: %d records, %d structures, %d boundaries, %d paths, %d srefs, %d arefs, %d texts\n",
            INPUT_FILE, c, $log["structures"], $log["boundaries"], $log["paths"], $log["srefs"], $log["arefs"], $log["texts"])
    end
rescue Errno::ENOENT
    STDERR.printf("\n%s not found.\n", INPUT_FILE)
rescue Errno::EACCES
    STDERR.printf("\ncannot open %s.\n", INPUT_FILE)
rescue => e
    STDERR.printf("\nexception: class=#{e.class}, msg=#{e.message}\n")
end

#EOF

■余談

実行してみると、やっぱり遅い。読んでパース、というのを繰り返しているからかもしれません。一気に読んでからパースすれば少しは早くなるかも。でもまあ、速さを求めるなら最初からCで作りますよね。

その昔、まだCGIでもてはやされる前のperl4を勉強したのですが、独特の文法と変数の頭につくいろいろな記号に馴染めないうちに、perl5でがらっと変わってしまい、perlとは決別しました。それ以来、shとawkとCで乗り切ってきました。今回、pythonを横目で見つつrubyに挑戦してみました。

偏差値 [雑記]





学生にはおなじみの「偏差値」ですが、あいまいな理解だったので、少し調べてみました。備忘録です。

定義は以下。

 Z = 50 + 10*(x - m)/σ

 ここで、Zが偏差値、xが自分の点数、mが平均点、σが標準偏差です。

つまりは、平均点との差をとることで平均を0に、σで割って10掛けることで標準偏差を10に正規化し、50を足すことで平均を50にしています。ここで、なぜ標準偏差が10で平均が50かっていうと、特に数学的な意味はなく、単にそうした、というもののようです。

ただの正規分布の話になってしまいますが、偏差値60(平均+1σ)なら上位16%に、70(平均+2σ)なら上位3%にいる、ということになります。目安の数字として覚えておくといいですね。

ただし、一般の試験において、平均点は発表されることが多いので知ることができますが、標準偏差は発表されませんし、全員の点数がわからないと計算できないので、上記の定義式では偏差値を算出するのは困難です。

そこで、簡易的な式があります。

 Z' = 50 + (x - m)/2

ZとZ'を比べてみると、σ=20と見なしていることがわかります。これは、一般的にテストはσ=20を目指して設計されることから来ているようです。

これなら平均点がわかれば計算できます。100点満点で、平均点が50点、自分が60点なら、偏差値は55ということです。


遺伝的アルゴリズム [プログラミング]

遺伝的アルゴリズムを知ったのはもう10年以上も前になるでしょうか。アルゴリズムとかプログラムというものは、解析的というか、わかっている解法を実行するものだと思っていたものですから、遺伝的アルゴリズムやニューラルネットワーク、さらには最近はやりの強化学習のように、解法というかそのパラメータをプログラム自身が探索する、解法はブラックボックス、というアプローチが、とても斬新に思えたものでした。

遺伝的アルゴリズムは、基本的なものは実装も簡単なので、素人でもその強力さが実感できて面白いです。こちらの「エンジニアが正しく「I love you」と伝えるための遺伝的アルゴリズム(殺伐) 」というページを拝見して、興味が再燃したので、おなじ課題をCで組んでみました。ランダムな文字列から出発して、世代交代を繰り返し、「I love you」にたどり着けるか?


   
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#define TARGET "I love you"
#define MUTATE_CHANCE 0.5
#define GENE_NUM 20
#define NUM_OF_MUTATE 1
#define ASCII_MIN 32
#define ASCII_MAX 127

typedef struct {
char *gstr;
int gval;
}GENE;

GENE gene[GENE_NUM];
int gstr_len;
int debug = 0;

void init_gene( void );
int eval( char * );
void gene_sort( void );
int comp( const void *, const void * );
void cross( void );
void mutate( float );
void pr( void );
void pr_usage( void );

// compare for qsort
int comp( const void *c1, const void *c2 ) {
GENE t1 = *(GENE *)c1;
GENE t2 = *(GENE *)c2;

return t1.gval - t2.gval;
}

// init gene
void init_gene() {
int i, j;

// allocate memory
gstr_len = strlen( TARGET );
for ( i = 0; i < GENE_NUM; i++ ) {
gene[i].gstr = (char *)malloc( sizeof(char)*(gstr_len+1) );
if ( gene[i].gstr == NULL ) {
printf( "memory allocation faild.\n" );
exit( EXIT_FAILURE );
}
}

// generate string & sort
srand( (unsigned)time( NULL ) );
for ( i = 0; i < GENE_NUM; i++ ) {
for ( j = 0; j < gstr_len; j++ ) {
sprintf( &gene[i].gstr[j], "%c", rand()%(ASCII_MAX-ASCII_MIN)+ASCII_MIN );
}
gene[i].gstr[j+1] = '\0';
gene[i].gval = eval( gene[i].gstr );
}
qsort( gene, sizeof(gene)/sizeof(gene[0]), sizeof(gene[0]), comp );
}

// mutation
void mutate( float chance ) {
int i, j, k;
int pm;

for ( i = 0; i < GENE_NUM; i++ ) {
if ( chance*10 < rand()%10 ) {
j = rand()%gstr_len;
pm = rand()%2 == 0 ? 1 : -1;
if ( gene[i].gstr[j] == ASCII_MIN) pm = 1;
if ( gene[i].gstr[j] == ASCII_MAX) pm = -1;
gene[i].gstr[j] += pm;
}
}
}

// evaluation
int eval( char *str ) {
int i, v;
int r = 0;
char target[] = TARGET;

for ( i = 0; i < gstr_len; i++ ) {
v = strncmp( target+i, str+i, 1 );
r += v*v;
}

return( r );
}

// select & cross
void cross() {
int i, cp;

cp = rand()%gstr_len;
for ( i = 0; i < gstr_len; i++ ) {
if ( i < cp ) {
gene[GENE_NUM-2].gstr[i] = gene[0].gstr[i];
gene[GENE_NUM-1].gstr[i] = gene[1].gstr[i];
} else {
gene[GENE_NUM-2].gstr[i] = gene[1].gstr[i];
gene[GENE_NUM-1].gstr[i] = gene[0].gstr[i];
}
}
}

// print
void pr() {
int i;

for ( i = 0; i < GENE_NUM; i++ ) {
printf( " >%2d %10s %d\n", i, gene[i].gstr, gene[i].gval );
}
}

// usage
void pr_usage() {
printf( "usage: ga [-dh]\n" );
}

// main
int main( int argc, char **argv ) {
int i, j;
int generation = 0;
int opt;

// optrion
while ( ( opt = getopt( argc, argv, "dh" ) ) != -1 ) {
switch ( opt ) {
case 'd': debug = 1; break;
case '?':
case 'h':
default: pr_usage(); exit( EXIT_SUCCESS );
}
}

// init
init_gene();
if ( debug ) pr();

// loop
while ( gene[0].gval > 0 ) {
// select & cross
cross();

// mutation
mutate( MUTATE_CHANCE );

// evaluation
for ( i = 0; i < GENE_NUM; i++ ) {
gene[i].gval = eval( gene[i].gstr );
}

// sort
qsort( gene, sizeof(gene)/sizeof(gene[0]), sizeof(gene[0]), comp );

printf( "%4d %5d %10s\n", generation, gene[0].gval, gene[0].gstr );
if ( debug ) pr();
generation++;
}
}



実行結果がこちら。左端の数字は世代です。2列目は、「I love you」からどれだけ遠いか、3列目がその文字列。2, 3列目はその世代で最も優秀な個体のものが示されています。

ga_term1.png

「I love you」にたどり着くと実行が停止します。数百世代を経て、ようやくたどり着きました。でもCygwinでも実行時間はあっという間です。

ga_term2.png

何世代くらいでたどり着くのか、100回繰り返してみました。横軸が世代数で、縦軸が「I love you」からどれくらい遠いか、です。0でたどり着いたことになるのですが、0近辺を拡大するために logスケールにしてみました。なので1が最小値です。1にたどり着く世代数には、結構、幅があります。

ga.png

今回の例では、1世代の個体数は20で、ベストな2個体で交叉してワースト2個体と交換します。その後、突然変異は全個体に対して確率50%で生じ、どれか1文字がASCIIコードで1だけ変化します。

このあたりのパラメータを変えてみるとなかなか興味深いです。突然変異なしでは、一向に収束しません。突然変異の確率は、高い方が早く収束するようです。世代交代は、ベスト2個体をワースト2個体と交換するだけでも十分で、交叉はあまり収束性に影響しないようです。


ラングトンのループ [プログラミング]

ラングトンにはもうひとつ、ループというものがあります。

永久に自己増殖を繰り返していくセル・オートマトンです。

ルールはなんと219個!、しかも初期状態がかなり複雑です。

詳しくはこちら、もしくはこちら

またまた、ルールだけを参考に、ncursesを利用して自前で組んでみました。

無限増殖とはいえ、画面には限りがあるので、上辺と下辺、左辺と右辺がそれぞれ繋がっているトーラス状の世界としてみました。

無限に続くので、終了はCtrl-Cによるものとし、シグナルをキャッチして終わるようにしました。

毎世代、画面の全セルごとに、ルールを検索することになるのですが、最初は甘く見て普通のリニアサーチにしてみたら、ループが増殖するに従い、目に見えて画面更新が遅くなっていきます。これは、最初の黒が多い状態ではルールテーブルの最初のあたりで検索が済むのに対し、色のついたセルのルールはテーブルの下方にあるので、検索に時間がかかるためでした。

Linuxではともかく、Cygwinでは待てないほど遅くなります。それに進むにしたがって遅くなる、というのもカッコ悪いです。

そこで、stdlibにあるバイナリサーチbsearchを使ってみました。バイナリサーチはテーブルがソートされていることが前提なので、これまたstdlibにあるクイックソートqsortを使いました。

効果てきめん! 安定して超高速になりました。



//
// langton's loop
// make: gcc lloop.c -lncurses -o lloop
//

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <ncurses.h>
#include <unistd.h>
#include <signal.h>

#define LLOOP_TABLE "lloop.table"
#define TABLE_SIZE 256
#define RULE_SIZE 10
#define BUF_SIZE 256
#define Q_W 15
#define Q_H 10
#define USLEEP 1000
#define VALUE_AT_NO_RULE 0

int **prev, **post;
char table[TABLE_SIZE*4][RULE_SIZE];
int num_of_table = 0;
int width, height;
int debug = 0;
int num_of_search;

void finalizer( void );
void sig_catch( int );
void rotate_rule( char *, char *, int );
int comp( const void *, const void * );
int comp2( const void *, const void * );
void load_table( void );
int search_table( int, int, int, int, int );
void alloc_mem( void );
void def_color( void );
void init_array( void );
void print_usage( void );

// finalizer
void finalizer() {
int i;

// free
for ( i = 0; i < width; i++ ) free( prev[i] );
free( prev );
for ( i = 0; i < width; i++ ) free( post[i] );
free( post );

attrset( COLOR_PAIR(0) );
mvprintw( 1, 0, "Hit any key" );
getch();
endwin();
exit( EXIT_SUCCESS );
}

// signal handler
void sig_catch( int sig ) {
finalizer();
}

// rotate rule
void rotate_rule( char *in, char *out, int rot ) {
int i;

out[0] = in[0];
for ( i = 1; i <= 4; i++ ) {
out[i] = in[(i-1+rot)%4+1];
}
out[5] = in[5];
}

// compare for qsort
int comp( const void *c1, const void *c2 ) {
return strcmp( (char *)c2, (char *)c1 );
}

// compare for bsearch
int comp2( const void *c1, const void *c2 ) {
return strncmp( (char *)c2, (char *)c1, 5 );
}

// load table
void load_table() {
FILE *fp;
char buf[BUF_SIZE];

if ( (fp = fopen( LLOOP_TABLE, "r" )) == NULL ) {
printf("faile open error\n");
exit( EXIT_FAILURE );
}
while ( fgets( buf, BUF_SIZE, fp ) != NULL ) {
if ( isdigit( buf[0] ) ) {
strncpy( table[num_of_table], buf, 6 );
table[num_of_table][6] = '\0';
num_of_table++;
// expand rule
rotate_rule( buf, table[num_of_table++], 1 );
rotate_rule( buf, table[num_of_table++], 2 );
rotate_rule( buf, table[num_of_table++], 3 );
}
}
// sort for bsearch
qsort( table, sizeof(table)/sizeof(table[0]), sizeof(table[0]), comp );
if ( debug ) {
for ( int i = 0; i < num_of_table; i++ ) {
printf("rule: %d %s\n", i, table[i] );
}
}
}

// search table
int search_table( int c, int n, int e, int s, int w ) {
int i;
char *result;
char key[RULE_SIZE];

sprintf( key, "%d%d%d%d%d", c, n, e, s, w );
result = bsearch( key, table, sizeof(table)/sizeof(table[0]), sizeof(table[0]), comp2 );
if ( result == NULL ) {
return( VALUE_AT_NO_RULE );
} else {
return( atoi( result+5 ) );
}
}

// allocate memory
void alloc_mem() {
int i;

prev = (int **)malloc( sizeof(int *)*width );
if ( prev == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
for ( i = 0; i < width; i++ ) {
prev[i] = (int *)malloc( sizeof(int)*height );
if ( prev[i] == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
}
post = (int **)malloc( sizeof(int *)*width );
if ( post == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
for ( i = 0; i < width; i++ ) {
post[i] = (int *)malloc( sizeof(int)*height );
if ( post[i] == NULL ) {
printf("memory allocation failed.\n");
exit(EXIT_FAILURE);
}
}
}

// define color
void def_color() {
start_color();
init_pair( 0, COLOR_BLACK, COLOR_BLACK );
init_pair( 1, COLOR_BLACK, COLOR_BLUE );
init_pair( 2, COLOR_BLACK, COLOR_RED );
init_pair( 3, COLOR_BLACK, COLOR_GREEN );
init_pair( 4, COLOR_BLACK, COLOR_YELLOW );
init_pair( 5, COLOR_BLACK, COLOR_MAGENTA );
init_pair( 6, COLOR_BLACK, COLOR_WHITE );
init_pair( 7, COLOR_BLACK, COLOR_CYAN );
}

// init array
void init_array() {
int i, j;
int init_q[Q_H][Q_W] = {
{ 0,2,2,2,2,2,2,2,2,0,0,0,0,0,0 },
{ 2,1,7,0,1,4,0,1,4,2,0,0,0,0,0 },
{ 2,0,2,2,2,2,2,2,0,2,0,0,0,0,0 },
{ 2,7,2,0,0,0,0,2,1,2,0,0,0,0,0 },
{ 2,1,2,0,0,0,0,2,1,2,0,0,0,0,0 },
{ 2,0,2,0,0,0,0,2,1,2,0,0,0,0,0 },
{ 2,7,2,0,0,0,0,2,1,2,0,0,0,0,0 },
{ 2,1,2,2,2,2,2,2,1,2,2,2,2,2,0 },
{ 2,0,7,1,0,7,1,0,7,1,1,1,1,1,2 },
{ 0,2,2,2,2,2,2,2,2,2,2,2,2,2,0 } };

for ( i = 0; i < width; i++ ) {
for ( j = 0; j < height; j++ ) {
if ( i >= (width-Q_W)/2 &&
i < (width+Q_W)/2 &&
j >= (height-Q_H)/2 &&
j < (height+Q_H)/2 ) {
prev[i][j] = init_q[j-(height-Q_H)/2][i-(width-Q_W)/2];
} else {
prev[i][j] = 0;
}
}
}
}

// print usage
void print_usage() {
printf( "usage: lloop [-dh]\n" );
}

// main
int main( int argc, char **argv ){
int i, j;
int x, y;
int generation = 0;
int c, n, e, s, w;
int opt;
int change = 0;

// option
while ( (opt = getopt( argc, argv, "dh" )) != -1 ) {
switch ( opt ) {
case 'd':
debug = 1; // debug mode
break;
case 'h':
case '?':
default:
print_usage();
exit(EXIT_SUCCESS);
}
}

// set signal handler
if ( SIG_ERR == signal( SIGINT, sig_catch ) ) {
fprintf( stderr, "cannot set signal handler.\n" );
exit( EXIT_FAILURE );
}

// load rule table
load_table();

// init screen
if ( !debug ) {
initscr();
getmaxyx( stdscr, height, width );
} else {
width = 80; height=51;
}

// define color
if ( !debug ) def_color();

// allocate memory
alloc_mem();

// init prev
init_array();
// init position
for ( i = 0; i < width; i++ ) {
for ( j = 0; j < height; j++ ) {
if ( !debug ) {
attrset( COLOR_PAIR( prev[i][j] ));
mvaddstr( j, i, " " );
}
}
}
if ( !debug ) {
mvprintw( 0, 0, "Hit any key" );
refresh();
}
getch();
if ( !debug ) erase();

// endless loop
for (;;) {
for ( i = 0; i < width; i++ ) {
for ( j = 0; j < height; j++ ) {
// set next generation
c = prev[i][j];
if ( j == 0 ) {
n = prev[i][height-1];
} else {
n = prev[i][j-1];
}
e = prev[(i+1)%width][j];
if ( i == 0 ) {
w = prev[width-1][j];
} else {
w = prev[i-1][j];
}
s = prev[i][(j+1)%height];
post[i][j] = search_table( c, n, e, s, w );
if ( post[i][j] < 0 ) {
printf("search faild.\r\n");
exit( EXIT_FAILURE );
}
}
}

// draw
change = 0;
for ( i = 0; i < width; i++ ) {
for ( j = 0; j < height; j++ ) {
if ( !debug ) {
attrset( COLOR_PAIR( post[i][j] ));
mvaddstr( j, i, " " );
}
if ( prev[i][j] != post[i][j] ) change++;
prev[i][j] = post[i][j];
}
}

// not changed
if ( change == 0 ) {
finalizer();
}

// print generation
if ( !debug ) {
attrset( COLOR_PAIR(6) | A_REVERSE );
mvprintw( 0, 0, "%d", generation );
num_of_search = 0;
refresh();
} else {
printf( "%d %d\n", generation, num_of_search );
num_of_search = 0;
if ( generation >= 500 ) exit(EXIT_SUCCESS);
}
generation++;
//usleep( USLEEP );
}

// finalize
finalizer();
}



実行するとこんな感じ。 カラーでにぎやか。わっかがぐるぐる回りながら上下左右に増えていきます。

lloop.png

真っ暗な世界を増殖する場合はいいんですが、自分の残骸などに衝突すると、ルールに記載のないパターンになることがあるみたいで、その場合は死ぬ(黒くなる)ようにしてみたら、最後に残骸だけ残って停止します。

lloop2.png


ラングトンのアリ [プログラミング]

前回書いたライフゲームを調べていたら、「ラングトンのアリ」というものを知りました。ライフゲームよりももっと簡単なたった2個のルールで、まさにアリが歩いた跡のような、複雑な図形が生成されます。

もっと興味深いのは、10000ステップを過ぎたあたりから、それまで混沌(カオス)としていた足跡が、急に規則正しく変化して、右下に一直線に走って行ってしまうように変化することです。

「カオスの縁」というのだそうですが、局所的な単純なルールから、全体的には混沌が生じ、その混沌から突然秩序が生じるわけです。なぞです。

これまた、ルールだけを頼りに自前でコーディングしてみました。またncursesを使いましたが、アリにはもっと広いフィールドが必要な感じです。ncursesだとどうしても表示の分解能が文字単位になってしまうので粗いです。

前回のライフゲームでは、フィールドの大きさを #define で決めうちにしていたのですが、今回は、ターミナルの大きさいっぱいを使うようにしました。起動時のターミナルサイズを取得しmallocしました。アリがフィールドから飛び出るとプログラムが止まるようにしました。

あと、Linuxではループごとにusleepで少し待たないとあっという間に終わってしまうのですが、Cygwinでは何秒に指定しようがusleepを呼ぶだけのオーバーヘッドが数十msくらいある感じで非常に遅いです。下の例ではusleepをコメントアウトしています。




//
// langton's ant
//

#include    <stdlib.h>
#include    <ncurses.h>
#include    <unistd.h>
#define     USLEEP      1

int     **array;
int     width, height;
enum    DIR { NORTH, EAST, SOUTH, WEST };

void    alloc_mem( void );
void    def_color( void );
void    init_array( void );

// allocate memory
void    alloc_mem() {
    int i;
    array = (int **)malloc( sizeof(int *)*width );
    if ( array == NULL ) {
        printf("memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
    for ( i = 0; i < width; i++ ) {
        array[i] = (int *)malloc( sizeof(int)*height );
        if ( array[i] == NULL ) {
            printf("memory allocation failed.\n");
            exit(EXIT_FAILURE);
        }
    }
}

// define color
void    def_color() {
    start_color();
    init_pair( 0, COLOR_WHITE,  COLOR_BLACK );
    init_pair( 1, COLOR_BLACK,  COLOR_WHITE );
}

// init array
void    init_array() {
    int i, j;

    for ( i = 0; i < width; i++ ) {
        for ( j = 0; j < height; j++ ) {
            array[i][j] = 0;
        }
    }
}

// main
int main(){
    int     i;
    int     x, y;
    int     counter = 0;
    enum DIR    dir;

    // init screen
    initscr();
    getmaxyx( stdscr, height, width );

    // define color
    def_color();

    // allocate memory
    alloc_mem();

    // init array
    init_array();

    // init position
    x = width / 2;
    y = height / 2;
    dir = NORTH;
    mvprintw( y, x, "Hit any key" );
    getch();
    erase();

    // endless loop
    for (;;) {
        if ( array[x][y] == 1 ) {
            array[x][y] = 0;
            attrset( COLOR_PAIR(0) );
            mvaddstr( y, x, " " );
            switch ( dir ) {
                case NORTH:
                    dir = EAST;
                    x = x + 1;
                    break;
                case EAST:
                    dir = SOUTH;
                    y = y + 1;
                    break;
                case SOUTH:
                    dir = WEST;
                    x = x - 1;
                    break;
                case WEST:
                    dir = NORTH;
                    y = y - 1;
                    break;
            }
        } else {
            array[x][y] = 1;
            attrset( COLOR_PAIR(1) );
            mvaddstr( y, x, " " );
            switch ( dir ) {
                case SOUTH:
                    dir = EAST;
                    x = x + 1;
                    break;
                case WEST:
                    dir = SOUTH;
                    y = y + 1;
                    break;
                case NORTH:
                    dir = WEST;
                    x = x - 1;
                    break;
                case EAST:
                    dir = NORTH;
                    y = y - 1;
                    break;
            }
        }

        // judge overflow
        if ( x < 0 || y < 0 || x > width-1 || y > height-1 ) {
            break;
        }

        // draw
        mvprintw( 0, 0, "%d", counter );
        refresh();
        counter++;
        //usleep( USLEEP );
    }

    // finalize
    attrset( COLOR_PAIR(0) );
    mvprintw( 1, 0, "Hit any key" );
    getch();
    endwin();
    return(0);
}


動かすとこんな感じ。

 lant.png


ライフゲーム [プログラミング]

ライフゲームといってもボードゲームの人生ゲームではなく、昔のUNIXには/usr/game/lifeとしてインストールされていたもののことです。

ふと思い立って、Cで実装してみました。ネットに溢れている実装例は見ていないので、正解ではないでしょうが、それっぽく動きます。ncursesを試しに使ってみたらきれいにできました。



//
// life
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <ncurses.h>
#include <string.h>

#define XSIZE 40
#define YSIZE 20
#define DIVBY 5
#define USLEEP 500000
#define MESSAGE "hit any key to exit"

int prev[XSIZE][YSIZE], post[XSIZE][YSIZE];

// initialize array
void init_array() {
int i, j, r;

srand( (unsigned)time( NULL ) );

for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
r = rand() % DIVBY;
if ( r != 0 ) {
prev[i][j] = 0;
} else {
prev[i][j] = 1;
}
}
}
}

// judge dead or alive
int dora( int sum, int now ) {
if ( now == 1 ) {
if ( sum == 2 || sum == 3 ) {
return(1);
} else {
return(0);
}
} else {
if ( sum == 3 ) {
return(1);
} else {
return(0);
}
}
}

// change generation
void chgen() {
int i, j;
int z;

for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
if ( i == 0 && j == 0 ) {
z = prev[i+1][j] + prev[i+1][j+1] + prev[i][j+1];
} else if ( i == XSIZE-1 && j == YSIZE-1 ) {
z = prev[i-1][j] + prev[i-1][j-1] + prev[i][j-1];
} else if ( i == 0 ) {
z = prev[i][j-1] + prev[i][j+1] \
+ prev[i+1][j-1] + prev[i+1][j] + prev[i+1][j+1];
} else if ( i == XSIZE-1 ) {
z = prev[i][j-1] + prev[i][j+1] \
+ prev[i-1][j-1] + prev[i-1][j] + prev[i-1][j+1];
} else if ( j == 0 ) {
z = prev[i-1][j] + prev[i+1][j] \
+ prev[i-1][j+1] + prev[i][j+1] + prev[i+1][j+1];
} else if ( j == YSIZE-1 ) {
z = prev[i-1][j] + prev[i+1][j] \
+ prev[i-1][j-1] + prev[i][j-1] + prev[i+1][j-1];
} else {
z = prev[i-1][j-1] + prev[i-1][j] \
+ prev[i-1][j+1] + prev[i][j-1] + prev[i][j+1] \
+ prev[i+1][j-1] + prev[i+1][j] + prev[i+1][j+1];
}
post[i][j] = dora(z, prev[i][j]);
}
}
}

// copy array
void copy_array() {
int i, j;

for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
prev[i][j] = post[i][j];
}
}
}

// judge loop
int isSilence() {
int i, j;
int z = 0;

for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
if ( prev[i][j] != post[i][j] ) {
z++;
}
}
}
return(z);
}

// main routine
int main() {
int i, j;
int x, y, w, h;
int gen;

// initialize screen
initscr();
getmaxyx( stdscr, h, w );

// initialize array
init_array();

erase();
for (;;) {
gen++;
x = w / 2;
y = ( h - YSIZE ) / 2 - 2;
move(y, x);
printw("%d", gen);
for ( i = 0; i < XSIZE; i++ ) {
for ( j = 0; j < YSIZE; j++ ) {
// display
x = ( w - XSIZE ) / 2 + i;
y = ( h - YSIZE ) / 2 + j;
move(y, x);
if ( prev[i][j] == 0 ) {
addch('.');
} else {
addch('@');
}
}
}
refresh();

// change generation
chgen();

// jedge silence
if ( 0 == isSilence() ) {
break;
}

copy_array();
usleep( USLEEP );
}

x = w / 2 - strlen( MESSAGE ) / 2;
y = h / 2 + YSIZE / 2 + 2;
move(y, x);
printw( MESSAGE );

timeout(-1);
getch();

endwin();
return(0);
}



動かすとこんな感じ。

life.png

ずっと見ていられます。


ズンドコキヨシ問題 [プログラミング]

先日、ズンドコキヨシ問題というのを知りました。

少し前に流行ったらしいのですが、プログラミングのセンスを試すのに課される問題のようです。

上記のページに様々な言語での実装例が載っています。そこになかった、awkで実装してみました。

BEGINブロックのみというawkにあるまじき実装ですが。

#!/bin/awk -f
# zunzoko.awk
BEGIN{
    srand()
    for (;;) {
        if ( 0 == int((rand()*10)%2) ) {
            z++
            printf("ズン ")
        } else {
            printf("ドコ")
            if ( z == 4 ) {
                printf("  キ・ヨ・シ!\n")
                break
            }
            z = 0
            printf("\n")
        }
    }
}



動かすとこんな感じ。

awk.png

ズンが4回より多く続いた場合はキヨシコールしないようにしたので、間抜けにズンが長い場合があります。


関数電卓

また関数電卓を買ってしまいました(中央)。

P_20160611_225854.jpg

CASIOのfx-JP900です。液晶が高精細なのが、これまでの電卓にはなかった特徴です。高精細とは言ってもスマホなどに比べれば全然ですが。

正直、これらの関数電卓はもう高機能すぎて、ほとんどの機能は使いません(断言)。自分の使いたい機能が使いやすく実装されているか、につきるわけです。

右に写っているCannonのF-766Sは、他の製品にない特徴があって、-9乗のn(ナノ)や、6乗のM(メガ)など、電気屋が多様する単位が2アクションで入力できます。表示もできます。CASIOもできるけど、入力も表示も手間が2、3倍掛かって使う気がしない。CASIOのテンキーには機能がアサインされていないキーがあるので、ぜひここに実装してほしいところです。Shift-3で3乗のk、Alfa-3で-3乗のm、6にuとM、9にnとG、2にpとT、5にfとP、とアサインすれば2アクションで入力できるし、覚えやすいじゃないですか。

左に写っているSHARPは、16進数の入力や計算が他メーカより簡単にできるので購入しました。その後、16進数計算はあまり使わなくなってしまったので、今回、CASIOを買いました。

液晶は確かにきれいなのですが、使っていてうれしかったのは、薄く軽くなっていることです。今の技術なら、もっともっと薄く軽くできるのにって、ずっと思っていたんです。まあ、コストとの兼ね合いなのでしょうが。ただし、机に置いて使うと、歪んでいるのか、カタカタして使いにくい。

 少々高くてもいいから、スマホの実装技術を駆使して、かっちりと薄く、キーも固く、液晶も超高精細で、というのを作れませんかね。いや、作れるんでしょうが、売れないんでしょうね。

とにかく、各社のいいとこどりをしたベストな関数電卓がほしいです。


nice!(1)  コメント(0)  トラックバック(0) 
共通テーマ:日記・雑感

ランサム・サーガ [本]

岩波少年文庫のランサム・サーガ新訳がついに完結しました。といってももう数か月も前ですけど。

P_20160502_090052.jpg 

子供が持って行ってしまっているので、最後の2巻分(上下で4冊)しか写真はありませんが、数年かけて全12巻(24冊)揃えましたよ。長かった。

岩波少年文庫は本当に名作ぞろいで、小中学校のうちにすべて読破すべき、と思うくらいです。ランサム・サーガを知ったのは残念ながら大人になってからだったので、少年時代に読みたかった、と思いました。

きっとコアなファンがたくさん解説していらっしゃると思いますので、 簡単にしか紹介しませんが、少年少女のありようが詰まっていて、忘れていた子供の頃の気持ちを思い出すことのできる、稀有な作品です。

また、ヨットが重要なモチーフとなっており、その技術的な面や船乗りとしての規律など、私には特に興味深く感じられました。

小学生のお子さんにぜひ勧めてください! 旧訳ならどこの図書館にも揃っています。

気になった方は、作者「アーサー・ランサム」や、このシリーズの第1作「ツバメ号とアマゾン号」などで検索してみてください。 


前の10件 | -

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。