Hatena::ブログ(Diary)

当面C#と.NETな記録 このページをアンテナに追加 RSSフィード

2009/11/15 (日)

[] goroutine を使ってみた  goroutine を使ってみた - 当面C#と.NETな記録 を含むブックマーク  goroutine を使ってみた - 当面C#と.NETな記録 のブックマークコメント

Go 翻訳プロジェクトが立ち上がったようですね。チュートリアルのかなりの部分がもう訳されてます。

http://go.shibu.jp/

遊んでるうちに、将来は C に取って代わりそうだなという気がしてきました。

昨日のコードの goroutine 版が動きました。まだ goroutine がどういうものかさっぱりわからないので、使い方が間違ってる可能性大ですが。

ちょっと新人いじめがすぎました。遅いです。いや、使い方が間違ってるほうが大きいかもしれないけど。

(追記) うわさの runtime.GOMAXPROCS つけたらものすごく速くなった!使えるかもと思った。コードは差し替えておきます。

4CPU割り当ててやってみたらむしろ遅くなったw みんな並列じゃ苦労してるんだねw

以下、コード

package main

import (
	"math";
	"fmt";
	"os";
	"runtime";
	"container/vector";
)

const (
	K	= 4;
	N	= 2;
)

const channelBufferNum = 2048

type DeBruijnSeq struct {
	k, n, max	int;
	out		chan *vector.IntVector;	// for output
	count		chan int;
}

type DeBruijnSeqResult struct {
	ch	chan *vector.IntVector;
	result	chan *vector.Vector;
}

func Init(k, n int) (d *DeBruijnSeq, result *DeBruijnSeqResult, ok bool) {
	if k < 2 || 10 < k {
		return nil, nil, false
	}
	if n < 1 {
		return nil, nil, false
	}

	max := math.Pow(float64(k), float64(n));
	if float64(0x7FFFFFFF) < max {
		return nil, nil, false
	}

	out, result := startOutputServer();
	count := make(chan int, channelBufferNum);
	return &DeBruijnSeq{k, n, int(max), out, count}, result, true;
}

func (d *DeBruijnSeq) Search() {
	a := vector.NewIntVector(d.n);
	for i := 0; i < d.n; i++ {
		a.Set(i, 0)
	}
	go d.searchCore(a);
}

func (d *DeBruijnSeq) searchCore(a *vector.IntVector) {
	// 重複判定
	if !d.isUnique(a) {
		d.count <- -1;
		return;
	}

	// 完成判定
	if d.isComplete(a) {
		//fmt.Println( " comp! " );
		d.out <- a;
		d.count <- -1;
		return;
	}

	// 次の反復へ
	for i := 0; i < d.k; i++ {
		d.count <- 1;
		b := vector.NewIntVector(0);
		b.AppendVector(a);	// copy
		b.Push(i);
		go d.searchCore(b);
	}
	d.count <- -1;
}

func (d *DeBruijnSeq) isUnique(a *vector.IntVector) bool {
	if a.Vector.Len() <= d.n {
		return true
	}

	pos := a.Vector.Len() - d.n;

	for i := 0; i < pos; i++ {
		if sequenceEqual(a, i, pos, d.n) {
			return false
		}
	}
	return true;
}

func sequenceEqual(v *vector.IntVector, a, b, len int) bool {
	for i := 0; i < len; i++ {
		if v.At(a) != v.At(b) {
			return false
		}
		a++;
		b++;
	}
	return true;
}

func (d *DeBruijnSeq) isComplete(a *vector.IntVector) bool {
	if a.Vector.Len() != d.max {
		return false
	}

	b := vector.NewIntVector(0);
	b.AppendVector(a);	// copy

	for i := 0; i < d.n-1; i++ {
		b.Push(b.At(i));
		if !d.isUnique(b) {
			return false
		}
	}
	return true;
}

func startOutputServer() (chan *vector.IntVector, *DeBruijnSeqResult) {
	out := make(chan *vector.IntVector, channelBufferNum);
	result := make(chan *vector.Vector, 2);
	go output(out, result);
	return out, &DeBruijnSeqResult{out, result};
}

func output(in chan *vector.IntVector, out chan *vector.Vector) {
	v := vector.New(0);
	for !closed(in) {
		if data := <- in; data != nil {
			//fmt.Println( data );
			v.Push(data);
		}
	}
	out <- v;
}

func main() {
	runtime.GOMAXPROCS(2);

	d, result, ok := Init(K, N);
	if !ok {
		os.Exit(1)
	}

	d.Search();
	for numOfGor := 1; numOfGor != 0; {
		numOfGor += <-d.count
	}
	close(result.ch);
	n := <-result.result;

	fmt.Println(n.Len());
}

[] C の弱点 default のスペルミスを継承していた  C の弱点 default のスペルミスを継承していた - 当面C#と.NETな記録 を含むブックマーク  C の弱点 default のスペルミスを継承していた - 当面C#と.NETな記録 のブックマークコメント

no more creat。

package main
import "fmt"

func main() {
	a := 4;

	switch a {
	case 0, 1, 2:
		fmt.Println( a );
	case 3:
		fmt.Println( "いっぱい" );
	defuuuuult:
		fmt.Println( "defuuuuuuult" );
/*
	default:
		fmt.Println( "default" );
*/
	}
}

何も表示されません。

文法見ると禁止されてるっぽいのに、穴がありますね。「defuuuuult:」は前の「case 3:」に続く StatementList 中のラベルになってるのかも。

「$ hg log」したらこんなのが。やられたw

changeset:   3956:4a3f6bbb5f0c
user:        Ken Thompson <xxx>
date:        Tue Nov 10 15:05:15 2009 -0800
summary:     spell it with an "e"

$ hg log -r3956 -p

+	O_CREATE	= O_CREAT;		// create a new file if none exists.

2009/11/14 (土)

[] Go でバックトラックを書いてみた  Go でバックトラックを書いてみた - 当面C#と.NETな記録 を含むブックマーク  Go でバックトラックを書いてみた - 当面C#と.NETな記録 のブックマークコメント

Go language に De Bruijn sequence を列挙するコードを移植してみました。C# で書いたときのコードは

goroutine を使って並列化したいんですが、まだデッドロックしてうまくいってませんw なのでとりあえずできたシーケンシャル版。ちなみに効率的に列挙するコードじゃなく、いじめ試験みたいなものです。

De Bruijn の読みがずっと謎だったんですが、コンピュータの数学という本では「ドブリューイン」としてました。O記法の数学のあたりにちらっと名前が出てきました。

Go は関数から多値で返す文法がきれいでいいですね。C# の out はやってることは正しいのに、汚い文法なのが悲しい。レシーバーとインターフェイスでも遊んでみたいな。Go を最初に見たときは古臭い文法だと思ったけど、調べているといろいろと今どきっぽい機能をちゃんと持ってたりします。まーまだわからないことだらけですが。

package main

import (
    "math";
    "fmt";
    "os";
    "container/vector";
)

type DeBruijnSeq struct {
    k, n, max int;
    results *vector.Vector;
}

func Init( k, n int ) ( d *DeBruijnSeq, ok bool ) {
    if k < 2 || 10 < k { return nil, false }
    if n < 1 { return nil, false }

    pow := math.Pow( float64( k ), float64( n ) );
    if float64( 0x7FFFFFFF ) < pow { return nil, false }
    max := int( pow );

    r := vector.New( 0 );
    return &DeBruijnSeq{ k, n, max, r }, true
}

func ( d *DeBruijnSeq ) Search() {
    a := vector.NewIntVector( d.n );
    for i := 0; i < d.n; i++ { a.Set( i, 0 ) }
    d.searchCore( a );
}

func ( d *DeBruijnSeq ) searchCore( a *vector.IntVector ) {
    // 重複判定
    if !d.isUnique( a ) { return }

    // 完成判定
    if d.isComplete( a ) {
        d.output2( a );
        return
    }

    // 次の反復へ
    for i := 0; i < d.k; i++ {
        b := vector.NewIntVector( 0 );
        b.AppendVector( a );  // copy
        b.Push( i );
        d.searchCore( b );
    }
}

func ( d *DeBruijnSeq ) isUnique( a *vector.IntVector ) bool {
    if a.Vector.Len() <= d.n { return true }

    pos := a.Vector.Len() - d.n;

    for i := 0; i < pos; i++ {
        if sequenceEqual( a, i, pos, d.n ) { return false }
    }
    return true
}

func sequenceEqual( v *vector.IntVector, a, b, len int ) bool {
    for i := 0; i < len; i++ {
        if v.At( a ) != v.At( b ) { return false }
        a++; b++;
    }
    return true
}

func ( d *DeBruijnSeq ) isComplete( a *vector.IntVector ) bool {
    if a.Vector.Len() != d.max { return false }

    b := vector.NewIntVector( 0 );
    b.AppendVector( a );  // copy

    for i := 0; i < d.n - 1; i++ {
        b.Push( b.At( i ) );
        if !d.isUnique( b ) { return false }
    }
    return true
}

func ( d *DeBruijnSeq ) output2( a *vector.IntVector ) {
    d.results.Push( a )
}

func main() {
    d, ok := Init( 4, 2 );
    if !ok { os.Exit( 1 ); }

    d.Search();

    fmt.Println( d.results.Len() );

    if len := d.results.Len(); len < 10 {
        for i := 0; i < len; i++ {
            fmt.Println( d.results.At(i) )
        }
    }
}

VMware Player 上の x86Ubuntu に 2CPU 割り当てて実行したんですが、結構速いかも。

2009/11/13 (金)

[] Go  Go - 当面C#と.NETな記録 を含むブックマーク  Go - 当面C#と.NETな記録 のブックマークコメント

ロブ パイクとケン トンプソン(と V8 の人。扱い低くてゴメンナサイ)の新言語が2009年の今、出てくるなんてスゴイですね。C/C++ の幕引きは俺たちの手で…ってところでしょうか。Plan9 もきっと Unix の幕引きのために作ったんだろうなぁ。

でも、Go って名前の googlability 悪すぎ。わざとだろうけどw 検索するとイラっとくるw

それにしても、初日からプログラム書いた人があちこちにいてすごい。

とりあえず Go のチュートリアルをちまちまやって楽しんでます。

(追記) x86用の汎用 Makefile おいときます。1ソース→1実行ファイル用

.SUFFIXES:.go .8
.go.8:
	8g $<

.SUFFIXES:.8 .out
.8.out:
	8l -o $@ $<

GO	= $(wildcard *.go)
OUT	= $(GO:.go=.out)

all:	$(OUT)

!8 とかやると泣けるので(T-T)


(追記2) The Go Programming Language とか書いておかないと気付いてもらえない気がしたので書いておく。でも Issue 9 って名前に変わるならそれでもいいw

文字列の長さは utf8.RuneCountInString( s ) で取れた。len(s) だとutf8でのバイト数が返ってくる…

Rune は Unicode character のことを短くそう呼んでるそうな。


(追記3) /go/src/pkg/exp/spacewar/ こ、これは伝説のwww

// This package and spacewar.go implement a simple PDP-1 emulator

// complete enough to run the original PDP-1 video game Spacewar!

でも make できない!

2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 09 | 11 | 12 |
2007 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 08 | 09 | 10 | 12 |
2009 | 01 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 07 |
2011 | 04 | 07 | 10 |
2012 | 04 | 12 |
2013 | 08 |
2014 | 03 | 08 |
2017 | 09 |