情報妖精の競プロ日記

この記事は競プロ Advent Calendar 2022の7日目として作成されました。

注意
本記事は競技プログラミングに寄せた内容が多々入りますが、競技プログラミングを前提とした記事ではありません。
一般的に趣味でプログラミングを行う全般に言及する内容として記載します。
また、必要に応じてJavaコードを用いた例を提示することがあります。

上は私のライブラリの例。

はじめに
作るべきライブラリとは？
実際にライブラリの例を見てみる
ライブラリを作る際に気を付けるべきこと
まとめ

はじめに

皆さん、プログラミングをしていますか？
趣味でプログラミングをする際、自分用に作った秘伝のライブラリ集がある方も多いと思います(私も数百MBほど持っています)。
しかし、そういう秘伝のライブラリ集をいざ使おうとしたとき、どんな処理をやっているか分からなくて困った経験はありませんか？
この記事では、私が自身の秘伝ライブラリを何年も継ぎ足してきて学んだことを共有していきたいと思います。

作るべきライブラリとは？

まずこれは前提なのですが、ライブラリは上手く作らないと負債になります。
とはいえ、一人で趣味で使うものなのであれば、負債を削除する選択肢も容易です。
従って、気を付けるべきはどちらかというと手に負えない規模になることを防ぐことです。

さて、ライブラリとして考えられるパターンは次のようなものがあります。

機能・処理を提供する(ユーティリティクラス)
新たなデータ型を作る
新たな性質・振る舞いを提供する(インタフェースなど)

順に見ていきましょう。

機能・処理を提供する(ユーティリティクラス)

このパターンはよくあるパターンですね。
例えば、配列が与えられた時に、その総和を求める関数を提供するクラスを作ろう！ということです。

public static final class ArrayUtility {
  private ArrayUtility() {
    throw new AssertionError("No ArrayUtility instances for you!");
  }
  /**
   * {@code int}型の配列に対して、その総和を求めます。
   * @param array 総和を求める配列
   * @return 総和
   * @exception NullPointerException 与えられた配列が{@code null}の場合
   */
  public static long sum(int[] array) {
    return Arrays.stream(array).mapToLong(i -> i).sum();
  }
}

上の例は配列に対してその総和を求める関数を持つユーティリティクラスを作成したものです。
ユーティリティクラスにはいくつかの特徴があります。

ユーティリティクラスはインスタンスを生成することができない

ArrayUtility

ラク

ArrayUtility

インスタンス

ArrayUtility::sum

ユーティリティクラスが持つメソッドは決定的である

Arrays::sort

なお、ユーティリティクラスはstaticなインスタンスを持つことを禁止していません。
例えば空の配列を返すメソッドを作り、予め用意しておいたstaticな空の配列を返す、という使い方もできます。
シングルトンのインスタンスを返したい時などに、この手法を用いると生成がギリギリまで遅延され、必要になった時に始めて作られるのでメモリの効率化と利便性を両立させることもできます(遅延初期化ホルダークラスイディオムと呼ばれます)。

ユーティリティクラスを用いれば、ちょっとした便利なメソッド群を一つに纏めることができます。
だからと言って、全部同じクラスに纏めるのは得策ではありません。
極端な例として、Utilityなるクラスに全ての便利なメソッドを集めまくった状態を考えてみましょう。
どんな欲しいメソッドも確かにUtilityクラスにはあるのでしょうが、何千、何万とあるメソッドの中から自分が欲しているメソッドを探すことは困難でしょう。
ちゃんと、各メソッドはそれが入るに相応しい名前のユーティリティクラスに収められていることが重要なのです(例えばMath::cosはMathクラスに、Arrays::sortメソッドはArraysクラスに収められているように)。

新たなデータ型を作る

このパターンも頻出ですね。
最も有名な形は構造体としての形ですが、そうでなくても新たなデータ型を作ること自体はよくあります。
ある種、Java16から追加されたレコードと同じようなものでしょうか？

例えば、一次関数を管理するクラスを作るとします。

/**
 * 一次関数ax+bを管理するクラスです。
 */
public class LinearFunction implements IntUnaryOperator {
  public final int a, b;
  /**
   * 一次関数をax+bで初期化します。
   * @param a 傾き
   * @param b 切片
   */
  LinearFunction(int a, int b) {
    this.a = a;
    this.b = b;
  }
  @Override
  public int applyAsInt(int x) {
    return a * x + b;
  }
  /**
   * まず入力に関数{@code before}を適用し、次に結果にこの関数を適用する合成関数を返します。
   * @param before この関数を適用する前に適用する関数
   * @return まず{@code before}関数を適用し、次にこの関数を適用する合成関数
   * @exception NullPointerException {@code before}が{@code null}の場合
   */
  public LinearFunction andThen(LinearFunction after) {
    return new LinearFunction(after.a * a, after.a * b + after.b);
  }
  /**
   * まず入力にこの関数を適用し、次に結果に関数{@code after}を適用する合成関数を返します。
   * @param after この関数を適用した後で適用する関数
   * @return まずこの関数を適用し、次に{@code after}関数を適用する合成関数
   * @exception NullPointerException {@code after}が{@code null}の場合
   */
  public LinearFunction compose(LinearFunction before) {
    return new LinearFunction(a * before.a, a * before.b + b);
  }
  /**
   * 一次関数の単位元、すなわちxを返します。
   * @return 1x+0
   */
  public static LinearFunction identity() {
    return new LinearFunction(1, 0);
  }
}

このように、データとそれを扱うメソッド群を作るのは一般的な設計ですね。

ここで一つ気を付けることは、データ型は内部をそこまで理解していなくても使えるようにしておくことです。
勿論データ型なのでどのようなデータを持っているかは理解していないとそもそも不可能ですが、その管理方法までは理解していなくても使える方が良いです。
例えば、TreeSetがどのようにデータを管理しているかを正確に理解していますか？
説明を読む限りでは赤黒木を用いたTreeMapの値域にダミーの値を入れて運用しているようですが、こんなことを知らなくてもTreeSetは利用できます。
ただ、TreeSetは全順序な要素の集合を管理しており、殆どの処理は $O(\log N)$ で行うことができるという事実が分かっていれば、内部実装は分からずともデータ型を扱うことができるのです。
(愚痴: Javaは計算量を明記して欲しい……。)

新たな性質・振る舞いを提供する(インタフェースなど)

これは前者二つに比べるとかなり分かり辛いかと思います。
このような例としては、例えばComparatorが挙げられます。
Comparatorは比較関数のインタフェースで、これを実装するクラスは何らかの値に対する比較関数を提供することになります。
つまり、演算子をクラスにしたもの、と言うことができるかもしれません。

このように、抽象的な性質をクラスという形に落とし込むと、様々な点でメリットが生まれます。
実際に具体例を見ながら、その良さを確認していきましょう。

マーカー・インタフェース

マーカー・インタフェースは、一切のメソッドも変数も持たない、空っぽのインタフェースです。
このインタフェースは、継承することで自身が特定の性質を持っていることをアピールするために使われます。
例えば、RandomAccessはListにランダムアクセス可能なことをアピールするマーカー・インタフェースです。
これを適切に継承すると、何ができるのでしょうか？
例えばリストの最大値を求めるメソッドが、もしランダムアクセス可能なリストなら何個かの区間に区切って並列化する処理を入れたいとします。
この時、与えられた引数がRandomAccessを継承しているかを判定すればランダムアクセス可能か判断できます(演算子instanceofを使います)。

新たな振る舞いを追加するインタフェース

よくあるインタフェースは、これを継承したクラスはこんなことができるよ、というインタフェースですね。
大抵は数個のメソッドを持ち、継承したクラスに特定のメソッドが保持されることを保証します。
～ableという名前のインタフェースは大抵これで、〇〇できるよ！という意味を持つ訳ですね。
実行可能を意味するRunnable、比較可能を意味するComparable、直列化可能を意味するSerializableなどが有名ですね(最後のはマーカー・インタフェースですが)。

演算を提供するインタフェース

これはなかなか面白い使い方で、これを継承したクラスは外部からデータ型などに性質を付与することができます。
例えば、以下は私が良く使っているMonoidインタフェースです。

/**
 * 演算がモノイドであることを示すために使用するマーカー・インターフェースです。
 * @param <T> 二項演算の型
 */
public interface Monoid<T> extends Associative<T>, Unital<T> {
}

このインタフェースでは、単位元を持ち、結合法則を満たすような二項演算を提供します。
これを実際に実装すると、例えば次のようになりますね。

public class LinearFunction implements IntUnaryOperator {
  /**
   * 一次関数の合成を行う二項演算を返します。
   * @return 一次関数の合成を行う二項演算
   */
  public static Monoid<LinearFunction> getOperator() {
    return new Monoid<LinearFunction>() {
      @Override
      public LinearFunction apply(LinearFunction t, LinearFunction u) {
        return t.compose(u);
      }
      @Override
      public LinearFunction identity() {
        return LinearFunction.identity();
      }
    };
  }
}

先ほどの例に書いた一次関数のメソッドに、関数の合成を行う演算を返すメソッドを追加したものです。
これを用いて、例えば次のようなメソッドを作ることができます。

/**
 * リストの全ての要素を与えられた演算で畳み込んだ結果を返します。
 * @param list 畳み込むリスト
 * @param operator 演算
 * @return 畳み込んだ結果
 * @exception NullPointerException {@code list}が{@code null}、あるいは{@code operator}が{@code null}
 */
public static <T> E fold(List<T> list, Monoid<T> operator) {
  return list.stream().reduce(operator.identity(), operator);
}

このメソッドは、Tが何かを一切知らなくても正しく振舞うことに注意してください。
例えばこのメソッドはlistが要素数0のリストでも正しく振舞い、この場合は単位元が返ってきます。
また、このメソッドは畳み込む順番に依存しません。
例え $(a \circ b) \circ c$ と計算しようが $a \circ (b \circ c)$ と計算しようが答えは同じになります。
これが正当な動作なのは、例えばTとしてInteger、Monoidとして通常の足し算を渡した時、空のリストからは0が返ってきて欲しいし、 $(a+b)+c = a+(b+c)$ になって欲しいことから分かるかと思います。
このように、演算をいったん外に切り出すことで、高度に抽象化したメソッドを作ることもできるようになります。
また、これはある意味で依存している性質を外に追い出し、後で必要なときに依存している性質を注入している(Dependency Injection)という考え方もできますね。

実際にライブラリの例を見てみる

せっかくなので、実際に作ったライブラリの例を一つ見てみましょう。
私はゲームやヒューリスティックコンテストなどで使える高速な乱数生成器が欲しいと思っていました。
欲しい条件は以下の通りです。

高速(重要！)
偏りが少ない
別にhackされることを気にする必要はない

この条件を満たすものとして、有名なものはxorshiftです。
xorshiftは少ない回数のbit演算のみで作れる乱数であることがポイントで、bitごとの偏りもほぼありません。
欠点は乱数が特定しやすいことで、一種の $\mathbb{F}_2$ 上の連立方程式を解いているだけなので64個の最下位bitがあるだけでseed値が割れてしまうことですが……今回の要件では問題無いので、気にせず作ることにします。
そうしてできたものが以下になります。

/**
 * xorshiftを用いた乱数生成器です。
 * @author 31536000
 *
 */
class FastRandom extends java.util.Random {

  private static final long serialVersionUID = -8497888336513480059L;
  private long rand;
  private static final float FLOAT_INV = 1f / (1 << 24);
  private static final double DOUBLE_INV = 1. / (1L << 53);

  /**
   * 新規乱数ジェネレータを作成します。
   * このコンストラクタは、乱数ジェネレータのシードを、このコンストラクタの他の呼び出しと区別可能な値に設定します。
   */
  public FastRandom() {
    this(new java.util.Random().nextLong());
  }

  /**
   * <p>
   * 単一の{@code long}型のシードを使って、新しい乱数ジェネレータを作成します。
   * シードは、擬似乱数ジェネレータの内部状態の初期値で、{@link #next(int)}メソッドによって保守されます。
   * </p>
   * <p>
   * 呼び出し{@code new FastRandom(seed)}は次と等価です。
   * <pre>{@code
   * FastRandom rnd = new FastRandom();
   * rnd.setSeed(seed);
   * }</pre>
   * </p>
   * @param seed 初期シード
   */
  public FastRandom(long seed) {
    rand = seed;
  }

  @Override
  public void setSeed(long seed) { rand = seed; }

  @Override
  protected int next(int bits) {
    return nextInt() & ((1 << bits - 1) - 1 << 1 | 1);
  }

  @Override
  public int nextInt() {
    rand = rand ^ rand << 7;
    rand = rand ^ rand >>> 9;
    return (int) (rand & 0xFFFFFFFFL);
  }

  @Override
  public int nextInt(int bound) {
    if (bound <= 0) throw new IllegalArgumentException(String.valueOf(bound));
    long random = next(31) * (long) bound;
    int leftover = (int) (random & Integer.MAX_VALUE);
    if (leftover < bound) {
      int threshold = (Integer.MIN_VALUE - bound) % bound;
      while (leftover < threshold) {
        random = next(31) * (long) bound;
        leftover = (int) (random & Integer.MAX_VALUE);
      }
    }
    return (int) (random >>> 31);
  }

  /**
   * <p>
   * 0以上{@code bound}未満の値を一様分布に従って生成する関数を返します。
   * 返された関数は、呼ぶ度に{@link #nextInt(bound)}を返します。
   * </p>
   * <p>
   * このメソッドによって生成される関数は{@code bound}の値に特化しています。
   * 従って、同じ{@code bound}を用いて複数回の乱数生成を行う場合、このメソッドを用いて生成された関数を用いた方が実行時間効率が良くなることがあります。
   * </p>
   * @param bound 上限(含まない)。正の値でなければならない
   * @return {@link #nextInt(bound)}を返す関数
   * @exception IllegalArgumentException {@code bound}が正でない場合
   */
  public java.util.function.IntSupplier IntGenerator(int bound) {
    if (bound <= 0) throw new IllegalArgumentException(String.valueOf(bound));
    int threshold = (Integer.MIN_VALUE - bound) % bound;
    return () -> {
      long random = next(31) * (long) bound;
      int leftover = (int) (random & Integer.MAX_VALUE);
      if (leftover < bound) {
        while (leftover < threshold) {
          random = next(31) * (long) bound;
          leftover = (int) (random & Integer.MAX_VALUE);
        }
      }
      return (int) (random >>> 31);
    };
  }

  /**
   * {@code startInclusive}以上{@code endExclusive}未満の値を一様分布に従って生成します。
   * @param startInclusive 下限
   * @param endExclusive 上限
   * @return {@code startInclusive}以上{@code endExclusive}未満の値
   * @exception IllegalArgumentException {@code startInclusive >= endExclusive}
   */
  public int nextInt(int startInclusive, int endExclusive) {
    if (startInclusive >= endExclusive)
      throw new IllegalArgumentException("range [" + startInclusive + ", " + endExclusive + ") is empty");
    return nextInt(endExclusive - startInclusive) + startInclusive;
  }

  /**
   * <p>
   * {@code startInclusive}以上{@code endExclusive}未満の値を一様分布に従って生成する関数を返します。
   * 返された関数は、呼ぶ度に{@link #nextInt(startInclusive, endExclusive)}を返します。
   * </p>
   * <p>
   * このメソッドによって生成される関数は入力値に特化しています。
   * 従って、同じ入力値を用いて複数回の乱数生成を行う場合、このメソッドを用いて生成された関数を用いた方が実行時間効率が良くなることがあります。
   * </p>
   * @param bound 上限(含まない)。正の値でなければならない
   * @return {@link #nextInt(startInclusive, endExclusive)}を返す関数
   * @exception IllegalArgumentException {@code startInclusive >= endExclusive}
   */
  public java.util.function.IntSupplier IntGenerator(int startInclusive, int endExclusive) {
    if (startInclusive >= endExclusive)
      throw new IllegalArgumentException("range [" + startInclusive + ", " + endExclusive + ") is empty");
    int bound = endExclusive - startInclusive;
    int threshold = (Integer.MIN_VALUE - bound) % bound;
    return () -> {
      long random = next(31) * (long) bound;
      int leftover = (int) (random & Integer.MAX_VALUE);
      if (leftover < bound) {
        while (leftover < threshold) {
          random = next(31) * (long) bound;
          leftover = (int) (random & Integer.MAX_VALUE);
        }
      }
      return (int) (random >>> 31) + startInclusive;
    };
  }

  /**
   * {@code startInclusive}以上{@code endExclusive}未満の値を{@code count}個、重複無しで一様分布に従って生成します。
   * @param startInclusive 下限
   * @param endExclusive 上限
   * @param count 個数
   * @return {@code startInclusive}以上{@code endExclusive}未満の値が重複無しで{@code count}個入った配列
   * @exception IllegalArgumentException {@code endExclusive - startInclusive >= count}
   */
  public int[] nextInts(int startInclusive, int endExclusive, int count) {
    if (endExclusive - startInclusive < count) throw new IllegalArgumentException(
        "number of integer in [" + startInclusive + ", " + endExclusive + ") is less than " + count);
    int len = endExclusive - startInclusive;
    int[] result = new int[count];
    java.util.HashMap<Integer, Integer> map = new java.util.HashMap<>();
    for (int i = 0; i < count; ++i) {
      int target = nextInt(len - i);
      int l = map.getOrDefault(i, i);
      int r = map.getOrDefault(target, target);
      map.put(target, l);
      result[i] = r + startInclusive;
    }
    return result;
  }

  /**
   * 与えられた離散型確率変数に従う分布を持つ乱数を返す関数を生成します。
   * この時、与えられた確率分布の総和が1でない場合は総和が1になるように適当な係数を全体に掛けたものとして扱われます。
   * 実装はAlias methodに基づきます。
   * @param distribution 各{@code distribution[i]}について、{@code i}が返る確率
   * @return 与えられた離散型確率変数に従う分布を持つ乱数
   * @exception NullPointerException {@code distribution}が{@code null}の場合
   * @exception IllegalArgumentException {@code distribution[i] < 0}となる{@code i}が存在する場合、あるいは全ての{@code distribution[i] == 0}の場合
   */
  public java.util.function.IntSupplier IntGenerator(double[] distribution) {
    double[] dist = distribution.clone();
    final class Box {
      int second;
      double firstChoose;

      Box(int second, double firstChoose, double secondChoose) {
        this.second = second;
        this.firstChoose = firstChoose / (firstChoose + secondChoose);
      }

      int get(int index) {
        return nextDouble() < firstChoose ? index : second;
      }
    }
    int N = dist.length;
    Box[] box = new Box[N];
    double average = 0;
    for (double i : dist) average += i;
    if (average <= 0) throw new IllegalArgumentException("sum is lower than 0: " + average);
    average /= N;
    int[] doubleStack = new int[N];
    int minIndex = -1, maxIndex = N;
    for (int i = 0; i < dist.length; ++i) {
      if (dist[i] < 0) throw new IllegalArgumentException(i + "th value is less than 0: " + dist[i]);
      if (dist[i] <= average) doubleStack[++minIndex] = i;
      else doubleStack[--maxIndex] = i;
    }
    minIndex = 0;
    maxIndex = N - 1;
    while (minIndex <= maxIndex) {
      int min = doubleStack[minIndex++];
      int max = doubleStack[maxIndex];
      double firstChoose = dist[min];
      double secondChoose = average - firstChoose;
      dist[max] -= secondChoose;
      if (dist[max] <= average) {
        doubleStack[--minIndex] = max;
        --maxIndex;
      }
      box[min] = new Box(max, firstChoose, secondChoose);
    }

    int threshold = (Integer.MIN_VALUE - N) % N;
    return () -> {
      long random = next(31) * (long) N;
      int leftover = (int) (random & Integer.MAX_VALUE);
      if (leftover < N) {
        while (leftover < threshold) {
          random = next(31) * (long) N;
          leftover = (int) (random & Integer.MAX_VALUE);
        }
      }
      int index = (int) (random >>> 31);
      return box[index].get(index);
    };
  }

  @Override
  public long nextLong() {
    rand = rand ^ rand << 7;
    rand = rand ^ rand >>> 9;
    return rand;
  }

  /**
   * この乱数ジェネレータのシーケンスを使って、0から指定された値の範囲(0は含むが、その指定された値は含まない)で一様分布の{@code long}型の擬似乱数値を返します。
   * @param bound 上限(含まない)。正の値でなければならない
   * @return この乱数ジェネレータのシーケンスを使った、0(含む)から{@code bound}(含まない)の範囲で一様分布の、{@code long}型の次の擬似乱数値
   * @exception IllegalArgumentException {@code bound}が正でない場合
   */
  public long nextLong(long bound) {
    if (bound <= 0) throw new IllegalArgumentException(String.valueOf(bound));
    long maxUse = Long.MAX_VALUE / bound * bound;
    while (true) {
      long val = nextLong();
      if (val < maxUse) return val % bound;
    }
  }

  /**
   * <p>
   * 0以上{@code bound}未満の値を一様分布に従って生成する関数を返します。
   * 返された関数は、呼ぶ度に{@link #nextLong(bound)}を返します。
   * </p>
   * <p>
   * このメソッドによって生成される関数は{@code bound}の値に特化しています。
   * 従って、同じ{@code bound}を用いて複数回の乱数生成を行う場合、このメソッドを用いて生成された関数を用いた方が実行時間効率が良くなることがあります。
   * </p>
   * @param bound 上限(含まない)。正の値でなければならない
   * @return {@link #nextLong(bound)}を返す関数
   * @exception IllegalArgumentException {@code bound}が正でない場合
   */
  public java.util.function.LongSupplier LongGenerator(long bound) {
    if (bound <= 0) throw new IllegalArgumentException(String.valueOf(bound));
    long maxUse = Long.MAX_VALUE / bound * bound;
    return () -> {
      while (true) {
        long val = nextLong();
        if (val < maxUse) return val % bound;
      }
    };
  }

  /**
   * {@code startInclusive}以上{@code endExclusive}未満の値を一様分布に従って生成します。
   * @param startInclusive 下限
   * @param endExclusive 上限
   * @return {@code startInclusive}以上{@code endExclusive}未満の値
   * @exception IllegalArgumentException {@code startInclusive >= endExclusive}
   */
  public long nextLong(long startInclusive, long endExclusive) {
    if (startInclusive >= endExclusive)
      throw new IllegalArgumentException("range [" + startInclusive + ", " + endExclusive + ") is empty");
    return nextLong(endExclusive - startInclusive) + startInclusive;
  }

  /**
   * <p>
   * {@code startInclusive}以上{@code endExclusive}未満の値を一様分布に従って生成する関数を返します。
   * 返された関数は、呼ぶ度に{@link #nextLong(startInclusive, endExclusive)}を返します。
   * </p>
   * <p>
   * このメソッドによって生成される関数は入力値に特化しています。
   * 従って、同じ入力値を用いて複数回の乱数生成を行う場合、このメソッドを用いて生成された関数を用いた方が実行時間効率が良くなることがあります。
   * </p>
   * @param bound 上限(含まない)。正の値でなければならない
   * @return {@link #nextLong(startInclusive, endExclusive)}を返す関数
   * @exception IllegalArgumentException {@code startInclusive >= endExclusive}
   */
  public java.util.function.LongSupplier LongGenerator(long startInclusive, long endExclusive) {
    if (startInclusive >= endExclusive)
      throw new IllegalArgumentException("range [" + startInclusive + ", " + endExclusive + ") is empty");
    long bound = endExclusive - startInclusive;
    long maxUse = Long.MAX_VALUE / bound * bound;
    return () -> {
      while (true) {
        long val = nextLong();
        if (val < maxUse) return val % bound + startInclusive;
      }
    };
  }

  /**
   * {@code startInclusive}以上{@code endExclusive}未満の値を{@code count}個、一様分布に従って重複無しで生成します。
   * @param startInclusive 下限
   * @param endExclusive 上限
   * @param count 個数
   * @return {@code startInclusive}以上{@code endExclusive}未満の値が重複無しで{@code count}個入った配列
   * @exception IllegalArgumentException {@code endExclusive - startInclusive >= count}
   */
  public long[] nextLongs(long startInclusive, long endExclusive, int count) {
    if (endExclusive - startInclusive < count) throw new IllegalArgumentException(
        "number of integer in [" + startInclusive + ", " + endExclusive + ") is less than " + count);
    long len = endExclusive - startInclusive;
    long[] result = new long[count];
    java.util.HashMap<Long, Long> map = new java.util.HashMap<>();
    for (int i = 0; i < count; ++i) {
      long target = nextLong(len - i);
      long l = map.getOrDefault((long) i, (long) i);
      long r = map.getOrDefault(target, target);
      map.put(target, l);
      result[i] = r + startInclusive;
    }
    return result;
  }

  @Override
  public boolean nextBoolean() {
    rand = rand ^ rand << 7;
    rand = rand ^ rand >>> 9;
    return (rand & 1) != 0;
  }

  @Override
  public float nextFloat() {
    rand = rand ^ rand << 7;
    rand = rand ^ rand >>> 9;
    return (int) (rand & 0x00FFFFFF) * FLOAT_INV;
  }

  /**
   * この乱数ジェネレータのシーケンスを使って、0から指定された値の範囲(0は含むが、その指定された値は含まない)で一様分布の{@code float}型の擬似乱数値を返します。
   * 浮動小数点数の仕組み上、生成される乱数は一様分布に近い分布ではあるものの多少の誤差があることに注意してください。
   * @param bound 上限(含まない)。正の値でなければならない
   * @return この乱数ジェネレータのシーケンスを使った、0(含む)から{@code bound}(含まない)の範囲で一様分布の、{@code float}型の次の擬似乱数値
   * @exception IllegalArgumentException {@code bound}が正でない場合
   */
  public float nextFloat(float bound) {
    if (bound <= 0) throw new IllegalArgumentException(String.valueOf(bound));
    return nextFloat() * bound;
  }

  /**
   * {@code startInclusive}以上{@code endExclusive}未満の値を一様分布に従って生成します。
   * 浮動小数点数の仕組み上、生成される乱数は一様分布に近い分布ではあるものの多少の誤差があることに注意してください。
   * @param startInclusive 下限
   * @param endExclusive 上限
   * @return {@code startInclusive}以上{@code endExclusive}未満の値
   * @exception IllegalArgumentException {@code startInclusive >= endExclusive}
   */
  public float nextFloat(float startInclusive, float endExclusive) {
    if (startInclusive >= endExclusive)
      throw new IllegalArgumentException("range [" + startInclusive + ", " + endExclusive + ") is empty");
    float bound = endExclusive - startInclusive;
    return startInclusive + nextFloat() * bound;
  }

  @Override
  public double nextDouble() {
    rand = rand ^ rand << 7;
    rand = rand ^ rand >>> 9;
    return (rand & 0x001FFFFFFFFFFFFFL) * DOUBLE_INV;
  }

  /**
   * この乱数ジェネレータのシーケンスを使って、0から指定された値の範囲(0は含むが、その指定された値は含まない)で一様分布の{@code double}型の擬似乱数値を返します。
   * 浮動小数点数の仕組み上、生成される乱数は一様分布に近い分布ではあるものの多少の誤差があることに注意してください。
   * @param bound 上限(含まない)。正の値でなければならない
   * @return この乱数ジェネレータのシーケンスを使った、0(含む)から{@code bound}(含まない)の範囲で一様分布の、{@code double}型の次の擬似乱数値
   * @exception IllegalArgumentException {@code bound}が正でない場合
   */
  public double nextDouble(double bound) {
    if (bound <= 0) throw new IllegalArgumentException(String.valueOf(bound));
    return nextDouble() * bound;
  }

  /**
   * <p>
   * 0以上{@code bound}未満の値を一様分布に従って生成する関数を返します。
   * 返された関数は、呼ぶ度に{@link #nextDouble(bound)}を返します。
   * 浮動小数点数の仕組み上、生成される乱数は一様分布に近い分布ではあるものの多少の誤差があることに注意してください。
   * </p>
   * <p>
   * このメソッドによって生成される関数は{@code bound}の値に特化しています。
   * 従って、同じ{@code bound}を用いて複数回の乱数生成を行う場合、このメソッドを用いて生成された関数を用いた方が実行時間効率が良くなることがあります。
   * </p>
   * @param bound 上限(含まない)。正の値でなければならない
   * @return {@link #nextDouble(bound)}を返す関数
   * @exception IllegalArgumentException {@code bound}が正でない場合
   */
  public java.util.function.DoubleSupplier DoubleGenerator(double bound) {
    if (bound <= 0) throw new IllegalArgumentException(String.valueOf(bound));
    return () -> nextDouble() * bound;
  }

  /**
   * {@code startInclusive}以上{@code endExclusive}未満の値を一様分布に従って生成します。
   * 浮動小数点数の仕組み上、生成される乱数は一様分布に近い分布ではあるものの多少の誤差があることに注意してください。
   * @param startInclusive 下限
   * @param endExclusive 上限
   * @return {@code startInclusive}以上{@code endExclusive}未満の値
   * @exception IllegalArgumentException {@code startInclusive >= endExclusive}
   */
  public double nextDouble(double startInclusive, double endExclusive) {
    if (startInclusive >= endExclusive)
      throw new IllegalArgumentException("range [" + startInclusive + ", " + endExclusive + ") is empty");
    double bound = endExclusive - startInclusive;
    return startInclusive + nextDouble() * bound;
  }

  /**
   * <p>
   * {@code startInclusive}以上{@code endExclusive}未満の値を一様分布に従って生成する関数を返します。
   * 返された関数は、呼ぶ度に{@link #nextDouble(startInclusive, endExclusive)}を返します。
   * 浮動小数点数の仕組み上、生成される乱数は一様分布に近い分布ではあるものの多少の誤差があることに注意してください。
   * </p>
   * <p>
   * このメソッドによって生成される関数は入力値に特化しています。
   * 従って、同じ入力値を用いて複数回の乱数生成を行う場合、このメソッドを用いて生成された関数を用いた方が実行時間効率が良くなることがあります。
   * </p>
   * @param bound 上限(含まない)。正の値でなければならない
   * @return {@link #nextDouble(startInclusive, endExclusive)}を返す関数
   * @exception IllegalArgumentException {@code startInclusive >= endExclusive}
   */
  public java.util.function.DoubleSupplier DoubleGenerator(double startInclusive, double endExclusive) {
    if (startInclusive >= endExclusive)
      throw new IllegalArgumentException("range [" + startInclusive + ", " + endExclusive + ") is empty");
    double bound = endExclusive - startInclusive;
    return () -> startInclusive + nextDouble() * bound;
  }
}

このクラスの面白い点として、IntGeneratorなどのメソッドが挙げられます(あ、いけない。先頭小文字にするのを忘れてた……直さないと)。
このメソッドは乱数の生成する範囲などのルールを受け取ると、「呼び出すと指定された条件を満たす乱数を生成する関数」を返すメソッドです。
ここで、予め乱数の生成する範囲などを受け取った時に入力が適切な入力かなどの検査を行い、前計算をして高速化を行うことで、戻り値で返ってくる関数は非常に高速な状態にチューニングされています。
これにより、入力を検査するなどの必要な行為を達成しつつ高速化も達成できているのですね。

ライブラリを作る際に気を付けるべきこと

ここからは、良いライブラリを作る際に気を付けるべきことを書いていきます。

ライブラリを作る前に知っておきたい知識

命名規則に則る

殆どのプログラミング言語には、その言語ごとの命名規則というものがあるはずです。
例えばメソッド名は小文字から始めるとか、定数は全部大文字であるといった規則です。
Javaの場合は例えばこちらの記事が良くまとまっており、コーディング規約なども載っているので一度は目を通しておくと良いでしょう。

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

Amazon

標準ライブラリに何があるかを理解する

流石に、標準ライブラリにあるライブラリをもう一度開発するのはバカらしいですよね。
なので、予めどのようなライブラリがあるのか、どのように使えば良いのかをある程度知っておくことは大事です。
標準ライブラリは当然ですが命名規則なども守っているので、ある種ライブラリを作る際のお手本としても有用です。
というか、標準ライブラリもちゃんと理解していない人間が適当なコードを量産するのはちょっと……。

デザインパターンを知る

デザインパターンとは、巨大なコードを設計するためのノウハウに名前を付け、分かりやすくしたものです。
最初にデザインパターンが広まった本が「オブジェクト指向における再利用のためのデザインパターン」であることもあり、オブジェクト指向に必要なものと勘違いされることもありますが、別にオブジェクト指向に限らずデザインパターンを利用することはできます。

オブジェクト指向における再利用のためのデザインパターン

Amazon

デザインパターンは先人が苦労しながら設計を行ってきたノウハウが詰まったものであり、ライブラリ作りをしたいと思うなら……というより、コードを長く書いていきたいならどこかでは知っておくべき内容だと思います。

抽象代数を学ぶ

これは、人によっては少し意外に感じられるかもしれません。
しかし、プログラミングの世界は抽象代数の世界と密接に結びついており、汎用的なコードを書こうと思うとどうしても抽象代数の知識は必要になってきます。
例えば、総称型について正しく理解していますか？リスコフの置換原則が必要な理由を説明できますか？
これは、集合論の定義などを理解していれば十分に説明できるようになりますし、そうでなければ総称型を扱うことは困難を極めるでしょう。
他にも、例えばreduceはparallelStreamを使ったら高速だから常にparallelStreamを使うべきだ、という主張が正しいかどうか判断できますか？
これは群論の知識を持っていれば答えることができ、結合則の存在が必要であることを示せるでしょう。
標準ドキュメントも、プログラマがこの手の知識を身に付けていることを暗黙に仮定しているような文章は時々出現します(例えばObject::equalsは反射性や対称性など、集合の同値関係の話を理解していることが求められます)。
もちろん抽象代数の話は奥深いため全部を扱うことは困難ですが、ちょっとした定義や定理など、情報系の大学生が習う程度までは理解しておいた方が良いとは思います。

そのライブラリは必要か？

この見出しで悪いのですが、これの答えはシンプルです。すなわち、ライブラリを作りたいと思ったなら、それは必要だと言うことです。

え、この答えに納得できない？では理由を説明します。
まず、ライブラリを作る必要があるか否か、は費用対効果の話ですね。
ここでライブラリを使った時間などをペイできるなら、作った方が得なはずですから。
さて、まず費用の部分を考えましょう。

ライブラリを作る時には作りたい機能についてじっくり考察し、時には参考文献などを眺めるはずですが……そもそもそのライブラリを作りたいと思ったということは、今すぐ必要だからですよね？
ということは、例えライブラリを作らないとしてもやっぱりやらなきゃいけない作業なわけで、この部分でかかる時間は0です。
汎用化するために余計なドキュメントが増えたりもしますが、これも誤差です。というか必要になってから後から機能を変更したり増やしたりしても文句を言う相手はいないので、最初は最小限のライブラリを作れば良いんじゃないでしょうか。

一方、効果、つまりメリットについて考えます。
まず、ライブラリ化するということは設計などについて色々と理解するまで調べたはずで、その部分については十分に知識として身に付いたのではないかと思います。
更に、少なくともその部分はライブラリ化したいほど複雑な処理だったはずなので、もしバグを埋め込めば後々面倒なことになったはずの場所です。
そのデバッグ時間を未然に防げたことは、リスク回避の点ではかなり成果を挙げていると言えるでしょう。
最後に、これは共感する人も多いと思いますが……単純に、ライブラリが増えるのは楽しいです(よく盆栽に例えられますね)。
楽しいことをやってるのだから何の問題も無いですね！

とはいえ、明らかに楽しくないフェーズに入ったならそこでライブラリ化を終了し、後はその時々に応じた問題独自の処理を書いても良いんじゃないでしょうか。
特に、自動ユニットテストまで書き始めると時間がかなり溶けますが、これ個人開発でいる？とはなりがちですし……。

将来の自分が読んでも大丈夫？

大丈夫ではないです。いやマジで。
とはいえ、将来の自分に修正しといて～って負債を投げつけるのも悪くないので、@TODOとか@FIXMEとかドキュメント書いて投げつけるのも手ではあります。将来の自分の方が高い実力を持っているので。
じゃあ何を気を付けるべきかというと、コメントを書け！！！！！ということです。
コード内に適切にコメントがあり、メソッドごとに何の処理をしているかのドキュメントがあれば、将来読んでも困りませんよね？そういうことです。
というかライブラリじゃなくその場限りのコードでもコメントは書こう、例え競技プログラミングのような特殊環境でも書いてくれというお気持ちですね。

ライブラリとはサクラダファミリアである

何度も建設しなおそうね。
私のライブラリ群も既に10回以上、全書き換えが行われています。昔書いたコードだとどうしても抽象化などが荒くて、また書き直しが多発するのんな……。
逆に言うと、完璧なライブラリを作る必要はありません。
現時点の自身が出せる実力を出したライブラリであれば、いったんそのまま保存しちゃいましょう。
将来、そのライブラリを使おうとした未来の自分が仕様に文句を付けるようなら、未来の自分が書き直せば良いのです。

まとめ

なんか28000文字とかなってる、コードがデカすぎたか……。
さて、色々と書いてきましたが、言いたいことは以下に集約されます。

ライブラリを書く習慣を付けて欲しい
書くならより使いやすいライブラリを追い求めて欲しい

ライブラリを書くことは、ある種もっともプログラミングを理解する近道であると私は考えています。
もちろんやや遠回りではあるのですが、深い理解には必須……つまり、急がば回れという観点から見て最短かなと。
初心者の方ほど、むしろライブラリを作って残していくという風習が広がってくれたら嬉しいなーって私は私は思ったり。

あ、もしこういうライブラリを作りたいけどどう作れば良いのか分からない、とかは気軽に@CuriousFairy315で相談に乗りますよー。
自分も別に凄く設計が得意というわけではないですが、流石に何年もライブラリ整備を続けつつ抽象代数などの理解を深めていった経緯から、設計力は私に一日の長があるかなーとか思ったり。

おまけ: 直近のコンテストをコード長が長い順にソートしたもの。

明らかにコードが長すぎる、全提出者中ぶっちぎりの一位ってお前……(2番目の人のRustはバイナリ提出だったのでノーカウント)。
もちろん他のコンテストサイトだとコード長制限に引っ掛かるので、流石になんとかしないとねぇ。

情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

Colorful Tree Game

はじめに

Yukicoder No.2256 Step by Stepの別解

使いやすいライブラリの設計手法のお話

はじめに

作るべきライブラリとは？

機能・処理を提供する(ユーティリティクラス)

新たなデータ型を作る

新たな性質・振る舞いを提供する(インタフェースなど)

実際にライブラリの例を見てみる

ライブラリを作る際に気を付けるべきこと

ライブラリを作る前に知っておきたい知識

命名規則に則る

標準ライブラリに何があるかを理解する

デザインパターンを知る

抽象代数を学ぶ

そのライブラリは必要か？

将来の自分が読んでも大丈夫？

ライブラリとはサクラダファミリアである

まとめ

ICPC2020アジア横浜地区大会参加記

ICPC2020国内予選参加記

天下一 Game Battle Contest 2020 に参加しました！

#東方ゲームジャムに参加しました