go - Go で BitSet を実装するには?

Question

Go で BitSet パッケージが見つからなかったので、実装してみました。ビットを格納するために uint64 の配列を使用したいと思います。

uint64 配列を割り当てるにはビット数が必要です。Java では、整数を取るコンストラクターを定義できます。Go はコンストラクターを提供しませんが、ユーザーが new() を呼び出すときに BitSet の「オブジェクト」を適切に初期化するにはどうすればよいですか?

Answer 1

bitSet をプライベート構造体として宣言します。

type bitSet struct {
  len int
  array []uint64
}

インターフェイス BitSet を公開します。

type BitSet interface {
  Has(pos int) bool
  Add(pos int) bool
  Len() int
}

関数 NewBitSet も公開します。

func NewBitSet(len int) BitSet {
  return &bitSet{len, make(uint64, (len+7) / 8) }
}

これはカプセル化の Go 方法です。実装ではなく、インターフェイスを共有します。

Answer 2

[]uint64 スライスを使用してデータを保存する場合、ゼロ スライスは空の BitSet として機能します。実際、 nil スライスに追加すると、新しい配列が割り当てられますが、言語仕様ではそれが保証されていないようです。そのようなセットアップでは、 new(BitSet) はすぐに使用できます。例：

bitset.go:

package bitset

const size = 64

type bits uint64

// BitSet is a set of bits that can be set, cleared and queried.
type BitSet []bits

// Set ensures that the given bit is set in the BitSet.
func (s *BitSet) Set(i uint) {
    if len(*s) < int(i/size+1) {
        r := make([]bits, i/size+1)
        copy(r, *s)
        *s = r
    }
    (*s)[i/size] |= 1 << (i % size)
}

// Clear ensures that the given bit is cleared (not set) in the BitSet.
func (s *BitSet) Clear(i uint) {
    if len(*s) >= int(i/size+1) {
        (*s)[i/size] &^= 1 << (i % size)
    }
}

// IsSet returns true if the given bit is set, false if it is cleared.
func (s *BitSet) IsSet(i uint) bool {
    return (*s)[i/size]&(1<<(i%size)) != 0
}

bitset_test.go:

package bitset

import "fmt"

func ExampleBitSet() {
    s := new(BitSet)
    s.Set(13)
    s.Set(45)
    s.Clear(13)
    fmt.Printf("s.IsSet(13) = %t; s.IsSet(45) = %t; s.IsSet(30) = %t\n",
               s.IsSet(13), s.IsSet(45), s.IsSet(30))
    // Output: s.IsSet(13) = false; s.IsSet(45) = true; s.IsSet(30) = false
}

Answer 3

簡単に言えば、クライアントが()BitSetを呼び出したときにオブジェクトを適切に初期化できないということです。new

あなたができる最善のことは、BitSetのゼロ値が有効になるようにすることです。これはlist.List、 、sync.Mutex、およびのような型big.Intです。これにより、クライアントが無効な値を取得することは不可能であることがわかります。

次善の策は、コンストラクターのような関数 (NewBitSetこの場合は名前付き) を作成し、クライアントがそれを呼び出すことを期待することです。