quicksort de fichier

Version imprimable

Bonjour,
je dois coloriser un nuage de point en 3D en fonction de son altitude. Je m'explique : j'ai un fichier .txt contenant plusieurs milliers (voir million) de points, une ligne par point, et chaque ligne contient le X, le Y et le Z espacé par des espaces.
ex :
1418361.400 4187958.200 -3.372
1418361.600 4187958.200 -3.472
1418354.000 4187958.400 -1.667
1418354.200 4187958.400 -1.686
1418355.000 4187958.400 -2.047
1418355.200 4187958.400 -2.146

Je possède également une liste de n valeurs qui me servent d'intervalle de sélection pour le tri, et une matrice (n,3) contenant le code RGB correspondant aux valeurs.
ex de liste d'intervalles:
[-20. -19. -18. -17. -16. -15. -14. -13. -12. -11. -10. -9. -8. -7. -6. -5. -4. -3. -2. -1. 0.]
exemple de matrice de code RGB:
[[ 0. 0. 255.]
[ 0. 43. 255.]
[ 0. 85. 255.]
[ 0. 128. 255.]
[ 0. 170. 255.]
[ 0. 213. 255.]
[ 0. 255. 255.]
[ 0. 226. 204.]
[ 0. 204. 153.]
[ 0. 172. 102.]
[ 0. 153. 51.]
[ 0. 128. 0.]
[ 51. 154. 0.]
[ 102. 179. 0.]
[ 153. 205. 0.]
[ 204. 230. 0.]
[ 255. 255. 0.]
[ 255. 191. 0.]
[ 255. 127. 0.]
[ 255. 63. 0.]
[ 255. 0. 0.]]

Ainsi, si l'altitude du point (le Z) est compris entre -20 et -19, le code RGB [0 0 255] lui sera attribué.

Le but du jeu est donc de lire le fichier txt, de regarder la valeur de l'altitude de chaque point et de lui attribuer le code RGB correspondant, puis d'enregistrer la nouvelle donnée dans un second fichier texte sous la forme (X Y X R G B). Ainsi, les points précédent donneront le fichier suivant:
1418361.400 4187958.200 -3.372 255 255 0
1418361.600 4187958.200 -3.472 255 255 0
1418354.000 4187958.400 -1.667 255 127 0
1418354.200 4187958.400 -1.686 255 127 0
1418355.000 4187958.400 -2.047 255 191 0
1418355.200 4187958.400 -2.146 255 191 0

Mon code marche mais je souhaiterais l'optimiser car il est actuellement très long d’exécution (plusieurs minutes voir dizaine de minutes en fonction du nombre de points et du nombre d'intervalles).
Le fichier texte initial étant potentiellement très grand, je ne peux pas le mettre directement dans un matrice à l'aide d'un genfromtxt par exemple pour ensuite faire un tri des points en fonction de l'altitude puis leur appliquer la couleur par intervalle. Je n'ai pas également pas trouvé comment trier directement le fichier sans l'ouvrir.
J'ai essayer des fonctions récursives mais elles ne sont pas beaucoup plus rapide ...
Je n'ai pas trouvé de solution plus rapide que de lire le fichier ligne par ligne, de regarder l'altitude du point, et d'écrire le point (X, Y, et Z) et son code RGB dans un autre fichier, avant de passer à la seconde ligne.
Voici mon code, savez-vous comment je pourrais l'optimiser ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 fichier_source = file('points_init.txt', "r") fichier_destination = file('points_couleur.txt', 'w') for ligne in fichier_source: M = np.matrix(ligne) if M[0,2] < intervalle[1]: fichier_destination.write("%.3f %.3f %.3f %i %i %i\n" %(M[0,0], M[0,1], M[0,2], couleur[0,0], couleur[0,1], couleur[0,2]) ) if M[0,2] >= intervalle[-1]: fichier_destination.write("%.3f %.3f %.3f %i %i %i\n" %(M[0,0], M[0,1], M[0,2], couleur[-1,0], couleur[-1,1], couleur[-1,2]) ) for i in range(1, len(couleur)-2): if M[0,2] >= intervalle[i] and M[0,2] < intervalle[i+1]: fichier_destination.write("%.3f %.3f %.3f %i %i %i\n" %(M[0,0], M[0,1], M[0,2], couleur[i,0], couleur[i,1], couleur[i,2]) ) fichier_source.close() fichier_destination.close()

06/12/2016, 09h13
IPreferCSharp

Bonjour,

Tu peux essayer de découper ton fichier en plusieurs parties et de lancer le traitement de chaque parties dans un processus indépendant avec la lib multiprocessing puis de récupérer le résultat du traitement dans ton script principal, ça devrai accélérer grandement ce traitement.

Quelques ressources :
https://github.com/ioga/mp-merge-sor...ster/pmsort.py
https://devopslog.wordpress.com/2012...ltiprocessing/
http://sebastianraschka.com/Articles...rocessing.html

Salut,

Sans faire usage de numpy (pas compris l'utilité d'ailleurs), j'arrive à ces résultats:

Code:

1
2
3
4
5
 
Données     temps (secondes)
   60.000   1.73152494430542
  600.000   17.942829132080078
6.000.000   171.1435091495514

La progression est linéaire, elle peut donc être anticipée.

Python3

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
 
# -*- coding: utf-8 -*-
 
import time
 
ALT = [-20, -19, -18, -17, -16, -15, -14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0]
COLORS = [[0, 0, 255],
[0, 43, 255],
[0, 85, 255],
[0, 128, 255],
[0, 170, 255],
[0, 213, 255],
[0, 255, 255],
[0, 226, 204],
[0, 204, 153],
[0, 172, 102],
[0, 153, 51],
[0, 128, 0],
[51, 154, 0],
[102, 179, 0],
[153, 205, 0],
[204, 230, 0],
[255, 255, 0],
[255, 191, 0],
[255, 127, 0],
[255, 63, 0],
[255, 0, 0]]
 
def get_pos(value):
    ALT.append(value)
    ALT.sort()
    pos = ALT.index(value)
    ALT.pop(pos)
    return pos
 
# on crée un fichier de 6.000.000 de ligne de données
data = "1418361.400 4187958.200 -3.372\n"\
"1418361.600 4187958.200 -3.472\n"\
"1418354.000 4187958.400 -1.667\n"\
"1418354.200 4187958.400 -1.686\n"\
"1418355.000 4187958.400 -2.047\n"\
"1418355.200 4187958.400 -2.146\n" * 1000000
with open('data.txt', 'w') as outf:
    outf.write(data)
 
del data
 
begin = time.time()
with open('result.txt', 'w') as outf:
    with open('data.txt', 'r') as inf:
        for line in inf:
            x, y, z = line.strip().split(' ')
            color = ' '.join([str(i) for i in COLORS[get_pos(float(z))]])
            outf.write("%s %s\n" %(line.strip(), color))
 
print(time.time() - begin, 'sec.')

06/12/2016, 13h39
Charlomètre

bonjour,
merci beaucoup pour vos réponse, je retiens pour ce programme celle de VinsS mais celle de IPreferCSharp pourra me servir pour d'autres codes.
Merci beaucoup
07/12/2016, 20h19
dividee

Citation:

Envoyé par VinsS

Sans faire usage de numpy (pas compris l'utilité d'ailleurs), j'arrive à ces résultats:

Si si si, numpy peut être utile ;)

Un tableau numpy possède la méthode searchsorted qui fait l'équivalent de la fonction get_pos:
En changeant la définition de ALT par

Code:

ALT = np.array([-20, -19, -18, -17, -16, -15, -14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0], dtype=np.double)

et la ligne qui appelle get_pos par

Code:

color = ' '.join([str(i) for i in COLORS[ALT.searchsorted(float(z))]])

cela permet d'améliorer un peu les performances (de 67 à 47 secondes pour 6 millions d'entrées sur mon PC).

La méthode searchsorted permet de traiter un tableau d'éléments à rechercher qui pourrait permettre d'améliorer encore les performances, mais cela devient difficile car la majorité du temps n'est pas passé dans cette méthode mais dans le code l'environnant.

Salut dividee,

En fait c'est en voyant le code de l'OP que je me suis dis qu'il avait bien compliqué son code avec numpy.

Mais après réflexion, je me suis rendu compte qu'une simple modification des données constantes pouvait drastiquement modifier les performances.

Comme ceci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
# -*- coding: utf-8 -*-
 
import time
 
ALT = [-20, -19, -18, -17, -16, -15, -14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0]
COLORS = ['0 0 255', '0 43 255', '0 85 255', '0 128 255', '0 170 255', 
          '0 213 255', '0 255 255', '0 226 204', '0 204 153', '0 172 102', 
          '0 153 51', '0 128 0', '51 154 0', '102 179 0', '153 205 0', 
          '204 230 0', '255 255 0', '255 191 0', '255 127 0', '255 63 0', 
          '255 0 0']
 
begin = time.time()
with open('result.txt', 'w') as outf:
    with open('data.txt', 'r') as inf:
        for line in inf:
            _, _, z = line.strip().split(' ')
            color = COLORS[ALT.index(int(float(z)))]
            outf.write("%s %s\n" %(line.strip(), color))
 
print(time.time() - begin, 'sec.')

Je l'ai testé quatre fois avec 6.000.000 de lignes de données.

Code:

1
2
3
4
5
6
7
8
9
 
vincent@tiemoko:~/test$ python3 altitude.py 
68.61417078971863 sec.
vincent@tiemoko:~/test$ python3 altitude.py 
62.651641845703125 sec.
vincent@tiemoko:~/test$ python3 altitude.py 
69.07437109947205 sec.
vincent@tiemoko:~/test$ python3 altitude.py 
63.70541000366211 sec.

08/12/2016, 11h07
dividee

Salut VinsS,

C'est bien vu pour le stockage de couleurs sous forme de chaînes, mais utiliser index pour retrouver l'intervalle c'est un peu de la triche, ça ne fonctionne que si tous les intervalles sont de taille unitaire, contrairement à get_pos / searchsorted.
On pourrait aussi bien écrire int(float(z))+20 dans ce cas.
08/12/2016, 11h27
VinsS

Citation:

Envoyé par dividee

On pourrait aussi bien écrire int(float(z))+20 dans ce cas.

Et je n'avais pas vu ça, honte à moi.