2019年1月24日木曜日

開発環境

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

コード

package main

import (
 "fmt"
 "time"
)

var pc [256]byte

func init() {
 for i, _ := range pc {
  pc[i] = pc[i/2] + byte(i&1)
 }
}

func main() {
 funcs := []func(uint64) int{PopCount1, PopCount2, PopCount3}
 s := []string{
  "テーブル参照",
  "最下位ビットの検査",
  "1が設定されている最下位ビットのクリア",
 }
 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 {
 count := 0
 for ; x != 0; x &= (x - 1) {
  count++
 }
 return count
}

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

$ go run sample5.go
テーブル参照
14846928128
4.81秒
最下位ビットの検査
14846928128
43.30秒
1が設定されている最下位ビットのクリア
14846928128
10.91秒
$

0 コメント:

コメントを投稿

関連コンテンツ