Pourquoi Arrays.binarySearch n'améliore-t-il pas les performances par rapport à la recherche dans le tableau ?

Question

J'ai essayé de résoudre le problème Défi de programmation des émetteurs radio de Hackerland .

Pour résumer, le défi est le suivant :

Hackerland est une ville unidimensionnelle avec n des maisons, où chaque maison i est situé à un certain x _i sur l'axe des x. Le maire veut installer des émetteurs radio sur les toits des maisons de la ville. Chaque émetteur a une portée, k , ce qui signifie qu'il peut transmettre un signal à toutes les maisons ≤. k unités de distance.

Étant donné une carte de Hackerland et la valeur de k pouvez-vous trouver le nombre minimum d'émetteurs nécessaires pour couvrir chaque maison ?

Ma mise en œuvre est la suivante :

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);
    }
}

Je suis pratiquement sûr que cette mise en œuvre est correcte. Mais veuillez voir le détail dans les fonctions : findNextTowerIndex y nextHouseNotCoveredIndex : ils parcourent le tableau un par un !

L'un de mes tests est le suivant :

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..");
}

où input.txt peut être téléchargé à partir de aquí . (Ce n'est pas le détail le plus important dans cette question, mais quand même ) Nous avons donc un tableau de 73382 maisons, et j'ai délibérément fixé la gamme d'émetteurs pour que les méthodes que j'ai bouclent beaucoup :

Voici un exemple de sortie de ce test dans ma machine :

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

J'ai aussi ce test, qui n'affirme rien, mais se contente de garder le temps :

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..");
}

où je crée au hasard 400 gammes d'émetteurs, et j'exécute le programme 400 fois J'obtiendrai les temps d'exécution suivants dans ma machine

Took: 20149 milliseconds..

Alors maintenant, j'ai dit, pourquoi ne pas utiliser la recherche binaire au lieu de parcourir le tableau ? et j'ai modifié mes implémentations comme suit :

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;
}

et je m'attends à un grand gain de performance, car maintenant je vais tout au plus boucler pour log(N) fois, au lieu de O(N) . Donc test_01 sort :

Took: 297 milliseconds..

Rappelle-toi, c'était Took : 359 millisecondes avant. Et pour le test_02 :

Took: 18047 milliseconds..

J'obtiens donc toujours des valeurs autour de 20 secondes avec l'implémentation de la marche en tableau et 18 - 19 secondes pour l'implémentation de la recherche binaire.

Je m'attendais à un gain de performance bien meilleur en utilisant Arrays.binarySearch mais ce n'est manifestement pas le cas, pourquoi ? Qu'est-ce qui me manque ? Ai-je besoin d'un tableau contenant plus de 73382 pour voir l'avantage, ou est-ce sans importance ?

Edit #01

Après le commentaire de @huck_cussler, j'ai essayé de doubler et tripler l'ensemble de données que j'ai (avec des nombres aléatoires) et j'ai essayé d'exécuter test02 (bien sûr en triplant la taille des tableaux dans le test lui-même ). Pour l'implémentation linéaire, les temps sont les suivants :

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

Pour la mise en œuvre de la recherche binaire, j'ai obtenu les valeurs suivantes :

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

Answer 1

Votre timing comprend la récupération des données de votre disque dur. Cela peut prendre la majorité de votre temps d'exécution. Omettez le chargement des données de votre timing pour obtenir une comparaison plus précise de vos deux approches. Imaginez que cela prenne 18 secondes et que vous compariez 18,644 contre 18,789 (amélioration de 0,77 %) au lieu de 0,644 contre 0,789 (amélioration de 18,38 %).

Si vous avez une opération linéaire O(n), comme le chargement d'une structure binaire, et que vous la combinez avec une recherche binaire O(log n), vous obtenez O(n). Si vous faites confiance à la notation Big O, alors vous devriez vous attendre à ce que O(n + log n) ne soit pas significativement différent de O(2 * n) puisqu'ils se réduisent tous deux à O(n).

De plus, une recherche binaire peut être plus ou moins performante qu'une recherche linéaire en fonction de la densité des maisons entre les tours. Considérons, par exemple, 1024 maisons avec une tour répartie uniformément tous les 4 logements. Une recherche linéaire fera 4 pas par tour, tandis qu'une recherche binaire prendra log2(1024)=10 pas par tour.

Une dernière chose... votre minNumOfTransmitters trie le tableau déjà trié qui lui a été transmis par la méthode test_01 y test_02 . Cette étape de recours prend plus de temps que vos recherches elles-mêmes, ce qui masque encore davantage les différences de temps entre vos deux algorithmes de recherche.

\======

J'ai créé une petite classe de timing pour donner une meilleure image de ce qui se passe. J'ai supprimé la ligne de code de minNumOfTransmitters pour l'empêcher de réexécuter le tri, et j'ai ajouté un paramètre booléen pour choisir d'utiliser ou non votre version binaire. Il totalise la somme des temps pour 400 itérations, en séparant chaque étape. Les résultats obtenus sur mon système montrent que le temps de chargement éclipse le temps de tri, qui éclipse à son tour le temps de résolution.

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

Il est facile de voir comment l'optimisation de cette dernière étape ne fait pas une grande différence dans le temps d'exécution global.

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 2

Dans votre mesure du temps, vous incluez des opérations qui sont beaucoup plus lentes que la recherche de tableaux. Il s'agit des E/S du système de fichiers et du tri des tableaux. Les E/S en général (lecture/écriture à partir du système de fichiers, communication réseau) sont plus lentes par ordre de grandeur que les opérations qui impliquent uniquement l'accès au CPU et à la RAM.

Réécrivons votre test de manière à ne pas lire le fichier à chaque itération de la boucle :

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..");
}

Remarquez que dans cette version du test, le fichier n'est lu qu'une seule fois et que la mesure du temps commence ensuite. Avec ce qui précède, j'obtiens Took: 1700 milliseconds.. (plus ou moins quelques millis) tant pour la version itérative que pour la recherche binaire. On ne voit donc toujours pas que la recherche binaire est plus rapide. C'est parce que la quasi-totalité de ce temps est consacré à trier le tableau 400 fois.

Maintenant, supprimons la ligne qui trie le tableau d'entrée de l'application minNumOfTransmitters méthode. Nous trions le tableau (une fois) de toute façon au début du test.

Nous pouvons maintenant constater que les choses vont beaucoup plus vite. Après avoir supprimé la ligne houseLocations = uniqueHouseLocationsSorted(houseLocations) de minNumOfTransmitters J'ai compris : Took: 68 milliseconds.. pour la version itérative. Il est clair que, puisque cette durée est déjà très faible, nous ne verrons pas de différence significative avec la version à recherche binaire.

Augmentons donc le nombre de tours de boucle à : 100000 .
Maintenant, j'ai Took: 2121 milliseconds.. pour la version itérative et Took: 36 milliseconds.. pour la version avec recherche binaire.

Parce que nous avons maintenant isolé ce que nous mesurons et que nous nous concentrons sur les recherches de tableaux, plutôt que d'inclure des opérations qui sont beaucoup plus lentes, nous pouvons remarquer la grande différence de performance (pour le mieux) de la recherche binaire.

Si vous voulez voir combien de fois la recherche binaire entre dans son while vous pouvez l'implémenter vous-même et ajouter un compteur :

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.
}

La méthode est copiée de la classe Arrays du JDK - j'ai juste ajouté le compteur de boucle et le println.
Lorsque la longueur du tableau à rechercher est de 73382, la boucle n'entre que 16 fois. C'est exactement ce que nous attendons : log(73382) =~ 16 .

Answer 3

Je suis d'accord avec les autres réponses : le principal problème de vos tests est qu'ils ne mesurent pas les bonnes choses : l'OI et le tri. Mais je ne pense pas que les tests suggérés soient bons. Ma suggestion est la suivante :

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);
}

Notez également que je supprime tous les System.out.println appels de findNextTowerIndex y nextHouseNotCoveredIndex y uniqueHouseLocationsSorted appel de minNumOfTransmitters car ils affectent également les tests de performance.

Donc ce que je pense est important ici :

1. Déplacer toutes les E/S et le triage hors de la boucle de mesure
2. Effectuer un échauffement en dehors de la mesure
3. Utiliser la même séquence aléatoire pour toutes les mesures
4. Ne pas disposer du résultat du calcul pour que le JIT ne puisse pas optimiser cet appel.

Avec un tel test, je vois une différence d'environ 10 fois sur ma machine : environ 80ms contre environ 8ms.

Et si vous voulez vraiment faire des tests de performance en Java, vous devriez envisager d'utiliser JMH (Java Microbenchmark Harness)

Answer 4

Je suis d'accord avec les autres réponses, le temps d'IO est le plus problématique, le tri est le second, la recherche est le dernier consommateur.

Et d'accord avec l'exemple de phatfingers, la recherche binaire est parfois pire que la recherche linéaire dans votre problème parce que la recherche linéaire totale fait une boucle pour chaque élément ( n fois comparer) mais la recherche binaire a été exécutée pour les temps de la tour ( O(logn)*#tower) ), une suggestion est que la recherche binaire ne commence pas à partir de 0, mais de la position actuelle

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

alors il devrait O(logn)*#tower/2) Encore plus, peut-être que vous pouvez calculer combien de maisons chaque tour couvre. avg alors comparez d'abord avg maisons, puis en utilisant la recherche binaire à partir de houseNotCoveredIndex + avg + 1 mais je ne suis pas sûr que les performances soient bien meilleures.

ps : tri et unique vous pouvez utiliser TreeSet comme

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 5

UniqueHouseLocationsSorted n'est pas efficace, la solution d'Andy semble meilleure, mais je pense que cela pourrait améliorer le temps passé (notez que je n'ai pas testé le code) :

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);
}

Envisagez également d'utiliser une liste de tableaux car la copie du tableau prend du temps.