Hatena::ブログ(Diary)

is BUG Ready ? このページをアンテナに追加 RSSフィード

プロフィール

ladybug

ladybug

オンラインゲーム好きのプログラマらしい…。

1900 | 05 | 10 |
2003 | 11 | 12 |
2004 | 01 | 02 | 03 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 05 | 06 | 07 | 08 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 06 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 09 | 10 | 12 |
2012 | 03 | 05 | 08 |
2013 | 02 | 03 | 06 |
2014 | 04 |
2015 | 12 |
2016 | 01 |

2005.11.16

[] 循環参照した短方向リンクリストを O(n) で検出する  循環参照した短方向リンクリストを O(n) で検出するを含むブックマーク

no title 発見しただけ。

明日おぼえてたら考えよう。@IT とコメントにちょっと書き込みがある。*1私が応えることじゃないがコメントの、

1パスの処理で出来るのですか?

というのは、@IT のほうの

計算量も O(2n) になるような・・・。(くわしくないのでどなたかつっこんで下さい)

あたりからきてるんだろうか?

2パスで処理する場合、o(2n) になる、3パスなら o(3n) だ。o(n) も o(2n) も o(3n) も、すべて O(n) である。よって、問題文が誤記述ではないかぎり1パスで解くという制約はないはず。ただし、問題は

ノード数を n とするが、n の値は分からない。リスト中にループ(循環参照)が存在するか否か

であるため、1パス目が完了した時点で、それは循環参照はないということの証明であるため、2パス目を実行する必要性は絶対にないと思う。もうすこし突っ込んで言うと、

1度目でnを求める。

2度目ででっち6号様のとおり

というアルゴリズムに対して循環参照をしているリストを投げると、1パス目で n を求めようとして無限ループして終わる、ということだ。

[] 考察1  考察1を含むブックマーク

@IT の投稿は、すでに4ページをこえているので、答えが書いてありそうだから読まない(苦笑

コメントにもあるように、リスト構造に対して手を加えずマーキングを実施することは不可能ではなく、そんなことお手軽にできるライブラリもごまんとある。しかし、元記事がそんなに面白みのない結果で満足するわけがない。(と勝手に決め付ける)

単方向リンクリストのエラー状態には、循環*2と分断*3があり、これらの検出はリンクリストを使用したプログラムの開発・保守を行うときに必須になるだろう。

さて、循環の検出には、ある特定のノード A からリンクを辿ることで、再びノード A に戻ってくることで検出できる。

// code coloring/formated by http://manoli.net/csharpformat/
static bool HasLoop(LinkList node)
{
  foreach (LinkList cur in node.Walk())
  {
    if (cur == node) return true;
  }

  return false;
}

もちろん、このコードじゃループを完全に検出することはできない。これは検査対象であるノード node がループに巻き込まれている場合は true を戻すことができるが、巻き込まれていなければ false を戻そうとして無限ループに陥る可能性がある。その無限ループを避けるためには、node に対する検査を実施する前に node.Next に対する検査が必要になり効率的にやろうとするとマーキングの手法になってしまう。すぐに思いつく案として、node を検査する際に node.Next に対して再帰的な検査を実施することが考えられる。

[] 考察2  考察2を含むブックマーク

とりあえず仕事と並行処理で考えたのは↑まで、単純に再帰しただけでは明らかにマズイので、具体的にどのように検査を実施するかを考えなければならない。

循環参照が存在する場合、循環の輪に巻き込まれたノードからリンクを m : m <= n 回辿ることで、そのノード自身に到達するはずなので、リンクリストを辿れる範囲に対して m 回先に自身が存在しないことを確認していくことで循環を検出できるのではないかと思われる。さらに循環している確認には、先頭から i 番目の要素が m 個目で終端であれば、n = i + m のはずで、i+1 番目の要素は n - (i + 1) == m - 1 個目で終端を迎えるはずであることが多少利用できそうだ。

つづく
ここで書いたコードの目コンパイルが通らないうちにデュナミスの時間です。

*1:この時点では返信3ぐらい

*2:参照が循環しリンクリストの終端が失われた状態

*3:リストに穴ができリストが2つ以上に分割され先端が失われた状態

yaneuraoyaneurao 2005/11/16 16:10 これだとダメなのかなぁ..。

set<list*> s;
while(p!=null){
if (p in s) return ”循環参照している”;
s.insert(p);
p = p->next;
}
return ”循環参照していない”;

辿っているリスト自体には手を加えていないので題意は満たすと思うのだけど..

ladybugladybug 2005/11/16 16:16 私は出題者ではないし題意は満たすと思います。しかし、「マーキングしていることをリスト上に保持できない」を「マーキングしない」と読み替えて解くべきだろうとも思いますよ。出題者がどういう意図か分かりませんが、GCJ ではありですしね。
がりゅうさんは GCJ に参加されているなどありますし、単純なマーキング処理だけならほとんどの人は数分で思いついてしまって、とりあえず課題として面白みがないと思います。

yaneuraoyaneurao 2005/11/16 18:22 うむうむ..私もそう思います。>面白みがない
しかしこれ本当にno marker,no labeling,no recursionでO(n)で出来るのなら、驚愕ものです..。

yaneuraoyaneurao 2005/11/16 20:52 効率が多少悪くてもいいなら、ループの循環長を2**nと想定しながら、nを拡大していくとかかなぁ..。
bool isCyclic(list*p){
int n=1,m=n; list*q=null;
loop {
if(p==NULL) return false;
if(p==q) return true;
if(--m ==0) { q=p; n<<=1; m=n; }
p = p->next;
}}
たとえば↑こんな感じ。一応、ノード数Nに対して2N回以内のループで済むことは保証されますから、O(n)ですよね。

yaneuraoyaneurao 2005/11/16 21:05 とか言ってる間に、k.inabaさんがytqwertyさんところに解答書いてたorz..

ladybugladybug 2005/11/16 21:29 ↑よし、そっちも読まないぞ(笑

k.inabak.inaba 2005/11/16 21:37 あぁーごめんなさいm(_ _)m。だってytさんが既に解答書いてるんだもの(責任転嫁

ytqwertyytqwerty 2005/11/16 21:41 えええー!?

ladybugladybug 2005/11/16 21:44 どんどん解答の在り処を書いて! 頑張って見ないようにするから!
そして、アルゴリズムを実装するよりも LinkList クラスを実装するほうにばかり時間をとられています(笑)

KeyID : FAF32CAB
Fingerprint : 0B3B CE61 48A9 779B 0324 6A7D DB82 6FAC FAF3 2CAB
Access:
written by Lady.BUG