Tri GNU tri stable lorsque tri ne connaît pas l'ordre de tri

18

J'ai un fichier à deux colonnes; le fichier est déjà trié comme je le souhaite dans la colonne 1. Je voudrais trier sur la colonne 2, dans chaque catégorie de la colonne 1. Cependant, sortne comprend pas l'ordre de tri de la colonne 1.

La manière normale (à partir de questions similaires ici sur la pile) serait la suivante:

sort --stable -k1,1 -k2,2n

Mais je ne peux pas spécifier le tri sur k1, car il est arbitraire.

Exemple d'entrée:

C 2
C 1
A 2
A 1
B 2 
B 1

et sortie:

C 1
C 2
A 1
A 2
B 1 
B 2
Evan Benn
la source

Réponses:

20

Vous pouvez utiliser awk pour démarrer un nouveau tri pour chaque bloc:

% awk -v cmd="sort -k2,2" '$1 != prev {close(cmd); prev=$1} {print | cmd}' foo
C 1
C 2
A 1
A 2
B 1
B 2
  • $1 != prev {close(cmd); prev=$1} - lorsque la valeur enregistrée est différente, nous avons un nouveau bloc, nous fermons donc tout précédemment commencé sort
  • {print | "sort -k2,2"}'dirige la sortie vers sort, la démarrant si elle n'est pas déjà en cours d'exécution (awk peut garder une trace des commandes qu'il démarre)
muru
la source
2
awk est vraiment incroyable. J'aime beaucoup plus que ce à quoi je m'attendais, qui était un awk decorate-sort-undecorate!
Evan Benn
J'ai essayé de comparer la performance de cette réponse à celle de l'autre réponse, je ne sais pas pourquoi celle-ci utilise plus de ressources ... Des idées? gist.github.com/EvanTheB/5b64eafb84eeaf51c289295ac06e1b0b
Evan Benn
Combien de runs avez-vous effectué en moyenne?
muru
Je n'ai pas fait de moyenne, mais je vois des temps d'exécution cohérents pendant que je répète et enquête.
Evan Benn
Voici un fichier similaire à ce que j'utilise si vous voulez enquêter:seq 30 | xargs -L1 bash -cs 'yes $1 | head -1000000 | paste - <(seq 1000000) | shuf' bash
Evan Benn
12

Vous pouvez utiliser une transformation schwartzienne (il s'agit essentiellement de l'approche décorer-trier-décorer que vous avez mentionnée dans un commentaire, mais probablement plus performante que la bonne réponse de muru en raison de l'utilisation d'une seule sortinvocation par opposition à plusieurs) - en utilisant awkajouter une colonne de préfixe qui incréments avec un changement de valeur dans la première colonne, trier par la colonne préfixe suivie de la "deuxième" colonne (dont la position ordinale a temporairement changé en 3raison de la présence de la colonne préfixe), et enfin se débarrasser de la colonne préfixe

awk '{print ($1 in a? c+0: ++c)"\t" $0; a[$1]}' file | sort -k1,1n  -k3,3 | cut -f 2-
iruvar
la source
Je suis surpris, mais vous avez raison, c'était plus rapide que l'autre réponse! 3 minutes contre 2 minutes sur mon fichier de 100 millions de lignes (~ 30 premières colonnes uniq).
Evan Benn
1
Pas besoin de conserver un tableau de la clé unique de la première colonne. Je pense que cela devrait être suffisant pour comparer la première colonne de la ligne actuelle avec la précédente.
Kusalananda
Quelque chose comme awk -v OFS="\t" '$1 != prev { key++ } { print key, $0; prev = $1 }(non testé).
Kusalananda