Code : Sélectionner tout - Visualiser dans une fenêtre à part printf "%i\n" ${tab[@]} | awk 'BEGIN(dmin=1000000;} (NR>1){d=$1-prec; if (d<dmin) dmin=d;} {prec=$1;} END{print dmin;}'
Code : Sélectionner tout - Visualiser dans une fenêtre à part printf "%i\n" ${tab[@]} | awk 'BEGIN(dmin=1000000;} (NR>1){d=$1-prec; if (d<dmin) dmin=d;} {prec=$1;} END{print dmin;}'
Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
Okay Donc j'y suis presque !
J'ai ceci :
Et ça me renvoie 1000 tout le temps.. Comment se fait-ce ? ^^
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 read N for (( i=0; i<N; i++ )); do read n tab[$n]=$n done XX=$(printf "%i\n" ${tab[*]}) min=1000 for (( i=0; i<${#XX[*]}-1; i++ )); do if [ ${XX[$i+1]} - ${XX[$i]} < $min ]; then min=${XX[$i+1]} - ${XX[$i]} fi done echo $min
EDIT : Merci flodelarab pour cette ligne, j'ai remplacé une accolade par une parenthèse (après le BEGIN), ça fonctionne nickel et... ça passe enfin les 100 000 entiers très rapidement !
Merci beaucoup à vous deux pour votre aide et votre patience
Je n'ai pas déclaré mon tableau XX comme tu le fait sur la ligne 8 (ici tu perd du temps)
et tu n'as pas le droit de faire $i+1 directement, la syntaxe est ((i+1))
Cordialement.
La solution de flodelarab ne fonctionne pas si tous les nombres du tableau sont égaux, et je ne vois pas pourquoi, ça DEVRAIT fonctionner !
Et je viens de réessayer ta solution avec tes remarques disedorgue, et j'ai toujours une erreur de syntaxe :
J'ai, ligne 13 : "/tmp/Answer.sh: line 13: 1000: No such file or directory"
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 read N for (( i=0; i<N; i++ )); do read n tab[$n]=$n done XX=(${tab[*]}) min=1000 for (( i=0; i<${#XX[*]}-1; i++ )); do if [ ${XX[((i+1))]} - ${XX[$i]} < $min ]; then min=${XX[((i+1))]} - ${XX[$i]} fi done echo $min
Franchement, je ne comprends pas la logique dans la syntaxe de ce langage.
Voici le code complet:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14 #!/bin/bash read N for (( i=0; i<N; i++ )); do read n tab[$n]=$n done XX=(${tab[*]}) min=1000 for (( i=0; i<${#XX[*]}-1; i++ )); do (( ${XX[i+1]} - ${XX[i]} < min )) && min=$(( ${XX[i+1]} - ${XX[i]} )) done echo $min
Cordialement.
Ce code n'est pas assez rapide
J'ai ceci actuellement, qui est assez rapide :
Ce code est donc basé sur la dernière ligne qu'a posté flodelarab, qui est la seule façon de faire qui a été suffisamment rapide jusqu'à présent;
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 read N tousEgaux=1 prev=0 for (( i=0; i<N; i++ )); do read n tab[$n]=$n if (( $i > 0 && $n != $prev )); then tousEgaux=0 fi prev=$n done if (( $tousEgaux == 1 )); then echo 0 else printf "%i\n" ${tab[@]} | awk 'BEGIN{dmin=1000000;} (NR>1){d=$1-prec; if (d<dmin) dmin=d;} {prec=$1;} END{print dmin;}' fi
J'ai rajouté un test pour savoir si tous les nombres étaient égaux, dans ce cas la distance minimale est de 0.
Je pensais que la ligne de flodelarab était censée gérer ce cas, mais apparemment non (et je ne comprends toujours pas pourquoi... mais enfin bref)
Donc là, presque tous les feux sont au vert : il ne me reste qu'une seule phase à valider, c'est le fait que les nombres soient "dans le désordre";
Je ne comprends pas ce qu'ils veulent dire par là, puisque c'est un souci dont on s'occupe depuis le début et c'est particulièrement pour ça qu'on cherchait à trier le tableau !
La solution fonctionne très bien pour des nombres entrés dans le désordre, et pourtant, lorsque je lance le code sur la plateforme de tests, elle refuse la solution pour cette phase-là.
Je n'y comprends plus rien !
Est-ce que ça pourrait être parce que dans la liste de nombres entrés, que je ne connais pas à l'avance, il y a deux nombres égaux, et dans ce cas la méthode où l'on utilise les nombres en guise d'indices ne fonctionne plus puisque les clés du tableau ne sont plus uniques... ?
Une version de tri qui garde les doublons (en rouge ce qui change):
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 $ cat sort_n.sh #!/bin/bash read N for (( i=0; i<N; i++ )); do read n tab[$n]="$n ${tab[$n]}" done XX=(${tab[*]}) min=1000 for (( i=0; i<${#XX[*]}-1; i++ )); do (( ${XX[i+1]} - ${XX[i]} < min )) && min=$(( ${XX[i+1]} - ${XX[i]} )) done echo $min
Cordialement.
salut,
on parle de "perfs" mais chez moi l'algo proposé par disedorgue est excessivement lent, et en plus il ne fait pas le job comme il faudrait, la première valeur N n'est pas replacée dans le tableau trié en sortie
j'ai fait quelques tests de mon coté, déjà si on considère uniquement 100.000 nombres à trier et que l'ordi ne peut pas le faire en moins d'1 seconde c'est qu'il y a probablement un souci quelque part, j'ai commencé mes tests sur une machine cadencée à 1.6GHz et que ce soit avec sort, awk ou perl on est systématiquement en dessous de la seconde
du coup j'ai benché avec 10M de nombres histoire que ce soit un peu plus parlant, le résultat est sans appel : sort -n fichier s'en sort haut la main loin devant ses ptits copains
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 $ ./gen 100000 generation de 100000 nombre compris entre 0 et 10**6 dans le fichier datas.txt $ ./pouet real 0m0.438s # sort -n datas.txt > /dev/null real 0m0.908s # printf "%i\n" ${tab[*]} | sort -n > /dev/null real 0m0.519s # awk '{t[c++]=$1} END {n=asort(t,t2); for (i=1;i<=n;i++){print t2[i]}}' datas.txt > /dev/null real 0m0.451s # perl -we 'print sort {$a <=> $b} <>' datas.txt > /dev/null real 0m34.304s # { read N; for (( i=0; i<N; i++ )); do read n; t[$n]=$n; done; printf "%i\n" ${t[*]} > /dev/null};} < datas.txt real 0m0.715s # sed 's/ /\n/g' <<< ${tab[*]} | sort -n > /dev/null
il en ressort également que ce qui pose problème ce n'est pas le tri des nombres finalement, c'est leur accès en mémoire, et les tableaux bash sont trèèèès lents
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 $ ./gen 10000000 generation de 10000000 nombre compris entre 0 et 10**6 dans le fichier datas.txt $ ./pouet real 0m8.202s # sort -n datas.txt > /dev/null real 1m22.916s # printf "%i\n" ${tab[*]} | sort -n > /dev/null real 0m23.132s # awk '{t[c++]=$1} END {n=asort(t,t2); for (i=1;i<=n;i++){print t2[i]}}' datas.txt > /dev/null real 0m19.866s # perl -we 'print sort {$a <=> $b} <>' datas.txt > /dev/null real --- non mesuré --- real 0m55.502s # sed 's/ /\n/g' <<< ${tab[*]} | sort -n > /dev/nullà ce stade, j'aurais envie de demander des précisions sur le pourquoi du comment @eldoir;
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 # bench SANS tri, depuis ${tab[*]} ! (toujours sur 10M de nombres en entrée) $ ./pouet real 0m42.690s # printf "%i\n" ${tab[*]} > /dev/null real 0m38.640s # sed 's/ /\n/g' <<< ${tab[*]} > /dev/null real 0m32.935s # tr ' ' '\n' <<< ${tab[*]} > /dev/null
- est-ce qu'il s'agit d'un challenge lancé par un collègue, un exo donné par le prof, un impératif dans le cadre du boulot ?
- sur quelle machine la mesure est-elle réalisée (fréquence cpu) ?
- es-tu obligé de partir du tableau ${tab[]} dans bash ou peux-tu envisager de prendre un fichier contenant les nombres en entrée ?
- ...
Merci disedorgue pour ton explication sur les indices, du coup je conserve l'ancienne solution (on écrase les doublons) puisque la nouvelle n'est pas assez rapide...
Et je suis d'accord, mais quand le challenge c'est d'écrire dans un langage qui me prendrait masse temps à comprendre, surtout vu comme je trouve la syntaxe pourrie, sans vouloir troller, ça me gonfle un peu ^^
@BufferBob : Le fait que tu affirmes que sort -n était le plus rapide m'a fait repenser le problème, et je suis finalement arrivé à une solution qui marche, je n'ai plus rien à dire, 100% des objectifs sont atteints ! Tadaaaaa En fait c'était tout stupide :
Bien plus simple et court que ce que j'aurais imaginé
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 read N for (( i=0; i<N; i++ )); do read tab[i] done printf "%i\n" ${tab[@]} | sort -n | awk 'BEGIN{dmin=1000000;} (NR>1){d=$1-prec; if (d<dmin) dmin=d;} {prec=$1;} END{print dmin;}'
Je peux donc dire vraiment cette fois-ci, merci à tous de votre patience envers moi, et il en fallait vu comme je suis buté
Et la bonne soirée à vous ! (Et jouez à Codingame, c'est le bien ! )
J'ai jamais dis que c'était un algo rapide, le problème c'est qu'il est obligé de le faire en bash, donc...
Sinon, il fonctionne très bien, et il n'y a aucun oubli, le fameux premier N ne fais pas partie du tri, c'est le nombre d'éléments qui seront en entrée.
Pour ma part, je n'ai fait que respecter le but de faire du bash
Il est sur que pour de la "perf", je ne ferais pas les choses en shell.
Pour les tri, il faudrait que tu les refasses sans bypasser la boucle for+read (qui dans son cas semble être une obligation, enfin il me semble...)
Et pour information, dans son dernier post, il précise que c'est pour un challenge.
Cordialement.
non c'est lui qui le disait, c'est pour ça j'étais resté sur la problématique de départ en fait ^^
ok ! j'ai du louper des morceaux je crois mais du coup effectivement ca prend son sensSinon, il fonctionne très bien, et il n'y a aucun oubli, le fameux premier N ne fais pas partie du tri, c'est le nombre d'éléments qui seront en entrée.
(...)
dans son dernier post, il précise que c'est pour un challenge.
ben finalement à regarder les résultats la commande sort s'en tire plutôt très bien, pour aller plus vite... faut sortir le C et se lancer dans des rituels sataniques j'imagineIl est sur que pour de la "perf", je ne ferais pas les choses en shell.
Noooooon. En fait, "bash" est le premier des langages proposés pour ce jeu (ordre alphabétique). Il a cliqué dessus sans aucune connaissance.PS: Le but d'un challenge n'est-il pas de le résoudre soi-même ?
Je tiens à souligner que nous avions la bonne réponse dès le départ: chaque programme fait une chose et il le fait bien. Quand on veut trier, on utilise sort.
Enfin, j'ai essayé ce site avec éditeur vim et langage bash. Pour l'instant je trouve ça amusant.
Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
C'est gentil de me faire passer pour un c*n
Je me suis mis au langage Bash dans le seul et unique but d'obtenir un achievement.
Le dernier exercice de la section Facile demande en effet de résoudre le problème en Bash pour obtenir un achievement, en Bash et pas un autre langage.
Donc forcément, je n'ai aucune connaissance dans le langage et j'avais moyennement envie de suivre un tuto pendant toute une après-midi pour réussir le défi.
Surtout que vu la tronche de la solution (et la contre-intuitivité de la syntaxe, sans vouloir rager), ça m'aurait pris plus qu'une après-midi à trouver;
Au final, j'ai quand même suivi un tuto de 3 heures, qui m'a à peine servi à comprendre 15% de la solution finale.
Je ne me considère donc pas déméritant d'avoir trouvé la solution en grande partie grâce à vous, puisque l'effort fourni était là : j'ai passé des heures à essayer de faire marcher ce b*rdel
Et oui, de toutes manières, quel que soit le langage, l'éditeur de texte utilisé, et même l'exercice demandé, c'est toujours amusant. Pour peu qu'on soit passionné.
Le jeu me dit que ma solution fonctionne en Bash, je ne vais pas vérifier si c'est bien du Bash
Quelque part on peut l'interpréter comme de l'étroitesse d'esprit, mais ça peut aussi juste être que je n'ai pas du tout apprécié l'expérience.
Quelqu'un qui n'aime pas l'espagnol, il n'est pas obtus après tout, c'est juste qu'il n'aime pas l'espagnol Il serait obtus s'il disait qu'il n'aimait pas ça sans avoir cherché à le pratiquer.
Il est donc hors de question que je retouche à cette horreur, mais merci pour la précision
c'est tellement vrai.et bien, tu peux recommencer, parce que awk ce n'est pas du bash !
Tu ne devrais pas mépriser un système qui est beaucoup plus sain (chaque logiciel son expertise), adaptatif (on peut changer une brique sans refaire l'édifice), rapide (pas de plan sur 3 ans), que ton truc monolithique créé en c++ ou java.à cette horreur,
Évidemment, y a un ticket d'entrée pour ce langage. Mais ce ticket est-il plus cher qu'en c++ ou java ?
Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
En fait, je suis de l'avis de N_BaH, j'ai été voir le site, et c'est bien bash qui est écrit, le fait de spécifier le nom du shell induit en erreur sur le droit ou pas d'utiliser des commandes externes.
Car ici, en fait, rien n'empêche d'utiliser perl,python,C,... à partir du moment qu'on le lance depuis bash.
Et pour répondre à Flodelarab, on peut résoudre un challenge à plusieurs, mais la moindre des choses est que tout le monde participant à cette résolution soit au courant dés le départ.
Cordialement.
Mon Tutoriel sur la programmation «Python»
Mon Tutoriel sur la programmation «Shell»
Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
Et on poste ses codes entre balises [code] et [/code]
Si tu as besoin d'aide, il faut choisir le bon forum, python en l’occurrence
Cordialement.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager