Last active
April 18, 2016 03:07
-
-
Save KevOrr/59b2098214b4e17ff1fc48a14a692e05 to your computer and use it in GitHub Desktop.
Simulates zipfian behaviors among paperclips
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Simulates zipfian behaviors among paperclips | |
// Assumes that all paperclips can be selected with equal probability, | |
// regardless of the chain size each is in. | |
#include <stdio.h> | |
#include <stdlib.h> | |
struct clip { | |
int id; | |
struct clip *prev; | |
struct clip *next; | |
}; | |
int connect2(struct clip *clips[], int n_clips, struct clip *chains[], int n_chains) { | |
// TODO make better random choice code (Try MT19937) | |
// http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html | |
struct clip *a = clips[(int)(rand() * n_clips / RAND_MAX)]; | |
struct clip *b = clips[(int)(rand() * n_clips / RAND_MAX)]; | |
// Find the end of a's chain and the beginning of b's | |
struct clip *a_end, *b_start; | |
for (a_end = a; a->next != NULL; a = a->next); | |
for (b_start = b; a->prev != NULL; b = b->prev); | |
// Connect the 2 | |
a_end->next = b_start; | |
b_start->prev = a_end; | |
// Find b_start in chains[] and remove it | |
int i; | |
for (i = 0; i < n_chains && chains[i] != b_start; i++); | |
if (i >= n_chains) { | |
fputs("Could not find b_start in chains[]\n", stderr); | |
return -1; | |
} | |
chains[i] = NULL; | |
return 0; | |
} | |
void count(struct clip *chains[], int *chain_sizes, int n_chains) { | |
int i, size; | |
struct clip *p; | |
for (i = 0; i < n_chains; i++) { | |
// Count length of chain[i] | |
for (size = 0, p = chains[i]; p != NULL; size++, p = p->next); | |
chain_sizes[i] = size; | |
} | |
} | |
// Returns the actual (possibly new) number of chains | |
int sort_chains(struct clip *chains[], int n_chains) { | |
} | |
void dealloc(struct clip *clips[], int n) { | |
int i; | |
for (i=0; i<n; i++) | |
free(clips[i]); | |
} | |
void usage(char *name) { | |
printf("USAGE: %s [N [STEPS [INT]]]\n\n" | |
"Simulates zipfian behaviors among paperclips\n" | |
"N Number of paperclips (must be >= 3)\n" | |
"STEPS Number of steps before termination\n" | |
"INT Number of steps between each report\n", name); | |
} | |
int main(int argc, char *argv[]) { | |
int n_clips = 100; | |
int n_chains = 100; | |
int steps = 100; | |
int report_interval = 10; | |
// Command line options | |
if (argc > 1) { | |
if (!(n_clips = atoi(argv[1])) || n_clips < 3) { | |
usage(argv[0]); | |
return 1; | |
} | |
n_chains = n_clips; | |
} | |
if (argc > 2) { | |
if (!(steps = atoi(argv[2]))) { | |
usage(argv[0]); | |
return 1; | |
} | |
} | |
if (argc > 3) { | |
if (!(report_interval = atoi(argv[3]))) { | |
usage(argv[0]); | |
return 1; | |
} | |
} | |
struct clip *clips[n_clips]; | |
struct clip *chains[n_chains]; | |
int chain_sizes[n_chains]; | |
// Create clips | |
int i; | |
for (i=0; i<n_clips; i++) { | |
// Store one clip in each chain | |
struct clip *new_clip = malloc(sizeof(struct clip)); | |
if (new_clip == NULL) { | |
fputs("Failed to allocate memory. Download more gigs\n", stderr); | |
if (i) | |
dealloc(clips, n_clips); | |
return 1; | |
} | |
// Set members | |
new_clip->next = NULL; | |
new_clip->prev = NULL; | |
new_clip->id = i; | |
clips[i] = new_clip; // Add to clip array for deallocation later | |
chains[i] = new_clip; // Add to chains array for chain tracking | |
chain_sizes[i] = 1; // Each chain size is 1 (all clips are disconnected) | |
} | |
// Print initial summary | |
fputs("0 ", stdout); // Step number | |
for (i=0; i<n_chains - 1; i++) | |
printf("%4d ", chain_sizes[i]); // Chain sizes | |
printf("%4d\n", chain_sizes[n_chains - 1]); | |
// Main loop | |
for (i = 0; i < steps; i++) { | |
int ret = connect2(clips, n_clips, chains, n_chains); | |
if (ret < 0) { | |
fputs("Encountered some error in connect2()\n", stderr); | |
return 1; | |
} | |
// TODO print report | |
} | |
dealloc(clips, n_clips); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment