東方算程譚

コメントを追加

# re: ...あれ? どぉやんだ? 2008/06/12 12:00 アキラ

Sort て Where すればいいんじゃないかと

# re: ...あれ? どぉやんだ? 2008/06/12 12:00 アキラ

訂正
Sort して

# re: ...あれ? どぉやんだ? 2008/06/12 12:02 επιστημη

ソートの後 foreach で 30 <= 得点 < 80 なのだけ
取り出しゃいいけど、それだとソートされてるって条件
が使われないから全件検索になっちゃうやん。
それを避けたいの。

# re: ...あれ? どぉやんだ? 2008/06/12 12:34 NyaRuRu

>それだとソートされてるって条件が使われないから全件検索になっちゃうやん。

それならフィルタしてからソートした方が良いような．
ソート済みのものを使うなら 30 未満をSkip して 80 以下で TakeWhile ですかね．

# re: ...あれ? どぉやんだ? 2008/06/12 12:40 NyaRuRu

var examResults = new []
{
　　new {Name = "相川", Score = 35},
　　new {Name = "井上", Score = 20},
　　new {Name = "上村", Score = 80},
　　new {Name = "江口", Score = 50},
　　new {Name = "小田", Score = 75},
};

var filtered = from result in examResults
　　　　　　　 where 30 <= result.Score
　　　　　　　 where result.Score <= 80
　　　　　　　 orderby result.Score
　　　　　　　 select result;

foreach (var item in filtered)
{
　　Console.WriteLine(item);
}

# re: ...あれ? どぉやんだ? 2008/06/12 12:43 NyaRuRu

あーすみません．80 点未満でした．

ソート済みのバージョンを使うならこうですね．

var sorted = examResults.OrderBy(result => result.Score);
var filtered = sorted.SkipWhile(result => result.Score < 30)
　　　　　　　　　　 .TakeWhile(result => result.Score < 80);

# re: ...あれ? どぉやんだ? 2008/06/12 12:43 melt

フィルタしながらソートするのと、ソートしてから２分探索するのではどっちの方が速いんだろう……。

# re: ...あれ? どぉやんだ? 2008/06/12 13:07 επιστημη

なるほどSkipWhile/TakeWhileで挟むのかー
...あれ?
SkipWhileは条件満たすまで読み飛ばすんでしょけど、
アタマから順に舐めるんですよね?
sortedのナカミがソートされてるからbinary-searchで、
なんてー気の利いたことできるわけないし。

# ソート済みListから範囲を取り出す 2008/06/12 13:15 FloralCompany.log

...あれ? どぉやんだ? (東方算程譚) より。 名前と得点をメンバに持つEx...

# re: ...あれ? どぉやんだ? 2008/06/12 13:21 NyaRuRu

>sortedのナカミがソートされてるからbinary-searchで、なんてー気の利いたことできるわけないし。

あーなるほど．
いや，IOrderedEnumerable<T> に対する拡張メソッドを使えば実現は可能ですが，標準の LINQ to Object の範囲内で SkipWhile はそこまで特殊化されてはないですね．確かに．

ただまあオーダー N Log(N) のソート操作後に，オーダー N の全スキャンをやるのってそんなに気になりますかね？
なんか全スキャンを N^2 ぐらいの勢いで気にする割に，N Log(N) のソートは無頓着に使う人をよく見る気がするです．不思議．

# re: ...あれ? どぉやんだ? 2008/06/12 13:21 NyaRuRu

>IOrderedEnumerable<T> に対する拡張メソッドを使えば
→ IOrderedEnumerable<T> に対する拡張メソッドを作れば

# re: ...あれ? どぉやんだ? 2008/06/12 13:25 επιστημη

まぁ、ね (^^;
ただ、"ソート済"のコンテナがあって、
そっから特定の範囲を見つけて来い! となるとですね。
Nがめっさり大きく、SkipWhileでごっそり読み飛ばされる
となると少なからず気になるます。

# re: ...あれ? どぉやんだ? 2008/06/12 13:45 NyaRuRu

すみません．
IOrderedEnumerable だとどのキーでソートされたかの情報が落ちてるので SkipWhile での最適化は無理っぽいです．

>ただ、"ソート済"のコンテナがあって、
>そっから特定の範囲を見つけて来い! となるとですね。

それは広義には「事前にインデックスが生成されているデータストレージ」の一種ですな．そっちは LINQ to SQL のような式木を使ったアプローチの守備範囲ですなぁ．
N が本当に大きくなって，32 bit をさくさく超えるような時代になると，プログラマが手続きを書き下すよりも，アルゴリズム自体をコンテナに渡してコンテナに計算してもらうような感じになるんでしょうな．

# re: ...あれ? どぉやんだ? 2008/06/12 14:01 NyaRuRu

なので，C# では，以下のコードが正道な気がします．

var seq = from result in indexed
　　　　　where 30 <= result.Score
　　　　　where result.Score < 80
　　　　　orderby result.Score
　　　　　select result;

つまり，このコードが最速になるように，適切にコンテナと拡張メソッドを実装すべし，と．
言い換えれば，コンテナや拡張メソッドを改良しながらも，上の式は再修正する必要がないわけですな．

# re: ...あれ? どぉやんだ? 2008/06/12 14:20 επιστημη

えー、LINQよぉわかっとらんのですけど、
where と orderby はどっちが先に評価されんですか?
つかどっちが先かをプログラマが決められるてコトすか?
orderbyが先に動いてくんないと、ソートされてるって
ことを有効に使えんわけで。

# re: ...あれ? どぉやんだ? 2008/06/12 14:29 アキラ

たぶん、↑と同じプログラム
var seq = indexed.Where(x => x.Score >= 30).Where(x => x.Score < 80).OrderBy(x => x.Score);

# re: ...あれ? どぉやんだ? 2008/06/12 17:17 出水

lower_boundならこんな実装でどうでしょう

int low = exam.BinarySearch(new {Name=null, Score = 30});
low = low < 0 ? ~low : low;

# re: ...あれ? どぉやんだ? 2008/06/12 17:46 NyaRuRu

>where と orderby はどっちが先に評価されんですか?
>つかどっちが先かをプログラマが決められるてコトすか?
>orderbyが先に動いてくんないと、ソートされてるって
>ことを有効に使えんわけで。

そこは indexed 変数の型とオーバーロードレゾリューションで決まります．即時評価するか遅延評価するかもメソッドオーバーロード次第です．

C++ の Expression Template と同じで，式構造そのものを返すようなオーバーロードを作成すれば，「where して orderby」という式そのものを indexed は受け取れます．
indexed が既にソート済みであれば，余計なソートは不要ですし，ソート済みの項目についての where も最適化可能と．
indexed 自身が，ある種の実行時コンパイラみたいなことをやるわけですな．

# re: ...あれ? どぉやんだ? 2008/06/12 17:59 επιστημη

あ、なるほどー。

タイトル		タイトルを入力してください
名前		名前を入力してください
URL
コメント   コメントを入力してください
名前をブラウザに記憶する