1
votes

Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000

J'essaye de trouver tous les nombres entre 1 et 10000000 (tous deux inclus). J'ai essayé deux solutions

  1. Approche de force brute: boucle sur tous les nombres de 1 à 10 000 000, et trouve tous ceux qui sont divisibles par 3 ou 5 ou les deux.
  2. Approche Divide & Conquer: avoir 4 compteurs (2 du début et 2 de la fin). 2 compteurs fonctionnent sur des multiples de 3 et deux sur des multiples de 5. Je mets tous les multiples dans un ensemble (je n'ai pas besoin d'éléments triés, je n'ai besoin que d'éléments, le tri augmente également ma complexité).

Mais l'approche en boucle prend moins de temps que l'approche «Divide & Conquer» (environ 10 fois moins). J'ai également recherché des solutions en ligne. Mais, je pourrais trouver une approche en boucle uniquement. Y a-t-il quelque chose qui me manque dans mon approche qui augmente mon temps d'exécution? Veuillez m'indiquer cela. Je suis parti d'une liste, je suis passé à un ensemble trié, puis j'ai finalement décidé d'utiliser HashSet, mais cela semble prendre du temps.

Voici ce que j'ai essayé.

»

public static void main(String[] args) {

    System.out.println("Numbers divisible by 3 and 5:");

    nosDivisibleBy3And5();    // divide & conquer approach (approach to consider)

    nosDivisibleBy3And5BruteForce();

}

private static void nosDivisibleBy3And5BruteForce() {

    IntStream ar = IntStream.range(1, 10000001);  // start inclusive, end exclusive

    Integer[] array = ar.boxed().toArray(Integer[]::new);

    List<Integer> list = new ArrayList<>();

    int count = 0;

    long start = System.currentTimeMillis();

    /* 
     * Traversing array from 1 to 100, 
     * if it is either divisible by 3 or 5 or both, count it , print it. 
     * 
     */
    for(int i = 0; i < array.length ; i ++) {

        if((array[i] % 3 == 0) || (array[i] % 5 == 0)) {

            //System.out.println(array[i]);

            list.add(array[i]);

            count++;
        }
    }
    long end = System.currentTimeMillis();

    System.out.println("Brute Force Approach:");
    System.out.println("No of elements counted: " + count);

    //Collections.sort(list);

    //System.out.println("Elements: " + list);

    System.out.println("Time: " + (end - start));

}

private static void nosDivisibleBy3And5() {

    /* 
     * Set has all those numbers which 
     * are divisible by both 3 and 5.
     * 
     */

    Set<Integer> elementsSet = new HashSet<Integer>();

    int fr3,
    fr5,
    mid,
    count;

    fr3 = 2;   // fr3 indicates the index of the first value divisible by 3.
    fr5 = 4;   // fr5 indicates the index of the first value divisible by 5.
    count = 0;

    int end3 = 9999998 , // end3 indicates the index of the last value divisible by 3.
            end5 = 9999999;   // end5 indicates the index of the last value divisible by 5.

    /* Getting all the numbers from 1 to 100 from Intstream object */
    IntStream ar = IntStream.range(1, 10000001);  // start inclusive, end exclusive

    Integer[] array = ar.boxed().toArray(Integer[]::new);

    /* 
     * Using divide and conquer approach , mid divides the array from 1 to 100
     * in two parts, on the first fr3 and fr5 will work, on the second part end3 
     * and end5 will work.
     */
    mid = (fr3 + end3)/2;

    long start = System.currentTimeMillis();

    while(fr3 <= mid && end3 >= mid) {

        elementsSet.add(array[fr3]);

        elementsSet.add(array[fr5]);

        elementsSet.add(array[end3]);

        elementsSet.add(array[end5]);

        fr3 += 3;
        fr5 += 5;
        end3 -= 3;
        end5 -= 5;
    }

    long end = System.currentTimeMillis();

    System.out.println("Our approach");
    System.out.println("No of elements counted: " + elementsSet.size());


    //System.out.println("Elements:" + elementsSet);
    System.out.println("Time:  " + (end - start));
}

}

»


13 commentaires

Veuillez lire ceci avant de mesurer le temps d'exécution de tout code. Vous avez besoin de mesures plus précises avant toute autre chose.


for (long i = 0; i <10_000_000; i + = 3) {} - pas de multiplications ni d'opérations de reste. Ou ai-je mal compris quelque chose à ce sujet? Vous pouvez faire la même chose avec 5, également. Et vous pouvez faire une astuce simple pour trouver ces éléments divisibles par 3 et 5.


@Sweeper, merci pour le lien. Bien que ce ne soit que la taille d'entrée croissante qui devrait décider de la complexité, mais ici je peux voir la console suspendue pour mon approche et beaucoup pour l'approche de la boucle alors que j'augmente la taille de l'entrée. Le décalage horaire est calculé uniquement pour vérifier le temps de fonctionnement, pas de lien avec la complexité que je veux avoir. Ce n'est que la console suspendue qui me préoccupe, car je peux voir que je prends du temps là-bas.


@NomadMaker. Je pense que je ne devrais pas utiliser Set ici, il suffit d'imprimer les éléments. Dans l'approche ci-dessous (pas en boucle un), il n'y a pas d'opération de multiplication ou de reste, juste des compteurs croissants et décroissants et les compteurs pointent eux-mêmes vers les éléments qui ne sont que des multiples et augmentent respectivement de 3 ou 5.


@Ashish (array[i] % 3 == 0) L'opérateur % est l'opérateur de reste. Cela provient de votre code. Je ne comprends toujours pas ce que vous essayez de faire.


@NomadMaker, veuillez vérifier la méthode nosDivisibleBy3And5 . Divide & Conquer y est implémenté. Il existe au total deux méthodes que j'ai implémentées. Opération de reste que j'ai effectuée dans la première méthode uniquement.


@NomadMaker, ma seule préoccupation est que lorsque je stocke les éléments dans les deux cas, c'est-à-dire BruteForce & Divide & Conquer, pourquoi Brute Force est plus rapide même lorsque j'augmente la plage d'entrée.


Voulez-vous les compter ou les trouver?


@Bohemian, je veux les trouver et les stocker.


"Brute Force" et "Divide and Conquer" sont normalement des algorithmes de calcul / recherche plutôt que de stockage. C'est peut-être la raison de ma confusion.


@Ashish Les nombres sont [3,5,6,9,10,12,15] + 15*n pour n = 0 à 666665, puis s'arrête à 10 avec n = 666666. Il suffit de les ajouter à une liste. La complexité est O (n), en supposant que l'ajout à une liste est O (1). Sinon, allouez un tableau de taille 4666667 et ajoutez-les au tableau. La complexité temporelle est O (n) puisque l'indexation dans un tableau est définitivement O (1).


Voulez-vous en avoir une List<Integer> ?


@Bohemian, List <Integer> sera plus rapide que Hashset, oui s'il vous plaît.


3 Réponses :


2
votes

HashSet prend beaucoup de temps sur le hachage et la vérification si l'élément existe déjà et est plus lent que add() de ArrayList nu

Si votre problème est vraiment de trouver tous les nombres divisibles par 3 ou 5, vous pouvez utiliser un tableau avec une longueur prédéterminée:

int from = 1;
int to = 1000000;
int d3 = (to / 3) - (from / 3) + (from % 3 == 0 ? 1 : 0); // how many divisible by 3
int d5 = (to / 5) - (from / 5) + (from % 5 == 0 ? 1 : 0); // how many divisible by 5
int d15 = (to / 15) - (from / 15) + (from % 15 == 0 ? 1 : 0); // how many divisible by 15

int[] array = new int[d3 + d5 - d15]; // counted 15's twice

int offset = 0;
for (int i = from; i <= to; i++) {
  if (i % 3 == 0 || i % 5 == 0) array[offset++] = i;
}


2 commentaires

Je suis d'accord avec votre première déclaration. Il semble que Hashset prenne beaucoup de temps. Je pense que je ne devrais que l'imprimer. Je verrais la structure de données que je peux utiliser pour stocker également des éléments. La partie de code que vous avez publiée est l'approche en boucle, donc selon vous, je devrais suivre l'approche en boucle?


Bonne réponse, bien que le calcul de la longueur du tableau puisse être un peu simplifié, voir ma réponse .



0
votes

Si le retour d'un List<Integer> est l'objectif, vous pourriez avoir une solution de temps et d'espace O (1) en étendant AbstractList et en implémentant un iterator() qui garde la trace de l'index du numéro suivant, et implémentez get(int index) , size() , equals() , hashCode() etc et les méthodes de l'itérateur, le tout par calcul basé sur le nombre maximum.

La liste serait immuable (simplement enveloppée en utilisant Collections. unmodifiableList() ), mais remplirait le contrat de List.

Tout est fait sans stocker aucun des nombres.


4 commentaires

De nos jours, avec Java 8, il devrait renvoyer un Stream au lieu d'un Iterator . Ce qui signifie en fait qu'il devrait implémenter un Spliterator , ou plutôt un Spliterator.OfInt . Ce Spliterator peut facilement implémenter trySplit() , permettant un traitement parallèle. Le Spliterator aurait toutes les caractéristiques sauf CONCURRENT .


@Andreas vous étendriez extend AbstractList et surchargeriez iterator() (et quelques autres méthodes comme size() etc.) qui vous donnent stream() (et d'autres méthodes Java 8 associées) gratuitement car elles sont implémentées dans Collection et utilisent toutes finalement le Iterator impl.


Pourquoi sous- AbstractList -vous AbstractList pour créer une implémentation de List qui viole le contrat de List pour la plupart des méthodes? C'est une très mauvaise solution. Ou aviez-vous en quelque sorte l'intention d'implémenter get(int index) , qui n'est pas une méthode facultative?


@Andreas Je ne pensais pas avoir besoin de le dire ... bien sûr, ce serait une liste immuable (simplement en utilisant Collections.unmodifiableList() ), et si bien sûr, il doit implémenter get(int index) (j'allais même pour poster un impl, mais j'ai décidé que je n'allais pas faire tout le travail d'OP), que j'utiliserais dans l'itérateur, qui n'aurait alors besoin que de stocker l'index (un impl à mon humble avis). Une telle liste remplirait le contrat de List . C'était toujours mon intention.



2
votes

Voici une autre solution, partiellement basée sur l'excellente réponse de DelfikPro .

Cela simplifie la logique de calcul de la taille du tableau, mais ajoute plus de code pour éviter d'avoir à utiliser l'opérateur % reste relativement lent, et élimine le besoin d'itérer sur des nombres qui n'entrent pas dans le tableau de résultats.

En tant que tel, il devrait s'exécuter plus rapidement, même si je n'ai pas effectué de benchmark pour voir si cela fonctionne réellement.

[3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30, 33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99, 100]
[0, 3, 5, 6, 9, 10, 12, 15, 18, 20, 21, 24, 25, 27, 30, 33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99]
[30, 33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99, 100]
[30, 33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99, 100]
[33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99]
[33, 35, 36, 39, 40, 42, 45, 48, 50, 51, 54, 55, 57, 60, 63, 65, 66, 69, 70, 72, 75, 78, 80, 81, 84, 85, 87, 90, 93, 95, 96, 99, 100]

Des tests

System.out.println(Arrays.toString(multiplesOfThreeAndFive(1, 100)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(0, 100)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(29, 100)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(30, 100)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(31, 99)));
System.out.println(Arrays.toString(multiplesOfThreeAndFive(31, 101)));

Les sorties

static int[] multiplesOfThreeAndFive(int from, int to) { // both inclusive
    int count = ((to /  3) - ((from - 1) /  3))  // how many divisible by 3
              + ((to /  5) - ((from - 1) /  5))  // how many divisible by 5
              - ((to / 15) - ((from - 1) / 15)); // how many divisible by 15,  counted twice above
    
    int[] result = new int[count];
    int[] multiples = { 0, 3, 5, 6, 9, 10, 12 };
    
    int startIndex = Arrays.binarySearch(multiples, from % 15);
    if (startIndex < 0)
        startIndex = -startIndex - 1;
    for (int r = 0, offset = from / 15 * 15; r < count; offset += 15, startIndex = 0)
        for (int i = startIndex; r < count && i < multiples.length; i++, r++)
            result[r] = offset + multiples[i];
    return result;
}


0 commentaires