Реализации трёх алгоритмов

Линейный

Реализация:

matrix-search-benchmark/src/main/java/dev/yawkar/algorithm/impl/LinearSearch.java

Lines 8 to 21 in 4dacc25

	public boolean search(long[][] array, long target) {
	int currentRow = 0;
	int currentColumn = array[0].length - 1;
	while (currentRow < array.length && currentColumn > -1) {
	if (array[currentRow][currentColumn] == target) {
	return true;
	} else if (array[currentRow][currentColumn] < target) {
	++currentRow;
	} else {
	--currentColumn;
	}
	}
	return false;
	}

Асимптотика: O(M+N), M x N

Бинарный

Реализация:

matrix-search-benchmark/src/main/java/dev/yawkar/algorithm/impl/BinaryOnRowLinearOnColumnSearch.java

Lines 5 to 34 in 4dacc25

	public class BinaryOnRowLinearOnColumnSearch implements SearchAlgorithm {
	private int firstLowerOrEqualTo(long target, int left, int right, long[] row) {
	while (right - left > 1) {
	int middle = (right + left) / 2;
	if (row[middle] > target) {
	right = middle;
	} else {
	left = middle;
	}
	}
	return right - 1;
	}
	@Override
	public boolean search(long[][] array, long target) {
	int currentRow = 0;
	int currentColumn = array[0].length - 1;
	while (currentRow < array.length && currentColumn > -1) {
	if (array[currentRow][currentColumn] == target) {
	return true;
	} else if (array[currentRow][currentColumn] < target) {
	++currentRow;
	} else {
	currentColumn = firstLowerOrEqualTo(target, -1, currentColumn, array[currentRow]);
	}
	}
	return false;
	}
	}

Асимптотика: O(Mlog(N)), M x N

Экспоненциальный + Бинарный

Реализация:

matrix-search-benchmark/src/main/java/dev/yawkar/algorithm/impl/ExpBinaryOnRowLinearOnColumnSearch.java

Lines 5 to 43 in 4dacc25

	public class ExpBinaryOnRowLinearOnColumnSearch implements SearchAlgorithm {
	private int firstLowerOrEqualTo(long target, int left, int right, long[] row) {
	while (right - left > 1) {
	int middle = (right + left) / 2;
	if (row[middle] > target) {
	right = middle;
	} else {
	left = middle;
	}
	}
	return right - 1;
	}
	@Override
	public boolean search(long[][] array, long target) {
	int currentRow = 0;
	int currentColumn = array[0].length - 1;
	while (currentRow < array.length && currentColumn > -1) {
	if (array[currentRow][currentColumn] == target) {
	return true;
	} else if (array[currentRow][currentColumn] < target) {
	++currentRow;
	} else {
	int exponentialAdjustment = 2;
	if (currentColumn > 32) {
	while (currentColumn >= exponentialAdjustment && array[currentRow][currentColumn - exponentialAdjustment] > target) {
	exponentialAdjustment <<= 1;
	}
	exponentialAdjustment >>= 1;
	} else {
	exponentialAdjustment = 0;
	}
	currentColumn = firstLowerOrEqualTo(target, -1, currentColumn - exponentialAdjustment, array[currentRow]);
	}
	}
	return false;
	}
	}

Асимптотика: ~O(Mlog(N)), M x N

Реализации двух генераций данных

Alpha matrix[i][j] = (N/M * i + j) * 2

Реализация:

matrix-search-benchmark/src/main/java/dev/yawkar/matrix/generator/AlphaGenerator.java

Lines 8 to 16 in ade5e61

	public long[][] generate(int rowsNumber, int columnsNumber) {
	long[][] matrix = new long[rowsNumber][columnsNumber];
	for (int i = 0; i < rowsNumber; ++i) {
	for (int j = 0; j < columnsNumber; ++j) {
	matrix[i][j] = ((long) columnsNumber / rowsNumber * i + j) * 2;
	}
	}
	return matrix;
	}

Beta matrix[i][j] = (N/M * i * j) * 2

Реализация:

matrix-search-benchmark/src/main/java/dev/yawkar/matrix/generator/BetaGenerator.java

Lines 8 to 16 in ade5e61

	public long[][] generate(int rowsNumber, int columnsNumber) {
	long[][] matrix = new long[rowsNumber][columnsNumber];
	for (int i = 0; i < rowsNumber; ++i) {
	for (int j = 0; j < columnsNumber; ++j) {
	matrix[i][j] = ((long) columnsNumber / rowsNumber * i * j) * 2;
	}
	}
	return matrix;
	}

Полученные замеры

Замеры производились с помощью Java Microbenchmark Harness: https://github.com/openjdk/jmh

matrix-search-benchmark/sample_results.txt

Lines 1 to 79 in fe2b4cc

	Benchmark (rowsNumber) Mode Cnt Score Error Units
	MatrixSearchBenchmark.alpha_binary 2 avgt 5 20.223 ± 4.435 ns/op
	MatrixSearchBenchmark.alpha_binary 4 avgt 5 122.347 ± 23.295 ns/op
	MatrixSearchBenchmark.alpha_binary 8 avgt 5 305.157 ± 47.870 ns/op
	MatrixSearchBenchmark.alpha_binary 16 avgt 5 706.069 ± 38.548 ns/op
	MatrixSearchBenchmark.alpha_binary 32 avgt 5 1484.815 ± 253.481 ns/op
	MatrixSearchBenchmark.alpha_binary 64 avgt 5 3375.647 ± 308.188 ns/op
	MatrixSearchBenchmark.alpha_binary 128 avgt 5 7375.769 ± 653.981 ns/op
	MatrixSearchBenchmark.alpha_binary 256 avgt 5 22225.095 ± 801.817 ns/op
	MatrixSearchBenchmark.alpha_binary 512 avgt 5 55331.355 ± 3919.791 ns/op
	MatrixSearchBenchmark.alpha_binary 1024 avgt 5 30112.431 ± 8398.054 ns/op
	MatrixSearchBenchmark.alpha_binary 2048 avgt 5 62791.996 ± 17826.088 ns/op
	MatrixSearchBenchmark.alpha_binary 4096 avgt 5 136733.040 ± 85220.420 ns/op
	MatrixSearchBenchmark.alpha_binary 8192 avgt 5 394865.869 ± 34207.710 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 2 avgt 5 49.478 ± 1.877 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 4 avgt 5 131.435 ± 9.716 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 8 avgt 5 317.395 ± 56.855 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 16 avgt 5 729.004 ± 82.494 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 32 avgt 5 1573.523 ± 173.617 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 64 avgt 5 3781.929 ± 351.963 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 128 avgt 5 8148.642 ± 590.290 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 256 avgt 5 21649.988 ± 2047.507 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 512 avgt 5 17884.274 ± 3945.974 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 1024 avgt 5 32241.698 ± 4974.021 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 2048 avgt 5 63650.111 ± 11983.455 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 4096 avgt 5 139897.384 ± 64328.703 ns/op
	MatrixSearchBenchmark.alpha_exp_binary 8192 avgt 5 216643.816 ± 71876.579 ns/op
	MatrixSearchBenchmark.alpha_linear 2 avgt 5 1376.068 ± 72.776 ns/op
	MatrixSearchBenchmark.alpha_linear 4 avgt 5 2069.051 ± 78.498 ns/op
	MatrixSearchBenchmark.alpha_linear 8 avgt 5 2456.726 ± 59.289 ns/op
	MatrixSearchBenchmark.alpha_linear 16 avgt 5 2680.719 ± 128.331 ns/op
	MatrixSearchBenchmark.alpha_linear 32 avgt 5 2762.400 ± 99.268 ns/op
	MatrixSearchBenchmark.alpha_linear 64 avgt 5 2890.716 ± 142.280 ns/op
	MatrixSearchBenchmark.alpha_linear 128 avgt 5 3247.413 ± 348.552 ns/op
	MatrixSearchBenchmark.alpha_linear 256 avgt 5 4160.621 ± 391.451 ns/op
	MatrixSearchBenchmark.alpha_linear 512 avgt 5 5548.951 ± 721.512 ns/op
	MatrixSearchBenchmark.alpha_linear 1024 avgt 5 11457.740 ± 607.021 ns/op
	MatrixSearchBenchmark.alpha_linear 2048 avgt 5 20059.945 ± 2285.555 ns/op
	MatrixSearchBenchmark.alpha_linear 4096 avgt 5 36730.647 ± 1796.882 ns/op
	MatrixSearchBenchmark.alpha_linear 8192 avgt 5 74679.633 ± 1921.657 ns/op
	MatrixSearchBenchmark.beta_binary 2 avgt 5 18.761 ± 0.304 ns/op
	MatrixSearchBenchmark.beta_binary 4 avgt 5 62.561 ± 3.050 ns/op
	MatrixSearchBenchmark.beta_binary 8 avgt 5 123.774 ± 6.854 ns/op
	MatrixSearchBenchmark.beta_binary 16 avgt 5 247.526 ± 18.959 ns/op
	MatrixSearchBenchmark.beta_binary 32 avgt 5 447.907 ± 29.982 ns/op
	MatrixSearchBenchmark.beta_binary 64 avgt 5 745.968 ± 102.114 ns/op
	MatrixSearchBenchmark.beta_binary 128 avgt 5 1312.202 ± 149.520 ns/op
	MatrixSearchBenchmark.beta_binary 256 avgt 5 1179.328 ± 80.373 ns/op
	MatrixSearchBenchmark.beta_binary 512 avgt 5 2532.209 ± 549.706 ns/op
	MatrixSearchBenchmark.beta_binary 1024 avgt 5 4118.879 ± 365.121 ns/op
	MatrixSearchBenchmark.beta_binary 2048 avgt 5 15465.168 ± 3024.496 ns/op
	MatrixSearchBenchmark.beta_binary 4096 avgt 5 29483.126 ± 5493.851 ns/op
	MatrixSearchBenchmark.beta_binary 8192 avgt 5 72203.307 ± 5601.930 ns/op
	MatrixSearchBenchmark.beta_exp_binary 2 avgt 5 28.658 ± 1.101 ns/op
	MatrixSearchBenchmark.beta_exp_binary 4 avgt 5 78.446 ± 2.085 ns/op
	MatrixSearchBenchmark.beta_exp_binary 8 avgt 5 136.910 ± 5.903 ns/op
	MatrixSearchBenchmark.beta_exp_binary 16 avgt 5 277.358 ± 18.593 ns/op
	MatrixSearchBenchmark.beta_exp_binary 32 avgt 5 488.765 ± 29.344 ns/op
	MatrixSearchBenchmark.beta_exp_binary 64 avgt 5 421.773 ± 7.445 ns/op
	MatrixSearchBenchmark.beta_exp_binary 128 avgt 5 740.423 ± 27.599 ns/op
	MatrixSearchBenchmark.beta_exp_binary 256 avgt 5 1442.732 ± 141.101 ns/op
	MatrixSearchBenchmark.beta_exp_binary 512 avgt 5 2666.027 ± 300.190 ns/op
	MatrixSearchBenchmark.beta_exp_binary 1024 avgt 5 4728.579 ± 1386.479 ns/op
	MatrixSearchBenchmark.beta_exp_binary 2048 avgt 5 14963.049 ± 2032.981 ns/op
	MatrixSearchBenchmark.beta_exp_binary 4096 avgt 5 30171.749 ± 5077.195 ns/op
	MatrixSearchBenchmark.beta_exp_binary 8192 avgt 5 73927.143 ± 3561.173 ns/op
	MatrixSearchBenchmark.beta_linear 2 avgt 5 2693.526 ± 85.919 ns/op
	MatrixSearchBenchmark.beta_linear 4 avgt 5 2727.058 ± 44.264 ns/op
	MatrixSearchBenchmark.beta_linear 8 avgt 5 2743.112 ± 55.085 ns/op
	MatrixSearchBenchmark.beta_linear 16 avgt 5 2746.235 ± 121.058 ns/op
	MatrixSearchBenchmark.beta_linear 32 avgt 5 2817.334 ± 82.586 ns/op
	MatrixSearchBenchmark.beta_linear 64 avgt 5 2892.852 ± 83.541 ns/op
	MatrixSearchBenchmark.beta_linear 128 avgt 5 3041.866 ± 123.016 ns/op
	MatrixSearchBenchmark.beta_linear 256 avgt 5 3510.579 ± 228.696 ns/op
	MatrixSearchBenchmark.beta_linear 512 avgt 5 4495.047 ± 199.751 ns/op
	MatrixSearchBenchmark.beta_linear 1024 avgt 5 6313.591 ± 785.150 ns/op
	MatrixSearchBenchmark.beta_linear 2048 avgt 5 15905.653 ± 2428.257 ns/op
	MatrixSearchBenchmark.beta_linear 4096 avgt 5 28545.084 ± 3467.570 ns/op
	MatrixSearchBenchmark.beta_linear 8192 avgt 5 71496.180 ± 3121.794 ns/op

Визуализация

Производительность на матрицах AlphaGenerator (Linear)

Производительность на матрицах AlphaGenerator (SemiLog)

Производительность на матрицах BetaGenerator (Linear)

Производительность на матрицах BetaGenerator (SemiLog)

Выводы

• Во всех тестовых случаях линейный алгоритм, ожидаемо, работает быстрее, за исключением лишь тестов матриц 2x8192, ..., 1024x8192, сгенерированных BetaGenerator (matrix[i][j] = (N/M * i * j) * 2)
  • Почему быстрее в большинстве случаев: у него минимальная константа и сама асимптотика в log раз меньше
  • Почему медленнее на вышеуказанных Beta матрицах: так как target = const = 16*N + 1 = 16 * 8192 + 1 = 131073 и числа, близкие к нему, находятся практически в начале второй строчки уже в матрице 2x8192, не говоря уже и о больших. Бинарный и экспоненциальный поиски быстрее приходят к началу, а линейный ещё должен успеть обойти ~8000 элементов, чтобы только дойти до начала второй строки
• На Alpha матрицах бинарный и экспоненциальный идут рука об руку вплоть до матрицы 4096x8192, на которой ситуация резко меняется. Бинарный начинает работать сильно хуже, чем экспоненциальный.
  • Почему так: всё просто - экспоненциальный растёт с этого момента уже только за счёт линейного спуска вниз, т.е. сам экспоненциальный поиск закончился, дальше все идёт линейно вниз (либо вырождается в бинарный на малых масштабах, см. реализацию экспоненциального+бинарного). А вот бинарный начинает буксовать, потому что постоянно двигается влево на 1, но тратя на это log(префикс текущей строки) операций, а спускается всё так же, как это делает эксп+бин