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

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

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

半角英数しかない文字列を高速で大小判定したい

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

■95315 / inTopicNo.1)  半角英数しかない文字列を高速で大小判定したい
  
□投稿者/ Tom (31回)-(2020/07/16(Thu) 09:35:45)

分類:[C#] 

半角英数(0123456789abcdef)のみで構成された文字列を大小判定したいのですが、
string.Compareだと遅いといろんなサイトで指摘がありました。
比較のみでしたら == が高速とありましたが、ソートで使用するため大小判定が必要なのです。

カルチャとか大文字小文字同一視とか一切考慮しないけど、速度だけは圧倒的って方法、ありませんでしょうか?

賢者の方、お知恵をお貸しくださいませ。
引用返信 編集キー/
■95316 / inTopicNo.2)  Re[1]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ 774RR (807回)-(2020/07/16(Thu) 09:44:53)
どっちがどう大きいのか仕様がわからないと判断つかないよ
"a" > "12" なのか? "a" < "12" なのか? (頭から辞書順なのか整数変換した後の値なのか?)
とか。

題意上大文字は含まれなくて、考察不要ってことでよい?
引用返信 編集キー/
■95317 / inTopicNo.3)  Re[1]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ 魔界の仮面弁士 (2782回)-(2020/07/16(Thu) 09:48:54)
No95315 (Tom さん) に返信
> 半角英数(0123456789abcdef)のみで構成された文字列を大小判定したいのですが、
> string.Compareだと遅いといろんなサイトで指摘がありました。
String.Compare や String.CompareOrdinal を使ってみた場合に、
現状、どの程度の時間がかかっており、
それをどの程度まで短縮したいのでしょうか。

> ソートで使用するため大小判定が必要なのです。
対象件数として、何件程度が想定されていますか?
引用返信 編集キー/
■95318 / inTopicNo.4)  Re[2]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ Tom (32回)-(2020/07/16(Thu) 11:04:08)
774RR さま
魔界の仮面弁士 さま

> どっちがどう大きいのか仕様がわからないと判断つかないよ
単純に"9"<"a"になります。
1文字単位の比較です。

>題意上大文字は含まれなくて、考察不要ってことでよい?
はい、英文字は小文字のa〜fだけです。


>String.Compare や String.CompareOrdinal を使ってみた場合に、現状、どの程度の時間がかかっており、
現在、 string.CompareOrdinal で比較し、2秒前後かかっています。
結構頻繁にソートするため、できればこれを1秒以下にしたいのです。
なお、ソートは複数の条件(これはint型の比較のため速度にはほとんど影響しません)があるため、カスタムソートにしています。
(つまりList.Sortが使えません)

>対象件数として、何件程度が想定されていますか?
件数は40万レコード弱です。

なにかいい方法、ご存知でしょうか?
引用返信 編集キー/
■95319 / inTopicNo.5)  Re[3]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ ぶなっぷ (230回)-(2020/07/16(Thu) 11:15:47)
> 半角英数(0123456789abcdef)のみで構成された文字列を大小判定したいのですが、
ということは、文字列は16進数なのかな?

だったら、数値に変換してからソートしたほうが速くない?

以下のようなデータだとして、
var datas = new List<string>()
{
"1234",
"2fff",
"1f3a",
"19fe",
"21a4",
"2ab7",
};

以下のようにする。
datas.Sort((x, y) =>
int.Parse(x, NumberStyles.AllowHexSpecifier) - int.Parse(y, NumberStyles.AllowHexSpecifier));
引用返信 編集キー/
■95320 / inTopicNo.6)  Re[4]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ ぶなっぷ (231回)-(2020/07/16(Thu) 11:25:58)
2020/07/16(Thu) 11:32:42 編集(投稿者)

いったん、中身を数字に置き換えてからの方が速いかな?

var int_datas = datas.Select(x => int.Parse(x, NumberStyles.AllowHexSpecifier));
var sort_datas = (from x in int_datas orderby x select string.Format("{0:X}", x));
引用返信 編集キー/
■95321 / inTopicNo.7)  Re[5]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ Tom (34回)-(2020/07/16(Thu) 12:53:28)
ぶなっぷ さま
アドバイス、ありがとうございます。

> いったん、中身を数字に置き換えてからの方が速いかな?
比較したい文字列の文字数が、数十〜数百文字になるため数値化は困難なのです…
さすがに数値配列にセットして配列同士を比較 ってのは、試しては居ませんが文字列比較より遅くなりそうです。

なにが妙案ございませんか?
引用返信 編集キー/
■95322 / inTopicNo.8)  Re[6]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ くまくま (15回)-(2020/07/16(Thu) 13:25:14)
No95321 (Tom さん) に返信
> ぶなっぷ さま
> アドバイス、ありがとうございます。
>
>>いったん、中身を数字に置き換えてからの方が速いかな?
> 比較したい文字列の文字数が、数十〜数百文字になるため数値化は困難なのです…
> さすがに数値配列にセットして配列同士を比較 ってのは、試しては居ませんが文字列比較より遅くなりそうです。
>
> なにが妙案ございませんか?
ソートに関してこんな記事があります。
https://www.sejuku.net/blog/40456
Array.Sortが一番早いのは意外です。
引用返信 編集キー/
■95323 / inTopicNo.9)  Re[7]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ くまくま (16回)-(2020/07/16(Thu) 14:30:55)
追記
単純な1次文字列配列でなければ
(並べ替えはキーで実際使う値は別にあるとか...)

Enumerable.OrderBy メソッド
https://docs.microsoft.com/ja-jp/dotnet/api/system.linq.enumerable.orderby?view=netcore-3.1
は文字列の場合はバイナリ比較だそうですので早いと思うけど

引用返信 編集キー/
■95324 / inTopicNo.10)  Re[8]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ ぶなっぷ (232回)-(2020/07/16(Thu) 14:31:43)
そうなると、比較用メソッドを自作するぐらいしか思いつかないですねぇ。

カルチャとか大文字/小文字意識せず、単純な文字コード比較でいいなら、
以下のような感じですかねぇ。

拡張メソッド使用してますが、他の方法でもいいです。

public static class StringFunc
{
    public static int FastCompare(this string src, string dest)
    {
        int min_len = Math.Min(src.Length, dest.Length);
        for (int idx = 0; idx < min_len; idx++)
        {
            int diff = src[idx] - dest[idx];
            if (diff != 0) return diff;
        }
        return src.Length - dest.Length;
    }
}
という拡張メソッドを用意して、
    datas.Sort((x, y) => x.FastCompare(y));
と呼び出す。

ただ、そもそものstring.Compare()の実装を知らないので、もしかすると
上記の実装と同じかもしれません。
だとしたら、それ以上速い方法は思いつかないです。

引用返信 編集キー/
■95325 / inTopicNo.11)  Re[9]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ Hongliang (1060回)-(2020/07/16(Thu) 14:52:45)
文字列の文字コード単位の比較であれば、String.CompareOrdinalが一番速いでしょう。自前実装しようがネイティブ関数を呼び出してみようが恐らく歯が立ちません。

常にソートされていれば十分なのであれば、SortedList<TKey, TValue>を使えばいいかもしれません。Addのコストが増える代わりに、手動でソートする必要がなくなります。
// リストに追加後にソートキーとなる値が変わらないという前提も必要ですが。

前準備してもいいのであれば、先頭から16文字ずつをそれぞれulongに変換してulong配列に保持しておき、ソート時にまずこの配列同士を順次比較し、それが同じであればString.CompareOrdinal(string, int, string, int, int)で残りの文字列を比較する、という方法は、単純にString.CompareOrdinalするよりいくらか速くなりそうです。
引用返信 編集キー/
■95326 / inTopicNo.12)  Re[10]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ くまくま (17回)-(2020/07/16(Thu) 15:03:22)
Hongliangさんの言われる通り
String.CompareOrdinal比較でクイックソート作って並べ替える方法もあるけど
元からあるSortよりはやくなるかな?
引用返信 編集キー/
■95327 / inTopicNo.13)  Re[11]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ Hongliang (1061回)-(2020/07/16(Thu) 15:05:11)
> String.CompareOrdinal比較でクイックソート作って並べ替える方法もあるけど
> 元からあるSortよりはやくなるかな?


Sort自体ではなく、Sortに渡す比較関数をどうするかという話かと思いますが?
引用返信 編集キー/
■95328 / inTopicNo.14)  Re[12]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ くまくま (18回)-(2020/07/16(Thu) 15:18:55)
2020/07/16(Thu) 15:41:22 編集(投稿者)

No95327 (Hongliang さん) に返信
>>String.CompareOrdinal比較でクイックソート作って並べ替える方法もあるけど
>>元からあるSortよりはやくなるかな?
>
> ?
> Sort自体ではなく、Sortに渡す比較関数をどうするかという話かと思いますが?
あ、端よりすぎました。
Sort自体のアルゴリズムが分からないので
大量データでも安定的なクイックソートアルゴリズムのソートを自前で用意して試すのも一つの手ではないか?
でも元になるSort自体最適化されているので意味はないのではないのか?
だからHongliangさんが提案した追加する際並び順を意識した形で挿入できるSortedList<TKey, TValue>は有効ではないか?
という話です。

ただ別の言語で比較にならないのですが同じような事を試しましたが追加が指数倍的に遅くなっていったことがあります。
引用返信 編集キー/
■95329 / inTopicNo.15)  Re[12]: 半角英数しかない文字列を高速で大小判定したい
□投稿者/ Tom (35回)-(2020/07/16(Thu) 15:24:41)
くまくま さま
ぶなっぷ さま
Hongliang さま
アドバイス、ありがとうございます。

うーん、皆さんのお話からどうも現在使用している String.CompareOrdinal より高速なのは難しそうですね。
せっかくサンプルコードまで作ってくださったのですが…
わかりました、残念ですがあきらめます。
現在でも ちょっともたつくかな? って程度なんで我慢できるレベルですから。

皆様、ありがとうございました。
解決済み
引用返信 編集キー/

このトピックをツリーで一括表示


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

このトピックに書きこむ