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

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

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

Re[4]: 自然ソートを高速で行う方法

(過去ログ 161 を表示中)

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

■93174 / inTopicNo.1)

　自然ソートを高速で行う方法

▼■

□投稿者/ 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のような変数に変換して、
後から、順番に比較するようなことをしたいのですが
そのようなことは可能でしょうか？

他にもっと高速な方法がありましたらお教えくださいませ。

引用返信 編集キー/

■93180 / inTopicNo.2)

　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ループ使っていないようですが
ソートは自作？
アルゴリズムは？

引用返信 編集キー/

■93185 / inTopicNo.3)

　Re[2]: 自然ソートを高速で行う方法

▲▼■

□投稿者/ はまぐり (79回)-(2019/11/26(Tue) 20:41:58)

■No93174 (NNN さん) に返信
シュワルツ変換を使ったソートならLINQのOrderByを使えば簡単にできます

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

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

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

引用返信 編集キー/

■93359 / inTopicNo.4)

　Re[3]: 自然ソートを高速で行う方法

▲▼■

□投稿者/ NNN (10回)-(2019/12/07(Sat) 12:11:42)

ありがとうございます。
返信遅れました
furuさんの仰る通り、
バブルソートを使っているのが原因でした

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

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

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

引用返信 編集キー/

■93361 / inTopicNo.5)

　Re[4]: 自然ソートを高速で行う方法

▲▼■

□投稿者/ キングダム (50回)-(2019/12/07(Sat) 20:42:59)

■No93359 (NNN さん) に返信

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

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

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

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

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

速いソートを実装するならそういった最適化をしつつ
マルチスレッドで処理するようにするとArray.Sortを超えられると思います

引用返信 編集キー/

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

このトピックに書きこむ

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

- Child Tree -