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

わんくま同盟

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

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

ツリー一括表示

自然ソートを高速で行う方法 /NNN (19/11/25(Mon) 21:42) #93174
Re[1]: 自然ソートを高速で行う方法 /furu (19/11/26(Tue) 09:40) #93180
  └ Re[2]: 自然ソートを高速で行う方法 /はまぐり (19/11/26(Tue) 20:41) #93185
    └ Re[3]: 自然ソートを高速で行う方法 /NNN (19/12/07(Sat) 12:11) #93359
      └ Re[4]: 自然ソートを高速で行う方法 /キングダム (19/12/07(Sat) 20:42) #93361


親記事 / ▼[ 93180 ]
■93174 / 親階層)  自然ソートを高速で行う方法
□投稿者/ NNN (9回)-(2019/11/25(Mon) 21:42:23)

分類:[.NET 全般] 

自然ソートに関してですが、
https://wiki.dobon.net/index.php?.NET%A5%D7%A5%ED%A5%B0%A5%E9%A5%DF%A5%F3%A5%B0%B8%A6%B5%E6%2F111

ここにコードが掲載されています。
いくつか方法がありますが、
StrCmpLogicalWを使用する方法 以外の方法だと
Explorerのソート順と一致しないことがあるため、
StrCmpLogicalWを使用する方法 を使っています。

ただ、ファイル数が多いとかなり時間がかかってしまいます。

この方法はForループで何度も二つのファイル間で比較を行うわけですが、
何度もStrCmpLogicalW関数を呼び出すのは時間がかかるため
最初に全ファイルをDoubleのような変数に変換して、
後から、順番に比較するようなことをしたいのですが
そのようなことは可能でしょうか?

他にもっと高速な方法がありましたらお教えくださいませ。
[ □ Tree ] 返信 編集キー/

▲[ 93174 ] / ▼[ 93185 ]
■93180 / 1階層)  Re[1]: 自然ソートを高速で行う方法
□投稿者/ furu (12回)-(2019/11/26(Tue) 09:40:07)
No93174 (NNN さん) に返信
> 自然ソートに関してですが、
> https://wiki.dobon.net/index.php?.NET%A5%D7%A5%ED%A5%B0%A5%E9%A5%DF%A5%F3%A5%B0%B8%A6%B5%E6%2F111
>
> ただ、ファイル数が多いとかなり時間がかかってしまいます。
>
> この方法はForループで何度も二つのファイル間で比較を行うわけですが、
リンクのサンプルでは、Forループ使っていないようですが
ソートは自作?
アルゴリズムは?
[ 親 93174 / □ Tree ] 返信 編集キー/

▲[ 93180 ] / ▼[ 93359 ]
■93185 / 2階層)  Re[2]: 自然ソートを高速で行う方法
□投稿者/ はまぐり (79回)-(2019/11/26(Tue) 20:41:58)
No93174 (NNN さん) に返信
シュワルツ変換を使ったソートならLINQのOrderByを使えば簡単にできます

StrCmpLogicalWの実装に従ってソートキーを正規化するのは
StrCmpLogicalWのソースコードが公開されてれば頑張りようもありますけど
ブラックボックスなのでどうにもできないような・・・

目的は高速化で手段としてシュワルツ変換をしようとしておられるわけですよねー
StrCmpLogicalW関数はそんなに遅いのかなと思って試してみましたけど1億回呼んでも10秒でした、結構速いです
シュワルツ変換は複数のフィールドでソートするときには効果的ですが今回はあまり効果なさそうな気がします

気になるほどの時間がかかっているとするなら原因は違うところにあるんじゃないかなと
ディスクのIOが遅いとか、furuさんの観点は鋭いと思いました


[ 親 93174 / □ Tree ] 返信 編集キー/

▲[ 93185 ] / ▼[ 93361 ]
■93359 / 3階層)  Re[3]: 自然ソートを高速で行う方法
□投稿者/ NNN (10回)-(2019/12/07(Sat) 12:11:42)
ありがとうございます。
返信遅れました
furuさんの仰る通り、
バブルソートを使っているのが原因でした

ちなみに自分でクイックソートプログラムを作って比較してみたのですが、
以下のように'Array.Sortの方が20%程度速かったのです。


'バブルソート 7390ミリ秒
'クイックソート 58ミリ秒
'Array.Sort 49ミリ秒

'Array.Sortはシュワルツ変換を使っているのでしょうか?
あるいは、同じクイックソートだけれど、中はC++のような高速な言語で走っているので
高速なのでしょうか?

[ 親 93174 / □ Tree ] 返信 編集キー/

▲[ 93359 ] / 返信無し
■93361 / 4階層)  Re[4]: 自然ソートを高速で行う方法
□投稿者/ キングダム (50回)-(2019/12/07(Sat) 20:42:59)
No93359 (NNN さん) に返信

Array.SortはkeySelectorを引数にとらないので
シュワルツ変換は行われていないはずです

コンパレータを渡さなければネイティブコードが呼ばれるみたいです
コンパレータを渡したらマネージコードでソートしてますね(GitHubのソースコード見ました)

クイックソートの実装が違えば20%くらいの
差はあるんじゃないかなと思います

・ピボットの選び方を工夫する
・交換の仕方を工夫する
・再帰をループに置き換える
・件数が少なかったら挿入ソートに切り替える
・再帰が深くなったらヒープソートに切り替える

クイックソートの実装ではこのような方法があるんでそのあたりの実装の違いで
20%くらいは差が出るんじゃないかなと思います

速いソートを実装するならそういった最適化をしつつ
マルチスレッドで処理するようにするとArray.Sortを超えられると思います
[ 親 93174 / □ Tree ] 返信 編集キー/


管理者用

- Child Tree -