Bonjour,
J'ai besoin d'un algo de tri extrêmement rapide en bash, du genre qui mettrait moins d'une seconde à trier un tableau de 100 000 entiers compris entre 0 et 1 million.
Actuellement, j'ai ça :
J'ai pris la fonction sortnumbers sur le net bien sûr.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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 sortnumbers() { local array=( `echo "$@"` ) local -a l local -a g local -a e local x= if [ ${#array[@]} -lt 2 ]; then echo -n ${array[@]} else local pivot=${array[0]} for x in ${array[@]} do if [ $x -lt $pivot ] then l=( ${l[@]} $x ) elif [ $x -gt $pivot ] then g=( ${g[@]} $x ) else e=(${e[@]} $x) fi done echo "`sortnumbers "${l[@]}"` ${e[@]} `sortnumbers "${g[@]}"`" fi } read N for (( i=0; i<N; i++ )); do read tab[i] done sorted=($(sortnumbers "${tab[@]}")) min=$(( sorted[1]-sorted[0] )) for (( i=1; i<N-1; i++ )); do diff=$(( sorted[i+1] - sorted[i] )) if [ "$diff" -lt "$min" ]; then min=$diff fi done echo $min
Cet algo met plus de cinq secondes à s'exécuter chez moi, ce qui est beaucoup trop lent !
Alors vous allez me dire, "Pourquoi tu le fais en bash alors ? Il existe plein d'autres langages pour lesquels ce que tu veux faire sera bien plus rapide !"
Héhé oui mais si seulement c'était aussi simple...
Le défi qu'on m'a posé est justement de résoudre ceci en bash.
On m'a parlé du bucket sort, ça m'a l'air bien, mais étant une nouille en bash je n'ai aucune idée de la syntaxe pour l'implémenter.
P.S : Après la ligne 40, je parcours mon tableau et je fais le calcul du minimum de la distance entre deux entiers consécutifs; Cette étape est indispensable à la résolution du problème, mais je ne pense pas que la lenteur de l'algo vienne de là puisque cette étape ne peut pas être plus simple, je pense (complexité en O(n)).
Merci d'avance de vos réponses !
Partager