非常に遅いメソッドのプロファイリングを行っているときに、コレクションの検索とフィルタリングにラグがあることを発見しました。
このメソッドは、次のことを (順番に) 実行します。プロファイラーによると、時間の 80% はステップ 1 ～ 3 に費やされています。
- ソートされたコレクションをファイルから読み取り、Protobuf-net (v2) を使用して逆シリアル化します
.RangeFromTo()ソートされたコレクションから、開始と終了の整数 (名前)に基づいてフィルタリングします- 同じソートされたコレクションから、コレクションの次の要素を取得します (name .
Right()) - いくつかのタスクを実行します...
.RangeFromTo()特定の範囲のフィルター。たとえば、次のようになります。
[3,7,9,12].RangeFromTo(2,9) -> [3,7,9]
[3,7,9,12].RangeFromTo(2,8) -> [3,7]
[3,7,9,12].RangeFromTo(7,13) -> [7,9,12]
[3,7,9,12].RangeFromTo(13,14) -> [ ]
.Right()コレクション内の要素を検索し、リスト内の次の要素を提供します。要素が存在しない場合は、右に数えて最も近い要素が表示されます。例えば：
[3,7,9,12].Right(0) -> 3
[3,7,9,12].Right(3) -> 7
[3,7,9,12].Right(4) -> 7
[3,7,9,12].Right(12) -> null
現在、コレクションはSortedArrayC5 ( https://github.com/sestoft/C5/ ) から使用しています。使用できるより適切なコレクションはありますか?
注: ステップ 1. は、合計時間の約 30% かかります。代わりにリストを使用すると、protobuf の逆シリアル化にかかる時間が実際に 40% 短縮されます。SortedArray に挿入すると、コレクションはデータが既にソートされていることを認識せず、一連の作業を行っていると思います。理想的なコレクション (存在する場合) もそれをバイパスできる必要があります。
編集： 明確にするために、リストは約1000〜5000で、90kの異なるコレクションがあります! 問題のメソッドは、ビジネス タスクを実行するためにメモリ内のすべてのコレクションを読み込む必要があります。
編集 2: ここにいくつかのサンプル ベンチマークを追加しました。
https://github.com/cchanpromys/so_19188345
SortedArrayC5SortedSetから .Netと比較します。これまでの結果は次のとおりです。
C5 sorted array deserialize took 904
Sorted set deserialize took 1040
C5 sorted array .Right() took 5
Sorted set .Right() took 798 <--- Not sure what happened here...
C5 sorted array .RangeFromTo() took 217
Sorted set .RangeFromTo() took 140
編集 3 これは私の予想外ですが、リストのカスタム実装になりました。
私が抱えていた問題は、SortedArray の Find 操作 (一般に) が O(Log(N)) を必要とする一方で、O(1) 操作にしたいということです。
また、リストは自然にソートされているため、リストの途中に追加することはありません。
そのため、内部インデクサー配列を持つリストを実装することになりました。たとえば、次のようになります。
例えば：
indexer: [0,0,0,0,1,1,1,1,2,2]
list: [3,7,9]
そう.Right(3)でしょうlist[indexer[3]++]。
コードはここにあります。
このタイプのリストがまだインターネットのどこかに実装されていないとは信じがたいです。できればライブラリを利用したいので、自分でリストを管理する必要はありません。
そのような実装はインターネット上に存在しますか?