- PR -

文字列配列のソートにて

«前のページへ 1|2
投稿者投稿内容
Izumi, Y.
ベテラン
会議室デビュー日: 2002/03/19
投稿数: 77
お住まい・勤務地: 東京
投稿日時: 2003-06-16 11:48
引用:

１０進指数表現みたいな物を使ってSORTできませんか

指数(?)を入れてしまえばもちろん簡単にソートできますが、どうやって入れるのでしょう？
「エディタですぐ」ということはひょっとして前後処理って Java でないものを…

＃念のため書いておきますが、上の parse 関数を利用しようというのであれば整数に直して
＃しまったほうが多分高速ですよ。
まさ
ベテラン
会議室デビュー日: 2002/11/15
投稿数: 74
投稿日時: 2003-06-16 13:15
まさです！お世話になっています！

引用:

１０進指数表現みたいな物を使ってSORTできませんか


すいません。この部分の意味がわからないんですが…
数値部分の桁を示す指数を付加するって意味であってますか？
でも結局、数値が何桁であるかどうかを1文字ずつ調べないと
だめそうですよねぇ…


1文字ずつ比較して「数値」「数値以外」で分けるのは確かに簡単ですが、
コストがぜんぜん違いますよね。
特に配列のソートなので何度も比較しますんで…

独自 Comparator でソートした結果、
単純に文字列比較と分割して比較するのでは
3〜8倍くらいの差が出てます。

# ん？比較する前に先に数値と数値以外で分割しておけばもしかして速いかも？
Izumi, Y.
ベテラン
会議室デビュー日: 2002/03/19
投稿数: 77
お住まい・勤務地: 東京
投稿日時: 2003-06-16 13:43
引用:
3〜8倍くらいの差が出てます。

もともとやっていることがややこしいので、そのぐらいの比になってしまうのは仕方ないです。
引用:
# ん？比較する前に先に数値と数値以外で分割しておけばもしかして速いかも？

ごもっとも :-)

あ、だから文字列に桁数を挿入するのか。
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2003-06-16 20:23
unibon です。こんにちわ。

引用:

まささんの書き込み (2003-06-16 13:15) より:
独自 Comparator でソートした結果、
単純に文字列比較と分割して比較するのでは
3〜8倍くらいの差が出てます。

# ん？比較する前に先に数値と数値以外で分割しておけばもしかして速いかも？

目的は、ソート時に必要な比較をできるだけ速くおこなう、ということですよね。

コンパレータの内部で、比較結果のキャッシュを持つか、
あるいは、おっしゃるように事前に比較し易い形式に変換してしまうか、
の2つのうちのどちらかだろうと思います。
ただ、いずれのやり方にしても、
比較対象のオブジェクトと「比較し易い形式」との関連付けをおこなう
良い方法がないことが問題となります。
せいぜい HashMap などを使うことになりますが、
こんどはこちらのコストのほうが高くなってしまうことが予想されます。
比較対象のオブジェクト自身に「比較し易い形式」を属性として持たせられれば良いのですが、
フィールドをそのためだけに増設するのもあまりキレイではなく気がひけます。

問題が単純なだけに、効果的な解決は難しいかもしれません。
まさ
ベテラン
会議室デビュー日: 2002/11/15
投稿数: 74
投稿日時: 2003-06-17 12:52
まさです！

引用:

unibon さんより
コンパレータの内部で、比較結果のキャッシュを持つか、
あるいは、おっしゃるように事前に比較し易い形式に変換してしまうか、


どのようにキャッシュを持つか想像もできないので
とりあえず事前に変換のほうで話を進めたいと思います。


引用:

せいぜい HashMap などを使うことになりますが、
こんどはこちらのコストのほうが高くなってしまうことが予想されます。


確かに。
分割してやってみたんですが多少早くなる程度で
あまりよいパフォーマンスは出ませんでした。


引用:

IZUMI Yusuke さんより
あ、だから文字列に桁数を挿入するのか。


この書き込みを見て「はっ！」としました。
桁数を示す指数を16進数にするとか、
工夫すれば結構な桁数の数値を指数で簡単にあらわせるかもしれませんね。

ちょっとやってみます。
まさ
ベテラン
会議室デビュー日: 2002/11/15
投稿数: 74
投稿日時: 2003-06-17 13:40
まさです！！

比較対象に指定された文字列を数値部分・数値以外の部分で分割し、
数値部分の前に数値部分の桁数を示す「指数」を挿入したものを比較対象とする
コンパレータを作ってみました。

引用:

工夫すれば結構な桁数の数値を指数で簡単にあらわせるかもしれませんね。


上記のような方針でソートをかけた場合、
16進で指数部分を表現すると A〜F があるので問題があることに気づきました。
したがって単純に桁数を10進数で表すことにして試してみました。

結果的には MMX さんがおっしゃっていた通りの比較方法で
約2倍程度のコストでソートができるようになりました。

2倍程度ならかなり満足です！
やったぁ〜！！
皆さんありがとうございました！！
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2003-06-17 18:32
unibon です。こんにちわ。

キャッシュや事前の計算とは別のソリューションとして、
コンパレータを極限までチューニングしてみました。ご参考までに。
10万個程度の要素数だと、単純な String の比較と比べても
処理時間は 2 倍程度に収まったみたいです。
数値の大小比較を工夫して、数値としての比較よりも、
まず桁数でふるい落とすのがミソです。

以下、試したコンパレータのコードと、簡単なテスト用ドライバです。
なお、取り扱える文字列には、
前ゼロを付けてはいけない("aaa001" はダメ)、マイナス("aaa-1")もダメ、
などの厳しい制約があるので使う際はそれなりの注意が必要です。

コード:
import java.util.*;

public class ComparatorTester {

    private static class MyComparator implements Comparator {

        public int compare(Object a, Object b) {
            String p = (String) a;
            String q = (String) b;
            int x = p.length();
            int y = q.length();
            int n = Math.min(x, y);
            for (int i = 0; i < n; i++) {
                char c = p.charAt(i);
                char d = q.charAt(i);
                if (c != d) {
                    boolean f = (c >= '0' && c <= '9');
                    boolean g = (d >= '0' && d <= '9');
                    if (f && !g) {
                        return -1;
                    } else if (!f && g) {
                        return 1;
                    } else if (!f && !g) {
                        return c - d;
                    }
                    if (x != y) {
                        return x - y;
                    }
                    return c - d;
                }
            }
            return x - y;
        }
    }

    public static void main(String[] args) {
        final int SIZE = 100;
        Random random = new Random(1438342932L);
        Comparator comparator = new MyComparator();
        String[] stringArray = new String[100000];
        for (int i = 0; i < stringArray.length; i++) {
            StringBuffer buf = new StringBuffer();
            for (int j = 0; j < random.nextInt(3) + 1; j++) {
                char c = (char) ('a' + random.nextInt(26));
                buf.append(c);
            }
            int value = random.nextInt(SIZE);
            buf.append(value);
            stringArray[i] = new String(buf);
        }
        long a = System.currentTimeMillis();
        Arrays.sort(stringArray, comparator);
        // Arrays.sort(stringArray);
        long b = System.currentTimeMillis();
        System.out.println("time = " + (b - a) + "[ms]");
        // for (int i = 0; i < stringArray.length; i++) {
        //     System.out.println("index = " + i + ", value = " + stringArray[i]);
        // }
    }
}

«前のページへ 1|2

スキルアップ／キャリアアップ（JOB@IT）