Search/buildProblem.c File Reference

Driver that populates a search structure by invoking insert on strings in random order. Populates a search structure by first inserting numElements strings, in random order. Thereafter, performs a number of search operations as dictated by the command line arguments. More...

#include <stdlib.h>
#include <stdio.h>
#include <getopt.h>
#include <math.h>
#include <string.h>
#include "problem.h"
#include "report.h"

Defines

#define UNIFORM   1
 Uniform distribution of random strings.
#define WEIGHTED   2
 Weighted distribution of random strings (not implemented).

Functions

void construct (int sz)
 Method to construct the initial search structure to contain 'sz' elements.
void insert (char *s)
 Method to insert an integer element into the search structure.
int search (char *target, int(*cmp)(const char *, const char *))
 Method to search for an integer element in the search structure.
int stringComp (const char *a1, const char *a2)
 comparator function to use for all searches.
static char * elt (int size, int k)
 generate the kth element from s.
static char ** materializeStrings ()
 Materialize in order the full set of strings in the n = 2^k set.
void rotate (char *str)
 Given a string, rotate from the right, rolling over at 254, back to 1.
static void constructSearchList ()
 Construct search list based on distribution type.
void prepareInput (int size, int argc, char **argv)
 Construct a random string of size ssize and have 'str1' and 'str2' be allocated strings with the same contents.
void postInputProcessing (long usecs)
 Report properly formatted for table.
void execute ()
 Execute by invoking malloc(numElements) a total of numT times.
void problemUsage ()
 No specific problem usage.

Variables

int verbose
 Determine whether output is to be printed as the computation progresses.
char ** searchList
 information will be stored as pointer of strings.
static int elementSize = 6
 Element size of strings to be used.
static float p = 0.25
 Likelihood that target will be in the collection being searched.
static int distrib = UNIFORM
 Distribution method to use (UNIFORM is only supported for now).
static int first = 0
 Should the target always be the first element.
static int z = 50
 Collection Size: default is 50.
static int numFound = 0
 Computed number found.
static char * firstInserted = 0
 Record the first string inserted, to use with -f option.
static char ** elementsInC
 Build up a collection of strings known to be in the collection.


Detailed Description

Driver that populates a search structure by invoking insert on strings in random order. Populates a search structure by first inserting numElements strings, in random order. Thereafter, performs a number of search operations as dictated by the command line arguments.

Build up an array of Strings.

Required Input:

  1. seed (-s n)
  2. verbose (-v) if you want expressive output
Overridden Input:
  1. int numElements (-n x) If this is set, we override to 24*z

Expected methods

  1. extern void construct (int) -- construct initial collection storage
  2. extern void insert (char *s) -- add string to collection
  3. extern int search (char *target, int(*cmp)(const char *,const char *));
-- function to initiate search Search considerations
Search domain will be {a,b}^k which guarantees the size of |S| will be a power of 2.
Input flags:
  1. -p n Ratio in range [0,1] of available elements in target [default: .25] This reflects the strings from the domain that are to be searched for. If p=0 then the target strings are never found in the list. If p=1 then the target strings are always found in the list. Value of p in between reflect ratio of behavior.

  2. -d s Distribution type ('u' for uniform, 'w' for weighted) [default: uniform]
  3. -k n Size of the element Strings drawn from {a,b}* [default: 6]
  4. -s use same failed id (-1) [default: use different ids starting -2, -3, ...]

  5. -f Always search for the first element [default: search without constraint]
  6. -z n Size of the target data structure. [default: 50] Note that the numElements is to be set to 24*z, overriding any previous value.

External API

  1. void problemUsage() shows what is expected
  2. void prepareInput() construct target instance DS by repeated invocation of insert(s)
  3. void postInputProcessing() performs post-solution processing
  4. void execute() begin the problem and invoke search methods

Author:
George Heineman
Date:
6/15/08

Define Documentation

#define UNIFORM   1

Uniform distribution of random strings.

#define WEIGHTED   2

Weighted distribution of random strings (not implemented).


Function Documentation

void construct ( int  n  ) 

Method to construct the initial search structure to contain 'sz' elements.

Allocate array of 'n' elements for 'ds'.

static void constructSearchList (  )  [static]

Construct search list based on distribution type.

Here n=numElements is equal to z^2 and we intend to fill up the elements of searchList with all elements from ds. Draw the elements themselves from elementsInC.

p can be one of {0.0,0.25,0.5,0.75,1.0} and we deal with accordingly in this method. Note there is no need to be random about anything since we are going to aggregate over all elements in the set C and everyone will eventually be searched for.

the searchlist is randomly shuffled 12*z times to ensure some bit of randomness...

static char* elt ( int  size,
int  k 
) [static]

generate the kth element from s.

void execute (  ) 

Execute by invoking malloc(numElements) a total of numT times.

.numElements

output sum to be sure is correct.

void insert ( char *  s  ) 

Method to insert an integer element into the search structure.

In our case, we insert the elements into a non-balancing tree.

Parameters:
s Value to be inserted.

static char** materializeStrings (  )  [static]

Materialize in order the full set of strings in the n = 2^k set.

void postInputProcessing ( long  usecs  ) 

Report properly formatted for table.

void prepareInput ( int  size,
int  argc,
char **  argv 
)

Construct a random string of size ssize and have 'str1' and 'str2' be allocated strings with the same contents.

use character-swapping algorithm from strfry.c in glibc

http://www.koders.com/c/fidBD83E492934F9F671DE79B11E6AC0277F9887CF5.aspx

void problemUsage (  ) 

No specific problem usage.

void rotate ( char *  str  ) 

Given a string, rotate from the right, rolling over at 254, back to 1.

Ensures that str[0] is never 'a' or 'b'.

int search ( char *  target,
int(*)(const char *, const char *)  cmp 
)

Method to search for an integer element in the search structure.

int stringComp ( const char *  a1,
const char *  a2 
)

comparator function to use for all searches.


Variable Documentation

int distrib = UNIFORM [static]

Distribution method to use (UNIFORM is only supported for now).

char** elementsInC [static]

Build up a collection of strings known to be in the collection.

int elementSize = 6 [static]

Element size of strings to be used.

int first = 0 [static]

Should the target always be the first element.

char* firstInserted = 0 [static]

Record the first string inserted, to use with -f option.

int numFound = 0 [static]

Computed number found.

float p = 0.25 [static]

Likelihood that target will be in the collection being searched.

char** searchList

information will be stored as pointer of strings.

int verbose

Determine whether output is to be printed as the computation progresses.

int z = 50 [static]

Collection Size: default is 50.

Algorithm Development Kit 1.0