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

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

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

Re[6]: List<T>.FindAll() で順序は維持されるか?


(過去ログ 78 を表示中)

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

■46152 / inTopicNo.1)  List<T>.FindAll() で順序は維持されるか?
  
□投稿者/ みきぬ (743回)-(2010/01/27(Wed) 11:47:15)

分類:[C#] 

2010/01/27(Wed) 11:48:32 編集(投稿者)

いくつかの要素が格納された List<T> オブジェクトがあります。
格納順にはある意図があって、Sort() を行うと順序が壊れて(変わって)しまいます。

これに対して、FindAll(〜) を実行した結果、得られる新しい List<T> オブジェクトの中身は、元の順序を保っているだろうか? という質問です。


自分なりに、可能性は3パターンあると思っています。

1. 順序は維持されるから大丈夫!
2. 今は維持されているけど、将来はわからない
3. 今もそうなるとは限らない。私が知らない例外ケースが存在する

直感的には、IEnumerator.MoveNext() を使って要素を順にたどり、条件を満たすものを新しい List<T> に詰め込んでるだけだと思うので 1(または2)な予感はしているのですが、裏がとれません。
MSDN で該当のメソッドを調べたり、ぐぐったりしていますが、今のところよりどころは、List<T>.FindAll() メソッドの解説にあるこの部分だけです。

> このメソッドは順次検索を実行します。

3 の可能性を最も恐れているので、少なくともそうではないという根拠が得られればうれしいです。
# 最悪、ライブラリの中を覗けば分かるような気はしますが…できればやりたくない
引用返信 編集キー/
■46155 / inTopicNo.2)  Re[1]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ επιστημη (2404回)-(2010/01/27(Wed) 12:05:28)
επιστημη さんの Web サイト
>>このメソッドは順次検索を実行します。

この文言が「順序を維持する」を含意しているとは思う....けどもその確証がないのよね。

どうしても信じられないなら namespace Mikinu に List<T> の拡張メソッドで
FindAllWithKeepingOrder() メソッドを...

引用返信 編集キー/
■46157 / inTopicNo.3)  Re[1]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ 囚人 (458回)-(2010/01/27(Wed) 12:08:08)
FindAll() した後、自分の意図通りに Sort すればいいのではないですか?
できません?
引用返信 編集キー/
■46158 / inTopicNo.4)  Re[2]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ επιστημη (2405回)-(2010/01/27(Wed) 12:17:52)
επιστημη さんの Web サイト
> FindAll() した後、自分の意図通りに Sort すればいいのではないですか?

いやー、それやるくらいなら 自分の意図通りに FindAll() したほーが。

引用返信 編集キー/
■46159 / inTopicNo.5)  Re[3]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ みきぬ (744回)-(2010/01/27(Wed) 12:37:53)
No46158 (επιστημη さん) に返信
>>FindAll() した後、自分の意図通りに Sort すればいいのではないですか?
>
> いやー、それやるくらいなら 自分の意図通りに FindAll() したほーが。
>
後出しですみませんが、実は List<T> を受け取って、条件でフィルタされた List<T> を返す処理を既に自前で実装してたりします。
でもあまり美しくないと思ったので、直せないかなーと思ったのが動機です。

Sort は…できれば避けたいですね。
今の T に格納順でソートするための情報がないとか、理由はいろいろあるのですが。
引用返信 編集キー/
■46160 / inTopicNo.6)  Re[2]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ 囚人 (459回)-(2010/01/27(Wed) 12:56:55)
>いやー、それやるくらいなら 自分の意図通りに FindAll() したほーが。

FindAllでは、「探すもの」は意図通りにできますけど、「探す順序」は意図通りにできないのでわ。


「このメソッドは順次検索を実行します」。信用できる気がしますけど、どうなんですかね〜。確かに悩む。

Find() で見つけて、見つけたものを削除して、また Find() を繰り返す・・・とか。
Find() はインデックスの最小のものが約束されていますし。
引用返信 編集キー/
■46161 / inTopicNo.7)  Re[3]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ επιστημη (2406回)-(2010/01/27(Wed) 13:00:43)
επιστημη さんの Web サイト
> 「このメソッドは順次検索を実行します」。信用できる気がしますけど、どうなんですかね〜。確かに悩む。

"from こん中から select こいつを where こんなシバりで" はどうなんだろ。順序は維持されるんだろか。


引用返信 編集キー/
■46164 / inTopicNo.8)  Re[3]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ みきぬ (745回)-(2010/01/27(Wed) 13:06:34)
No46160 (囚人 さん) に返信
> 「このメソッドは順次検索を実行します」。信用できる気がしますけど、どうなんですかね〜。確かに悩む。
>
この文言が示すところって「探すのは前から順にやりますよ」なんですよね。
なので悲観的に見れば、条件で true を返す要素に対して結果の List<T> にどう詰め込むかは不明…。
# ふつーは List<T>.Add() と思うんだけど…疑ったらきりがない


No46161 (επιστημη さん) に返信
>>「このメソッドは順次検索を実行します」。信用できる気がしますけど、どうなんですかね〜。確かに悩む。
>
> "from こん中から select こいつを where こんなシバりで" はどうなんだろ。順序は維持されるんだろか。
>
LINQ の場合はわかりませんが、SQL からの連想だと「順序が維持されることを期待しちゃだめ」かなあ。
引用返信 編集キー/
■46165 / inTopicNo.9)  Re[4]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ 囚人 (460回)-(2010/01/27(Wed) 13:07:28)
>"from こん中から select こいつを where こんなシバりで" はどうなんだろ。順序は維持されるんだろか

SQL なら「順序を期待しちゃ駄目」が普通ですが、LINQ なら、ん〜・・・。やっぱり
"from こん中から select こいつを where こんなシバりで order こんな順序で" ってすべきでしょうかね。
引用返信 編集キー/
■46176 / inTopicNo.10)  Re[4]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ επιστημη (2407回)-(2010/01/27(Wed) 13:53:28)
επιστημη さんの Web サイト
> SQL からの連想だと「順序が維持されることを期待しちゃだめ」かなあ。

ふつーはそうでしょね。

けどね、LINQは「IEnumerableをforeachしながらイロイロする」って
ことははっきりしてるわけで、IEnumerableによる列挙が順序維持するなら
from...select...where... で順序が狂うわけないっ!
と考えるのも妥当に思えるのね。

引用返信 編集キー/
■46177 / inTopicNo.11)  Re[4]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ もりお (174回)-(2010/01/27(Wed) 13:57:17)
No46159 (みきぬ さん) に返信

> # 最悪、ライブラリの中を覗けば分かるような気はしますが…できればやりたくない

ソースを見ずに保証しましょうというお題でしょうか。

> Sort は…できれば避けたいですね。

SortedList を使うことで、あたかもソートしていないかのように・・・

var source = new List<string>();
for (int i = 1; i <= 28; i++) {
	source.Add("node" + i.ToString());
}

var found = new SortedList<int, string>();
foreach (var i in source.FindAll((s) => s.Contains("3"))) {
	found.Add(source.IndexOf(i), i);
}

foreach (var i in found.Keys) {
	Console.WriteLine("{0} {1}", i, found[i]);
}

引用返信 編集キー/
■46178 / inTopicNo.12)  Re[3]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ επιστημη (2408回)-(2010/01/27(Wed) 14:05:19)
επιστημη さんの Web サイト
> Find() で見つけて、見つけたものを削除して、また Find() を繰り返す・・・とか。
> Find() はインデックスの最小のものが約束されていますし。

うん、確実なのはコレみたい。

for ( int pos = 0; (pos = こん中.FindIndex(条件,pos)) >= 0 ; ++pos ) {
 こん中[pos] をごにょごにょする
}

引用返信 編集キー/
■46180 / inTopicNo.13)  Re[5]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ みきぬ (747回)-(2010/01/27(Wed) 14:53:00)
脱線になりますが…

No46177 (もりお さん) に返信
> ソースを見ずに保証しましょうというお題でしょうか。
>
どこかに仕様が書いてあれば、それがほしいというお題です。

私が納得して終わりではなく、いざというときはその内容を第三者に説明する必要があります。
なので、そのまま資料として提示できる形(例えば MSDN の内容)が望ましいです。

ライブラリを解析して得た内容があったとして、それを説明するには私が日本語に訳す必要があります。
そのとき、私に都合のいいように意訳していると思われるようなリスクは避けたいです。

※また、そもそもライブラリを解析していいのかといった問題もあります。


なので裏がとれなければ、たぶん現状維持になると思います。
# 自前で組めば、何かあっても自分のせいなのであきらめがつく
引用返信 編集キー/
■46182 / inTopicNo.14)  Re[4]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ みきぬ (748回)-(2010/01/27(Wed) 14:58:49)
あ、ちなみに今はすっげー単純に組んでますよ。

// 実際は T はある決まった型
List<T> Filter(List<T> before)
{
    List<T> after = new List<T>();
    foreach (T item in before)
    {
        if( 〜 ) after.Add(item);
    }
    return after;
}

引用返信 編集キー/
■46183 / inTopicNo.15)  Re[5]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ επιστημη (2409回)-(2010/01/27(Wed) 15:56:04)
επιστημη さんの Web サイト
2010/01/27(Wed) 15:56:19 編集(投稿者)
# いやまぜーんぜん関係ないんだけど

Listのコピー作るってだけでもったいないオバケがお出ましになる僕は

IEnumerable<T> Filter(IEnumerable<T> before> {
  foreach ( T item in before ) {
    if ( これホスイ ) yield return item;
  }
}

とかやっちゃう鴨。

引用返信 編集キー/
■46187 / inTopicNo.16)  Re[6]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ Jitta on the way (538回)-(2010/01/27(Wed) 18:29:40)
No46180 (みきぬ さん) に返信

> ※また、そもそもライブラリを解析していいのかといった問題もあります。

シェアード ソース だっけ?
VS2008 って、デバッグ時に潜っていけたのでは?


って、それが正しく MSIL である保証はない(というか、否定された)のですが。
引用返信 編集キー/
■46189 / inTopicNo.17)  Re[6]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ 囚人 (462回)-(2010/01/27(Wed) 18:36:46)
>シェアード ソース だっけ?
>VS2008 って、デバッグ時に潜っていけたのでは?

中身がどう実装されていようが、事後条件(この場合は、インデックスの小さいものから順に見つかったものを、インデックスの小さいものから順に格納した List<T> を返す)が明確にされていないと、アルゴリズムを変更されても文句言えないので、
やっぱり「このメソッドは順次検索を実行します」をどう解釈できるか、なんですよねぇ・・・。
引用返信 編集キー/
■46190 / inTopicNo.18)  Re[7]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ aetos (217回)-(2010/01/27(Wed) 18:41:42)
No46187 (Jitta on the way さん) に返信
> ■No46180 (みきぬ さん) に返信
>
>>※また、そもそもライブラリを解析していいのかといった問題もあります。
>
> シェアード ソース だっけ?
> VS2008 って、デバッグ時に潜っていけたのでは?
>
>
> って、それが正しく MSIL である保証はない(というか、否定された)のですが。

シェアードソース、いわゆる SSCLI ってやつと、Reference Source は別です。

SSCLI
http://msdn.microsoft.com/en-us/library/ms973880.aspx

Reference Source
http://referencesource.microsoft.com/netframework.aspx

後者は本物のソースだと思うけどなぁ。
引用返信 編集キー/
■46191 / inTopicNo.19)  Re[7]: List<T>.FindAll() で順序は維持されるか?
□投稿者/ aetos (218回)-(2010/01/27(Wed) 18:46:00)
No46189 (囚人 さん) に返信
> >シェアード ソース だっけ?
> >VS2008 って、デバッグ時に潜っていけたのでは?
>
> 中身がどう実装されていようが、事後条件(この場合は、インデックスの小さいものから順に見つかったものを、インデックスの小さいものから順に格納した List<T> を返す)が明確にされていないと、アルゴリズムを変更されても文句言えないので、
> やっぱり「このメソッドは順次検索を実行します」をどう解釈できるか、なんですよねぇ・・・。

ですねぇ。

呼び出し側が List<T> を継承した MyList<T> を渡して来ることも想定すると、嫌な想像がより一層現実的に。
引用返信 編集キー/
■46193 / inTopicNo.20)  Re[1]: List<T>.FindAll() で順序は維持されるか?
 
□投稿者/ ななし (12回)-(2010/01/27(Wed) 19:36:12)
No46152 (みきぬ さん) に返信
>>このメソッドは順次検索を実行します。

原文は
This method performs a linear search;
となってました。
http://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2
にも「先頭から順に」と書いてあるので、大丈夫じゃないでしょうか。

検索は先頭からするけど、返すリストは逆順(とか不定)、という実装には今後も変更されないと思いますが、
メソッドの解説への記述の追加依頼を出されてはいかがですか?

ちなみに今の実装ですが、■No46182 でのみきぬさんのコードより単純に、先頭から処理してありました。
引用返信 編集キー/

次の20件>
トピック内ページ移動 / << 0 | 1 >>

管理者用

- Child Tree -