Go 言語で sorted list がほしかった
C# だと SortedList Class のような順番が保証されているデータ構造があったりするのだが、Go 言語では標準パッケージやメジャーなパッケージになさそうだったので、自分で実装することにした。
go-zen-chu/time-sorted-list: Golang time sorted list
使いどころ
ログの集計を時間単位で行うプログラムにてこのデータ構造の利用しようとしているが、時系列にそろえておきたいということは幾度と発生しそうだったのでデータ構造として切り出した。
例えば、
- ログをオンメモリで保持しておき、その中の特定の時間帯のログを取得したい
- ストリームデータのうち、新しいデータを残し続けるようにしたい
というようなときに使えるのではないかと考えている。また、時系列データは動かしていると どんどんメモリを圧迫していく ケースがあるため、データ構造内部の Slice は固定長になるように調整している。
それにより、最初に決めた容量 (capacity) を確保してしまい、高々そのサイズまでしかメモリ上へ保持しないようになった。
*ちなみに、slice なので item が追加されない限り、メモリはほとんど使わない。
挿入時に時系列になるようにする
すでにソートされている配列に新しい要素を追加するとき、比較は O(log2 n) で済む。とはいえ、容量がいっぱいのときは「古い item を捨てて要素をシフトする」作業が入るため、全要素をなめることになる。 （後述するが、常に挿入されるデータが新しいと保証されていれば、O(1) で追加可能）
また要素の取り出しについては、sort パッケージの二分探索を利用しているため、こちらも O(log2 n) で済む。
godoc もサポートしてみた
汎用的に利用できるデータ構造を作ったため、godoc も試しに作ってみた。
作るときは、godoctricks - GoDoc を参考にした。 godoc の作り方を網羅したドキュメントは、日本語・英語ともに多くないですね…
詰まった点
- 設計上、interface のみを public にしていたが、それだと private structure の関数が一切 godoc に出てこないため、仕方なく public structure にして内部は private にした
- ヘッダとなる条件は、「ピリオドが入っていない、かつ上下が 1 行空いていて、前がヘッダではない」という、なかなかトリッキーな仕様になっていて、意図したドキュメントへ仕上げるのに時間がかかった
しかし、godoc を作ってみると一端のプログラムを作った気になれるので、なかなか楽しい。
今後、対応が必要になりそうな点
だいたいデータ構造としてやってほしい機能は実装したのだが、まだ対応が必要になりそうな機能がある。
- 時系列で古いものから捨てるように決まっている。ただ、捨てる基準はユーザ側で決めるほうがよい（古いものを残す需要もありそう）
- Add するとき、データ構造内の item を先頭から比較している。ただ、常に新しいデータが来るユースケースでは、純粋に append するだけのほうが高速に処理できる
- 取り出すときに型変換が必要（Go言語は generics がないので仕方あるまい）
- スレードセーフ対応。これは遅かれ早かれ対応に迫られる気がしている。
どこかでお役に立てば。