我正在对 Java 中迭代和递归二分搜索算法的性能进行基准测试，特别是测量不同数据集大小的执行时间和内存使用情况。但是，我在执行搜索算法期间遇到了准确测量内存使用情况的问题。
package backend;
import java.util.Arrays;
/**
* Benchmark for the performance of iterative and recursive binary search algorithms.
* It measures both execution time and memory usage for various dataset sizes.
*/
public class BinarySearchBenchmark {
private static final long[] EXTRA_ARRAY = new long[10_000_000];
static {
Arrays.fill(EXTRA_ARRAY, 1000);
}
/**
* The main method that runs the benchmarks for iterative and recursive binary search algorithms
* for different dataset sizes.
*
* @param args Command line arguments (not used)
*/
public static void main(String[] args) {
long[] dataset = new long[100_000];
for (long i = 0; i < dataset.length; i++) {
dataset[(int) i] = i;
}
long[] testSizes = {1_000, 5_000, 10_000, 25_000, 50_000, 100_000, 150_000, 200_000};
System.out.printf("%-15s %-20s %-20s %-20s %-20s%n",
"Input Size (n)", "Iterative Time (ms)", "Recursive Time (ms)",
"Iterative Memory (MB)", "Recursive Memory (MB)");
for (long size : testSizes) {
long[] subDataset = Arrays.copyOf(dataset, (int) size);
long iterativeTime = benchmark(() -> iterativeBinarySearch(subDataset, subDataset[(int) (size / 2)]));
long iterativeMemoryUsed = measureMemoryUsage(() -> iterativeBinarySearch(subDataset, subDataset[(int) (size / 2)]));
long recursiveTime = benchmark(() -> recursiveBinarySearch(subDataset, 0, (int) (subDataset.length - 1), subDataset[(int) (size / 2)]));
long recursiveMemoryUsed = measureMemoryUsage(() -> recursiveBinarySearch(subDataset, 0, (int) (subDataset.length - 1), subDataset[(int) (size / 2)]));
System.out.printf("%-15d %-20.2f %-20.2f %-20.2f %-20.2f%n",
size,
iterativeTime / 1_000_000.0,
recursiveTime / 1_000_000.0,
iterativeMemoryUsed / 1.0,
recursiveMemoryUsed / 1.0);
}
}
/**
* Performs the iterative binary search on the given array.
*
* @param array The array on which the search is performed
* @param target The target number to search for
*/
private static void iterativeBinarySearch(long[] array, long target) {
long low = 0, high = array.length - 1;
while (low <= high) {
long mid = low + (high - low) / 2;
if (array[(int) mid] == target) return;
if (array[(int) mid] < target) low = mid + 1;
else high = mid - 1;
}
}
/**
* Performs the recursive binary search on the given array.
*
* @param array The array on which the search is performed
* @param low The lowest index of the search range
* @param high The highest index of the search range
* @param target The target number to search for
* @return The index of the target number, or -1 if not found
*/
private static int recursiveBinarySearch(long[] array, long low, long high, long target) {
if (low > high) return -1;
long mid = low + (high - low) / 2;
if (array[(int) mid] == target) return (int) mid;
if (array[(int) mid] < target) return recursiveBinarySearch(array, mid + 1, high, target);
return recursiveBinarySearch(array, low, mid - 1, target);
}
/**
* Measures the time it takes to run the given search function.
*
* @param search The search function to measure
* @return The time in nanoseconds
*/
private static long benchmark(Runnable search) {
long startTime = System.nanoTime();
for (int i = 0; i < 100; i++) {
search.run();
}
return System.nanoTime() - startTime;
}
/**
* Measures the memory usage during the execution of the given search function.
*
* @param search The search function to measure
* @return The difference in memory usage in MB
*/
private static long measureMemoryUsage(Runnable search) {
System.gc();
try {
Thread.sleep(100);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
long beforeMemory = getUsedMemory();
search.run();
long afterMemory = getUsedMemory();
try {
Thread.sleep(100);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
return (afterMemory - beforeMemory) / (1024 * 1024);
}
/**
* Gets the used memory in the JVM in bytes.
*
* @return The used memory in bytes
*/
private static long getUsedMemory() {
return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
}
}
代码使用 System.gc() 触发垃圾收集，并使用 Thread.sleep(100) 来允许 GC 在测量内存使用情况之前完成其工作，但我不确定这是否准确捕获搜索算法使用的内存。此外，我正在测量运行搜索 100 次之前和之后的内存使用情况，但我不确定结果是否反映了算法的真实内存消耗。
以下是我正在使用的方法：
benchmark() - 通过运行 100 次来测量搜索算法的执行时间。 measureMemoryUsage() - 通过比较搜索算法执行之前和之后使用的内存来测量内存使用情况，并进行垃圾收集和短暂的暂停以使其完成。 问题：
如何提高 Java 中迭代和递归二分搜索算法的内存使用测量的准确性？有没有更可靠的方法来测量这些算法执行过程中的内存使用情况？
我尝试过的：
我使用 System.gc() 触发垃圾收集，并使用 Thread.sleep(100) 允许垃圾收集在测量内存使用情况之前完成。这是在搜索算法执行之前和之后完成的，以捕获内存差异。 我通过计算运行二分搜索 100 次之前和之后使用的内存之间的差异来测量内存使用情况，假设这将准确反映搜索算法消耗的内存。 我还在各种数据集大小上测试了迭代和递归二分搜索算法，并测量了执行时间和内存使用情况以进行比较。 我的期望：
我希望measureMemoryUsage()方法能够准确测量二分搜索算法执行期间的内存消耗。我希望看到不同数据集大小的迭代和递归实现之间的内存使用情况存在可靠的差异。结果将帮助我比较两种方法在时间和内存使用方面的效率。
import java.util.Arrays;
/**
* Benchmark for the performance of iterative and recursive binary search algorithms.
* It measures execution time and approximates memory usage for various dataset sizes.
*/
public class BinarySearchBenchmark {
/**
* The main method that runs the benchmarks for iterative and recursive binary search algorithms
* for different dataset sizes.
*
* @param args Command line arguments (not used)
*/
public static void main(String[] args) {
long[] dataset = new long[200_000];
for (long i = 0; i < dataset.length; i++) {
dataset[(int) i] = i;
}
long[] testSizes = {1_000_000, 2_000_000, 3_000_000, 4_000_000, 5_000_000, 6_000_000, 7_000_000, 8_000_000,
9_000_000, 10_000_000, 20_000_000, 30_000_000, 40_000_000, 50_000_000, 60_000_000,
70_000_000, 80_000_000, 90_000_000, 100_000_000, 200_000_000, 300_000_000,
400_000_000, 500_000_000, 600_000_000, 700_000_000, 800_000_000, 900_000_000,
1_000_000_000};
System.out.printf("%-15s %-20s %-20s %-20s %-20s%n",
"Input Size (n)", "Iterative Time (ns)", "Recursive Time (ns)",
"Iterative Memory (bytes)", "Recursive Memory (bytes)");
for (long size : testSizes) {
long[] subDataset = Arrays.copyOf(dataset, (int) size);
long target = subDataset[(int) (size / 2)];
long iterativeTime = benchmark(() -> iterativeBinarySearch(subDataset, target));
long iterativeMemoryUsed = measureIterativeMemoryUsage(subDataset);
long recursiveTime = benchmark(() -> recursiveBinarySearch(subDataset, 0, subDataset.length - 1, target));
long recursiveMemoryUsed = measureRecursiveMemoryUsage(subDataset);
System.out.printf("%-15d %-20d %-20d %-20d %-20d%n",
size,
iterativeTime,
recursiveTime,
iterativeMemoryUsed,
recursiveMemoryUsed);
}
}
/**
* Performs the iterative binary search on the given array.
*
* @param array The array on which the search is performed
* @param target The target number to search for
*/
private static void iterativeBinarySearch(long[] array, long target) {
long low = 0, high = array.length - 1;
while (low <= high) {
long mid = low + (high - low) / 2;
if (array[(int) mid] == target) return;
if (array[(int) mid] < target) low = mid + 1;
else high = mid - 1;
}
}
/**
* Performs the recursive binary search on the given array.
*
* @param array The array on which the search is performed
* @param low The lowest index of the search range
* @param high The highest index of the search range
* @param target The target number to search for
* @return The index of the target number, or -1 if not found
*/
private static int recursiveBinarySearch(long[] array, long low, long high, long target) {
if (low > high) return -1;
long mid = low + (high - low) / 2;
if (array[(int) mid] == target) return (int) mid;
if (array[(int) mid] < target) return recursiveBinarySearch(array, mid + 1, high, target);
return recursiveBinarySearch(array, low, mid - 1, target);
}
/**
* Measures the time it takes to run the given search function.
*
* @param search The search function to measure
* @return The time in nanoseconds
*/
private static long benchmark(Runnable search) {
long startTime = System.nanoTime();
for (int i = 0; i < 100; i++) {
search.run();
}
return System.nanoTime() - startTime;
}
/**
* Measures the memory usage during the execution of the given search function for the iterative binary search.
*
* @param array The array on which the search is performed
* @return The memory usage in bytes
*/
private static long measureIterativeMemoryUsage(long[] array) {
System.gc();
long beforeMemory = getUsedMemory();
iterativeBinarySearch(array, array[0]);
long afterMemory = getUsedMemory();
long arrayMemory = (long) array.length * Long.BYTES;
long overheadMemory = 3 * Long.BYTES;
return (afterMemory - beforeMemory) + arrayMemory + overheadMemory;
}
/**
* Measures the memory usage during the execution of the given search function for the recursive binary search.
*
* @param array The array on which the search is performed
* @return The memory usage in bytes
*/
private static long measureRecursiveMemoryUsage(long[] array) {
System.gc();
int depth = (int) (Math.log(array.length) / Math.log(2));
long stackMemoryPerFrame = 128;
return depth * stackMemoryPerFrame;
}
/**
* Gets the used memory in the JVM in bytes.
*
* @return The used memory in bytes
*/
private static long getUsedMemory() {
return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
}
}