Рандомизация в shell.

[agbr]

Вопрос: нужно из результата, который выдает find выбрать одну СЛУЧАЙНУЮ строчку.
Т.е. find ... | <незнаю-что>

[serzh-z]

Вопрос: нужно из результата, который выдает find выбрать одну СЛУЧАЙНУЮ строчку.
Т.е. find ... | <незнаю-что>

Достать/написать утилиту, которая будет перемешивать вывод find. Потом можно просто брать первую строчку из перемешанного списка.

Есть ссылка на код подобного приложения в C, думаю, что никто не мешает перенести это на Perl, например, и поделиться кодом с общественностью.

http://www.seebs.net/ops/ibm/files/unsort.c

[serzh-z]

Немного исправленный и рабочий исходник вышеуказанного приложения:

/* Copyright 1994-2003 Peter Seebach
* All wrongs reversed. */
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

//#include "opts.h"
//#include "version.h"

/* unsort - unsort arbitrary input */

char *buffer = 0; /* character storage */
size_t *lines = 0; /* offsets into buffer */
int size = 0; /* size of buffer */
int count = 0; /* characters used in buffer */
int lcount = 0; /* offsets used */
int lsize = 0; /* size of offsets "array" */
char *us; /* argv[0] or thereabouts */

static void fail(void);
static void mesg(char *, ...);
static int spew_output(int);
static int slurp_input(FILE *);

static void
fail(void) {
free(buffer);
free(lines);
exit(EXIT_FAILURE);
}

/* print an identified message */
static void
mesg(char *fmt, ...) {
va_list ap;

fprintf(stderr, "%s: ", us);
va_start(ap, fmt);
vfprintf(stderr, fmt, ap);
va_end(ap);
}

/* the astute reader will note that rand() may not be a great randomizer;
* feel free to provide a more effective one.
*/
static int
spew_output(int nitems) {
int i, j;
size_t temp;

if (nitems == 0)
return 0;

for (i = 0; i < nitems; ++i) {
#ifdef __bsdi__
j = random() % nitems;
#else
j = rand() % nitems;
#endif
temp = lines[i];
lines[i] = lines[j];
lines[j] = temp;
}

for (i = 0; i < nitems; ++i) {
puts(buffer + lines[i]);
}

return 0;
}

/* Slurp input. Our goal is to always leave this function in a state such
* that count refers (accurately) to the number of lines. Lines should be
* an allocated array of count size_t's, offsets into buffer, each `pointing'
* to a null terminated string.
*
* We keep track of:
* 1. Current line.
* 2. Position in buffer.
* 3. Size of buffer, and of lines[].
*
*/
static int
slurp_input(FILE *fp) {
int c;
int lastcount;
size_t *tlines;
char *tbuffer;

if (!lines) {
lsize = 256;
lines = malloc(lsize * sizeof(size_t));
if (!lines) {
mesg("couldn't allocate memory.\n");
fail();
}
lcount = 0;
}
if (!buffer) {
size = 4096;
buffer = malloc(size);
if (!buffer) {
mesg("couldn't allocate memory.\n");
fail();
}
count = 0;
}
lastcount = count;
while ((c = getc(fp)) != EOF) {
switch © {
default:
buffer[count++] = (char) c;
break;
case '\n':
buffer[count++] = '\0';
lines[lcount++] = lastcount;
lastcount = count;
if (lcount >= lsize) {
tlines = realloc(lines,
(lsize *= 2) * sizeof(size_t));
if (!tlines) {
mesg("couldn't allocate memory.\n");
fail();
}
lines = tlines;
}
}
if (count >= size) {
tbuffer = realloc(buffer, size *= 2);
if (!tbuffer) {
mesg("couldn't allocate memory.\n");
fail();
}
buffer = tbuffer;
}
}
buffer[count] = '\0';
return 0;
}

int
main(int argc, char *argv[])
{
int i, o, ret = 0;
char *s;
FILE *fp;

srand(time(NULL));

/*s = argv[0];

if ((us = strrchr(s, '/')))
++us;
else
us = argv[0];

#ifdef __bsdi__
srandom(time(NULL));
#else
srand(time(NULL));
#endif
while ((o = optsopt(argc, argv, "hV")) != -1) {
switch (o) {
case 'V':
version();
break;
case 'h':
mesg("usage: unsort [-hV] [ file ...]\n");
exit(0);
break;
default:
mesg("usage: unsort [-hV] [ file ...]\n");
exit(EXIT_SUCCESS);
break;
}
}*/

/*if (optsind < argc) {
for (i = optsind; i < argc; ++i) {
if (strcmp(argv[i], "-"))
fp = fopen(argv[i], "r");
else
fp = stdin;
if (!fp) {
mesg("couldn't open file '%s'\n", argv[i]);
ret = EXIT_FAILURE;
} else {
if (slurp_input(fp))
ret = EXIT_FAILURE;
}
if (fp && (fp != stdin))
fclose(fp);
}
} else {*/
if (slurp_input(stdin))
ret = EXIT_FAILURE;
//}

if (spew_output(lcount))
ret = EXIT_FAILURE;
return ret;
}

Вот так, например, работает:

#!/bin/sh
echo `ls -1 $1 | unsort | tail -n 1`

[agbr]

а на shell?

[madskull]

можно и "чиста башем", но придется создавать временный файл

Код: Выделить всё

find > file
sed -n "$(($RANDOM%$(cat file|wc -l)+1))p" file

либо запускать два финда

Код: Выделить всё

find | sed -n "$(($RANDOM%$(find|wc -l)+1))p"

[agbr]

можно и "чиста башем", но придется создавать временный файл

Код: Выделить всё

find > file
sed -n "$(($RANDOM%$(cat file|wc -l)+1))p" file

либо запускать два финда

Код: Выделить всё

find | sed -n "$(($RANDOM%$(find|wc -l)+1))p"

круто, а я не знал про переменную $RANDOM если б знал, сам сделал. спасибо.

[jsv]

можно и "чиста башем", но придется создавать временный файл

Необязательно, кстати. Достаточно буфера в одну строчку, правда, при этом придётся больше случайных чисел считать. Примерно так:

Код: Выделить всё

function random_line
{
    local lnum=0
    local chosen
    while read current
    do
        ((RANDOM % ++lnum)) || chosen=$current
    done
    echo $chosen
}

find ... | random_line

На sh оно, конечно, несколько многословно выходит. На perl можно в однострочник втиснуть

[madskull]

На sh оно, конечно, несколько многословно выходит. На perl можно в однострочник втиснуть

не втиснешь.
В твоем случае рандом очень уж нерандомный. Чем ближе к концу списка, тем больше вероятность попадания элемента списка в результат. Может я и ошибаюсь (тервер изучалась лет двадцать назад).

На мой взгляд, чтобы получить более или менее равномерно размазанную по списку вероятность, надо знать размер списка. То есть, двух проходов не избежать.

[jsv]

На sh оно, конечно, несколько многословно выходит. На perl можно в однострочник втиснуть

не втиснешь.

Втисну. Не нестолько уж у меня короткие строчки.

Код: Выделить всё

find ... | perl -ne '$r = $_ unless(int rand $.); END{ print $r; }'

В твоем случае рандом очень уж нерандомный. Чем ближе к концу списка, тем больше вероятность попадания элемента списка в результат. Может я и ошибаюсь (тервер изучалась лет двадцать назад).

На мой взгляд, чтобы получить более или менее равномерно размазанную по списку вероятность, надо знать размер списка. То есть, двух проходов не избежать.

Я когда первый раз этот приём увидел (где-то в коде zangband'a, кажется), тоже с некоторым скепсисом отнёсся.
Но распределение получается равномерное. Первая строчка выбирается всегда, вторая замещает её с вероятностью 1/2. Третья выбирается с вероятностью 1/3, вероятнось того, что там осталась первая -- 1/2*2/3 = 1/3, оставшаяся 1/3 достаётся второй строчке... Ну и так далее.

Ну или вот:

Код: Выделить всё

% ls test
1  2  3  4  5
% repeat 5000; do find test -type f |
>  perl -ne '$r = $_ unless int rand $.; END { print $r; }'
>  done | sort | uniq -c
    992 test/1
   1025 test/2
    971 test/3
   1012 test/4
   1000 test/5

Довольно равномерно. У самого $RANDOM распределение примерно такое же.

[madskull]

Довольно равномерно.

Хм. Интересненько. На досуге надо будет обдумать