Início / coding / Perguntas / 79009885
Accepted
dawg
Asked: 2024-09-21 23:20:22 +0800 CST

Gerar muitas strings alfanuméricas aleatórias

  • 772

De dentro do awk, quero gerar uma sequência de X caracteres alfanuméricos razoavelmente aleatórios (ou seja, aleatórios, mas não criptográficos) sob demanda e rapidamente.

Em Ruby, eu poderia fazer isso:

ruby -e '
def rand_string(len, min=48, max=123, pattern=/[[:alnum:]]/)
    rtr=""
    while rtr.length<len do
        rtr+=(0..len).map { (min + rand(max-min)).chr }.
            select{|e| e[pattern] }.join
    end                     # falls out when min length achieved 
    rtr[0..len]
end

(0..5).each{|_| puts rand_string(20)}'

Impressões:

7Ntz5NF5juUL7tGmYQhsc
kaOzO1aIxkW5rmJ9CaKtD
49SpdFTibXR1WPWV7li6c
PT862YZQd0dOIaFOIY0d1
vYktRXkdsj38iH3s2WKI
3nQZ7cCVEXvoaOZvm6mTR

Para uma comparação de tempo, o Ruby pode produzir 1.000.000 de strings exclusivas (sem duplicatas) em aproximadamente 9 segundos.

Levando isso em consideração, tentei no awk:

awk -v r=$RANDOM '
# the r value will only be a new seed each invocation -- not each f call
function rand_string(i) {
    s=""
    min=48
    max=123
    srand(r)
    while (length(s)<i) {
        c=sprintf("%c", int(min+rand()*(max-min+1)))
        if (c~/[[:alnum:]]/) s=s c
    }
    return s
}
BEGIN{ for (i=1; i<=5; i++) {print rand_string(20)}}'

Isso não funciona -- mesma semente, mesmo resultado de string. Imprime:

D65CsI55zTsk5otzSoJI
D65CsI55zTsk5otzSoJI
D65CsI55zTsk5otzSoJI
D65CsI55zTsk5otzSoJI
D65CsI55zTsk5otzSoJI

Agora tente ler /dev/urandomcom od:

awk '
function rand_string(i) {
    arg=i*4
    cmd="od -A n -t u1 -N " arg " /dev/urandom"  # this is POSIX
    #             ^  ^                unsigned character
    #                   ^  ^          count of i*4 bytes
    s=""
    min=48
    max=123
    while (length(s)<i) {
        while((cmd | getline line)>0) {
            split(line, la)
            for (e in la) {
                if (la[e]<min || la[e]>max) continue
                c=sprintf("%c", la[e])
                if (c~/[[:alnum:]]/) s=s c
            }
        }
        close(cmd)
    }
    return substr(s,1,i)
}
BEGIN {for(i=1;i<=5;i++) print rand_string(20) }'

Isso funciona como desejado. Imprime:

sYY195x6fFQdYMrOn1OS
9mv7KwtgdUu2DgslQByo
LyVvVauEBZU2Ad6kVY9q
WFsJXvw8YWYmySIP87Nz
AMcZY2hKNzBhN1ByX7LW

Mas agora o problema é que o pipe od -A n -t u1 -N " arg " /dev/urandomestá muito lento — inutilizável, exceto para um número trivial de strings.

Alguma ideia de como posso modificar um desses awks para que ele:

  1. Funciona na maioria das plataformas (ou seja, kit POSIX padrão);
  2. Pode produzir sequências razoavelmente aleatórias de comprimento X rapidamente.

Esta pergunta já foi feita algumas vezes:

  1. Como posso substituir uma string por uma string alfanumérica aleatória de 48 caracteres usando o awk onde a resposta é usar ferramentas externas -- muito lento;
  2. Substitua o padrão fornecido por um aleatório com awk, mas esse é um int aleatório e não usa srand;
  3. Execute um comando (para gerar strings aleatórias) dentro do awk , mas novamente use o shell pipe (muito lento) e somente Linux.
bash

5 respostas

  1. Best Answer

    Não tenho acesso ao Ruby, mas no meu sistema (aparentemente lento!) o script awk da resposta do @dawgs leva 24 segundos para ser executado, enquanto este leva 5 segundos:

    $ cat tst.sh
#!/usr/bin/env bash

time awk -v r=$RANDOM '
function rand_string(n,         s,i) {
    for ( i=1; i<=n; i++ ) {
        s = s chars[int(1+rand()*numChars)]
    }
    return s
}
BEGIN{
    srand(r)      # Use srand ONCE only
    for (i=48; i<=122; i++) {
        char = sprintf("%c", i)
        if ( char ~ /[[:alnum:]]/ ) {
            chars[++numChars] = char
        }
    }

    for (i=1; i<=1000000; i++) {print rand_string(20)}
}' | sort | uniq -c | awk '$1>1'


    $ ./tst.sh

real    0m5.078s
user    0m4.077s
sys     0m0.045s

    então se você quiser produzir muitas strings, crie primeiro uma matriz das letras possíveis e depois indexe a matriz usando rand()em vez de chamar sprintf()cada letra de cada string.

    Como tornar uma variável siterativamente maior é lento em termos de [re]alocação de memória, você pode tornar o script cerca de 20% mais rápido ainda definindo OFS=""cada $icaractere em vez de criar uma string:

    function rand_string(n,         i) {
    for ( i=1; i<=n; i++ ) {
        $i = chars[int(1+rand()*numChars)]
    }
    return $0
}


    $ ./tst2.sh

real    0m3.954s
user    0m3.420s
sys     0m0.015s

    contanto que você não precise $0de mais nada.

    • 6

  2. Pegue o awk 1 e faça isto:

    time awk -v r=$RANDOM '
function rand_string(i) {
    s=""
    min=48
    max=123
    #srand(r) Duh!! WRONG! Only use srand once or it resets to the same sequence
    while (length(s)<i) {
        c=sprintf("%c", int(min+rand()*(max-min+1)))
        if (c~/[[:alnum:]]/) s=s c
    }
    return s
}
BEGIN{ 
    srand(r)      # Use srand ONCE only
    for (i=1; i<=1000000; i++) {print rand_string(20)}
}'  1> /dev/null

real    0m6.690s
user    0m6.677s
sys 0m0.012s

    O que eu reescrevi (olhando para a resposta de Ed Morton) para ser:

    time awk -v r=$RANDOM '
function fill_buf(low, high,          i, char) {
    # We WANT chars and numChars to be global...
    for(i=low; i<=high; i++) {
        char = sprintf("%c", i)
        if ( char ~ /[[:alnum:]]/ ) {
            chars[++numChars] = char
        }
    }
}
function rand_string(n,         s,i) {
    if (numChars=="") fill_buf(48,123)
    for ( i=1; i<=n; i++ ) {
        s = s chars[int(1+rand()*numChars)]
    }
    return s
}
BEGIN{ 
    srand(r)      # Use srand ONCE only
    for (i=1; i<=1000000; i++) {print rand_string(20)}
}' 1> /dev/null 

real    0m6.765s
user    0m6.747s
sys 0m0.017s

    VS o Ruby (bastante melhorado):

    time ruby -e 'def rand_string(len, min=48, max=123, pat=/[[:alnum:]]/)
    # @tgt ||= means only run the first time this function is called
    @tgt ||= (min..max).map(&:chr).grep(pat)
    (1..len).map{ @tgt.sample }.join
end

1_000_000.times{puts rand_string(20)}' 1> /dev/null


real    0m1.634s
user    0m1.632s
sys 0m0.035s

    Então o Ruby é um pouco mais rápido — como esperado. (Mas se você usar gawkvs, awko gawk é concluído em 6,2 segundos.)

    Não tenho certeza se acredito no Ruby timing. Quando o executo em um servidor, é mais parecido com o gawk. Mas estou relatando. Apple M3 PowerBook.

    • 2 
  3. $ awk '
    function get20(){
        "tr -dc A-Za-z0-9 </dev/urandom | fold -b20" | getline s
        return s
    }
    BEGIN {
        for (i=1; i<=10; ++i)
            print get20()
    }
'
ds3bnaDUlYhxETdwTUwT
1OgMbkoAfcptTHG8guPd
RJQj2e1MbU1PVsQ0biGo
pAo7NlaOwXUSkgxG8ZAS
fESVcYBK5cBOBQxCDQ3T
ZZqE454jIiUc7oEtwPry
IX4WSw47pvbhoQ8zdXLy
pOM2bZjQVolek35nuCWt
deAa9ddHhGeX8FJGJFCb
NH5FTSWNKcvzYnTkvewM
$

    $ time gawk '
    function get20(){
        "tr -dc A-Za-z0-9 </dev/urandom | fold -b20" | getline s
        return s
    }
    BEGIN {
        for (i=1; i<=1000000; ++i)
            len += length(get20())
        print len
    }
'
20000000

real    0m0.522s
user    0m0.782s
sys 0m0.263s
$

    $ time mawk '
    function get20(){
        "tr -dc A-Za-z0-9 </dev/urandom | fold -b20" | getline s
        return s
    }
    BEGIN {
        for (i=1; i<=1000000; ++i)
            len += length(get20())
        print len
    }
'
20000000

real    0m0.534s
user    0m0.145s
sys 0m0.013s
$

    $ time busybox awk '
    function get20(){
        "tr -dc A-Za-z0-9 </dev/urandom | fold -b20" | getline s
        return s
    }
    BEGIN {
        for (i=1; i<=1000000; ++i)
            len += length(get20())
        print len
    }
'
20000000

real    0m1.344s
user    0m1.703s
sys 0m0.416s
$

    Xubuntu 24.04.1 no i5-8350U

    Acabei de encontrar: https://unix.stackexchange.com/questions/230673/how-to-generate-a-random-string que tem uma resposta usando a mesma abordagem. Há uma nota de que a configuração LC_ALL=Cpara o trcomando pode ser desejável.

    Para permitir saída de comprimento variável, selecionar um valor adequadamente grande/pequeno para o foldparâmetro e acumular um pequeno número de getlinepode ser quase tão rápido. Talvez o dobro do comprimento típico desejado pode ser uma escolha razoável? Então para 20, algo como:

    awk -v chunksz=40 '
    BEGIN {
        randomchunk = "tr -dc A-Za-z0-9 </dev/urandom | fold -b" chunksz
    }
    function getn_alnum(n,        i,s,r){
        for (i=0; i<n; i+=chunksz) {
            randomchunk | getline s
            r = r s
        }
        return substr(r,1,n)
    }
    # ...
'
    • 2

  4. Claro que executar od, ou qualquer processo externo, 1 milhão de vezes vai levar tempo. Mas você realmente não precisa do Awk aqui.

    base64 -w 20 /dev/urandom | head -n 1000000

    Se você precisar de um alfabeto diferente do fornecido em base64, existem ferramentas como base85essa, que, no entanto, são menos onipresentes.

    Notavelmente, o alfabeto base64 inclui /e +. Se esses forem inaceitáveis, você pode adicionar uma tretapa simples de pós-processamento:

    base64 -w 20 /dev/urandom | head -n 1000000 | tr /+ 0-9A-Za-z

    A distribuição será então um pouco menos aleatória novamente, mas provavelmente não o suficiente para fazer alguma diferença real.

    Não tenho Ruby aqui, então não posso comparar diretamente, mas os tempos para isso na minha VM Debian são

    bash$ time base64 -w 20 /dev/urandom | head -n 1000000 >/dev/null
real    0m0.064s
user    0m0.033s
sys 0m0.034s

    Para comparação indireta, o primeiro script Awk de Ed Morton leva 2 segundos em tempo real aqui. Adicionar o trpipeline empurra isso para 0,081s em tempo real.

    • 2

  5. Isso não funciona — mesma semente, mesmo resultado de string.

    Isso está em conformidade com o que o manual do usuário do GNU Awk diz sobresrand

    rand([x])

    Defina o ponto inicial, ou semente, para gerar números aleatórios para o valor x.

    Cada valor de semente leva a uma sequência particular de números aleatórios.49 Assim, se a semente for definida para o mesmo valor uma segunda vez, a mesma sequência de números aleatórios será produzida novamente.

    CUIDADO: Diferentes implementações do awk usam diferentes geradores de números aleatórios internamente. Não espere que o mesmo programa awk produza a mesma série de números aleatórios quando executado por diferentes versões do awk.

    Se o argumento x for omitido, como em srand(), então a data e a hora atuais do dia são usadas para uma semente. Esta é a maneira de obter números aleatórios que são realmente imprevisíveis.

    O valor de retorno de srand()é a semente anterior. Isso facilita o acompanhamento das sementes caso você precise reproduzir consistentemente sequências de números aleatórios.

    POSIX não especifica a semente inicial; ela difere entre as implementações do awk.

    As últimas 4 palavras são especialmente importantes considerando que você está estipulando

    Funciona na maioria das plataformas (ou seja, kit POSIX padrão)

    • 1

relate perguntas