東方算程譚

Oriental Code Talk ── επιστημηが与太をこく、弾幕とは無縁のシロモノ。

目次

Blog 利用状況

ニュース

著作とお薦めの品々は

著作とお薦めの品々は
東方熱帯林へ。

あわせて読みたい

わんくま

  1. 東京勉強会#2
    C++/CLI カクテル・レシピ
  2. 東京勉強会#3
    template vs. generics
  3. 大阪勉強会#6
    C++むかしばなし
  4. 東京勉強会#7
    C++むかしばなし
  5. 東京勉強会#8
    STL/CLRによるGeneric Programming
  6. TechEd 2007 @YOKOHAMA
    C++・C++/CLI・C# 適材適所
  7. 東京勉強会#14
    Making of BOF
  8. 東京勉強会#15
    状態遷移
  9. 名古屋勉強会#2
    WinUnit - お気楽お手軽UnitTest

CodeZine

  1. Cで実現する「ぷちオブジェクト指向」
  2. CUnitによるテスト駆動開発
  3. SQLiteで組み込みDB体験(2007年版)
  4. C++/CLIによるCライブラリの.NET化
  5. C# 1.1からC# 3.0まで~言語仕様の進化
  6. BoostでC++0xのライブラリ「TR1」を先取りしよう (1)
  7. BoostでC++0xのライブラリ「TR1」を先取りしよう (2)
  8. BoostでC++0xのライブラリ「TR1」を先取りしよう (3)
  9. BoostでC++0xのライブラリ「TR1」を先取りしよう (4)
  10. BoostでC++0xのライブラリ「TR1」を先取りしよう (5)
  11. C/C++に対応した、もうひとつのUnitTestFramework ─ WinUnit
  12. SQLiteで"おこづかいちょう"
  13. STL/CLRツアーガイド
  14. マージ・ソート : 巨大データのソート法
  15. ヒープソートのアルゴリズム
  16. C++0xの新機能「ラムダ式」を次期Visual Studioでいち早く試す
  17. .NETでマンデルブロ集合を描く
  18. .NETでマンデルブロ集合を描く(後日談)
  19. C++/CLI : とある文字列の相互変換(コンバージョン)
  20. インテルTBBによる選択ソートの高速化
  21. インテルTBB3.0 によるパイプライン処理
  22. Visual C++ 2010に追加されたSTLアルゴリズム
  23. Visual C++ 2010に追加されたSTLコンテナ「forward_list」
  24. shared_ptrによるObserverパターンの実装
  25. .NETでマンデルブロ集合を描く(番外編) ── OpenCLで超並列コンピューティング
  26. StateパターンでCSVを読む
  27. 状態遷移表からStateパターンを自動生成する
  28. 「ソートも、サーチも、あるんだよ」~標準C++ライブラリにみるアルゴリズムの面白さ
  29. インテルTBBの同期メカニズム
  30. なぜsetを使っちゃいけないの?
  31. WPFアプリケーションで腕試し ~C++でもWPFアプリを
  32. C++11 : スレッド・ライブラリひとめぐり
  33. Google製のC++ Unit Test Framework「Google Test」を使ってみる
  34. メールでデータベースを更新するココロミ
  35. Visitorパターンで遊んでみたよ
  36. Collection 2題:「WPFにバインドできる辞書」と「重複を許す検索set」
  37. Visual C++ 2012:stateless-lambdaとSQLiteのぷち拡張
  38. 「Visual C++ Compiler November 2012 CTP」で追加された6つの新機能

@IT

  1. Vista時代のVisual C++の流儀(前編)Vista到来。既存C/C++資産の.NET化を始めよう!
  2. Vista時代のVisual C++の流儀(中編)MFCから.NETへの実践的移行計画
  3. Vista時代のVisual C++の流儀(後編) STL/CLRによるDocument/Viewアーキテクチャ
  4. C++開発者のための単体テスト入門 第1回 C++開発者の皆さん。テスト、ちゃんとしていますか?
  5. C++開発者のための単体テスト入門 第2回 C++アプリケーションの効率的なテスト手法(CppUnit編)
  6. C++開発者のための単体テスト入門 第3回 C++アプリケーションの効率的なテスト手法(NUnit編)

AWARDS


Microsoft MVP
for Visual Developer - Visual C++


Wankuma MVP
for いぢわる C++


Nyantora MVP
for こくまろ中国茶

Xbox

Links

記事カテゴリ

書庫

日記カテゴリ

...あれ? どぉやんだ?

名前と得点をメンバに持つExamの集合がある。
得点順にソートし、30点以上80点未満を列挙せよ。

って問題があるとするわな。
STL/CLRならさっくしと解決できて:

cliext::vector<Exam^> exam;
exam.push_back(gcnew Exam(L"相川", 35));
exam.push_back(gcnew Exam(L"井上", 20));
exam.push_back(gcnew Exam(L"上村", 80));
exam.push_back(gcnew Exam(L"江口", 50));
exam.push_back(gcnew Exam(L"小田", 75));
cliext::sort(exam.begin(), exam.end());
cliext::vector<Exam^>::iterator
  from = cliext::lower_bound(exam.begin(), exam.end(), gcnew Exam(L"",30));
cliext::vector<Exam^>::iterator 
  to   = cliext::lower_bound(exam.begin(), exam.end(), gcnew Exam(L"",80));
while ( from != to ) {
  Console::WriteLine(L"{0}:{1}", from->name, from->score);
  ++from;
}

ま、こんな感じ。
これを System.Collections.Generic.List<Exam> でやろうとすると
どないになるんす? おしえてC#/VBのえらいひと。

投稿日時 : 2008年6月12日 11:54

コメントを追加

# 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

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

# 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
コメント