最优中值函数

Question

我正在尝试使用一些代码来尝试回答并试图确保 compareTo 方法被调用的次数最少并最大限度地提高代码的效率和想出了这个：

// Flattens the results of a compareTo to -1, 0, 1
static int sign(int x) {
    return x < 0 ? -1 : x == 0 ? 0 : 1;
}

// Use an enum to help.
enum ABC {

    A() {

                @Override
                <T> T which(T a, T b, T c) {
                    return a;
                }

            },
    B() {

                @Override
                <T> T which(T a, T b, T c) {
                    return b;
                }

            },
    C() {

                @Override
                <T> T which(T a, T b, T c) {
                    return c;
                }

            },
    INSANE() {

                @Override
                <T> T which(T a, T b, T c) {
                    // Something like a < b and b < c but c < a
                    return null;
                }

            };

    abstract <T> T which(T a, T b, T c);
}

// Straight lookup.
private static final ABC[][][] median = {
    { // a < b
        { // b < c
            // a < c
            ABC.B,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.INSANE
        },
        { // b == c
            // a < c
            ABC.B,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.INSANE
        },
        { // b > c
            // a < c
            ABC.C,
            // a == c
            ABC.A,
            // a > c
            ABC.A
        }
    },
    { // a == b
        { // b < c
            // a < c
            ABC.B,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.INSANE
        },
        { // b == c
            // a < c
            ABC.INSANE,
            // a == c
            ABC.B,
            // a > c
            ABC.INSANE
        },
        { // b > c
            // a < c
            ABC.A,
            // a == c
            ABC.B,
            // a > c
            ABC.A
        }
    },
    { // a > b
        { // b < c
            // a < c
            ABC.A,
            // a == c
            ABC.A,
            // a > c
            ABC.C
        },
        { // b == c
            // a < c
            ABC.INSANE,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.B
        },
        { // b > c
            // a < c
            ABC.INSANE,
            // a == c
            ABC.INSANE,
            // a > c
            ABC.B
        }
    }
};

private static <T extends Comparable> T median(T a, T b, T c) {
    System.out.print(" ab=" + sign(a.compareTo(b)) + " bc=" + sign(b.compareTo(c)) + " ac=" + sign(a.compareTo(c)));
    // Least number of comparisons.
    return median[sign(a.compareTo(b)) + 1][sign(b.compareTo(c)) + 1][sign(a.compareTo(c)) + 1]
            .which(a, b, c);
}

// My test case.
private static <T extends Comparable> T median2(T a, T b, T c) {
    List<T> medianHelper = Arrays.asList(a, b, c);

    Collections.sort(medianHelper);

    return medianHelper.get(1);
}

public void test() {
    for (int a = -5; a <= 5; a += 5) {
        for (int b = -3; b <= 3; b += 3) {
            for (int c = -1; c <= 1; c++) {
                System.out.print("(" + a + "," + b + "," + c + ")");
                Integer m = median(a, b, c);
                Integer m2 = median2(a, b, c);
                System.out.print(" -> " + m + " & " + m2);
                if (m != m2) {
                    System.out.print(" <-- WRONG");
                }
                System.out.println();
            }

        }
    }
}

为了让它工作，我只是使用了 sort them and pick the middle one 技术并手动调整我的矩阵，直到它返回相同的结果。

虽然这似乎可行，但显然没有涵盖 compareTo 不稳定（例如 a < b && b < c && c < a）时的所有可能性，但我认为这不太重要。

有什么机制可以用来正确生成矩阵吗？理想情况下，也可以用于生成 min 和 max 矩阵。

Answer 1

我最终推出了自己的方法，从一个填充了 INSANE 的矩阵开始，并修复了所有与 sort and pick one 方法不匹配的地方。

这还需要一个 print 方法将矩阵打印为 Java 源。

// Flattens the results of a compareTo to -1, 0, 1
static int sign(int x) {
    return Integer.signum(x);
}

// Use an enum to help.
enum ABC {

    A() {

                @Override
                <T> T which(T a, T b, T c) {
                    return a;
                }

            },
    B() {

                @Override
                <T> T which(T a, T b, T c) {
                    return b;
                }

            },
    C() {

                @Override
                <T> T which(T a, T b, T c) {
                    return c;
                }

            },
    INSANE() {

                @Override
                <T> T which(T a, T b, T c) {
                    // Something like a < b and b < c but c < a
                    return null;
                }

            };

    abstract <T> T which(T a, T b, T c);
}

private static <T extends Comparable> T byLookup(ABC[][][] matrix, T a, T b, T c) {
    // Least number of comparisons.
    return matrix[sign(a.compareTo(b)) + 1][sign(b.compareTo(c)) + 1][sign(a.compareTo(c)) + 1]
            .which(a, b, c);
}

private static <T extends Comparable> T bySort(T a, T b, T c, int which) {
    // Sort and pick one.
    List<T> medianHelper = Arrays.asList(a, b, c);

    Collections.sort(medianHelper);

    return medianHelper.get(which);
}

private void checkMatrix(ABC[][][] matrix, int a, int b, int c, int which) {
    // Use the two functions.
    Integer m1 = byLookup(matrix, a, b, c);
    Integer m2 = bySort(a, b, c, which);
    if (!Objects.equal(m1, m2)) {
        // Wrong! Fix it.
        matrix[sign(Integer.compare(a, b)) + 1][sign(Integer.compare(b, c)) + 1][sign(Integer.compare(a, c)) + 1]
                = m2 == a ? ABC.A : m2 == b ? ABC.B : ABC.C;
    }
}

public void buildMatrix(String name, int which) {
    // All INSANE to start with.
    ABC[][][] matrix = new ABC[3][3][3];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            for (int k = 0; k < matrix[0][0].length; k++) {
                matrix[i][j][k] = ABC.INSANE;
            }
        }
    }
    // Test it.
    for (int a = -5; a <= 5; a += 5) {
        for (int b = -3; b <= 3; b += 3) {
            for (int c = -1; c <= 1; c++) {
                checkMatrix(matrix, a, b, c, which);
            }

        }
    }
    // Print it.
    printMatrixAsJava(name, matrix);
}

public void buildMatrices() {
    buildMatrix("min", 0);
    buildMatrix("median", 1);
    buildMatrix("max", 2);
}

static final String CR = "\r\n";

private void printMatrixAsJava(String name, ABC[][][] m) {
    StringBuilder s = new StringBuilder();
    String[] op = {"<", "=", ">"};
    s.append("private static final ABC[][][] ").append(name).append(" = {" + CR);
    for (int a = 0; a < 3; a++) {
        s.append("\t{ // a ").append(op[a]).append(" b" + CR);
        for (int b = 0; b < 3; b++) {
            //{ // b < c
            s.append("\t\t{ // b ").append(op[b]).append(" c" + CR);
            for (int c = 0; c < 3; c++) {
                //                // a < c
                //ABC.INSANE,

                s.append("\t\t\t// a ").append(op[c]).append(" c" + CR);
                s.append("\t\t\tABC.").append(m[a][b][c].name()).append("," + CR);
            }
            s.append("\t\t}," + CR);
        }
        s.append("\t}," + CR);
    }
    s.append("};" + CR);
    System.out.println(s);
}

这导致：

// The lookups generated by the above.
private static final ABC[][][] min = {
  { // a < b
    { // b < c
      // a < c
      ABC.A,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.INSANE,},
    { // b = c
      // a < c
      ABC.A,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.INSANE,},
    { // b > c
      // a < c
      ABC.A,
      // a = c
      ABC.A,
      // a > c
      ABC.C,},},
  { // a = b
    { // b < c
      // a < c
      ABC.A,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.INSANE,},
    { // b = c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.A,
      // a > c
      ABC.INSANE,},
    { // b > c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.C,},},
  { // a > b
    { // b < c
      // a < c
      ABC.B,
      // a = c
      ABC.B,
      // a > c
      ABC.B,},
    { // b = c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.B,},
    { // b > c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.C,},},};

private static final ABC[][][] median = {
  { // a < b
    { // b < c
      // a < c
      ABC.B,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.INSANE,},
    { // b = c
      // a < c
      ABC.B,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.INSANE,},
    { // b > c
      // a < c
      ABC.C,
      // a = c
      ABC.A,
      // a > c
      ABC.A,},},
  { // a = b
    { // b < c
      // a < c
      ABC.A,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.INSANE,},
    { // b = c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.A,
      // a > c
      ABC.INSANE,},
    { // b > c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.A,},},
  { // a > b
    { // b < c
      // a < c
      ABC.A,
      // a = c
      ABC.A,
      // a > c
      ABC.C,},
    { // b = c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.B,},
    { // b > c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.B,},},};

private static final ABC[][][] max = {
  { // a < b
    { // b < c
      // a < c
      ABC.C,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.INSANE,},
    { // b = c
      // a < c
      ABC.B,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.INSANE,},
    { // b > c
      // a < c
      ABC.B,
      // a = c
      ABC.B,
      // a > c
      ABC.B,},},
  { // a = b
    { // b < c
      // a < c
      ABC.C,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.INSANE,},
    { // b = c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.A,
      // a > c
      ABC.INSANE,},
    { // b > c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.A,},},
  { // a > b
    { // b < c
      // a < c
      ABC.C,
      // a = c
      ABC.A,
      // a > c
      ABC.A,},
    { // b = c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.A,},
    { // b > c
      // a < c
      ABC.INSANE,
      // a = c
      ABC.INSANE,
      // a > c
      ABC.A,},},};

我仍然对一种不那么奇怪的自我参照的方法感兴趣。

Answer 2

经过深思熟虑，我放弃了 table 查找技术，转而使用可证明是最佳的代码。

public static <T extends Comparable> T median(T a, T b, T c) {
  switch (Integer.signum(a.compareTo(b))) {
    case -1:
      // a < b
      switch (Integer.signum(b.compareTo(c))) {
        case -1:
          // b < c
          return b;

        case 0:
          // b = c - pick one.
          return b;

        case 1:
          // b > c
          return max(a, c);

        default:
          // Should never happen.
          return null;

      }

    case 0:
      // First two the same - median must be one of them - just pick one.
      return b;

    case 1:
      // a > b
      switch (Integer.signum(a.compareTo(c))) {
        case -1:
          // a < c
          return a;

        case 0:
          // a = c - pick one.
          return a;

        case 1:
          // a > c
          return max(b, c);

        default:
          // Should never happen.
          return null;

      }

    default:
      // Should never happen.
      return null;

  }
}

public static <T extends Comparable> T min(T a, T b, T c) {
  switch (Integer.signum(a.compareTo(b))) {
    case -1:
      // a < b
      return min(a, c);

    case 0:
      // a = b.
      return min(a, c);

    case 1:
      // a > b
      return min(b, c);

    default:
      return null;

  }
}

public static <T extends Comparable> T max(T a, T b, T c) {
  switch (Integer.signum(a.compareTo(b))) {
    case -1:
      // a < b
      return max(b, c);

    case 0:
      // a = b.
      return max(a, c);

    case 1:
      // a > b
      return max(a, c);

    default:
      return null;

  }
}

public static <T extends Comparable> T min(T a, T b) {
  switch (Integer.signum(a.compareTo(b))) {
    case -1:
      // a < b
      return a;

    case 0:
      // Same - just pick one.
      return b;

    case 1:
      // a > b
      return b;

    default:
      return null;

  }
}

public static <T extends Comparable> T max(T a, T b) {
  switch (Integer.signum(a.compareTo(b))) {
    case -1:
      // a < b
      return b;

    case 0:
      // Same - just pick one.
      return b;

    case 1:
      // a > b
      return a;

    default:
      return null;

  }
}

private static void test(int a, int b, int c, String results) {
  boolean ok = false;
  int m = median(a, b, c);
  for (int i = 0; i < results.length(); i++) {
    switch (results.charAt(i)) {
      case 'A':
        if (m == a) {
          ok = true;
        }
        break;
      case 'B':
        if (m == b) {
          ok = true;
        }
        break;
      case 'C':
        if (m == c) {
          ok = true;
        }
        break;
    }
  }
  if (!ok) {
    System.out.println("Failed median(" + a + "," + b + "," + c + ") = " + m);
  }
}

public static void main(String args[]) {
  try {
    test(0, 0, 0, "ABC");
    test(0, 0, 1, "AB");
    test(0, 1, 0, "AC");
    test(1, 0, 0, "BC");
    test(1, 1, 0, "AB");
    test(1, 0, 1, "AC");
    test(0, 1, 1, "BC");
    test(0, 1, 2, "B");
    test(0, 2, 1, "C");
    test(1, 0, 2, "A");
    test(1, 2, 0, "A");
    test(2, 1, 0, "B");
    test(2, 0, 1, "C");
  } catch (Throwable t) {
    t.printStackTrace(System.err);
  }
}

Answer 3

如果你只想调用 compareTo 3 次（我不认为你可以调用 2 次），为什么不使用简单的嵌套 if/else:

public static <T extends Comparable> T median(T a, T b, T c) {
  if (a.compareTo(b) <= 0) {
    if (a.compareTo(c) <= 0) {
      return b.compareTo(c) <= 0 ? b : c; //a <= b && a <= c, return min(b, c)
    } else {
      return a;  //c < a <= b, return a
    }
  } else { // b < a
    if (a.compareTo(c) <= 0) {
      return a; // b < a <= c, return a
    } else {
      return b.compareTo(c) <= 0 ? c : b; //b < a && a > c, return max(b, c)
    }
  }
}

最优中值函数

Optimal median function

java

comparable