What's New Qiita

20190822のGoに関する記事は4件です。

  • 投稿日：2019-08-22T23:36:49+09:00

ビット演算の高速化メモ２

はじめに

前回のメモの続きです。

ネタの起点はThe Art of Computer Programming。

trailing zeros

（08/26追記）

LSBの説明が間違っていたため修正しました。
fujitanozomuさん、ご指摘ありがとうございます。

trailing zerosは右端から0が連続する数を10進数で表した数値です。
例えば、

10100000 -> 5
01001101 -> 0

です。

ビットマップのループ再訪

前回のメモでx & -xとx &= x - 1を組み合わせて、立っているビットのみループさせてみました。

01011000
↓
f(00001000)
f(00010000)
f(01000000)

しかし、受け手の関数としてはビットマップよりもインデックス値のほうが扱いやすいことが多いと思います。
そこで上の処理を

01011000
↓
f(3)
f(4)
f(6)

このように変える方法 ＝ trailing zerosの計算 が必要になります。
標準的なプログラミング言語では、ライブラリが次のような関数を用意していますが...

# Java
Long.numberOfTrailingZeros(long bits)

ここでは敢えて使わずに済ます方法を書き留めます。

ビットカウントによる方法

シンプルな方法としては、前回の記事で書いたビットカウントを使う方法があります。

最右の1ビットを抜き出したビット列から1を引くと、
末尾まで1ビットが連続するのでビットカウントした値がそのままtrailing zerosに。

00100000 -> -1 -> 00011111 -> ビットカウント -> 5
00000001 -> -1 -> 00000000 -> ビットカウント -> 0

(注)0だと正しい値にならないので別途考慮が必要

簡単ですが、Log(ビット長)のオーダになってしまうのが気になるところ。

De Brujin Sequenceによる方法

掛け算１回＋シフト１回＋配列アクセス１回で済ます方法があります。

流れ

De Brujin Sequenceという名のマジックナンバー00011101を掛け算して
00100000 -> * 00011101 -> 10100000
00000001 -> * 00011101 -> 00011101

マジックナンバーの長さに応じて右シフトして（8 - log(8)ビット）
10100000 -> ５ビット右シフト -> 00000101
00011101 -> ５ビット右シフト -> 00000000

あらかじめ作った参照表をみると

ビットパターン(下3桁) trailing zeros
000 0
001 1
010 6
011 2
100 7
101 5
110 4
111 3

00000101 -> 5
00000000 -> 0

と計算できます。

解説

De Brujin Sequenceはグレイコードの圧縮表現です。
例えば、8ビットのDe Brujin Sequenceは3桁のグレイコードをつなげたものになっています。

00011101に対して、先頭から順番に3桁ずつ切り取る＝5ケタの右シフト演算をすると
000 001 011 111 110 101 010 100 000
となっていて、8ビットの中に0〜7を折りたたむことが可能です。

つまり最右の1ビットをDe Brujin Sequenceに掛ける（8ビット）ということは、

De Brujin Sequence 最右の1ビット De Brujin Sequence x 最右の1ビット 先頭から3桁切り取る
00011101 00000001 00011101 000
00011101 00000010 00111010 001
00011101 00000100 01110100 011
00011101 00001000 11101000 111
00011101 00010000 11010000 110
00011101 00100000 10100000 101
00011101 01000000 01000000 010
00011101 10000000 10000000 100

最右の1ビットをグレイコード＝0〜7にマッピングする、ということと同じです。

あとはインデックスにグレイコード、値にtrailing zerosを対応させた配列を作っておけばOK。

ビットパターン(下3桁) trailing zeros
000 0
001 1
010 6
011 2
100 7
101 5
110 4
111 3

掛け算が高速に実行できるのであれば、ビットカウントを使うより効率的です。
ちなみに、GoのTrailingZeros関数はDe Brujin Sequenceで実装されています。

Goのbitsパッケージ（ソースコード）
https://golang.org/src/math/bits/bits.go?s=3946:3972#L103

ビット長ごとのDe Brujin Sequence

8ビットの場合を例にとりましたが、16ビット、32ビット、64ビット版は次の通りです。

ビット長 De Brujin Sequence 右シフト長
8 0x1D または 0x17 5
16 0x0D2F など16種 12
32 0x077CB531 0x077BE629 など2048種 27
64 0x03F79D71B4CA8B09 0x022FDD63CC95386D など 67108864種 58

32ビットの値はGo実装、
64ビットの値はThe Art of Computer Programming＝Go実装、
De Brujin Sequenceの数や他の値の例についてはChess Programming Wikiから引用。

ここまで書いたけど

trailing zerosはBMI1拡張命令のひとつ「tzcnt」命令として実装されてるので、
言語によってはライブラリが提供する関数で勝手に最適化されるかもしれません。

あと、De Brujinの読み方がわからない。。。
「ド・ブラン」「デ・ブルーイン」等々
どれが多数派なんでしょうね？

参考

De Bruijn Sequence
https://www.chessprogramming.org/De_Bruijn_Sequence

Goのbitsパッケージで参照されている論文
Leiserson, Charles E., Harald Prokop, and Keith H. Randall. "Using de Bruijn sequences to index a 1 in a computer word." Available on the Internet from http://supertech. csail. mit. edu/papers. html 3.5 (1998)

de Bruijn Graph を使った de novo アセンブリの発想がすごい件
http://hoxo-m.hatenablog.com/entry/20100930/p1

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む
  • 投稿日：2019-08-22T23:36:49+09:00

De Brujin Sequenceを使ってtrailing zerosを計算する

はじめに

（元ネタはThe Art of Computer Programmingです。「こんなのもあるよ」ぐらいの説明ですが...）

trailing zeros

LSB（Least Significant Bit）は最下位ビットのことです。
例えば、

10100000 -> LSB -> 00100000
01001101 -> LSB -> 00000001

となります。
ここで求めたいのは、LSBが出てくる位置を10進数で表した数値です。こんな感じ。

10100000 -> LSB -> 00100000 -> LSBの位置 -> 5
01001101 -> LSB -> 00000001 -> LSBの位置 -> 0

一般的には、これをtrailing zerosと呼ぶようです。

ビットマップのループ再訪

前回の記事でx & -xとx &= x - 1を組み合わせて、立っているビットのみループさせてみました。

01011000
↓
f(00001000)
f(00010000)
f(01000000)

しかし、受け手の関数としてはビットマップよりもインデックス値のほうが扱いやすいことが多いと思います。
そこで上の処理を

01011000
↓
f(3)
f(4)
f(6)

このように変える方法 ＝ trailing zerosの計算 が必要になります。
標準的なプログラミング言語では、ライブラリが次のような関数を用意していますが...

# Java
Long.numberOfTrailingZeros(long bits)

ここでは敢えて使わずに済ます方法を紹介します。

ビットカウントによる方法

シンプルな方法としては、前回の記事で書いたビットカウントを使う方法があります。

LSBを抜き出したビット列から1を引くと、
末尾まで1ビットが連続するのでビットカウントした値がそのままLSBの位置に。

00100000 -> -1 -> 00011111 -> ビットカウント -> 5
00000001 -> -1 -> 00000000 -> ビットカウント -> 0

(注)0だと正しい値にならないので別途考慮が必要

簡単ですが、Log(ビット長)のオーダになってしまうのが気になるところ。

De Brujin Sequenceによる方法

本題です。
どんなビット長であっても、掛け算１回＋シフト１回＋配列アクセス１回で済ます方法があります。

流れ

De Brujin Sequenceという名のマジックナンバー00011101を掛け算して
00100000 -> * 00011101 -> 10100000
00000001 -> * 00011101 -> 00011101

マジックナンバーの長さに応じて右シフトして（8 - log(8)ビット）
10100000 -> ５ビット右シフト -> 00000101
00011101 -> ５ビット右シフト -> 00000000

あらかじめ作った参照表をみると

ビットパターン(下3桁) trailing zeros
000 0
001 1
010 6
011 2
100 7
101 5
110 4
111 3

00000101 -> 5
00000000 -> 0

と計算できます。

解説

De Brujin Sequenceはグレイコードの圧縮表現です。
例えば、8ビットのDe Brujin Sequenceは3桁のグレイコードをつなげたものになっています。

00011101に対して、先頭から順番に3桁ずつ切り取る＝5ケタの右シフト演算をすると
000 001 011 111 110 101 010 100 000
となっていて、8ビットの中に0〜7を折りたたむことが可能です。

つまりLSBをDe Brujin Sequenceに掛ける（8ビット）ということは、

De Brujin Sequence LSB De Brujin Sequence x LSB 先頭から3桁切り取る
00011101 00000001 00011101 000
00011101 00000010 00111010 001
00011101 00000100 01110100 011
00011101 00001000 11101000 111
00011101 00010000 11010000 110
00011101 00100000 10100000 101
00011101 01000000 01000000 010
00011101 10000000 10000000 100

LSBをグレイコード＝0〜7にマッピングする、ということと同じです。

あとはインデックスにグレイコード、値にtrailing zerosを対応させた配列を作っておけばOK。

ビットパターン(下3桁) trailing zeros
000 0
001 1
010 6
011 2
100 7
101 5
110 4
111 3

掛け算が高速に実行できるのであれば、ビットカウントを使うより効率的です。
ちなみに、GoのTrailingZeros関数は実装はDe Brujin Sequenceが使われています。

Goのbitsパッケージ（ソースコード）
https://golang.org/src/math/bits/bits.go?s=3946:3972#L103

ビット長ごとのDe Brujin Sequence

8ビットの場合を例にとりましたが、16ビット、32ビット、64ビット版は次の通りです。

ビット長 De Brujin Sequence 右シフト長
8 0x1D または 0x17 5
16 0x0D2F など16種 12
32 0x077CB531 0x077BE629 など2048種 27
64 0x03F79D71B4CA8B09 0x022FDD63CC95386D など 67108864種 58

32ビットの値はGo実装、
64ビットの値はThe Art of Computer Programming＝Go実装、
De Brujin Sequenceの数や他の値の例についてはChess Programming Wikiから引用。

ここまで書いたけど

LSBはBMI1拡張命令のひとつ「tzcnt」命令として実装されてるので、
言語によってはライブラリが提供する関数で勝手に最適化されるかもしれません。

あと、De Brujinの読み方がわからない。。。
「ド・ブラン」「デ・ブルーイン」等々
どれが多数派なんでしょうね？

参考

De Bruijn Sequence
https://www.chessprogramming.org/De_Bruijn_Sequence

Goのbitsパッケージで参照されている論文
Leiserson, Charles E., Harald Prokop, and Keith H. Randall. "Using de Bruijn sequences to index a 1 in a computer word." Available on the Internet from http://supertech. csail. mit. edu/papers. html 3.5 (1998)

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む
  • 投稿日：2019-08-22T22:01:31+09:00

Macでgo-tfliteを動かしてみる

はじめに

mattn/go-tfliteというものが出て動かそうとしていたのですが、動くまでに詰まることがとても多かったのでメモ代わりに残します。

環境

バージョンとかの違いで、変わってしまうかもしれないので
go-tfliteやtensorflowのビルドのバージョンも載せておきます。

1. tensorflow liteのビルド

このビルドに関してはmruby + TensorFlow Liteで画像分類するという記事を参考にしました。
おそらくUbuntuの方は、この記事通りにビルドしてもらったらいいと思います。

まずは $GOPATH/src/github.com/tensorflow/tensorflowにこのリポジトリをcloneします。
なぜ、$GOPATH以下に置くのかというとgo-tfliteのtflite.goでライブラリを取得する際に相対パスでライブラリへのパスを指定しているみたいだからです。

次に、ld: library not found for -lrtというエラーが出ないように、tensorflow/lite/tools/make/Makefileから -lrtオプションを消します。(このエラーについてはあまり良くわからなかったので詳しい方がいれば教えて下さい。)

tensorflow/lite/tools/make/Makefile
        CORE_CC_ALL_SRCS += tensorflow/lite/delegates/nnapi/quant_lstm_sup.cc
        CORE_CC_ALL_SRCS += tensorflow/lite/nnapi/nnapi_implementation.cc
-       LIBS += -lrt

次に以下のコマンドを実行します。

$ ./tensorflow/lite/tools/make/download_dependencies.sh
$ make -f tensorflow/lite/tools/make/Makefile

2. C experimental APIライブラリのビルド

こちらも上述の記事を参考にさせてもらって以下のように、Makefileを書きました。
tensorflow/lite/experimental/c以下でmakeを実行すると、libtensorflowlite_c.soというファイルが出来上がります。

tensorflow/lite/experimental/c/Makefile
CXX = clang++
SRCS =  c_api.cc c_api_experimental.cc
OBJS = $(subst .cc,.o,$(subst .cxx,.o,$(subst .cpp,.o,$(SRCS))))
TENSORFLOW_ROOT = ../../../../
CXXFLAGS = -DTF_COMPILE_LIBRARY -I$(TENSORFLOW_ROOT) -I$(TENSORFLOW_ROOT)/tensorflow/lite/tools/make/downloads/flatbuffers/include -fPIC
TARGET = libtensorflowlite_c
OS_ARCH = osx_x86_64
TARGET_SHARED := $(TARGET).so
LDFLAGS += -L$(TENSORFLOW_ROOT)/tensorflow/lite/tools/make/gen/$(OS_ARCH)/lib
LIBS = -ltensorflow-lite

.SUFFIXES: .cpp .cxx .o

all : $(TARGET_SHARED)

$(TARGET_SHARED) : $(OBJS)
    $(CXX) -shared -o $@ $(OBJS) $(LDFLAGS) $(LIBS)
.cxx.o :
    $(CXX) -std=c++14 -c $(CXXFLAGS) -I. $< -o $@
.cpp.o :
    $(CXX) -std=c++14 -c $(CXXFLAGS) -I. $< -o $@
clean :
    rm -f *.o $(TARGET_SHARED)

上のmakeで出来たlibtensorflowlite_c.soを/usr/local/lib以下にコピーすると準備完了です。

go-tfliteをクローンする

$GOPATH/src/github.com/mattn/go-tfliteにmattn/go-tfliteをクローンしてください。
_exampleで何個か遊んでみましょう。

$GOPATH/src/github.com/mattn/go-tflite/_example/mnist
$ go run main.go 0.png
# github.com/mattn/go-tflite
./tflite_experimental.go:35:12: warning: expression result unused [-Wunused-value]
0

無事mnistの画像認識に成功しています。

$GOPATH/src/github.com/mattn/go-tflite/_example/fizzbuzz
$ go run main.go
# github.com/mattn/go-tflite
./tflite_experimental.go:35:12: warning: expression result unused [-Wunused-value]
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz

fizzbuzzも成功しました。

まとめ

tensorflowのようなツールをGoでも使えるのはすごく嬉しいですね。
こういうツールはPythonが使われることが多いのですが、僕個人としてはGolangでも機械学習する人が増えればいいなあと思います。

go-tfliteは推論にしか使えないようで、まだpythonのように学習から推論までというふうには行きませんが、今後Golangでも学習が出来たらうれしいなあと思います。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む
  • 投稿日：2019-08-22T00:24:20+09:00

goenvで1.12.9を使えるようにする

概要

goenvを利用していて、goenv install -l を打ったが、1.12.9がなかったので、goenvに用意されているgo-buildプラグインを使って、1.12.9を使えるようにしてみた。

使い方は下記READMEにて
https://github.com/syndbg/goenv/tree/master/plugins/go-build

手順

# goenvのリポジトリをクローン
git clone https://github.com/syndbg/goenv.git

# インストールしたいVersionのDirecotryを作っとく
mkdir $HOME/.goenv/versions/1.12.9

# １．１２．９のインストール
cd ./goenv
go-build 1.12.9 $HOME/.goenv/versions/1.12.9

# goenvのバージョンに追加されているかどうか確認
goenv versions

あとはgoenv local 1.12.9 や goenv global 1.12.9 で切り替えができる。

  • このエントリーをはてなブックマークに追加
  • Qiitaで続きを読む

日付別

タグ一覧