From: etxmesa@eos.ericsson.se (Michael Salmon)
Subject: Re: use of rand
Keywords: read
Reply-To: etxmesa@eos.ericsson.se (Michael Salmon)
Organization: Ericsson Telecom AB
Date: Thu, 15 Oct 1992 07:54:59 GMT

In article <Bw5Bsx.Gp7@acsu.buffalo.edu>, yli@acsu.buffalo.edu (Yanhong Li) writes:
|> I want to operate on 100 random lines of a file whose length is about
|> 500 lines, is there an easy way to do that?
|> thanx

Here is a little C filter that extracts n random lines from a file,
while preserving their order. It shouldn't be so hard to translate to
perl.

#!/bin/sh
# This is a shell archive (produced by shar 3.49a)
# To extract the files from this archive, save it to a file, remove
# everything above the "!/bin/sh" line above, and type "sh file_name".
#
# made 10/15/1992 07:50 UTC by etxmesa@eos6c02
# Source directory /tmp_mnt/home/eos6/u2/users/etxmesa
#
# existing files will NOT be overwritten unless -c is specified
#
# This shar contains:
# length  mode       name
# ------ ---------- ------------------------------------------
#   1858 -rw-r--r-- c/randlines/randlines.c
#
# ============= c/randlines/randlines.c ==============
if test ! -d 'c'; then
    echo 'x - creating directory c'
    mkdir 'c'
fi
if test ! -d 'c/randlines'; then
    echo 'x - creating directory c/randlines'
    mkdir 'c/randlines'
fi
if test -f 'c/randlines/randlines.c' -a X"$1" != X"-c"; then
        echo 'x - skipping c/randlines/randlines.c (File already exists)'
else
shar: saving c/randlines/randlines.c (Text)
echo 'x - extracting c/randlines/randlines.c (Text)'
sed 's/^X//' << 'SHAR_EOF' > 'c/randlines/randlines.c' &&
/*      randlines.c - select randomlines from a file    */
/*
X       This programme is based upon algorithm R (Reservoir Sampling) from 
X       The Art of Computer Programming
X       Volume 2
X       Seminumerical Algorithms
X       by Donald Knuth
X       ISBN 0-201-03822-6
*/
X
#include        <stdio.h>
#include        <ctype.h>
#include        <malloc.h>
#include        <sys/types.h>
#include        <sys/time.h>
X
#define NR_LINES        1024
#define LINE_LEN        256
X
static struct l {
X    int                linenr;
X    char       line[ LINE_LEN ];
} *linep[ NR_LINES ];
X    
static int      n = 1;
X
static int cmp( p1, p2)
X    struct l   **p1, **p2;
{
X    return (*p2)->linenr - (*p1)->linenr;
}
X
int main ( argc, argv)
X    int                argc;
X    char       *argv[];
{
X    int                i, t = 0;
X    struct l   *tmp;
X    int                random();
X    void       srandom();
X
X    srandom( time( NULL));
X
X    if ( argc == 2) {
X       if ( !isdigit( *argv[ 1 ])) {
X           fprintf( stderr, "Usage: randlines [n]\n");
X           return 1;
X       }
X       else {
X           n = atoi( argv[ 1 ]);
X           if ( n <=  0 || n >= NR_LINES) {
X               fprintf( stderr, "Illegal n: %d. Must be between 1 and %d.\n", n, NR_LINES);
X               return 1;
X           }
X           --argc;
X       }
X    }
X    if ( argc > 1) {
X       fprintf( stderr, "Usage: randlines [n]\n");
X       return 1;
X    }
X
X    for ( i = n + 1; --i >= 0; )
X       if ( ( linep[ i ] = (struct l *)malloc( sizeof( struct l))) == NULL) {
X           fprintf( stderr, "Insufficient memory.\n");
X           return 1;
X       }
X    
X    for ( i = n; --i >= 0; )
X       if ( fgets( linep[ i ]->line, LINE_LEN, stdin) == NULL) {
X           fprintf( stderr, "Insufficient data.\n");
X           return 1;
X       }
X       else linep[ i ]->linenr = ++t;
X
X    while ( fgets( linep[ n ]->line, LINE_LEN, stdin) != NULL) {
X       if ( ( i = random() % ++t) < n) {
X           linep[ n ]->linenr = t;
X           tmp = linep[ n ];
X           linep[ n ] = linep[ i ];
X           linep[ i ] = tmp;
X       }
X    }
X
X    qsort( linep, n, sizeof( struct l *), cmp);
X
X    for ( i = n; --i >= 0; )
X       fputs( linep[ i ]->line, stdout);
X    
X    return 0;
}
SHAR_EOF
chmod 0644 c/randlines/randlines.c ||
echo 'restore of c/randlines/randlines.c failed'
Wc_c="`wc -c < 'c/randlines/randlines.c'`"
test 1858 -eq "$Wc_c" ||
        echo 'c/randlines/randlines.c: original size 1858, current size' "$Wc_c"
fi
exit 0

-- 

Michael Salmon

#include	<standard.disclaimer>
#include	<witty.saying>
#include	<fancy.pseudo.graphics>

Ericsson Telecom AB
Stockholm
Newsgroups: comp.lang.perl,comp.unix.admin,alt.folklore.computers