Wie kann die Speichernutzung für iterative und rekursive binäre Suchalgorithmen in Java genau gemessen werden? ⇐ Java

[Anonymous]

Ich bewerte die Leistung iterativer und rekursiver binärer Suchalgorithmen in Java und messe dabei insbesondere sowohl die Ausführungszeit als auch die Speichernutzung für verschiedene Datensatzgrößen. Allerdings stoße ich bei der genauen Messung der Speichernutzung während der Ausführung der Suchalgorithmen auf Probleme.
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) 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();
}
}

Der Code verwendet System.gc(), um die Speicherbereinigung auszulösen, und Thread.sleep(100), damit GC seine Arbeit abschließen kann, bevor die Speichernutzung gemessen wird. Ich bin mir jedoch nicht sicher, ob dies korrekt ist Erfassen des von den Suchalgorithmen verwendeten Speichers. Darüber hinaus messe ich die Speichernutzung vor und nach 100-maliger Ausführung der Suche, bin mir aber nicht sicher, ob die Ergebnisse den tatsächlichen Speicherverbrauch der Algorithmen widerspiegeln.
Hier sind die Methoden, die ich verwende :
benchmark() – Misst die Ausführungszeit der Suchalgorithmen durch 100-maliges Ausführen.
measureMemoryUsage() – Misst die Speichernutzung durch Vergleich des verwendeten Speichers vor und nach der Suche Algorithmusausführung, mit Müll Sammlung und eine kurze Pause, um sie abzuschließen.
Frage:
Wie kann ich die Genauigkeit der Speichernutzungsmessung für die iterativen und rekursiven binären Suchalgorithmen in Java verbessern? Gibt es eine zuverlässigere Möglichkeit, die Speichernutzung während der Ausführung dieser Algorithmen zu messen?
Was ich versucht habe:
Ich habe System.gc() verwendet um die Garbage Collection auszulösen und Thread.sleep(100), um den Abschluss der Garbage Collection vor der Messung der Speichernutzung zu ermöglichen. Dies wurde sowohl vor als auch nach der Ausführung des Suchalgorithmus durchgeführt, um die Speicherdifferenz zu erfassen.
Ich habe die Speichernutzung gemessen, indem ich die Differenz zwischen dem verwendeten Speicher vor und nach 100-maliger Ausführung der binären Suche berechnet habe, in der Annahme, dass dies genau widerspiegeln würde Von den Suchalgorithmen verbrauchter Speicher.
Ich habe außerdem sowohl iterative als auch rekursive binäre Suchalgorithmen an verschiedenen Datensatzgrößen getestet und zum Vergleich sowohl die Ausführungszeit als auch die Speichernutzung gemessen.
Was ich erwartet habe:
I erwartete, dass die Methode „measureMemoryUsage()“ eine genaue Messung des Speicherverbrauchs während der Ausführung der binären Suchalgorithmen liefert. Ich hoffte, einen zuverlässigen Unterschied in der Speichernutzung zwischen den iterativen und rekursiven Implementierungen für verschiedene Datensatzgrößen zu sehen. Die Ergebnisse würden mir dann helfen, die Effizienz der beiden Ansätze hinsichtlich Zeit und Speicherverbrauch zu vergleichen.