Discussion :

[eldoir]

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 :

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

J'ai pris la fonction sortnumbers sur le net bien sûr.

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 !

[Flodelarab]

Bonjour

"Trier" = "to sort"

Chaque programme ne fait qu'une chose et il le fait bien.

En quoi la commande sort ne comble pas tes attentes ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
$ cat atrier.txt
23 toto
25 tata
13 titi
5 tutu
7 tete
$ sort -n atrier.txt
5 tutu
7 tete
13 titi
23 toto
25 tata

[eldoir]

Salut à toi,
Et merci de ta réponse rapide ,
Il me semble que j'avais essayé et que ça n'était pas assez rapide.
Et j'ai beau essayer dans tous les sens, j'ai des erreurs de syntaxe tout le temps... !
J'ai essayé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

echo ${tab[@]} | sort -n

Mais ça ne semble pas fonctionner...

[Flodelarab]

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
$ toto=( 9 8 7 6 5 4 3 2 1 )
$ echo ${toto[3]}
6
$ echo ${toto[@]}
9 8 7 6 5 4 3 2 1
$ printf "%i\n" ${toto[@]}
9
8
7
6
5
4
3
2
1
$ printf "%i\n" ${toto[*]} |sort -n
1
2
3
4
5
6
7
8
9

Donc, en supposant que le nombre est dans la première colonne:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

printf "%i\n" ${tab[@]} |sort -n

[eldoir]

Ah ok
Mais si j'ai besoin de récupérer ce tableau trié ?
Pour faire mon calcul de minimum après, justement !
J'ai essayé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
sorted=${tab[@]} |sort -n
echo ${sorted[@]}

Çą n'a pas fonctionné...

[Flodelarab]

Plusieurs choses:

• Bash est un langage de script. Tu résonnes comme si tu faisais un programme C++/Java/Python.
  Moi, je n'aurais pas créé de tableau.
• Bash est un langage de script. Lent mais parfait pour des petites moulinettes. Si tu veux de la grande vitesse, pas sûr que ce soit ce qu'il convient d'utiliser.
• Quelle est la finalité ?
  On voit beaucoup d'utilisateurs qui découpent en petites marches (longues et hétérogènes), alors qu'un outil fait ça en une ligne.
• Pour récupérer la sortie standard d'une commande, ce n'est comme tu fais. Mais plutôt.
  

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  variable=$(commande)

• Ici, tu ne veux pas récupérer le fichier. Mais remplir un tableau avec un fichier.
  

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  $ ma_sortie=($(printf "%i\n" ${toto[@]} |sort -n ))
  $ echo ${ma_sortie[3]}
  4