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 がないので仕方あるまい）
- スレードセーフ対応。これは遅かれ早かれ対応に迫られる気がしている。
どこかでお役に立てば。