fast searching algorithm

Shell Programming and Scripting
1

hello,

i need a searching algorithm in unix. since my input file is very bulky, so need a real fast searching algorithm, to match words. i am already using grep.

2

one is to write multiple concurrent instances
and the other one,
our own algorithm based on the search pattern by narrowing search domain

3

grep already uses a good algorithm for searching.

If the file is ordered with respect to your search key, you can use a simple binary search approach on fixed record length files -

/*****************************************
*   ffind.c --
*   find a value in a file using random access
*   usage ffind <value> <nrec> <filename>
*   requires a fixed length record file
*   possibly with a newline for each record,
*   reclen= data + newline
*   returns:
*    0 if the value is found,
*    1 if not found
**********************************/
#define RECL 10

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

FILE *in=NULL;
char _Wvalue[RECL*2]={0x0};

void usage(void)       /* help */
{
    fprintf(stderr,"%s\n",
        "usage: ffind <value to find> <number records> <filename>");
    exit(EXIT_FAILURE);
}

char  *setfilepos(long pos)  /* read from  in the file*/
{
     if(fseek(in,pos*RECL,SEEK_SET)!=0)
     {  /* note we do not check for EINTR which is possible */
     	perror("Parameter error - incorrect number of records");
     	exit(EXIT_FAILURE);
     }
     memset(_Wvalue,0x0,sizeof(_Wvalue));
     if(fgets(_Wvalue,sizeof(_Wvalue),in)==NULL)
     {
        if(!feof(in))
        {
            perror("File read error");
            exit(EXIT_FAILURE);
        }      
     }
     return _Wvalue;
}

int compar(const char *key,long rec) /* compare key & test value */
{
    char value[RECL+1]={0x0};
    char *p=NULL;

    strcpy(value,setfilepos(rec));
    p=strchr(value,'\n');
    if(p!=NULL) *p=0x0;
    return strcmp(key,value);
}

/* binary search against a fixed Rec Len  file */
int fbsearch(const char *key, long nrecs)
{
    int retval=0;
    long offset=0;
    long guess=0;

    nrecs--;
    guess=(nrecs - offset)/2;
    for(;;)
    {
        retval=compar(key,guess);
        if(retval)
        {
            if(retval>0)
            {
            	offset=guess+1;
            }
            else
            {
                nrecs=guess-1;
            }
            if(offset > nrecs) break;

            guess=offset + (nrecs-offset)/2;
            continue;
        }
        break;
    }
    return retval;
}

int main(int argc, char *argv[])
{
    int result=0;
    if(argc<4)
    {
        usage();
    }
    in=fopen(argv[3],"r");
    if(in==NULL)
    {
        perror("Error opening input file");
        exit(EXIT_FAILURE);
    }
    result=fbsearch(argv[1],atol(argv[2]));
    return (result!=0);
}
4

jim,

i have few questions

1) using binary search algorithm,
you have additional overhead of sorting and then making useof it
i believe you have given an example assuming ordered sort keys.

2) file is not closed, that should be

3) in compar what is the need of pointer to character 'p'?