Javaの優先度付きキュー

Javaで複数条件でソートする。 - ITエンジニアの技術メモ
で扱った題材を優先度付きキュー PriorityQueue を使って実装してみた。

以下のような感じになる。

        Queue<Work> queue = new PriorityQueue(Comparator.
                comparing(Work::getReward, Comparator.reverseOrder()).
                thenComparing(Work::getTimeToFinish));
        queue.add(new Work(1, 3));
        queue.add(new Work(3, 8));
        queue.add(new Work(2, 6));
        queue.add(new Work(3, 7));
        queue.add(new Work(1, 4));
        queue.add(new Work(4, 6));

        while (true) {
            Work work = queue.poll();
            if (work == null) {
                break;
            }
            System.out.println("TimeToFinish: " + work.getTimeToFinish() + 
                    ", Reward: " + work.getReward());
        }
    }

実行結果は以下になる。(前記事と同じ結果)

TimeToFinish: 3, Reward: 8
TimeToFinish: 3, Reward: 7
TimeToFinish: 2, Reward: 6
TimeToFinish: 4, Reward: 6
TimeToFinish: 1, Reward: 4
TimeToFinish: 1, Reward: 3

なお、この PriorityQueue から要素を取り出す時に、iterator を使うと、意図した順番で取得できないので注意。
PriorityQueue (Java Platform SE 8)

iterator()メソッド内で提供されるIteratorでは、特定の順序で優先度キューの要素をトラバースすることは保証されません。

Javaで複数条件でソートする。

Javaでリストを複数の条件でソートしたい時は、Comparator クラスの comparing() と thenComparing() を使うと簡単に実現できる。

例えば、以下の Work クラスのオブジェクトが複数入った List があるとする。

    class Work {
        private int timeToFinish; // 仕事が終わるまでにかかる時間
        private int reward; // 報酬
        Work(int timeToFinish, int reward) {
            this.timeToFinish = timeToFinish;
            this.reward = reward;
        }
        public int getTimeToFinish() {
            return timeToFinish;
        }
        public int getReward() {
            return reward;
        }
    }

その List について、報酬が高い順に、そして報酬が同じだったら、仕事が終わるまでにかかる時間が少ない順でソートしたいとする。
# つまり、ソートの第一条件が報酬(降順)で、第二条件が仕事が終わるまでにかかる時間(昇順)。

このソートを実現するには以下のように実装する。

        List<Work> works = new ArrayList<>();
        ・・・
        Comparator<Work> workComparator =
                Comparator.comparing(Work::getReward, Comparator.reverseOrder())
                        .thenComparing(Work::getTimeToFinish);
        works.sort(workComparator);

ソートの第一条件にソートの第二条件を繋げて Comparator を作成し、それを sortメソッドの引数として与えている。

以上を踏まえて、例えば以下を実行すると、

        List<Work> works = new ArrayList<>();
        works.add(new Work(1, 3));
        works.add(new Work(3, 8));
        works.add(new Work(2, 6));
        works.add(new Work(3, 7));
        works.add(new Work(1, 4));
        works.add(new Work(4, 6));

        Comparator<Work> workComparator =
                Comparator.comparing(Work::getReward, Comparator.reverseOrder())
                        .thenComparing(Work::getTimeToFinish);
        works.sort(workComparator);
        for (Work work : works) {
            System.out.println("TimeToFinish: " + work.getTimeToFinish() + ", Reward: " + work.getReward());
        }
    }

出力結果は以下にようになる。

TimeToFinish: 3, Reward: 8
TimeToFinish: 3, Reward: 7
TimeToFinish: 2, Reward: 6
TimeToFinish: 4, Reward: 6
TimeToFinish: 1, Reward: 4
TimeToFinish: 1, Reward: 3

期待通り、報酬が高い順に、報酬が同じだったらかかる時間が短い順にソートされている。

SNMPのCounterBasedGauge64型について

以前、https://akrad.hatenablog.com/entry/2019/08/21/232701 の記事を書いた後、ネット上で、CounterBasedGauge64 という型があるという情報を見つけた。

「SNMPに Counter64型以外で64bitの範囲の値を表現できる型があるのかな？」と思ったが、さらに調べたところ、これは Counter64 型の Textual Convention (別名のようなもの) だった。つまり、SNMPに Counter64型以外で64bitの範囲の値を表現できる型があるわけではない。

ちなみに、RFCでの説明は以下になっている。

3.1. CounterBasedGauge64
This textual convention defines a 64-bit gauge, but defined with
Counter64 syntax, since no Gauge64 or Unsigned64 base type is
available in SMIv2.

This TC is used for storing the difference between two Counter64
values, or simply storing a snapshot of a Counter64 value at a given
moment in time.

・・・

4. Definitions

CounterBasedGauge64 ::= TEXTUAL-CONVENTION 

STATUS current

DESCRIPTION
"The CounterBasedGauge64 type represents a non-negative
integer, which may increase or decrease, but shall never
exceed a maximum value, nor fall below a minimum value. The
maximum value can not be greater than 2^64-1
(18446744073709551615 decimal), and the minimum value can
not be smaller than 0. The value of a CounterBasedGauge64
has its maximum value whenever the information being modeled
is greater than or equal to its maximum value, and has its
minimum value whenever the information being modeled is
smaller than or equal to its minimum value. If the
information being modeled subsequently decreases below
(increases above) the maximum (minimum) value, the
CounterBasedGauge64 also decreases (increases).

★Note that this TC is not strictly supported in SMIv2,
because the 'always increasing' and 'counter wrap' semantics
associated with the Counter64 base type are not preserved.
It is possible that management applications which rely
solely upon the (Counter64) ASN.1 tag to determine object
semantics will mistakenly operate upon objects of this type
as they would for Counter64 objects.

★This textual convention represents a limited and short-term
solution, and may be deprecated as a long term solution is
defined and deployed to replace it."

SYNTAX Counter64

 https://tools.ietf.org/html/rfc2856

上記の★の辺りを読むと、SMIv2 で厳密にサポートされているわけではなく、使われなくなるかもしれないという記載もあるので、今後もあまり目にする機会はなさそうな気がする。

Javaで Stringの配列中の単語の出現回数をカウントする。

競技プログラミングの問題を解く際の時間短縮のため、主題のメソッドを作成した。

    // Stringの配列の中で、単語の出現回数をカウントする。
    Map<String, Integer> countWordsAppearance(String[] words) {
        if (words == null || words.length == 0) {
            throw new IllegalArgumentException("Input words is null or empty.");
        }
        Map<String, Integer> wordToCount = new HashMap<>();
        for (String word : words) {
            if (wordToCount.containsKey(word)) {
                // 2回目以降
                int count = wordToCount.get(word);
                wordToCount.put(word, ++count);
            }
            else {
                // 初回
                wordToCount.put(word, new Integer(1));
            }
        }
        return wordToCount;
    }

カウント結果は、単語(String) ⇒ 出現回数(Integer) のマップとして返す。結果を参照する場合は、以下のようにして取り出す。

    Map<String, Integer> result = countWordsAppearance(words);
    int count = result.get("aaa");

ちなみに、Javaでは、MapのValueにはプリミティブ型は使用できないので、int 型ではなく Integer型を使っている。

Javaで配列が昇順 or 降順かを調べる

競技プログラミングの問題を解く際の時間短縮のため、Javaで配列が昇順 or 降順かを調べるメソッドを作成した。配列の要素が一個しかない場合、どう判定しようか迷ったが、そもそも要素が一個しかない場合、このメソッドを使うべきではないので、例外を上げることにした。

// 配列が昇順か調べる
boolean isAscendingOrder (int[] array) {
    if (array == null || array.length == 0) {
        throw new IllegalArgumentException("Input array is null or empty.");
    }
    // 要素が一個しかない場合は、判定できないので、例外を上げる。
    if (array.length == 1) {
        throw new IllegalArgumentException("Input array has only one element, so can't judge it.");
    }
    for (int i = 0; i <= array.length - 2; i++) {
        if (array[i] > array[i + 1]) { // 同値の場合は、false にしないことにする。(昇順と判定)
            return false;
        }
    }
    return true;
}

// 配列が降順か調べる
boolean isDescendingOrder (int[] array) {
    if (array == null || array.length == 0) {
        throw new IllegalArgumentException("Input array is null or empty.");
    }
    // 要素が一個しかない場合は、判定できないので、例外を上げる。
    if (array.length == 1) {
        throw new IllegalArgumentException("Input array has only one element, so can't judge it.");
    }
    for (int i = 0; i <= array.length - 2; i++) {
        if (array[i] < array[i + 1]) { // 同値の場合は、false にしないことにする。(降順と判定)
            return false;
        }
    }
    return true;
}

JavaプログラムのCPU使用率高騰

JavaプログラムのCPU使用率が高騰するパターンの一つについて簡単に纏める。

1. 一時的に負荷が上がり、Javaプログラムのメモリ使用量が増大する。
2. メモリリソースが逼迫し、Javaが不要なメモリを解放するため、GCが頻繁に走るようになる。
3. GCがCPUリソースを消費し、CPU使用率が高騰する。

〇参考

https://qa.atmarkit.co.jp/q/720

https://www.atmarkit.co.jp/ait/articles/1005/13/news095.html

Javaで配列の要素が全て同じか調べる

競プロの問題を解いていて必要になったので、今後の時間短縮のため、主題のメソッドを作成した。

    // 配列の要素がすべて同じか調べる
    boolean isAllSame (int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("Input array is null or empty.");
        }
        // 要素が一個しかないので、すべて同じとして true を返す。
        if (array.length == 1) {
            return true;
        }
        for (int i = 0; i <= array.length - 2; i++) {
            if (array[i] != array[i + 1]) {
                return false;
            }
        }
        return true;
    }

上記は int 型の配列に対するメソッドなので、他の型の場合は型のところを書き換えて使う。