Skip to content

Instantly share code, notes, and snippets.

@cstorey
Created June 28, 2013 20:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cstorey/5887829 to your computer and use it in GitHub Desktop.
Save cstorey/5887829 to your computer and use it in GitHub Desktop.
Random reservoir sampler in C. Lacks a good deal of proper error checking.
#define _XOPEN_SOURCE 700
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
int size = atoi(argv[1]);
char **resrv = calloc(size, sizeof(char*));
int i = 0; size_t nread;
char *line = NULL;
while (i < size && getline(&line, &nread, stdin) > 0) {
// printf ("Got line in 1st loop: i:%d, read: %d bytes\n", i, nread);
resrv[i++] = line;
line = NULL;
}
// printf ("After 1st loop: i:%d, read: %d bytes\n", i, nread);
for (; line=NULL, getline(&line, &nread, stdin) > 0; ++i) {
int off = random() % i;
// printf ("1nd loop: i:%d, off:%d, read: %d bytes\n", i, off, nread);
if(off < size) {
free(resrv[off]);
resrv[off] = line;
} else {
free(line);
}
line = NULL;
}
for (int i = 0; i < size && resrv[i]; ++i) {
fputs(resrv[i], stdout);
free(resrv[i]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment