Tablica sortowania według Bash według długości elementów?

9

Biorąc pod uwagę tablicę ciągów, chciałbym posortować tablicę według długości każdego elementu.

Na przykład...

    array=(
    "tiny string"
    "the longest string in the list"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
    )

Powinien sortować do ...

    "the longest string in the list"
    "also a medium string"
    "medium string"
    "middle string"
    "short string"
    "tiny string"

(Jako bonus, byłoby miło, gdyby lista posortowała ciągi o tej samej długości, alfabetycznie. W powyższym przykładzie medium stringzostała posortowana wcześniej, middle stringmimo że są one tej samej długości. Ale to nie jest „trudne” wymaganie, jeśli nadmiernie komplikuje rozwiązanie).

Jest OK, jeśli tablica jest sortowana na miejscu (tj. „Tablica” jest modyfikowana) lub jeśli tworzona jest nowa sortowana tablica.

PJ Singh
źródło
1
kilka ciekawych odpowiedzi tutaj, powinieneś być w stanie dostosować jedną do testowania długości łańcucha, a także stackoverflow.com/a/30576368/2876682
frostschutz

Odpowiedzi:

12

Jeśli ciągi nie zawierają znaków nowej linii, poniższe powinny działać. Sortuje indeksy tablicy według długości, używając samych łańcuchów jako dodatkowego kryterium sortowania.

#!/bin/bash
array=(
    "tiny string"
    "the longest string in the list"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
)
expected=(
    "the longest string in the list"
    "also a medium string"
    "medium string"
    "middle string"
    "short string"
    "tiny string"
)

indexes=( $(
    for i in "${!array[@]}" ; do
        printf '%s %s %s\n' $i "${#array[i]}" "${array[i]}"
    done | sort -nrk2,2 -rk3 | cut -f1 -d' '
))

for i in "${indexes[@]}" ; do
    sorted+=("${array[i]}")
done

diff <(echo "${expected[@]}") \
     <(echo "${sorted[@]}")

Zauważ, że przejście na prawdziwy język programowania może znacznie uprościć rozwiązanie, np. W Perlu możesz to zrobić

sort { length $b <=> length $a or $a cmp $b } @array
choroba
źródło
1
W Pythonie:sorted(array, key=lambda s: (len(s), s))
wjandrea
1
W Ruby:array.sort { |a| a.size }
Dmitrij Kudriavtsev,
9
readarray -t array < <(
for str in "${array[@]}"; do
    printf '%d\t%s\n' "${#str}" "$str"
done | sort -k 1,1nr -k 2 | cut -f 2- )

Odczytuje wartości posortowanej tablicy z podstawienia procesu.

Podstawienie procesu zawiera pętlę. Pętla wyprowadza każdy element tablicy poprzedzony długością elementu i znakiem tabulacji pomiędzy nimi.

Sygnał wyjściowy obwodu jest sortowana liczbowo od największej do najmniejszej (a w porządku alfabetycznym, jeśli rozmiary są takie same, użycie -k 2rzamiast -k 2odwrócenia kolejności alfabetycznej) oraz wynik , który jest wysyłany do cutktórego usuwa kolumnę długości ciągów.

Posortuj skrypt testowy, a następnie uruchom testowy:

array=(
    "tiny string"
    "the longest string in the list"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
)

readarray -t array < <(
for str in "${array[@]}"; do
    printf '%d\t%s\n' "${#str}" "$str"
done | sort -k 1,1nr -k 2 | cut -f 2- )

printf '%s\n' "${array[@]}"
$ bash script.sh
the longest string in the list
also a medium string
medium string
middle string
short string
tiny string

Zakłada się, że ciągi nie zawierają znaków nowej linii. W systemach GNU z najnowszymi bashwersjami możesz obsługiwać osadzone znaki nowej linii w danych, używając znaku nul jako separatora rekordów zamiast znaku nowego wiersza:

readarray -d '' -t array < <(
for str in "${array[@]}"; do
    printf '%d\t%s\0' "${#str}" "$str"
done | sort -z -k 1,1nr -k 2 | cut -z -f 2- )

Tutaj dane są drukowane z ciągiem \0w pętli zamiast nowego wiersza, sorti cutodczytuje linie rozdzielane zerami przez ich -zopcje GNU, a na readarraykoniec odczytuje dane rozdzielane zerami -d ''.

Kusalananda
źródło
3
Należy zauważyć, że -d '\0'w rzeczywistości jest -d ''jak bashnie można przekazać znaki NUL na polecenia, nawet jego builtins. Ale to rozumie -d ''jako oznaczające delimit na NUL . Zauważ, że potrzebujesz do tego bash 4.4+.
Stéphane Chazelas,
@ StéphaneChazelas Nie, nie jest '\0', jest $'\0'. I tak, konwertuje (prawie dokładnie) do ''. Ale to jest sposób, aby porozumieć się z innymi czytelnikami rzeczywista intencja przy użyciu separatora NUL.
Izaak
4

Nie będę całkowicie powtórzyć to, co już mówiłem o sortowaniu w bash , tylko ty możesz posortować ciągu bash, ale być może nie należy. Poniżej znajduje się tylko implementacja typu bash typu wstawiania, która jest O (n 2 ), a zatem jest tolerowana tylko dla małych tablic. Sortuje elementy tablicy w miejscu według ich długości, w malejącej kolejności. Nie wykonuje wtórnego sortowania alfabetycznego.

array=(
    "tiny string"
    "the longest string in the list"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
    )

function sort_inplace {
  local i j tmp
  for ((i=0; i <= ${#array[@]} - 2; i++))
  do
    for ((j=i + 1; j <= ${#array[@]} - 1; j++))
    do
      local ivalue jvalue
        ivalue=${#array[i]}
        jvalue=${#array[j]}
        if [[ $ivalue < $jvalue ]]
        then
                tmp=${array[i]}
                array[i]=${array[j]}
                array[j]=$tmp
        fi
    done
  done
}

echo Initial:
declare -p array

sort_inplace

echo Sorted:
declare -p array

Jako dowód na to, że jest to wyspecjalizowane rozwiązanie, rozważ czasy istniejących trzech odpowiedzi dla tablic o różnych rozmiarach:

# 6 elements
Choroba: 0m0.004s
Kusalananda: 0m0.004s
Jeff: 0m0.018s         ## already 4 times slower!

# 1000 elements
Choroba: 0m0.004s
Kusalananda: 0m0.004s
Jeff: 0m0.021s        ## up to 5 times slower, now!

5000 elements
Choroba: 0m0.004s
Kusalananda: 0m0.004s
Jeff: 0m0.019s

# 10000 elements
Choroba: 0m0.004s
Kusalananda: 0m0.006s
Jeff: 0m0.020s

# 99000 elements
Choroba: 0m0.015s
Kusalananda: 0m0.012s
Jeff: 0m0.119s

Choroba i Kusalananda mają dobry pomysł: oblicz raz długości i użyj dedykowanych narzędzi do sortowania i przetwarzania tekstu.

Jeff Schaller
źródło
4

Hackish? (złożony) i szybki sposób jednoliniowy do sortowania tablicy według długości
( bezpieczny dla znaków nowej linii i rzadkich tablic):

#!/bin/bash
in=(
    "tiny string"
    "the longest
        string also containing
        newlines"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
    "test * string"
    "*"
    "?"
    "[abc]"
)

readarray -td $'\0' sorted < <(
                    for i in "${in[@]}"
                    do     printf '%s %s\0' "${#i}" "$i";
                    done |
                            sort -bz -k1,1rn -k2 |
                            cut -zd " " -f2-
                    )

printf '%s\n' "${sorted[@]}"

W jednej linii:

readarray -td $'\0' sorted < <(for i in "${in[@]}";do printf '%s %s\0' "${#i}" "$i"; done | sort -bz -k1,1rn -k2 | cut -zd " " -f2-)

Po wykonaniu

$ ./script
the longest
        string also containing
        newlines
also a medium string
medium string
middle string
test * string
short string
tiny string
[abc]
?
*
Izaak
źródło
4

To także obsługuje elementy tablicy z nowymi liniami; działa, przechodząc sorttylko przez długość i indeks każdego elementu. Powinien współpracować z bashi ksh.

in=(
    "tiny string"
    "the longest
        string also containing
        newlines"
    "middle string"
    "medium string"
    "also a medium string"
    "short string"
)
out=()

unset IFS
for a in $(for i in ${!in[@]}; do echo ${#in[i]}/$i; done | sort -rn); do
        out+=("${in[${a#*/}]}")
done

printf '"%s"\n' "${out[@]}"

Jeśli elementy o tej samej długości również muszą zostać posortowane leksykograficznie, pętla może zostać zmieniona w następujący sposób:

IFS='
'
for a in $(for i in ${!in[@]}; do printf '%s\n' "$i ${#in[i]} ${in[i]//$IFS/ }"; done | sort -k 2,2nr -k 3 | cut -d' ' -f1); do
        out+=("${in[$a]}")
done

To również przejdzie do sortłańcuchów (z nowymi wierszami zamienionymi na spacje), ale nadal będą kopiowane ze źródła do tablicy docelowej przez ich indeksy. W obu przykładach $(...)będą widoczne tylko wiersze zawierające liczby (i /znak w pierwszym przykładzie), więc nie zostaną wyzwolone przez globbing znaków lub spacji w łańcuchach.

mosvy
źródło
Nie można odtworzyć. W drugim przykładzie $(...)podstawienie polecenia widzi tylko indeksy (listę liczb oddzielonych znakami nowej linii), ze względu cut -d' ' -f1na sortowanie po. Można to łatwo wykazać tee /dev/ttyna końcu $(...).
mosvy
Przepraszam, mój zły, brakowało mi cut.
Stéphane Chazelas,
@Isaac Nie ma potrzeby cytowania rozszerzeń ${!in[@]}lub ${#in[i]}/$izmiennych, ponieważ zawierają one tylko cyfry, które nie podlegają globalnej ekspansji, i unset IFSzresetują IFSspację, tabulator, nowy wiersz. W rzeczywistości, cytowanie ich byłoby szkodliwe , ponieważ dawałoby fałszywe wrażenie, że takie cytowanie jest użyteczne i skuteczne, i że ustawienie IFSi / lub filtrowanie wyników sortw drugim przykładzie może być bezpiecznie zniesione.
mosvy
@Isaac NIE psuje się, jeśli inzawiera "testing * here"i shopt -s nullglobjest ustawiony przed pętlą.
mosvy 21.11.18
3

W przypadku, gdy przejście do zshjest opcją, hackish droga tam (dla tablic zawierających dowolną sekwencję bajtów):

array=('' blah $'x\ny\nz' $'x\0y' '1 2 3')
sorted_array=( /(e'{reply=("$array[@]")}'nOe'{REPLY=$#REPLY}') )

zshpozwala definiować porządki sortowania dla jego globalnej ekspansji za pomocą globalnych kwalifikatorów. Więc tu jesteśmy oszukując go zrobić to dla dowolnych macierzy przez globbing na /, ale zastępując /z elementami macierzy ( e'{reply=("$array[@]")}'), a następnie numerically order (w odwrotnej z dużą literą O) elementów na podstawie ich długości ( Oe'{REPLY=$#REPLY}').

Pamiętaj, że jest to oparte na długości w liczbie znaków. Dla liczby bajtów ustaw ustawienia regionalne na C( LC_ALL=C).

Kolejne bashpodejście 4.4+ (przy założeniu niezbyt dużej tablicy):

readarray -td '' sorted_array < <(
  perl -l0 -e 'print for sort {length $b <=> length $a} @ARGV
              ' -- "${array[@]}")

(to długość w bajtach ).

W starszych wersjach bashzawsze możesz:

eval "sorted_array=($(
    perl -l0 -e 'for (sort {length $b <=> length $a} @ARGV) {
      '"s/'/'\\\\''/g"'; printf " '\'%s\''", $_}' -- "${array[@]}"
  ))"

(który będzie również współpracować z ksh93, zsh, yash, mksh).

Stéphane Chazelas
źródło