Programme trop long

Version imprimable

Programme trop long

Bonjour à vous. J'ai un problème:

Je dois créer un programme qui fait la somme de toutes les valeurs d'une liste entre deux bornes, cependant la liste pouvant être immenses et le nombre de fois où l'on peut me demander des sommes aussi, mon programme est trop long ...

Après plusieurs essais j'ai ce code qui est le plus cours pour l'instant:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys input=sys.stdin.readline n,r=input().split() n=int(n) r=int(r) N=list(map(int,input().split())) c=sum(N) for i in range(r): a,b=input().split() a=int(a) b=int(b) if (b-a)<=n/2: #si l'intervalle est plus petit que la moitié de la liste print(sum(N[a-1:b])) else: d=c-sum(N[0:a-1])-sum(N[b:]) #sinon on retire les termes en "trop" print(d)
Avez vous des idées afin d'améliorer la vitesse de mon programme? J'ai pensé a stocker toutes les valeurs que j'aurais calculé afin de pouvoir les réutiliser mais je ne sais pas comment faire.

Merci et bonne journée.

19/04/2014, 21h54
VinsS

Salut,

Difficile de comprendre, le lien de l'énoncé est un lien privé. Si tu peux copier ici le texte ...

Ensuite on ne sait pas ce que tu saisis à chaque input(), la liste de nombres c'est N ? tu dis qu'elle est particulièrement longue et il faut l'entrer au clavier ?
19/04/2014, 22h14
sayannel29

Désolé j'avais oublié.

Vous êtes employé dans un parc d'attraction et votre patron, grand commercial, adore faire des statistiques, notamment sur le nombre de visiteurs.
Vous connaissez le nombre de visiteurs qu'il y a eu chaque jour mais ce qui intéresse votre patron, c'est le nombre de visiteurs sur certaines périodes, par exemple entre le 15 Mars et le 20 Juin.
Étant aussi très impatient, votre patron souhaite que vous lui répondiez aussi vite que possible.

LIMITES DE TEMPS ET DE MEMOIRE (Langage : Python)

Temps : 3.5s sur une machine à 1Ghz.
Mémoire : 20000 Ko.

La première ligne contient deux entiers : N et R
La seconde ligne contient N entiers : le nombre de visiteurs pour chacun des N jours
Les R lignes suivantes contiennent chacune deux entiers 1<= D <= F <= N, les jours de début et de fin de la période

CONTRAINTES

0 <= N <= 100 000, le nombre de jours où le parc a reçu des visiteurs
0 <= V < 10 000, le nombre maximum de visiteurs chaque jour
0 <= R < 100 000, le nombre de périodes pour lesquelles il faut calculer le nombre de visiteurs

SORTIE

Pour chaque période (D,F), vous devez écrire un entier : le nombre de visiteurs venus dans le parc entre les jours D (inclus) et F (inclus).
EXEMPLE

entrée :

10 3
77 60 67 67 63 100 68 55 98 66
2 2
1 10
5 7
sortie :

60
721
231

Bonjour

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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
# Statistiques
def stat(fic):
	fp=open(fic, "r")
 
	# Récupération N et R
	(N, R)=(int(x) for x in fp.readline().split(" "))
 
	# Récupération nb visiteurs
	visiteurs=[int(x) for x in fp.readline().split(" ")]
	if len(visiteurs) != N:
		fp.close()
		raise IOError, "Le nombre (%d) de visiteurs ne correspond pas au nombre (%d) attendu" % (len(visiteurs), N)
	# if
 
	# Récupération périodes
	periode=[[int(x) for x in lig.split(" ")] for lig in fp]
	if len(periode) != R:
		fp.close()
		raise IOError, "Le nombre (%d) de périodes ne correspond pas au nombre (%d) attendu" % (len(periode), R)
	# if
 
	# Fichier traité
	fp.close()
 
	# Traitement de chaque periode (rappel, en Python un indice commence à 0 alors que dans le fichier il commence à 1 => -1 à chaque fois...)
	for p in periode: yield sum(visiteurs[p[0] - 1:p[1]])
# stat()
 
for x in stat("fic"):
	print x

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
moi@virtualux:~/bbb$ cat fic
10 3
77 60 67 67 63 100 68 55 98 66
2 2
1 10
5 7
moi@virtualux:~/bbb$ time python stat.py 
60
721
231
 
real	0m0.007s
user	0m0.004s
sys	0m0.004s

Accessoirement, je ne vois même pas à quoi servent les nombres N et R (moi je les ai utilisés comme test que le fichier avait bien autant d'info que prévu)...