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

[disedorgue]

Bonjour,
Un exemple simple de tri de nombre en bash:

Code :

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

1
2
3
4
5
6
7
8
9
$ cat sort_n.sh
#!/bin/bash
read N
for (( i=0; i<N; i++ )); do
    read n
    tab[$n]=$n
done
echo "les nombres triés:"
printf "%i\n" ${tab[*]}

Et l'exemple d’exécution:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
$ ./sort_n.sh
5
9
1
10000
99
74
les nombres triés:
1
9
74
99
10000

[eldoir]

Merci à vous pour votre aide

@Floderalab J'ai appliqué ton exemple à mon cas, et le tri n'est toujours pas suffisamment rapide
Pour ce qui est de tes autres remarques :
- Je ne vois pas comment calculer la distance minimum entre deux valeurs parmi 100 000, sans utiliser un tableau trié !
- Comme je le disais, je n'ai pas choisi de faire ça en Bash, on me l'a imposé

[Flodelarab]

Il faut être cohérent. Soit on impose bash et on est clément sur la vitesse. Soit on impose la vitesse et on prend du C++.

Maintenant, la question de la distance minimum est intéressante et mériterait d'être posée dans le forum Algorithmes.

Je ne suis pas sûr qu'il faille trier pour avoir cette valeur. Par exemple:

Code :

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

1
2
$ awk '(NR==2){dmin=sqrt((a[2]-a[1])**2);} (NR>2){for (i in a) if ((a[i]+dmin>$1)&&(a[i]-dmin<$1)) dmin=sqrt((a[i]-$1)**2);} {a[NR]=$1;} END{print dmin;}' atrier.txt
2

Dans l'exemple, j'ai repris le même fichier atrier.txt que ci-dessus. La différence minimale est bien 2.
J'ai utilisé la racine carrée du carré pour éviter de redéfinir une fonction valeur absolue.

[eldoir]

Je ne suis pas sûr de savoir comment l'appliquer à mon cas...
Et, par exemple, je ne vois pas à quoi correspond $1, je croyais que c'était le premier paramètre d'une fonction mais ici je ne vois pas de fonction !

[Flodelarab]

Dans awk, $ suivi d'un nombre ou d'une variable étant un nombre désigne un champ de la ligne.
Ici, $1 désigne le premier champ.
NF étant le nombre de champ, $NF désigne le dernier champ.

Code :

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

1
2
3
4
1 Dieu
2 paires de lunettes
12 singes en armée
54 hiver

$1 vaudra, à chaque ligne, 1, 2, 12, ou 54.

Le script déjà donné prend le premier champ pour calculer la distance minimale.

[eldoir]

Ah ok ! Donc j'ai désormais ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
read N
 
$( touch atrier.txt )
 
for (( i=0; i<N; i++ )); do
    read tab[i]
    $( echo tab[i] >> atrier.txt )
done
 
$( awk '(NR==2){dmin=sqrt((tab[2]-tab[1])**2);} (NR>2){for (i in tab) if ((tab[i]+dmin>$1)&&(tab[i]-dmin<$1)) dmin=sqrt((tab[i]-$1)**2);} {tab[NR]=$1;} END{print dmin;}' atrier.txt )

Mais j'ai une syntax error que je ne comprends pas du tout : "awk: line 1: syntax error at or near *"
J'ai essayé de faire genre (tab[2]-tab[1])*(tab[2]-tab[1]) au lieu de (tab[2]-tab[1])**2, ça a résolu les erreurs mais ensuite j'avais un joli"/tmp/Answer.sh: line 10: 0: command not found"

Tu vas sûrement hurler en lisant ça et en te disant que je n'ai rien compris ^^
À vrai dire, puisque je ne voyais pas d'où sortait le tableau a alors que tu disais qu'il n'y avait pas besoin de tableau, je me suis dit que tu devais tout de même faire référence au tableau dans lequel je rentrais mes valeurs au début, donc j'ai remplacé a par tab dans la formule (j'avais déjà la syntax error avant ça) et ça ne fonctionne bien sûr toujours pas.
Mais je ne dois pas être loin... Si ?

[disedorgue]

Oui, la syntaxe n'est pas terrible, les $(....) ne sont utiles que si tu as besoin de mettre le résultat dans une variable par exemple, sinon pas la peine de faire ça, car tu ralentis entre autre ton process inutilement en appelant un sous shell.

Par contre, si tu continus à utiliser ta boucle pour tes données, pourquoi n'utilises-tu pas la forme que je t'ai donnée plus haut, au moins c'est trié implicitement ?

[eldoir]

Oui mais si j'enlève le $() autour du awk, je n'ai effectivement pas de syntax error mais en revanche le résultat n'est plus correct, il m'affiche 0 pour un tableau qui contient [5,8,9] alors qu'il devrait m'afficher 1...
Et si quand tu me parles de ta boucle, tu parles de ce code :

Code :

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

1
2
3
4
5
6
7
8
9
$ cat sort_n.sh
#!/bin/bash
read N
for (( i=0; i<N; i++ )); do
    read n
    tab[$n]=$n
done
echo "les nombres triés:"
printf "%i\n" ${tab[*]}

Je ne vois vraiment pas en quoi c'est différent de ce que je fais déjà, je veux dire, c'est la même chose... ?

[disedorgue]

Si c'était la même chose, tu aurais un tableau déjà trié, ce qui n'est pas le cas...

Si tu regardes bien mon exemple, l'index du tableau n'est pas le "i" de la boucle for mais la valeur ramené par le read.

[Flodelarab]

echo tab[i]

Ce n'est pas comme ça qu'on accède à un élément de tableau.

Code :

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

1
2
3
4
5
6
7
$ tab[5]=toto
$ echo tab[5]
tab[5]
$ echo $tab[5]
[5]
$ echo ${tab[5]}
toto

Evidemment, seule la dernière forme est valable.

[eldoir]

Aah effectivement j'avais pas fait gaffe désolé !
En plus c'est vachement fort

Sauf que, dernier problème (je l'espère), du coup je ne vois pas comment parcourir mon tableau pour calculer ma distance minimale, puisque je ne connais pas la valeur de mes indices à l'avance... ?
Vu que mes valeurs vont de 0 à 1 million, et que j'ai 100 000 valeurs, j'ai un tableau dont les indices sont un peu éparpillés si tu vois ce que je veux dire !
Genre par exemple, pour un tableau qui contient [5, 8, 9], comment faire ? J'ai 3 cases dans mon tableau, mais aux indices 5, 8 et 9...

[Flodelarab]

si tu vois ce que je veux dire

Pas du tout. Dans le tableau [5,8,9] les valeurs sont 5, 8 et 9, les indices sont 0, 1 et 2 ou 1, 2 et 3.

En plus c'est vachement fort

Ca veut dire quoi ? Que tu as appliqué le script et qu'il a sorti la distance minimale des 100.000 valeurs ?

J'ai 3 cases dans mon tableau, mais aux indices 5, 8 et 9.

Et alors ?

Code :

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

1
2
3
4
5
$ tab[5]=toto
$ tab[3]=tata
$ printf "%s\n" ${tab[@]}
tata
toto

[eldoir]

@Floderalab : Avec la méthode de disedorgue, qui est de faire tab[$n]=$n, j'ai bel et bien des indices éparpillés, si je rentre les valeurs 5, 8, 9, je vais bien avoir un tableau comme ceci :
tab[5] = 5
tab[8] = 8
tab[9] = 9
Donc quand je disais que c'était vachement fort, c'était que du coup ça triait implicitement mon tableau comme disedorgue le faisait remarquer : et du coup je n'ai plus à effectuer l'opération coûteuse de trier le tableau une fois qu'il est rempli.
J'étais donc enthousiaste puisque je sentais que ça pouvait résoudre mon problème de performance.
Mais je me suis vite rendu compte que du coup, pour calculer la distance minimale entre 2 valeurs de mon tableau, je risquais d'avoir un problème si je faisais une boucle for pour le parcourir pusiqu'il y aurait des cases du tableau qui seraient vides, par exemple ici, tab[0] est indéfini, tab[4] également etc.
J'ai essayé de faire un truc du genre for (( i in tab )), puisque j'ai vu que tu faisais ça dans awk, et que j'ai aussi l'habitude de le faire en C#, et bien sûr ça ne fonctionne pas, comme tout ce que je tente dans ce langage.

Donc quand tu remplis un tableau avec des indices arbitraires comme tu le fais dans ton dernier exemple, c'est nickel puisque le printf fonctionne quand même, sauf que je ne veux pas faire un printf, mais parcourir mon tableau pour calculer la distance minimale, donc je n'ai aucune idée de comment faire puisque je ne connais pas les indices à l'avance !

[disedorgue]

Pas difficile de résoudre ton problème d'indexe:

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
$ cat sort_n.sh
#!/bin/bash
read N
for (( i=0; i<N; i++ )); do
    read n
    tab[$n]=$n
done
echo "les nombres triés:"
printf "%i\n" ${tab[*]}
XX=(${tab[*]})
for (( i=0; i<${#XX[*]}; i++ )); do
echo "i=$i => XX[$i]=${XX[$i]}"
done
$ cat input.txt
5
9
2
10000
99
74
$ ./sort_n.sh <input.txt
les nombres triés:
2
9
74
99
10000
i=0 => XX[0]=2
i=1 => XX[1]=9
i=2 => XX[2]=74
i=3 => XX[3]=99
i=4 => XX[4]=10000