Mon aventure sur SPOJ et autres CodeForces

Haha, la bourde de merde. Je sais même pas pourquoi je n’y ai pas pensé.

J’en profite pour reposter mon code. Si quelqu’un a une idée de pourquoi c’est plus lent qu’avant..

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

# Prime1 on SPOJ - SpheOnlineJudge.com

import sys
import math

def binary_search(array, left, right, e, always_return=False, bool_return=False):
    if left - right < 2:
        if always_return:
            return right
        elif bool_return:
            return False
        else:
            return None

    mid = math.floor((left + right) / 2)
    if array[mid] == e:
        if bool_return:
            return True
        else:
            return mid
    elif e < array[mid]:
        return binary_search(array, left, mid, e, always_return)
    else:
        return binary_search(array, mid, right, e, always_return)

def prime_sieve(end):
    nb = [False, False] + [True for i in range(2, end + 1)]  # 0 and 1 to False
    i = 2
    max = math.ceil(math.sqrt(len(nb)))
    while i < max:
        if nb[i]:
            for j in range(i**2, len(nb), i):
                nb[j] = False
        i += 1
    return [n for n in range(len(nb)) if nb[n]]


def main():
    nb_test = int(sys.stdin.readline())
    cases = []
    max_end = 0
    for e in range(nb_test):
        start, end = map(int, sys.stdin.readline().split(" "))
        cases.append({"start": start, "end": end})
        if max_end < end:
            max_end = end

    primes = prime_sieve(math.ceil(math.sqrt(max_end)))

    for case in cases:
        start, end = case["start"], case["end"]
        if start < 3:
            start = 3
            if end >= 2:
                print(2)
            else:
                print()
        if start % 2 == 0:
            start += 1

        sqrt_end = math.ceil(math.sqrt(end))
        max_p = binary_search(primes, 0, len(primes), sqrt_end, always_return=True) # True so there's an index returned
        primes_array = primes[1:max_p]

        for i in range(start, end + 1, 2):
            is_prime = True
            if i not in primes_array:
                for p in primes_array:
                    if i % p == 0:
                        is_prime = False
                        break
            if is_prime:
                print(str(i))
        print()  # New line and each test case


if __name__ == '__main__':
    main()

Je n’ai pas lu le sujet depuis le début mais ton binary_search m’a intrigué. En fait tu aurais pu te passer de coder ça puisque juste après tu fais des trucs avec primes_array qui sont linéaires en max_p. edit Il existe une librairie pour faire ça, bisect.

Ensuite pour améliorer ton code, regardes ce que tu fais : pour chaque i entre start et end, pour chaque nombre premier, tu regardes s’il divise ce i. Mais tu vas parcourir plein de nombres premier pour finalement dire « ah non ça ne divise pas, on passe au suivant ». Tu as d’ailleurs déjà utilisé dans ton code une idée permettant d’améliorer ça (et tu peux fusionner les deux mais je ne pense pas que ça apporte grand chose).

Je ne sais pas quel est ton code d’"avant", mais:

• python dispose d’une recherche dichotomique dans bisect;
• d’autre part, il y a moyen de s’arrêter plus simplement sans faire cette recherche préalable;
• enfin et surtout, ton code pour trouver les premiers sur l’intervalle est plutôt naïf (ce n’est pas un crible);

J’ai fait un print(max_p) pour voir, et j’ai vu.

Par ailleurs, dans ta fonction prime_sieve(), tu utilises len(nb) un peu partout. Autrement dit, comme len() est une fonction, tu calcules len(nb) un certain nombre de fois. Calcule len_nb = len(nb) une fois pour toutes, et utilise len_nb au lieu de len(nb)

En Python, len(nb) ne va pas calculer la taille à chaque appel. La taille est connue, c’est une métadonnée de la liste. Par contre, dans le cas présent, on connaît très bien len(nb), vu qu’elle vaut end + 1.

Par contre, différentes boucles sont faites à l’aide de range et len là où d’autres opérations seraient à privilégier (enumerate). Et il y a un while qui devrait être remplacé par un for.

Pour le crible entre Stat et End c’est prévu que je l’implémente. Je voulais juste voir comment améliorer le code avant de le modifier. Du coup je vais implémenter le crible pour l’intervalle [start, end]

@Elegance J’ai regardé max_p, je ne vois pas où il y a une erreur potentielle. En fait ce qui ralenti considérablement le programme c’est quand je vérifie si il y a des premiers entre start et sqrt(end) (ie : max_p)

@Entwann Je vais regarder ça. Si je code en Python et que je poste ici, c’est aussi pour en apprendre plus sur ce langage que j’aime beaucoup

Je continue d’avancer sur ce problème ci mais j’aimerais essayer autre chose. Le problème c’est que je me perds un peu dans l’immense liste de problèmes. J’ai regardé un peu les problèmes de programmation dynamique mais j’ai aucune idée duquel prendre pour commencer. Du coup je suis ouvert à vos suggestions (je ne me restreint pas à SPOJ, faites vous plaisir).

Je fais en même temps mes implémentations de divers algorithmes et structures de données classiques (les tris, arbres, tas…). Si vous êtes ok j’aimerais bien vous envoyer le code et que vous me disiez comment mieux faire (en complexité mais surtout en "pythonicité").

Encore merci de votre aide, le billet arrive dès que j’ai optimisé ce fichu problème !

Edit : @Yoch Le problème de ton astuce c’est qu’il faut faire un cas particulier pour 2. Je n’y avais pas réflechi avant de l’implémenter

Edit 2: J’ai eu une "bonne" idée, je me suis dit que je pouvais utiliser un générateur pour itérer pendant mon crible. Voici ce avec quoi je suis arrivé :

1
2
3
4
5
6

prime = (n for n, is_prime in enumerate(nb[3:], start=3) if is_prime)

for p in prime:
    print(p)
    nb[p**2::2*p] = [False] * int(math.ceil((len(nb)-p*p) / (2*p)))
    output.append(p)

Mais j’ai constaté une chose sur le fonctionnement du générateur : il évalue toute les sorties sans prendre en compte l’évolution du tableau sur lequel il itère. On a pas moyen d’éviter ça ? C’est plus par curiosité sur quelque chose que je n’ai jamais utilisé autre qu’en tuto.

Edit 3 : Après un peu de travail j’ai implémenté un crible pour l’intervalle qui nous intéresse. Sauf que je me prend encore un TLE, je désespère un peu de comprendre pourquoi très honnêtement.

Voici mon code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

# Prime1 on SPOJ - SpheOnlineJudge.com

import sys
import math
import bisect


def prime_sieve(end):
    nb = [False, False] + [True] * (end - 1)  # 0 and 1 to False

    nb[2**2::2] = [False] * int(math.ceil((len(nb) - 4) / 2))

    for i in range(3, math.ceil(math.sqrt(len(nb)))):
        if nb[i]:
            nb[i**2::2*i] = [False] * math.ceil((len(nb)-i*i) / (2*i))

    return [n for n, is_prime in enumerate(nb) if is_prime]


def main():
    nb_test = int(sys.stdin.readline())
    cases = []
    max_end = 0
    for e in range(nb_test):
        start, end = map(int, sys.stdin.readline().split(" "))
        cases.append({"start": start, "end": end})
        if max_end < end:
            max_end = end

    primes = prime_sieve(math.ceil(math.sqrt(max_end)))

    for case in cases:
        start, end = case["start"], case["end"]
        if start == 1:
            if end >= 2:
                start = 2
            else:
                print()
                continue

        nb = [True] * (end - start + 1)

        max_p = bisect.bisect(primes, math.sqrt(end))
        min_p = bisect.bisect_left(primes, start)

        [print(i) for i in primes[min_p:max_p]]  # cette ligne permet d'afficher les nombres premiers entre start et sqrt(end)

        for p in primes[:max_p]:
            try:
                first = next(filter(lambda i: (start + i) % p == 0,
                                    range(len(nb))
                                    )
                             )
                nb[first::p] = [False] * len(nb[first::p])  # Parce qu'ici ils seront mis à False
            except StopIteration:
                break

        [print(i) for i, is_prime in enumerate(nb, start=start) if is_prime]

        print()  # New line and each test case


if __name__ == '__main__':
    main()

Merci encore du temps que vous passez pour moi

Sur le code d’aujourd’hui, je ne dirai rien, je connais trop peu Python pour cela.

Sur le code de dimanche soir 19h32, on t’a parlé de la fonction bisect() … mais pour moi, le plus gros problème était la ligne 67 :

1

if i not in primes_array:

Cette ligne n’apporte rien à l’algorithme. Mais elle ralentit dramatiquement l’exécution.

En fait je me sers de cette ligne pour sélectionner les premiers qui sont dans le tableau. Sinon ils ne sortent pas. Après coup je pense qu’une sélection préalable est plus rapide non ?

Qu’est-ce que tu veux dire ? Quel est le problème que tu rencontres avec les générateurs ?

En fait c’est moi qui codait pas comme il faut

J’ai voulu tester si utiliser une générateur pour le crible était plus rapide, en fait pas vraiment. J’avais codé la boucle comme suit :

1
2

for p in (prime for prime, is_prime in enumerate(nb[3:], start=3)):
    nb[p**2::2*p] = [False] * int(math.ceil((len(nb)-p*p) / (2*p)))

C’est très condensé mais étonamment moins rapide qu’une boucle qui teste si p est premier.