Implémentation en Haskell, histoire de pouvoir détailler le fonctionnement dans un thread dédié et non dans la sous-cat C

edit: je me suis rendu compte en écrivant le post que j'avais oublié une clause, le programme originel était buggé chuis trop nul
ca m'apprendra à faire le kéké

Code principal:

isNull :: Integer -> Bool
isNull = (== 0)
     
isMultiple :: Integer -> Integer -> Bool
isMultiple a b = isNull $ mod a b
     
sieve :: Integer -> [Integer]
sieve limit = 
   2 : (sieveHelper [3,5..limit])
     
sieveHelper :: [Integer] -> [Integer]
sieveHelper [] = []
sieveHelper (x:xs) = 
  x:rest
    where
        rest = sieveHelper (filter (not . (`isMultiple` x)) xs)

Commençons par les helpers (qui ne sont là que pour rendre le code plus lisible)

isNull :: Integer -> Bool
isNull = (== 0)

Utilise le currying pour créer une fonction comparant un Integer (un entier sans limites) à 0: appliquer isNull à 0 renvoie True, l'appliquer à n'importe quoi d'autre renvoie False

isMultiple :: Integer -> Integer -> Bool
isMultiple a b = isNull $ mod a b

Teste si "a" est un multiple de "b":

• Calcule le modulo de a par b (mod a b, renvoie 0 si a est un multiple de b)
• Compare ce modulo à 0 (via le helper isNull créé précédement)

isMultiple renvoie donc True si a est un multiple de b, False s'il ne l'est pas

Passons maintenant à l'implémentation de l'algo.

Commençons par la définition de la fonction "sieve" (qui prend un unique argument "limit", la limite supérieure des tests de primalité)

est la signature de "sieve": "sieve" prend un entier en paramètre et renvoie une liste d'entiers

crée une liste de tous les entiers impairs entre 3 et la limite donnée (3, 5, 7, 9, 11, etc...). À noter qu'Haskell a une sémantique dite "lazy evaluation", la liste n'est donc pas générée en mémoire, n'est générée que sa potentialité (on peut trivialement définir une liste infinite en Haskell, on pourrait d'ailleurs trivialement définir le Crible sous forme d'une liste infinie de nombres premiers)

crée une liste dont le premier élément est "2" et la suite (tail) est le résultat de l'application de "sieveHelper" sur la liste générée au dessus.

sieveHelper :: [Integer] -> [Integer]

sieveHelper prend une liste d'entiers (non premiers) et renvoie une liste d'entiers (premiers)

On arrive maintenant à l'implémentation réelle du crible.

sieveHelper (x:xs) = 
  x:rest
    where
        rest = filter (not . (`isMultiple` x)) xs

(x:xs) est la syntaxe permettant de "déstructurer" une liste Haskell: le premier élément de la liste ira dans "x" et la queue de la liste ira dans "xs"
Exemple: si on appelle sieveHelper en lui donnant la liste [3, 5, 7, 9] alors on aura x = 3 et xs = [5, 7, 9]
Le premier élément de la liste étant par définition un entier, on le renvoie directement, en lui attachant rest que l'on crée en dessous (on remarquera que cette syntaxe de structuration est exactement la même que celle de déstructuration, utilisée dans un contexte différent)

Génération de rest:

crée une fonction par currying et composition (avec une définition de closure en bonus), cette fonction (anonyme) teste si l'entier qu'on lui donne en paramètre est un multiple de x (elle renvoie False si le nombre est un multiple de x, et True s'il n'en est pas un)

L'équivalent en Python serait:

def foo(n):
    return not isMultiple(x, n)

est une fonction appliquant son premier argument (une autre fonction) à tous les éléments d'une liste (son 2e argument). Elle renvoie une liste de tous les éléments pour lesquels la fonction a renvoyé True.

Par exemple si on définit une fonction isPair renvoyant True si son paramètre est pair, filter isPair [1, 2, 3, 4, 5] va renvoyer 2, 4.

Ici, on applique donc à notre liste un filtre enlevant tous les multiples du nombre actuel

Puis on réapplique sieveHelper récursivement sur la liste obtenue.

À l'exécution, si on donne le paramètre "30" on a donc:

Utilisabilité en prod:
nulle, la fonction sieveHelper n'est pas tail-récursive et va donc prendre O(n) en taille de stack au lieu de O(1)

Juste une question, car je n'ai rien compris à vos temps d'exécution sous Linux/Unix (je sais je suis nul).  
J'ai fait un programme Prolog sous Vista qui génère les nombres premiers par la méthode du crible, il a mis 0.73 s pour obtenir les nombres premiers inférieurs à 10 000, c'est concurrentiel avec vos programmes ou je ferais mieux d'aller me coucher ?
Au passage, je génère tous les nombres de 2 à 10 000.
 
De toute façon, c'est inutilisable car Prolog explose à partir de 50 000 à cause de l'utilisation de listes.

 
gni ? quels temps d'execution ?
 
 

L'autre topic sans la section C je pense
http://forum.hardware.fr/forum2.ph [...] w=0&nojs=0
 
Je dirais (en réponse à l'autre topic), que comparé au truc de Masklinn (qu'il explique bien, mais j'ai toujours rien pigé ) c'est nul à chier.
Par rapport à mon programme en C#, sous Vista aussi, tu arrives à un résultat légèrement inférieur, mais rien de follichon. Reste à savoir ensuite quel est ton processeur et autres paramètres pouvant influer sur le temps de traîtement (moi j'ai un pure processeur, mais sur un portable *sic* et surtout, je tourne en mode débug, ce qui n'est pas là pour arranger les perfs).
 
Bon, ensuite, l'approche de Masklinn pour cet algo précis est un plus évolué que mon algo, ce qui explique (minablement, je sais) un peu la différence (mais bon, de là à passer de 24 secondes à 0,15 secondes, ça fait mal quand même )
Notamment, Masklinn utilise la récursivité dans on algo, alors que j'utilise une approche séquentielle. Il passeapparement par des listes là où je passe par un bon gros array des familles de plusieurs Mo... Forcément ça fausse un peu la donne
 
Par contre, je serais intéressé de savoir ce que donne "mon" algo avec Haskell plutôt que le crible machin (qui me semble une pure usine à gaz, à cause de l'énumération inutile de tous les nombres entiers au départ, puis une réévaluation, successive en plus, par la suite).

Ça y'est, j'ai les yeux en face des trous et je comprends les temps d'exécution. Effectivement, mon prog est archi lent, normal c'est de l'interprété et la manipulation des listes est lente et gourmande en mémoire.
J'adore ce que je viens de voir ici :  http://www.scriptol.org/langages-populaires.php
"Haskell Programmation fonctionnelle. Lent et gros consommateur de mémoire.  pour essayer de programmer autrement. "

Ca dépend de l'implémentation (il y a des interpréteurs Haskell et des compilos, GHC est un compilateur), et il est effectivement lent par rapport à d'autres langages (C++ ou C, mais aussi D ou OCaml, OCaml par exemple a un très très bon compilateur)

pourquoi 27 n'est pas dégagé lors du filtrage "multiple de 3"? Un simple oubli?

Ouais, j'ai tapé le truc à la main j'ai laissé passer ça  
 
C'est corrigaid

pour rire, (presque) le meme programme en erlang: (presque, parce que j'utilise un accumulateur )
 

sieve_aux([],Acc) -> lists:reverse(Acc);
sieve_aux([H|T],Acc) -> sieve_aux( [X || X <- T, X rem H =/= 0] , [H|Acc] ).

sieve(L) -> sieve_aux(L,[]).

 
ou sinon, le programme complet (a sauver dans un fichier erat.erl):  
 

-module(eratosthene).  
-export([sieve/1, main/1]).

sieve_aux([],Acc) -> lists:reverse(Acc);
sieve_aux([H|T],Acc) -> sieve_aux([X || X <- T, X rem H =/= 0], [H|Acc]).

sieve(L) -> sieve_aux(L,[]).

main([A]) -> UpperBound = list_to_integer(atom_to_list(A)),  
             sieve( lists:seq(2,UpperBound) ),  
             init:stop().

 
pour l'executer, d'abord le compiler avec  

puis on le lance (ici pour des entiers jusqu'a 10000):

/*
En cours d'édition, grosse connerie dans l'algo qui plombe effectivement les perfs
 
-- T'ain la grosse tanche, cf.2 posts plus loin...
*/
 
 
Masklinn, je pige pas comment t'arrive à trouver les nombres premiers jusqu'à 100 000 000 en 15 secondes...
J'ai beau tortiller le truc dans tous les sens, même en C pur, y'a pas moyen de moyenner, je tourne autour de 50 secondes...
 
Il aurait pas du mal avec les gros array et oublierait de le dire ton bidule ?
 

// cnprems.cpp : Defines the entry point for the console application.
 
#include "stdafx.h"
#include "time.h"
#include "stdlib.h"
 
int _tmain(int argc, _TCHAR* argv[])
{
    unsigned int val, maxi;
    long elapsedTime;
    clock_t startTime, stopTime;
    unsigned char *nbrs;
 
    printf("Jusqu'a combien compter les nombres premiers ? " );
    scanf("%u", &val);
 
    startTime = clock();
 
    maxi = val + 1;
    nbrs = (unsigned char *)calloc(maxi, sizeof(unsigned char));;
 
    for (unsigned int i = 2; i < maxi; i++)
    {
        for (unsigned int j = i * 2; j < maxi; j += i)
        {
            nbrs[j] = 1;
        }
    }
 
    for (unsigned int i = 2; i < maxi; i++)
    {
        if (nbrs[i] == 0)
        {
            //printf("%d\n", i);
        }
    }
 
    stopTime = clock();
    elapsedTime = (stopTime - startTime) / (CLOCKS_PER_SEC / 1000);
    printf("Caluls effectues en %d ms\n", elapsedTime);
    //scanf("%s", &nbrs);
    return 0;
}

Même en collant le timer après le calloc et avant le parcours inutile (le printf en commentaire) je suis à des années lumières de tes 15 secondes... Je vois pourtant pas comment faire plus rapide que du C, et je vois pas ce qui peut clocher avec mon code... unsigned, type de base, pas un seul calcul... pige pas
 
Et vient pas me dire que t'as un PC récent, j'ai un pur portable de folie (Core 2 Duo T7200 // 2 Go DDR2)
 
=> Ca donne un lamentable 48605 ms...

Ouais bon, ok, laisse béton, faut que je prenne 3 ans de vacances, ou alors l'euthanasie directe, je sais pas...
 

 
Je passe un peu à 7 secondes...

Ah oui mais non la perf initiale est fausse hein, yavait un bug dans le code je le mentionne au début du post, faut l'oublier, les du code qui fonctionne sont plus proches de ce que sort souk

tu veux dire que depuis 24 heures je suis vexé comme un poux d'avoir mon prog C# explosé par ton truc, et que j'ai passé la journée à l'optimiser pour... finalement n'exploser qu'un faux record ?

Ouaip