[mhc:01318] Re: conflict detection

[Yoshinari Nomura <nom@xxxxxxxxxxxxxxxxxxx>]

乃村です。

On Tue, 3 Apr 2001 16:22:59 +0900,
	KOIE Hidetaka (鯉江英隆) <hide@xxxxxxxx> said:

> 単純に、ソートするときのキーをaとbの2つにするというのではだめ?

えっと、多分そんな感じでいいと思います。
後でちょっと落ち着いて考えてみます。

> 区間木というデータ構造をつかうと
> 全conflictを検出できますがコストはO(n log n)になります。

ありがとうございます。
間違ってるかもしれませんが、二色木とかは、
挿入とか削除をすることが前提で、そのときの効率まで考えるから
こうなるんですよね。

mhc は、summary を作るときに、時間順にソートして、
それぞれを順番になめて、表示する必要があるので、
その中に conflict の判定も入れられるのが一番いいです。
いまはそのへんを考慮していて、conflict をチェックすることによる
コストの増大は、ほとんどありません。

  他の目的で sort してある
  [C] を付けるのが目的で、何と/何個と conflict しているかは問題にしない

という事情を利用しています。
あと、sort は builtin-function なので速いというのもありますね。
--
nom