java - libreria - ¿Por qué Arrays.binarySearch no está mejorando el rendimiento en comparación con recorrer la matriz?

como usar binarysearch java

Question

Di una oportunidad para resolver el problema de programación de los transmisores de radio de Hackerland .

Para resumir, el desafío es el siguiente:

Hackerland es una ciudad unidimensional con n casas, donde cada casa i está ubicada en alguna x _i en el eje x. El alcalde quiere instalar transmisores de radio en los techos de las casas de la ciudad. Cada transmisor tiene un rango, k , lo que significa que puede transmitir una señal a todas las casas ≤ k unidades de distancia.

Dado un mapa de Hackerland y el valor de k , ¿puede encontrar el número mínimo de transmisores necesarios para cubrir cada casa?

Mi implementación es la siguiente:

package biz.tugay;
import java.util.*;
public class HackerlandRadioTransmitters {
public static int minNumOfTransmitters(int[] houseLocations, int transmitterRange) {
// Sort and remove duplicates..
houseLocations = uniqueHouseLocationsSorted(houseLocations);
int towerCount = 0;
for (int nextHouseNotCovered = 0; nextHouseNotCovered < houseLocations.length; ) {
final int towerLocation = HackerlandRadioTransmitters.findNextTowerIndex(houseLocations, nextHouseNotCovered, transmitterRange);
towerCount++;
nextHouseNotCovered = HackerlandRadioTransmitters.nextHouseNotCoveredIndex(houseLocations, towerLocation, transmitterRange);
if (nextHouseNotCovered == -1) {
break;
}
}
return towerCount;
}
public static int findNextTowerIndex(final int[] houseLocations, final int houseNotCoveredIndex, final int transmitterRange) {
final int houseLocationWeWantToCover = houseLocations[houseNotCoveredIndex];
final int farthestHouseLocationAllowed = houseLocationWeWantToCover + transmitterRange;
int towerIndex = houseNotCoveredIndex;
int loop = 0;
while (true) {
loop++;
if (towerIndex == houseLocations.length - 1) {
break;
}
if (farthestHouseLocationAllowed >= houseLocations[towerIndex + 1]) {
towerIndex++;
continue;
}
break;
}
System.out.println("findNextTowerIndex looped : " + loop);
return towerIndex;
}
public static int nextHouseNotCoveredIndex(final int[] houseLocations, final int towerIndex, final int transmitterRange) {
final int towerCoversUntil = houseLocations[towerIndex] + transmitterRange;
int notCoveredHouseIndex = towerIndex + 1;
int loop = 0;
while (notCoveredHouseIndex < houseLocations.length) {
loop++;
final int locationOfHouseBeingChecked = houseLocations[notCoveredHouseIndex];
if (locationOfHouseBeingChecked > towerCoversUntil) {
break; // Tower does not cover the house anymore, break the loop..
}
notCoveredHouseIndex++;
}
if (notCoveredHouseIndex == houseLocations.length) {
notCoveredHouseIndex = -1;
}
System.out.println("nextHouseNotCoveredIndex looped : " + loop);
return notCoveredHouseIndex;
}
public static int[] uniqueHouseLocationsSorted(final int[] houseLocations) {
Arrays.sort(houseLocations);
final HashSet<Integer> integers = new HashSet<>();
final int[] houseLocationsUnique = new int[houseLocations.length];
int innerCounter = 0;
for (int houseLocation : houseLocations) {
if (integers.contains(houseLocation)) {
continue;
}
houseLocationsUnique[innerCounter] = houseLocation;
integers.add(houseLocationsUnique[innerCounter]);
innerCounter++;
}
return Arrays.copyOf(houseLocationsUnique, innerCounter);
}
}

Estoy bastante seguro de que esta implementación es correcta. Pero vea los detalles en las funciones: findNextTowerIndex y nextHouseNotCoveredIndex : ¡recorren el array uno por uno!

Una de mis pruebas es la siguiente:

static void test_01() throws FileNotFoundException {
final long start = System.currentTimeMillis();
final File file = new File("input.txt");
final Scanner scanner = new Scanner(file);
int[] houseLocations = new int[73382];
for (int counter = 0; counter < 73382; counter++) {
houseLocations[counter] = scanner.nextInt();
}
final int[] uniqueHouseLocationsSorted = HackerlandRadioTransmitters.uniqueHouseLocationsSorted(houseLocations);
final int minNumOfTransmitters = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, 73381);
assert minNumOfTransmitters == 1;
final long end = System.currentTimeMillis();
System.out.println("Took: " + (end - start) + " milliseconds..");
}

donde input.txt se puede descargar desde here . (No es el detalle más importante en esta pregunta, pero aún así ...) Así que tenemos un conjunto de 73382 casas, y configuro deliberadamente el rango del transmisor, así que los métodos que hago sonar mucho:

Aquí hay un ejemplo de salida de esta prueba en mi máquina:

findNextTowerIndex looped : 38213
nextHouseNotCoveredIndex looped : 13785
Took: 359 milliseconds..

También tengo esta prueba, que no afirma nada, sino que solo mantiene el tiempo:

static void test_02() throws FileNotFoundException {
final long start = System.currentTimeMillis();
for (int i = 0; i < 400; i ++) {
final File file = new File("input.txt");
final Scanner scanner = new Scanner(file);
int[] houseLocations = new int[73382];
for (int counter = 0; counter < 73382; counter++) {
houseLocations[counter] = scanner.nextInt();
}
final int[] uniqueHouseLocationsSorted = HackerlandRadioTransmitters.uniqueHouseLocationsSorted(houseLocations);
final int transmitterRange = ThreadLocalRandom.current().nextInt(1, 70000);
final int minNumOfTransmitters = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
}
final long end = System.currentTimeMillis();
System.out.println("Took: " + (end - start) + " milliseconds..");
}

donde creo aleatoriamente 400 rangos de transmisores y ejecuto el programa 400 veces ... Obtendré los tiempos de ejecución de la siguiente manera en mi máquina ...

Took: 20149 milliseconds..

Así que ahora, dije, ¿por qué no uso la búsqueda binaria en lugar de recorrer la matriz y cambié mis implementaciones de la siguiente manera?

public static int findNextTowerIndex(final int[] houseLocations, final int houseNotCoveredIndex, final int transmitterRange) {
final int houseLocationWeWantToCover = houseLocations[houseNotCoveredIndex];
final int farthestHouseLocationAllowed = houseLocationWeWantToCover + transmitterRange;
int nextTowerIndex = Arrays.binarySearch(houseLocations, 0, houseLocations.length, farthestHouseLocationAllowed);
if (nextTowerIndex < 0) {
nextTowerIndex = -nextTowerIndex;
nextTowerIndex = nextTowerIndex -2;
}
return nextTowerIndex;
}
public static int nextHouseNotCoveredIndex(final int[] houseLocations, final int towerIndex, final int transmitterRange) {
final int towerCoversUntil = houseLocations[towerIndex] + transmitterRange;
int nextHouseNotCoveredIndex = Arrays.binarySearch(houseLocations, 0, houseLocations.length, towerCoversUntil);
if (-nextHouseNotCoveredIndex > houseLocations.length) {
return -1;
}
if (nextHouseNotCoveredIndex < 0) {
nextHouseNotCoveredIndex = - (nextHouseNotCoveredIndex + 1);
return nextHouseNotCoveredIndex;
}
return nextHouseNotCoveredIndex + 1;
}

y estoy esperando un gran aumento en el rendimiento, ya que ahora lo haré en la mayoría de los bucles para registrar (N) veces, en lugar de O (N). Por lo tanto, las salidas de prueba_01:

Took: 297 milliseconds..

Recuerda, se tardó: 359 milisegundos .. antes. Y para test_02:

Took: 18047 milliseconds..

Por lo tanto, siempre obtengo valores de alrededor de 20 segundos con la implementación de desplazamiento de matriz y de 18 a 19 segundos para la implementación de búsqueda binaria.

Esperaba un aumento de rendimiento mucho mejor con Arrays.binarySearch pero obviamente no es el caso, ¿por qué es esto? ¿Qué me estoy perdiendo? ¿Necesito una matriz con más de 73382 para ver el beneficio, o es irrelevante?

Edición # 01

Después del comentario de @huck_cussler, intenté duplicar y triplicar el conjunto de datos que tengo (con números aleatorios) e intenté ejecutar test02 (por supuesto, triplicando los tamaños de matriz en la prueba en sí misma). Para la implementación lineal los tiempos van así:

Took: 18789 milliseconds..
Took: 34396 milliseconds..
Took: 53504 milliseconds..

Para la implementación de búsqueda binaria, obtuve los siguientes valores:

Took: 18644 milliseconds..
Took: 33831 milliseconds..
Took: 52886 milliseconds..

Answer 1

De acuerdo con otras respuestas, el tiempo de E / S es el mayor problema, y ​​la clasificación es la segunda, la búsqueda es la última vez que el consumidor.

Y, de acuerdo con el ejemplo de phatfingers, la búsqueda binaria en algún momento es peor que la búsqueda lineal en su problema porque la búsqueda totalmente lineal pasa un bucle por cada elemento ( n veces se compara) pero la búsqueda binaria se ejecuta en tiempos de torre ( O(logn)*#tower) ), una sugerencia es que la búsqueda binaria no comienza desde 0, sino desde la ubicación actual

 int nextTowerIndex = Arrays.binarySearch(houseLocations, houseNotCoveredIndex+1, houseLocations.length, arthestHouseLocationAllowed)

entonces debería O(logn)*#tower/2) Incluso más, quizás pueda calcular cada torre que cubre la avg casas y luego, primero, comparar las casas de avg y luego comenzar la búsqueda binaria desde houseNotCoveredIndex + avg + 1 , pero no está seguro de que el rendimiento sea mucho mejor.

ps: clasifica y único puedes usar TreeSet como

public static int[] uniqueHouseLocationsSorted(final int[] houseLocations) {
final Set<Integer> integers = new TreeSet<>();
for (int houseLocation : houseLocations) {
integers.add(houseLocation);
}
int[] unique = new int[integers.size()];
int i = 0;
for(Integer loc : integers){
unique[i] = loc;
i++;
}
return unique;
}

Answer 2

En su medición de tiempo, incluye operaciones que son mucho más lentas que la búsqueda de matrices. Es decir, la E / S del sistema de archivos y la clasificación de matrices. La E / S en general (lectura / escritura desde el sistema de archivos, comunicación de red) es por órdenes de magnitud más lenta que las operaciones que involucran solo el acceso a la CPU y la RAM.

Reescribamos su prueba de una manera que no lea el archivo en cada iteración de bucle:

static void test_02() throws FileNotFoundException {
final File file = new File("input.txt");
final Scanner scanner = new Scanner(file);
int[] houseLocations = new int[73382];
for (int counter = 0; counter < 73382; counter++) {
houseLocations[counter] = scanner.nextInt();
}
scanner.close();
final int rounds = 400;
final int[] uniqueHouseLocationsSorted = uniqueHouseLocationsSorted(houseLocations);
final int transmitterRange = 73381;
final long start = System.currentTimeMillis();
for (int i = 0; i < rounds; i++) {
final int minNumOfTransmitters = minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
}
final long end = System.currentTimeMillis();
System.out.println("Took: " + (end - start) + " milliseconds..");
}

Observe en esta versión de la prueba que el archivo se lee solo una vez y luego comienza la medición de tiempo. Con lo anterior, obtengo Took: 1700 milliseconds.. (más o menos unos pocos milis) tanto para la versión iterativa como para la búsqueda binaria. Así que todavía no podemos ver que la búsqueda binaria es más rápida. Esto se debe a que casi todo ese tiempo se usa para ordenar la matriz 400 veces.

Ahora eliminemos la línea que ordena la matriz de entrada del método minNumOfTransmitters . Ordenamos la matriz (una vez) de todos modos al comienzo de la prueba.

Ahora podemos ver que las cosas son mucho más rápidas. Después de eliminar la línea houseLocations = uniqueHouseLocationsSorted(houseLocations) de minNumOfTransmitters , recibo: Took: 68 milliseconds.. para la versión iterativa. Claramente, dado que esta duración ya es muy pequeña, no veremos una diferencia significativa con la versión de búsqueda binaria.

Así que vamos a aumentar el número de rondas de bucle a: 100000 .
Ahora tengo Took: 2121 milliseconds.. para la versión iterativa y Took: 36 milliseconds.. para la versión de búsqueda binaria.

Debido a que ahora aislamos lo que medimos y nos enfocamos en las búsquedas de matriz, en lugar de incluir operaciones que son mucho más lentas, podemos notar la gran diferencia en el rendimiento (para mejor) de la búsqueda binaria.

Si desea ver cuántas veces la búsqueda binaria ingresa en su ciclo while, puede implementarla usted mismo y agregar un contador:

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;
int loop = 0;
while (low <= high) {
loop++;
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key) {
low = mid + 1;
} else if (midVal > key) {
high = mid - 1;
} else {
return mid; // key found
}
}
System.out.println("binary search looped " + loop + " times");
return -(low + 1); // key not found.
}

El método se copia de la clase Arrays en el JDK. Acabo de agregar el contador de bucles y la impresión.
Cuando la longitud de la matriz a buscar es 73382, el bucle entra solo 16 veces. Eso es exactamente lo que esperamos: log(73382) =~ 16 .

Answer 3

Estoy de acuerdo con otras respuestas en que el principal problema con sus pruebas es que miden cosas incorrectas: IO y clasificación. Pero no creo que las pruebas sugeridas sean buenas. Mi sugerencia es la siguiente:

static void test_02() throws FileNotFoundException {
final File file = new File("43620487.txt");
final Scanner scanner = new Scanner(file);
int[] houseLocations = new int[73382];
for (int counter = 0; counter < 73382; counter++) {
houseLocations[counter] = scanner.nextInt();
}
final int[] uniqueHouseLocationsSorted = uniqueHouseLocationsSorted(houseLocations);
final Random random = new Random(0); // fixed seed to have the same sequences in all tests
long sum = 0;
// warm up
for (int i = 0; i < 100; i++) {
final int transmitterRange = random.nextInt(70000) + 1;
final int minNumOfTransmitters = minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
sum += minNumOfTransmitters;
}
// actual measure
final long start = System.currentTimeMillis();
for (int i = 0; i < 4000; i++) {
final int transmitterRange = random.nextInt(70000) + 1;
final int minNumOfTransmitters = minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
sum += minNumOfTransmitters;
}
final long end = System.currentTimeMillis();
System.out.println("Took: " + (end - start) + " milliseconds. Sum = " + sum);
}

Tenga en cuenta también que findNextTowerIndex todas las llamadas de System.out.println de findNextTowerIndex y nextHouseNotCoveredIndex y uniqueHouseLocationsSorted call de minNumOfTransmitters ya que también afectan las pruebas de rendimiento.

Entonces, lo que creo que es importante aquí:

1. Mueva todas las E / S y ordene fuera del ciclo de medición
2. Realizar un calentamiento fuera de la medida.
3. Usa la misma secuencia aleatoria para todas las mediciones
4. No deseche el resultado del cálculo, por lo que JIT no puede optimizar esa llamada por completo

Con tal prueba, veo una diferencia de 10 veces en mi máquina: alrededor de 80 ms frente a 8 ms.

Y si realmente desea hacer pruebas de rendimiento en Java, debería considerar el uso de JMH, también conocido como Java Microbenchmark Harness

Answer 4

Su tiempo incluye la recuperación de datos de su disco duro. Esto podría estar tomando la mayoría de su tiempo de ejecución. Omita la carga de datos de su tiempo para obtener una comparación más precisa de sus dos enfoques. Imagínese si toma 18 segundos y está comparando 18.644 vs 18.789 (mejora del 0.77%) en lugar de 0.644 vs 0.789 (mejora del 18.38%).

Si tiene una operación lineal O (n), como cargar una estructura binaria, y la combina con una búsqueda binaria O (log n), termina con O (n). Si confía en la notación Big O, debe esperar que O (n + log n) no sea significativamente diferente de O (2 * n), ya que ambos se reducen a O (n).

Además, una búsqueda binaria puede funcionar mejor o peor que una búsqueda lineal dependiendo de la densidad de casas entre torres. Considere, digamos 1024 casas con una torre distribuida uniformemente cada 4 casas. Una búsqueda lineal pasará 4 veces por torre, mientras que una búsqueda binaria tomará log2 (1024) = 10 pasos por torre.

Una cosa más ... su método minNumOfTransmitters es ordenar la matriz ya ordenada que se le pasa desde test_01 y test_02 . Ese paso de recurso lleva más tiempo que sus propias búsquedas, lo que oculta aún más las diferencias de tiempo entre sus dos algoritmos de búsqueda.

======

Creé una pequeña clase de tiempo para dar una mejor idea de lo que está sucediendo. He eliminado la línea de código de minNumOfTransmitters para evitar que vuelva a ejecutar el ordenamiento, y agregué un parámetro booleano para seleccionar si usar su versión binaria. Totaliza la suma de los tiempos para 400 iteraciones, separando cada paso. Los resultados en mi sistema ilustran que el tiempo de carga empequeñece el tiempo de clasificación, que a su vez empequeñece el tiempo de resolución.

 Load: 22.565s
Sort: 4.518s
Linear: 0.012s
Binary: 0.003s

Es fácil ver cómo optimizar ese último paso no hace mucha diferencia en el tiempo de ejecución general.

private static class Timing {
public long load=0;
public long sort=0;
public long solve1=0;
public long solve2=0;
private String secs(long millis) {
return String.format("%3d.%03ds", millis/1000, millis%1000);
}
public String toString() {
return " Load: " + secs(load) + "/n Sort: " + secs(sort) + "/nLinear: " + secs(solve1) + "/nBinary: " + secs(solve2);
}
public void add(Timing timing) {
load+=timing.load;
sort+=timing.sort;
solve1+=timing.solve1;
solve2+=timing.solve2;
}
}
static Timing test_01() throws FileNotFoundException {
Timing timing=new Timing();
long start = System.currentTimeMillis();
final File file = new File("c://path//to//xnpwdiG3.txt");
final Scanner scanner = new Scanner(file);
int[] houseLocations = new int[73382];
for (int counter = 0; counter < 73382; counter++) {
houseLocations[counter] = scanner.nextInt();
}
timing.load+=System.currentTimeMillis()-start;
start=System.currentTimeMillis();
final int[] uniqueHouseLocationsSorted = HackerlandRadioTransmitters.uniqueHouseLocationsSorted(houseLocations);
timing.sort=System.currentTimeMillis()-start;
start=System.currentTimeMillis();
final int minNumOfTransmitters = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, 73381, false);
timing.solve1=System.currentTimeMillis()-start;
start=System.currentTimeMillis();
final int minNumOfTransmittersBin = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, 73381, true);
timing.solve2=System.currentTimeMillis()-start;
final long end = System.currentTimeMillis();
return timing;
}

Answer 5

uniqueHouseLocationsSorted no es eficiente, y la solución parece mejor, pero creo que esto podría mejorar el tiempo empleado (tenga en cuenta que no probé el código):

public static int[] uniqueHouseLocationsSorted(final int[] houseLocations) {
int size = houseLocations.length;
if (size == 0) return null; // you have to check for null later or maybe throw an exception here
Arrays.sort(houseLocations);
final int[] houseLocationsUnique = new int[size];
int previous = houseLocationsUnique[0] = houseLocations[0];
int innerCounter = 1;
for (int i = 1; i < size; i++) {
int houseLocation = houseLocations[i];
if (houseLocation == previous) continue; // since elements are sorted this is faster
previous = houseLocationsUnique[innerCounter++] = houseLocation;
}
return Arrays.copyOf(houseLocationsUnique, innerCounter);
}

Considere también usar una lista de Arreglos, ya que copiar el arreglo lleva tiempo.