Matriz de ordenação Bash de acordo com o comprimento dos elementos?

9

Dada uma matriz de seqüências de caracteres, eu gostaria de classificar a matriz de acordo com o comprimento de cada elemento.

Por exemplo...

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

Deve classificar para ...

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

(Como um bônus, seria bom se a lista classificasse seqüências de caracteres do mesmo tamanho em ordem alfabética. No exemplo acima, medium stringfoi ordenada antes middle stringmesmo que sejam do mesmo tamanho. Mas esse não é um requisito "difícil", se complicar demais o solução).

Tudo bem se a matriz for classificada no local (por exemplo, "matriz" for modificada) ou se uma nova matriz classificada for criada.

PJ Singh
fonte
1
algumas respostas interessantes por aqui, você deve ser capaz de se adaptar um para teste para comprimento da corda bem stackoverflow.com/a/30576368/2876682
frostschutz

Respostas:

12

Se as seqüências de caracteres não contiverem novas linhas, o seguinte deve funcionar. Ele classifica os índices da matriz pelo comprimento, usando as próprias seqüências de caracteres como o critério de classificação secundária.

#!/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[@]}")

Observe que mudar para uma linguagem de programação real pode simplificar bastante a solução, por exemplo, no Perl, você pode simplesmente

sort { length $b <=> length $a or $a cmp $b } @array
choroba
fonte
1
Em Python:sorted(array, key=lambda s: (len(s), s))
wjandrea
1
Em Ruby:array.sort { |a| a.size }
Dmitry 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- )

Isso lê os valores da matriz classificada de uma substituição de processo.

A substituição do processo contém um loop. O loop gera cada elemento da matriz precedido pelo comprimento do elemento e um caractere de tabulação no meio.

A saída do loop é classificada numericamente do maior para o menor (e alfabeticamente se os comprimentos forem iguais; use -k 2rno lugar de -k 2para reverter a ordem alfabética) e o resultado disso é enviado para o cutqual exclui a coluna com os comprimentos de string.

Classifique o script de teste seguido por uma execução de teste:

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

Isso pressupõe que as seqüências não contenham novas linhas. Em sistemas GNU recentes bash, você pode oferecer suporte a novas linhas incorporadas nos dados usando o caractere nul como separador de registros em vez de nova linha:

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- )

Aqui, os dados são impressos com rastreamento \0no loop, em vez de novas linhas, sorte cutlê linhas delimitadas por nulas através de suas -zopções GNU e, readarrayfinalmente, lê os dados delimitados por nula -d ''.

Kusalananda
fonte
3
Observe que, -d '\0'na verdade -d '', bashnão é possível transmitir caracteres NUL para comandos, mesmo seus componentes internos. Mas entende -d ''como delimitar o significado em NUL . Observe que você precisa do bash 4.4+ para isso.
Stéphane Chazelas
@ StéphaneChazelas Não, não é '\0', é $'\0'. E sim, ele converte (quase exatamente) em ''. Mas essa é uma maneira de comunicar a outros leitores a intenção real de usar um delimitador NUL.
Isaac #
4

Não repetirei completamente o que já disse sobre a classificação no bash , apenas você pode classificar no bash, mas talvez não deva. Abaixo está uma implementação somente bash de uma classificação de inserção, que é O (n 2 ) e, portanto, só é tolerável para matrizes pequenas. Ele classifica os elementos da matriz no local pelo comprimento, em ordem decrescente. Não faz uma classificação alfabética secundária.

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

Como evidência de que esta é uma solução especializada, considere os tempos das três respostas existentes em várias matrizes de tamanho:

# 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 e Kusalananda têm a idéia certa: calcule os comprimentos uma vez e use utilitários dedicados para classificação e processamento de texto.

Jeff Schaller
fonte
4

Um hackish? (complexa) e rápida de uma linha para classificar a matriz por comprimento
( seguro para novas linhas e matrizes esparsas):

#!/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[@]}"

Em uma linha:

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

Em execução

$ ./script
the longest
        string also containing
        newlines
also a medium string
medium string
middle string
test * string
short string
tiny string
[abc]
?
*
Isaac
fonte
4

Isso também lida com elementos de matriz com novas linhas; funciona passando sortapenas o comprimento e o índice de cada elemento. Deve funcionar com bashe 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[@]}"

Se os elementos do mesmo comprimento também precisarem ser classificados lexicograficamente, o loop poderá ser alterado assim:

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

Isso também passará para sortas strings (com novas linhas alteradas para espaços), mas elas ainda serão copiadas da fonte para a matriz de destino por seus índices. Nos dois exemplos, $(...)ele verá apenas linhas contendo números (e o /caractere no primeiro exemplo), para que não seja disparado por caracteres ou espaços em movimento nas strings.

mosvy
fonte
Não pode se reproduzir. No segundo exemplo, a $(...)substituição de comando vê apenas os índices (uma lista de números separados por novas linhas), por causa do cut -d' ' -f1depois da classificação. Isso pode ser facilmente demonstrado por um tee /dev/ttyno final do $(...).
mosvy
Desculpe, meu mal, eu perdi o cut.
Stéphane Chazelas
@Isaac Não é necessário citar as expansões ${!in[@]}ou ${#in[i]}/$ivariáveis, pois elas contêm apenas dígitos que não estão sujeitos à expansão glob e unset IFSredefinirão o IFSespaço, a guia e a nova linha. De fato, citá-las seria prejudicial , porque causaria a falsa impressão de que essa citação é útil e eficaz, e que a configuração IFSe / ou filtragem da saída do sortsegundo exemplo poderia ser eliminada com segurança.
mosvy
@ Isaac NÃO quebra se incontém "testing * here"e shopt -s nullglobestá definido antes do loop.
mosvy
3

No caso de alternar para zshé uma opção, é uma maneira hackiana (para matrizes que contêm qualquer sequência de bytes):

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

zshpermite definir ordens de classificação para sua expansão glob através de qualificadores glob. Então, aqui, tentamos fazer isso para matrizes arbitrárias observando /, mas substituindo /pelos elementos da matriz ( e'{reply=("$array[@]")}') e, em seguida, numericamente rder o(ao contrário com maiúsculas O) os elementos com base em seu comprimento ( Oe'{REPLY=$#REPLY}').

Observe que é baseado no tamanho do número de caracteres. Para o número de bytes, defina o código do idioma para C( LC_ALL=C).

Outra bashabordagem 4.4+ (assumindo uma matriz não muito grande):

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

(isso é comprimento em bytes ).

Nas versões mais antigas do bash, você sempre pode:

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

(que também iria trabalhar com ksh93, zsh, yash, mksh).

Stéphane Chazelas
fonte