Go - プログラム構造 - パッケージとファイル - パッケージ初期化(ビットシフト、最下位ビットの検査、ポピュレーションカウント、テーブル参照、init関数、性能比較)

プログラミング言語Go
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Go (プログラミング言語)

プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES) (Alan A.A. Donovan(著)、Brian W. Kernighan(著)、柴田 芳樹(翻訳)、丸善出版)の第2章(プログラム構造)、2.6(パッケージとファイル)、2.6.2(パッケージ初期化)、練習問題2.4の解答を求めてみる。

コード

package main

import (
 "fmt"
 "time"
)

var pc [256]byte

func init() {
 start := time.Now()
 for i, _ := range pc {
  pc[i] = pc[i/2] + byte(i&1)
 }
 secs := time.Since(start).Seconds()
 fmt.Printf("テーブルの初期化の速度: %.2f秒\n", secs)
}

func main() {
 funcs := []func(uint64) int{PopCount1, PopCount2, PopCount3}
 s := []string{"テーブル参照", "最下位ビットの検査", "テーブル参照(初期化無し)"}
 n := uint64(10e8)
 for i, fn := range funcs {
  var j uint64 = 0
  var b int = 0
  start := time.Now()
  for ; j < n; j++ {
   b += fn(j)
  }
  secs := time.Since(start).Seconds()
  fmt.Printf("%s\n%d\n%.2f秒\n", s[i], b, secs)
 }
}

func PopCount1(x uint64) int {
 return int(pc[byte(x>>(0*8))] +
  pc[byte(x>>(1*8))] +
  pc[byte(x>>(2*8))] +
  pc[byte(x>>(3*8))] +
  pc[byte(x>>(4*8))] +
  pc[byte(x>>(5*8))] +
  pc[byte(x>>(6*8))] +
  pc[byte(x>>(7*8))])
}

func PopCount2(x uint64) int {
 var bits uint64 = 0
 for i := 0; i < 64; i++ {
  bits += x & 1
  x >>= 1
 }
 return int(bits)
}

func PopCount3(x uint64) int {
 var pc [256]byte
 for i, _ := range pc {
  pc[i] = pc[i/2] + byte(i&1)
 }
 return int(pc[byte(x>>(0*8))] +
  pc[byte(x>>(1*8))] +
  pc[byte(x>>(2*8))] +
  pc[byte(x>>(3*8))] +
  pc[byte(x>>(4*8))] +
  pc[byte(x>>(5*8))] +
  pc[byte(x>>(6*8))] +
  pc[byte(x>>(7*8))])
}

入出力結果(cmd(コマンドプロンプト)、Terminal)

$ go run sample4.go
テーブルの初期化の速度: 0.00秒
テーブル参照
14846928128
4.79秒
最下位ビットの検査
14846928128
42.36秒
テーブル参照(初期化無し)
14846928128
260.33秒
$

テーブル参照の場合は初期化時にinit関数で計算済みなのでビットシフトしならが最下位ビットの検査を64回繰り返す場合より速い。(メモ化と似たような効果？)なので、初期化しないテーブル参照の場合は、初期化有りのテーブル参照はもちろんのこと、ビットシフトしならが最下位ビットの検査を64回繰り返す場合より格段に遅い。

初期化の速度とテーブル参照(初期化有り)の場合の速度を合計すれば、初期化無しの場合のテーブル参照の速度と似たような感じになるのかなぁと思って初期化の速度も計測してみたけど、初期化の速度は0.00秒という結果に。まだ初期化のことをよく理解できてないかも。