(遅延セグ木を含めた) セグ木の単位元の扱いに関して相談したいです.
本家 AtC STL では単位元を生成する関数を渡す設計をとっていますが, 私の実装では単位元のオブジェクトを渡すようにしています (パフォーマンス的にはこの方がよいはずです).
この場合，単位元が破壊されるような演算がセグ木に載ると困るんですが，そういうケースって何かありますか？
Merge pull request #2 from suisen-cp/two-sat
↑とは関係ない話題かつ結論としては効果なさそうでしたが、せっかく試したので書いておきます。
datを渡すコンストラクタでもデフォルトコンストラクタ内でdat.length * 2要素を初期化しているため、 切り分けてdat.length要素だけ初期化するようにすればちょっと早くなるのではと思ったので、部分的に試してみました。
dat
dat.length * 2
dat.length
AtCoderのコードテストで、下記の1,2のコメントアウトを切り替えて試してみました。
public class Main{ public static void main(String[] args) { int n = 1000000; int[] data = new int[n]; for (int i = 0; i < n / 2; i++) data[i] = -1; // 1 //java.util.Arrays.fill(data, -1); // 2 System.out.println(data[0]); } }
1: for文でn/2要素を初期化
for
n/2
1. 88ms 2. 80ms 3. 96ms 4. 85ms 5. 89ms avg 87.6ms
2: Array.fillでn要素を初期化
Array.fill
n
1. 96ms 2. 88ms 3. 92ms 4. 88ms 5. 91ms avg 91.0ms
……ほぼ誤差でした。残念。
(遅延セグ木を含めた) セグ木の単位元の扱いに関して相談したいです. 本家 AtC STL では単位元を生成する関数を渡す設計をとっていますが, 私の実装では単位元のオブジェクトを渡すようにしています (パフォーマンス的にはこの方がよいはずです). この場合，単位元が破壊されるような演算がセグ木に載ると困るんですが，そういうケースって何かありますか？
segtreeには一応半群が乗っかるのですが、多くの場合拡張して単位元を作れてモノイドになるので、例外を作るほうが難しいかもしれません。
ありがとうございます．
取り敢えず今はそのままにしておいて，問題があれば修正します．
Activity
suisen-cp commentedon Sep 9, 2020
(遅延セグ木を含めた) セグ木の単位元の扱いに関して相談したいです.
本家 AtC STL では単位元を生成する関数を渡す設計をとっていますが, 私の実装では単位元のオブジェクトを渡すようにしています (パフォーマンス的にはこの方がよいはずです).
この場合，単位元が破壊されるような演算がセグ木に載ると困るんですが，そういうケースって何かありますか？
Merge pull request #2 from suisen-cp/two-sat
m1zz1y commentedon Sep 11, 2020
↑とは関係ない話題かつ結論としては効果なさそうでしたが、せっかく試したので書いておきます。
datを渡すコンストラクタでもデフォルトコンストラクタ内でdat.length * 2要素を初期化しているため、切り分けて
dat.length要素だけ初期化するようにすればちょっと早くなるのではと思ったので、部分的に試してみました。AtCoderのコードテストで、下記の1,2のコメントアウトを切り替えて試してみました。
1:
for文でn/2要素を初期化2:
Array.fillでn要素を初期化……ほぼ誤差でした。残念。
uwi commentedon Sep 25, 2020
segtreeには一応半群が乗っかるのですが、多くの場合拡張して単位元を作れてモノイドになるので、例外を作るほうが難しいかもしれません。
suisen-cp commentedon Sep 26, 2020
ありがとうございます．
取り敢えず今はそのままにしておいて，問題があれば修正します．