Help us understand the problem. What is going on with this article?

重複しない乱数配列(Java版/O(n)アルゴリズム)

More than 3 years have passed since last update.

ここまで O(n) のアルゴリズムのものが出ていないようですので、投稿します。
解説記事は気が向いたらそのうち書きます。⇒書きました。

public static int[] makeRandomArray1(Random rand, int size, int randMin, int randMax) {

    // パラメータチェック
    Objects.requireNonNull(rand, "rand==null はダメよ。");
    if (size < 0) {
        throw new IllegalArgumentException("size は 0 以上でお願いします。 size==" + size);
    }
    if (randMax < randMin) {
        throw new IllegalArgumentException(String.format(
                "max < min っておかしいよね?ねぇねぇおかしいよね?? randMin==%d, randMax==%d",
                randMin, randMax));
    }
    if (randMax - randMin + 1 < size) {
        throw new IllegalArgumentException(String.format(
                "範囲が狭すぎて size に足りないよ。 size==%d, randMin==%d, randMax==%d",
                size, randMin, randMax));
    }

    // 本処理
    int[] randArray = new int[size];
    Map<Integer, Integer> conversion = new HashMap<>();

    for (int i = 0, upper = randMax - randMin + 1; i < size; i++, upper--) {
        int key = rand.nextInt(upper);
        int val = conversion.getOrDefault(key, key);

        randArray[i] = val + randMin;

        conversion.put(key, conversion.getOrDefault(upper - 1, upper - 1));
        conversion.remove(upper - 1); // この行はメモリ節約のためのもの。無くても動く。
    }

    return randArray;
}

ポイントは「本処理」の部分が計算量 O(size) のアルゴリズムであることです。
size が大きくなっても衝突による性能劣化は生じません。
[2015/10/1追記] また、randMin~randMax の範囲が大きくなっても性能劣化は生じません。(randMin~randMax の広さによる影響を受けません。)

※上のコードでは、ちっとはメモリ節約になるかと思って HashMap を使いましたが、素直に配列を使っても良いかもしれません

最近のパソコンは性能が良いので力づくでやっちゃえば良いじゃん、という人もいるかもしれませんが。性能のことを考えずコーディングの手間だけを考えるのであれば、今や次のコードが一番簡単ですね。1

public static int[] makeRandomArray2(Random rand, int size, int randMin, int randMax) {
    // makeRandomArray1 と同じパラメータチェックを実施(記載略)

    return rand.ints(randMin, randMax + 1).distinct().limit(size).toArray();
}


  1. みなさん、たとえば後輩がこのコードを持ってきたらレビューで弾きますか? 測定はしていませんが、きっと1万件くらいまでなら実用時間で通るんだろうなぁ、と。ソースコードの見た目がとてもスマートなだけに悩ましいところだなあと感じました。私なら、アルゴリズム上の問題を理解しているか本人に確認し、理解したうえで敢えて採用しているのであれば通しちゃうかなぁ... 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした