substitution par nombres premiers

[SAKAROV]

Bon, je ne vais pas vous apprendre ce que sont les nombres premiers, vous le savez déjà. Donc là, on va utiliser les nombres premiers situés avant 1000.

Il y en a donc 168, les voici :

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

Note: on peut décaler la base. En gros, A=1 en base 1. Mais en base 2, c'est A=2.

Là en l'occurrence, la substitution se fait par nombre premiers (dans l'ordre croissant, et ayant 1000 pour limite en général).

Ainsi donc, A=2, B=3, C=5... H=19 etc pour la base 1. Pour la base 2, A=3, B=5, C=7... H=23 etc.

Il y a au total 168 nombres premiers avant le nombre 1000 (présentés dans la table ci-dessus).

L'alphabet ne boucle pas. C'est à dire que 997 ne peut pas être = à 'A'.

A = 1 (base1)
A = 823 (base 142)

Il ne peut y avoir une base supérieure à 142.

Car si 823=A, Z=997 soit la limite (vu qu'on ne boucle pas).


Exemples :

spike (base 1 ; 1=A) = 67 53 23 31 11

ex nihilo = (base 95 ; A=499) = 523 647  593 563 569 563 577 599  <-- deux espaces entre les deux mots (entre 647(x) et 593 (n))

[Yarflam]

Si ça intéresse des gens de générer des nombres premiers, j'ai un petit tools :
http://pastebin.com/DwQKxErF
Renommez le fichier par exemple en Premier.py et écrivez dans le shell _ Premier.py 2 1000 _ pour générer l'intervalle [2;1000]

Merci Sakarov pour cette article sur la substitution ! Ça peut toujours servir; l'idée est pas mal.

[fred]

Bonjour, j'ai créé une lib interfacée en C/python afin d'accélérer la génération des nombres premiers.

Normalement ça devrait booster, mais j'ai pas comparé.

Voici le code avant compilation (utilisation de cython)

def prime(n):
    cdef int j
    cdef int i
    cdef int val = n
    rang = []
    if n == 2: return [2]
    elif n < 2: return []
    for i from 3 <= i < val+1 by 2:
        rang.append(i)
    cdef double root = val ** 0.5
    cdef int half = (val+1)/2
    i=0
    cdef int m=3
    while m <= root:
        if rang[i]:
            j = (m*m-3)/2
            rang[j] = 0
            while j < half:
                rang[j] = 0
                j += m
        i += 1
        m = 2*i + 3
    return [2]+[x for x in rang if x]

Pour son utilisation c'est simple, voici un exemple

from primes import prime

print prime(3000) # Affichera tous les nombres premiers inférieurs à 3000

Je peux encore l'améliorer en utilisant l'api C avec mes listes, mais pas trop le temps, je verrais ça plus tard...

Voilà une optimisation...

from cpython cimport PyObject

cdef extern from "Python.h":
    PyObject* PyList_New(Py_ssize_t len)
    int PyList_Append(PyObject *list, PyObject *item)
    PyObject* PyList_GetItem(PyObject *list, Py_ssize_t index)
    int PyList_SetItem(PyObject *list, Py_ssize_t index, PyObject *item)
    long PyLong_AsLong(PyObject *pylong)
    PyObject* PyLong_FromLong(long v)
    Py_ssize_t PyList_Size(PyObject *list)

def prime(n):
    result = []
    cdef int j
    cdef int i
    cdef int val = n
    rang = PyList_New(0)
    if n == 2: return [2]
    elif n < 2: return []
    for i from 3 <= i < val+1 by 2:
        PyList_Append(rang, PyLong_FromLong(<long>i))
    cdef double root = val ** 0.5
    cdef int half = (val+1)/2
    i=0
    cdef int m=3
    while m <= root:
        if PyList_GetItem(rang, i):
            j = (m*m-3)/2
            PyList_SetItem(rang, j, <PyObject *>0)
            while j < half:
                PyList_SetItem(rang, j, <PyObject *>0)
                j += m
        i += 1
        m = 2*i + 3
    for i in range(<int>PyList_Size(rang)):
        val = PyLong_AsLong(PyList_GetItem(rang, i))
        if val != -1:
            result.append(val)
    return result

Bonne journée,

[Yarflam]

Mon code ressemblait à rien.

Celui là est beaucoup mieux :

def nbrp(min,max):
  for i in range(min,max):
      t=1
      for j in range(2,i):
          t=0 if (float(i) % float(j)) == 0 else t
      if t == 1: print(i)


def nbrp(min,max):
  out_r=[]
  for i in range(min,max):
      t=1
      for j in range(2,i):
          t=0 if (float(i) % float(j)) == 0 else t
      if t == 1: out_r.append(i)
  return out_r

Après je ne sais pas si ton code est plus rapide, mais il est très long (taille de code ).
Je vais tester ça !

[fred]

Bon je l'avais déjà dis, le plus important c'est pas le nombre de ligne, c'est l'algorithme et le langage qui se rapproche le plus du processeur.

En l’occurrence le score est sans appel, mais c'était évident

Pour 1000000

[email protected]:~/Desktop$ time python yar_prime.py

real 0m2.171s
user 0m0.068s
sys 0m0.036s
[email protected]:~/Desktop$ time python fred_prime.py

real 0m0.420s
user 0m0.248s
sys 0m0.036s
[email protected]:~/Desktop$

Pour 10000000

[email protected]:~/Desktop$ time python yar_prime.py

real 0m9.472s
user 0m0.404s
sys 0m0.344s
[email protected]:~/Desktop$ time python fred_prime.py

real 0m4.239s
user 0m2.652s
sys 0m0.136s

Pour 100000000

[email protected]:~/Desktop$ time python fred_prime.py

real 1m16.838s
user 0m27.488s
sys 0m2.424s

Mais en ce qui concerne ton code je n'ai pas eu la patience, ça à fait exploser ma RAM

[fred]

J'ai fais 2x plus rapide

from libc.stdlib cimport malloc, free

def prime(n):
    if n == 2: return [2]
    elif n < 2: return []
    cdef int j = 0
    cdef int k=0, i
    cdef int m=3
    cdef int val = n
    cdef int *rang = <int *>malloc(sizeof(int) * val)
    for i from 3 <= i < val+1 by 2:
        rang[j] = i
        j += 1
    cdef double root = val ** 0.5
    cdef int half = (val+1)/2
    i=0
    while m <= root:
        if rang[i]:
            k = (m*m-3)/2
            rang[k] = 0
            while k < half:
                rang[k] = 0
                k += m
        i += 1
        m = 2*i + 3
    liste = [2]+[rang[i] for i in range(k) if rang[i] != 0]
    free(rang)
    return liste

Pour 100000000

[email protected]:~/Desktop$ time python fred_prime.py

real 0m2.002s
user 0m1.748s
sys 0m0.216s

Pour 1000000000

[email protected]:~/Desktop$ time python fred_prime.py

real 0m57.770s
user 0m20.748s
sys 0m2.012s

20 secondes de gagné

[Anonyme77]

Une petite question (sûrement très bête):

Quel est l'avantage d'utiliser du C/Python ? Ne serait-il pas plus rapide d'utiliser du C (j'ai envie de dire tout court) ?

[fred]

C'est un exemple d'utilisation de cython, je dirais un exemple simple.

Étant donné que ce n'est que du calcul, le C (seul) s'y prête bien, mais pour un projet nécessitant puissance de calcul et "autres choses", l'interfaçage C/python simplifie grandement les choses que de coder seulement en C.

L'avantage de python est de retrouver très facilement des fonctions évitant de réinventer la roue comme le langage C.

Je peux aussi coder avec PyQt en utilisant le langage C, ce que je ne peux pas avec le C (seul). Tu me diras on utilise le C++...

La gestion des erreurs en python, rend très simple l'écriture du code.

Ce que j'aime

La syntaxe C est simple et c'est puissant pour les calculs -> optimisation
La syntaxe python est simple et on code rapidement (surtout grâce à ses fonctions) -> gain de temps

Ce que j'aime pas

Le temps de codage en C, le nombre de lignes à coder
L'utilisation seule de GTK en C
La lenteur parfois agaçante du python

J'allie donc la puissance du C et la simplicité d'écrire du code en python.

Qui puis-est les accolades sont virées... ça j'aime bien

[Anonyme77]

Ma question était plutôt pour rebondir sur le fait que vous parliez d'optimisation du code. Je demandais donc si dans ce cas le C n'était pas plus rapide.

Personnelement,et après plusieurs autres langages, je suis un python-addict mais je ne me suis pas encore penché sur cpython.


Quels sont les différences de performances entre C et cpython ?

Merci beaucoup pour tes "éclaircissements".

[fred]

" Je demandais donc si dans ce cas le C n'était pas plus rapide."

Si clairement, le C est plus rapide, mais je conseillerais de l'utiliser seulement pour du calcul, le python pour le reste est très bien.

Mais je n'allais pas comparer le langage python au langage C concernant une optimisation. Par contre cython reste du python en quelque sorte.

"Quels sont les différences de performances entre C et cpython ?"

En moyenne le C est 1,2 fois à 1,6 fois plus rapide à ce que j'ai déjà pu tester... (je n'utilise pas cython tous les jours)

Et pour ce peu de différences, cython étant bien plus confortable, mon choix est vite fait entre le C ou cython.

[Anonyme77]

Je suis bien d'accord avec toi sur le fait que python soit pratique pour pratiquement tout.

Pour ma part, j'apprécie combiner les langages dans mes développements.

Par exemple dans le cas sus-mentionné, je ferais un algorythme en C retournant les nombres premiers et je ferais un appel à ce programme en C dans mon code python pour récupérer les résultats et faire je vais dire tout le reste...

Je trouve que cette méthode à de quoi séduire dans le sens chaque partie du programme/projet utilise le langage répondant le mieux à la demande.

Je vais maintenant me concentrer un peu sur cpython. Tu as éveillé mon intérêt .

[SAKAROV]

Bah vas-y fais-le, ça permettra de voir la diff entre ton procédé et celui de fred en Cython tu nous fais un petit bench

[TorTukiTu]

Je trouve que cette méthode à de quoi séduire dans le sens chaque partie du programme/projet utilise le langage répondant le mieux à la demande.

Ouhla, quand je lis ca, j'ai les écailles qui s'hérissent...

Le fait de vouloir utiliser X langages pour un seul petit projet est souvent une fausse bonne idée.

Je m'explique:

Lorsque tu utilises X langages, j'ai cru comprendre que tu allais devoir faire beaucoup de binding. Ce qui implique la plupart du temps un couplage important entre tes différents composants logiciels.

Qui plus est, tu gagnes certes localement les avatages du langage bindé, mais ca implique aussi que tu vas être globalement soumis aux limitations de ce langage.
(c'est encore une histoire de couplage en fait...)

Prenons exemple du python et du C.

- Localement, c'est très bien, tu gagnes en rapidité avec ton C.
- Globalement, c'est merdique puisque tu vas perdre la portabilité de python pour une toute pertite portion de ton programme.
- Qui plus est, si demain tu casses tes libs en C, tu vas certainement devoir casser la partie python qui s'interface avec.

La plupart du temps, il est mieux d'en faire le plus possible dans un même langage, ou de limiter le nombre de langages utilisés.
Si tu veux vraiment utiliser plusieurs langages, alors pense d'avanatge a une architecture orientée service où chaque composant fournit ses services aux autres d'une facon standardisée (En papotant en XML par exemple (cf. SOAP et les WSDL) ).

Après, ce découplage implique une perte de rapidité. A toi de voir si tu peux rendre ca acceptable ou pas dans ton projet.

Il est effectivement parfois nécéssaire de faire du binding ou d'utiliser X langages, ca dépend de chaque projet. Mais ca devrait toujours être choisi en dernier recours.

Tortue 974.

[fred]

Ouhla, quand je lis ca, j'ai les écailles qui s'hérissent...

Tu ne devrais pas!

Le fait de vouloir utiliser X langages pour un seul petit projet est souvent une fausse bonne idée.

Ah oui, je suis d'accord, mais si ton petit projet s'exécute en 27 heures, il va falloir penser à faire quelque chose, non?

- Globalement, c'est merdique puisque tu vas perdre la portabilité de python pour une toute pertite portion de ton programme.

Python est codé en quoi? Réponse en C, et pourquoi en C ? Réponse, parce-qu'il n'y a pas plus portable que le C.

Cette remarque, désolé, je la trouve un peu HS, car on parle bien d'optimisation sur du calcul, et là je ne vois pas en quoi des mathématiques ne sont pas portables dans un langage de programmation, quel qu'il soit.

cython est portable, tu peux faire du cross-compiling sans soucis (créer des exécutables Windows sous Linux), créer des dll sous Linux, etc...

Bref cython c'est du python mélangé avec du C, mais ça reste du python, et sa portabilité n'en est pas du tout touché à moins que tu le souhaites personnellement.

La plupart du temps, il est mieux d'en faire le plus possible dans un même langage, ou de limiter le nombre de langages utilisés.

Ça je suis ultra-méga-super d'accord, mais python et C ??? python créé en C, ne se mélangerait pas super bien avec le langage C ? Ça serait le comble, non?

Après, ce découplage implique une perte de rapidité. A toi de voir si tu peux rendre ca acceptable ou pas dans ton projet.

C'est comme tout, mal fait, mieux vaut pas le faire, mais si on maitrise son art, l'optimisation est faite pour optimiser, je vois rien de négatif là dedans.

Il est effectivement parfois nécéssaire de faire du binding ou d'utiliser X langages, ca dépend de chaque projet. Mais ca devrait toujours être choisi en dernier recours.

Je dis oui car ça coule sous le sens, dans le fait qu'un projet doit être réfléchi avant de coder, ce qui même chez un développeur de profession n'est pas toujours le cas.

[TorTukiTu]

Je trouve que cette méthode à de quoi séduire dans le sens chaque partie du programme/projet utilise le langage répondant le mieux à la demande.
...
Tu ne devrais pas!

Mmmm, je me suis insurgé contre un principe qui est présenté comme une généralité et qui devrait rester une exception. Le calcul lourd est une exception. Et même dans ce cas, une architecture orienté services devrait être envisagée.

Comme je l'ai dit, tout dépend du projet en question. Si ta contrainte principale est la durée d'éxécution, alors oui, un binding avec du C est envisageable et peut-être souhaitable. Dans tous les autres cas, c'est à proscrire.

Bon, après, je ne vais pas m'attarder d'avantage, ca va encore partir en troll (j'avoue que mon post s'y prétait). Je reste cependant en total désacort sur la portabilité du C. Un langage qui nécéssite une recompilation pour chaque plate forme est forcément moins portable qu'un langage interprété (pour peu que les clients soient tous déjà équipés de l'interpréteur ou de la VM qui va bien).

Si tu veux en troller en privé, ce sera avec joie !

Tortue 974.