お知らせ『1月31日に一度初期化したいと思います。』　（他のお知らせを読むにはここをクリック）
並び順： 階層 時系列
0
+35		(^-^)しらちゃ[06:35]
おはようございますー☆
1
+1		(・_・)masahiko[06:38]
しらちゃさんおは Ufionは落ちましたね☆
3
(T-T)しらちゃ[06:40]>>1
おはようございますー．Ufion落ちちゃってますねえ．．．☆
2
+30		(・_・)テスト中につき反応鈍し◆JINX.xzK8k[06:40]
おはよう、しらちゃ！　早速質問で悪いんだけど、制限を設けた場合の入れ子集合モデルのノード追加のアルゴリズムを教えてもらえると助かります。ノードの左右の幅は余裕持たすの？☆
4
+23		(・_・)しらちゃ[06:41]>>2
はいー．そうです．ゼロに対して，ツリー全体でn回のしか発言できないということにするなら，n^2を余裕として，ゼロ発言は区間を持ちます．☆
6
+22		(・_・)テスト中につき反応鈍し◆JINX.xzK8k[06:44]>>4
じゃあ制限100のゼロはleft1,right10000、ゼロに追加したノードはleft？,right9801？☆
8
+21		(・_・)しらちゃ[06:46]>>6
ゼロは0-10000,その直下に追加1回目は0-5000, 2回目は5000-7500, 3回目は, 7500-8750という具合に，なります．一般には，1回目に追加したノードの直下は，1回目は0-2500，2回目は2500-3750...☆
9
(・_・)しらちゃ[06:48]>>8
これは，ノードを追加するたびに，「残りの追加があり得る回数」が1つ減るため，必要な余裕を「2分の1にしてもよい」からこういうアルゴリズムなのです☆
10
+19		(・_・)テスト中につき反応鈍し◆JINX.xzK8k[06:48]>>8
ノードのアドレスを決め打ちしているようなイメージ？☆
11
+18		(・_・)しらちゃ[06:50]>>10
はい．そういう印象は正しいと想います．ぶっちゃけ，簡単に実装する方法は，区間に対するツリー全体の「次猶予カウント」を保持しておいてそれを毎回2分の1にしながら，追加箇所のleftにその値を足したrightを持つノードを追加することです☆
12
+15		(・_・)しらちゃ[06:52]>>11
いかなるleftも，最初は10000です．ですのでleftを主キーに，猶予カウントをもつテーブルを作り，存在しないならば，10000をクエリ，存在するならばその2分の1にupdateという手が使えます．もし猶予カウントが0になったならば，そのツリーはもう次のノードを追加できません☆
15
+13		(・_・)テスト中につき反応鈍し◆JINX.xzK8k[06:55]>>12
なるほど。実装するなら、ゼロのID+leftが主キーって感じ？☆
17
+12		(・_・)しらちゃ[06:56]>>15
んっと，私なら，発言格納したテーブルも，猶予カウントテーブルも，も，そもそもleftを主キーにしてしまうかな？☆
20
(・_・)しらちゃ[06:58]>>17
ある発言のゼロノードは，結局上手く得てくる方法を考えないといけないですしね．．．☆
23
+10		(・_・)テスト中につき反応鈍し◆JINX.xzK8k[06:58]>>17
leftって、ゼロの中では一意に値が決まるけど、他のゼロとかぶるんじゃ？それとも全てに共通して一意なleftを割り振るの？☆
24
+9		(・_・)しらちゃ[07:00]>>23
そういうことです．最後のゼロのrightが，次のゼロのleftです．☆
25
(・_・)テスト中につき反応鈍し◆JINX.xzK8k[07:01]>>24
なるほろ納得！よくわかった！☆
26
+1		(・_・)テスト中につき反応鈍し◆JINX.xzK8k[07:02]>>24
本当にありがとね！☆
28
(・_・)しらちゃ[07:02]>>26
いえいえー．☆
27
+5		(^-^)しらちゃ[07:02]>>24
こうしてあげれば，あるツリーを単に持ってくるのは，ゼロの範囲left-rightに含まれる範囲を探せばいいですし，あるノードの部分木も同じ．ツリーIDの比較をしない分高速(ツリーIDがプライマリIDならDBは高速サーチできるので利点にならない可能性もあり．理論と実践は比較必要)☆
29
+4		(・_・)bookbook[07:05]>>27
あれ？ゼロのみ取り出したいときはどうすればいいの？☆
30
+3		(・_・)しらちゃ[07:05]>>29
区間10000のノードを探せばいいです☆
31
(・_・)bookbook[07:07]>>30
あ、なるほどー！さんくす！☆
32
(^-^)しらちゃ[07:08]>>30
ちなみに応用で「ゼロからn回目の発言のノード」だけ集めるのもn/2区間のノードを探せばOKなんですが，これは直接の応用性はありません．でも，区間サイズでソートすると追加順にソートされるという面白い性質が出てきます．☆
33
(・_・)しらちゃ[07:09]>>30
間違えた，n回目の発言は，「10000 / (n^2)」です☆
35
(・_・)しらちゃ[08:37]>>12
× いかなるleftも　○ いかなるゼロも☆
13
+1		(・_・)テスト中につき反応鈍し◆JINX.xzK8k[06:52]>>11
大体イメージできた！サンクス！☆
14
(^-^)しらちゃ[06:53]>>13
はい．それならよかったです～．☆
5
+5		(・_・)しらちゃ[06:42]>>2
でも，すでに入れ子区間モデルを実装されているなら無理して変換するほどじゃないですよ？それほど効率が変わるわけじゃないはずなので，キチキチの高速化が必要とか，新規に作るとかの時なら選択するくらいの話しで．．．☆
7
+4		(・_・)テスト中につき反応鈍し◆JINX.xzK8k[06:45]>>5
ちょっと興味があるのでｗ☆
16
+3		( ´_ゝ｀)目次◆IndexIsVCs[06:56]>>7
お前ら頼むから日本語で会話しろ☆
18
(・_・)テスト中につき反応鈍し◆JINX.xzK8k[06:57]>>16
すまぬ☆
19
( ´_ゝ｀)目次◆IndexIsVCs[06:57]>>16
なんとなくイメージは出来るが、理解できねぇ☆
22
(T-T)しらちゃ[06:58]>>16
あう．すいません～．☆
21
+1		(^-^)目次◆IndexIsVCs[06:58]
まぁ遅れたけどおはよう☆
34
(^-^)しらちゃ[07:14]>>21
こちらも遅れましたが，おはようございます．☆