C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[6]: リストのサイズの求め方についての疑問

(過去ログ 56 を表示中)

[トピック内 7 記事 (1 - 7 表示)]　 << 0 >>

■31425 / inTopicNo.1)

　リストのサイズの求め方についての疑問

▼■

□投稿者/ 気になって眠れない (1回)-(2009/01/22(Thu) 00:31:58)

分類:[ソフトウェア全般]　

リンクリスト？連結リスト？のサイズを求める際の計算量についてなんですけど、
O(N)って書いてあるのをよく見かけます。
これは、先頭から末尾までたどることを前提としてますけど、サイズ用の変数を用意する方法では何か問題があるのでしょうか？
例えば追加するときに+1、削除するときに-1、リストをまとめて追加するときに追加するリストのサイズ分加算すれば、
大丈夫だと思うのですが、素人では考えも付かないような問題が潜んでいるのでしょうか？
どうぞよろしくお願いします。

引用返信 編集キー/

■31428 / inTopicNo.2)

　Re[1]: リストのサイズの求め方についての疑問

▲▼■

□投稿者/ 倉田　有大 (423回)-(2009/01/22(Thu) 01:22:09)

■No31425 (気になって眠れないさん) に返信
> リンクリスト？連結リスト？のサイズを求める際の計算量についてなんですけど、
> O(N)って書いてあるのをよく見かけます。
> これは、先頭から末尾までたどることを前提としてますけど、サイズ用の変数を用意する方法では何か問題があるのでしょうか？
> 例えば追加するときに+1、削除するときに-1、リストをまとめて追加するときに追加するリストのサイズ分加算すれば、
> 大丈夫だと思うのですが、素人では考えも付かないような問題が潜んでいるのでしょうか？
> どうぞよろしくお願いします。

一個追加するたびに、領域を確保すると遅いので、STLなんかは、たしか最初から多めに領域を確保してたりなんかします。
うーん、この答え方であってるかな。

引用返信 編集キー/

■31431 / inTopicNo.3)

　Re[2]: リストのサイズの求め方についての疑問

▲▼■

□投稿者/ 気になって眠れない (2回)-(2009/01/22(Thu) 01:36:51)

■No31428 (倉田　有大さん) に返信
> ■No31425 (気になって眠れないさん) に返信
>>リンクリスト？連結リスト？のサイズを求める際の計算量についてなんですけど、
>>O(N)って書いてあるのをよく見かけます。
>>これは、先頭から末尾までたどることを前提としてますけど、サイズ用の変数を用意する方法では何か問題があるのでしょうか？
>>例えば追加するときに+1、削除するときに-1、リストをまとめて追加するときに追加するリストのサイズ分加算すれば、
>>大丈夫だと思うのですが、素人では考えも付かないような問題が潜んでいるのでしょうか？
>>どうぞよろしくお願いします。
>
> 一個追加するたびに、領域を確保すると遅いので、STLなんかは、たしか最初から多めに領域を確保してたりなんかします。
> うーん、この答え方であってるかな。
C++のstd::listは最初から多めに領域確保はしていません。std::vectorはしてますが、std::dequeとかはわかりません。。。
でも、そういうことじゃなくて、サイズ計算の話です。
サイズ求めるためにO(N)の計算量が必要って書いてあるのをよく見かけて、素人考えでO(1)でいけないのかな？と考えた次第です。

引用返信 編集キー/

■31432 / inTopicNo.4)

　Re[3]: リストのサイズの求め方についての疑問

▲▼■

□投稿者/ れい (827回)-(2009/01/22(Thu) 02:01:54)

■No31431 (気になって眠れないさん) に返信
> サイズ求めるためにO(N)の計算量が必要って書いてあるのをよく見かけて、素人考えでO(1)でいけないのかな？と考えた次第です。

いけなくないですよ。
問題ありません。

そういうクラスを作ってもいいですし、他の方法・場所・クラスでカウントしても問題ありません。

連結リストを提供するライブラリがそのリストのサイズをO(1)で知る方法を提供すべきかどうか、
という話ならいろいろ考えるべきことがあり、簡単に結論はでません。
速度、メモリ使用量、同期処理とか。

リストのサイズくらいなら自分で簡単に組めますので、
「自分でやれ」というのが多いようですね。

引用返信 編集キー/

■31433 / inTopicNo.5)

　Re[4]: リストのサイズの求め方についての疑問

▲▼■

□投稿者/ 気になって眠れない (3回)-(2009/01/22(Thu) 02:32:27)

■No31432 (れいさん) に返信
> ■No31431 (気になって眠れないさん) に返信
>>サイズ求めるためにO(N)の計算量が必要って書いてあるのをよく見かけて、素人考えでO(1)でいけないのかな？と考えた次第です。
>
> いけなくないですよ。
> 問題ありません。
>
> そういうクラスを作ってもいいですし、他の方法・場所・クラスでカウントしても問題ありません。
>
> 連結リストを提供するライブラリがそのリストのサイズをO(1)で知る方法を提供すべきかどうか、
> という話ならいろいろ考えるべきことがあり、簡単に結論はでません。
> 速度、メモリ使用量、同期処理とか。
>
> リストのサイズくらいなら自分で簡単に組めますので、
> 「自分でやれ」というのが多いようですね。
なるほど、実現は可能だけど、考える点がそこだけではないと言うことですね。
それならそれでそう書いておいて欲しいものです。
よく見てみると、O(N)としているのはC言語のものが多く、もしかするとサイズ用の変数を用意し、管理するのが面倒だ、と言うことかもしれないですね。
その他の言語でO(N)となっているのは、C言語で理由も説明せずにO(N)としているのを何の疑いもせずにそのまま受け止めてしまった、と言うことでしょうか。

そんなことは置いといて、ありがとうございます。やっと眠れます。

解決済み

引用返信 編集キー/

■31434 / inTopicNo.6)

　Re[5]: リストのサイズの求め方についての疑問

▲▼■

□投稿者/ れい (828回)-(2009/01/22(Thu) 04:26:55)

■No31433 (気になって眠れないさん) に返信
> それならそれでそう書いておいて欲しいものです。

当たり前な内容は書いてあると邪魔な場合もあります。
信号機の横に「青は渡って良い」と書かれているようなものかと。

> よく見てみると、O(N)としているのはC言語のものが多く、もしかするとサイズ用の変数を用意し、管理するのが面倒だ、と言うことかもしれないですね。
> その他の言語でO(N)となっているのは、C言語で理由も説明せずにO(N)としているのを何の疑いもせずにそのまま受け止めてしまった、と言うことでしょうか。

リンクリストというデータ構造は、そのデータ構造の本質として、
(サイズ用変数を確保したりしていなければ)サイズを求める際にはO(N)かかります。
そこが一番重要なところです。

リンクリストの構造やサイズ取得の方法などはあちこちに書かれています。
アルゴリズムの本を読んでいるのか、ライブラリのマニュアルを見ているのか、
プログラムの本を読んでいるのかわかりませんが、
本にしろライブラリにしろ、「何の疑いもせずに」ということはないでしょう。

それなりに理由があってそういう説明をしているか、そういう実装をしているのだと思います。
もう一度よく読んでみることをオススメします。

ちなみに、.Net FrameworkのLinkedList<>はO(1)で要素数を取得できますね。

解決済み

引用返信 編集キー/

■31435 / inTopicNo.7)

　Re[6]: リストのサイズの求め方についての疑問

▲▼■

□投稿者/ επιστημη (1561回)-(2009/01/22(Thu) 07:11:18)

2009/01/22(Thu) 11:04:31 編集(投稿者)

ご参考:

標準C++のstd::listには要素数をO(1)で求められないケースがあります。
listの一部を他のlistに移動するspliceがそれ。
いくつ追加されるかわかんないから。

ひとつずつ勘定しながら追加していけばよさそなものですが、
もともと数珠つなぎになってるものを勘定しながら追加
するには要素を辿んなきゃならんのでO(N)となりパフォーマンスを落とします。
数珠のままつなげばO(1)ですが要素数の勘定はO(1)じゃなくなるです。

解決済み

引用返信 編集キー/

トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

- Child Tree -