Programmer 7500/MAX_PROGRAMMERS.iso/PASCAL/JUMPSRCH.ZIP/JUMPSRCH.PAS

Pascal/Delphi Source File | 1986-10-22 | 8.8 KB | 345 lines

program Jump_search;
{$u-,r-,k+,c-}
{ Marshall Brain       July 17, 1986
  This program implements the Jump Search algorithm.}


type
  num_pntr=^data_rec;
  jump_pntr=^jump_rec;

  {typical data record - forward and backward pointers and data}
  data_rec=record
     nextpntr,prevpntr : num_pntr;
     num  : integer;
  end;

  {A Jump Node consists of a single link forward and a
   pointer to a specific data item.}
  jump_rec=record
    nextjump:jump_pntr;
    data_pntr:num_pntr;
  end;

var
  tempdata,firstdata,lastdata:num_pntr;
  tempjump,firstjump,lastjump:jump_pntr;
  prevtimecx,prevtimedx,timedx,timecx:integer;
  list_size:integer;
  time:real;

  procedure fill_data_list;
  {creates a double linked list of list_size elements on the
   heap. Each record on the heap contains 2 pointers and the
   "data", it this case a single integer.}
  var x:integer;

    procedure append_to_list;
    {appends the next data record to the end of the list. In a normal
     program this would be replaced by insertion and deletion
     routines for the linked list.}
    begin
      {if no records in list, then make current record the first.}
      if firstdata=nil then
      begin
        firstdata:=tempdata;
        lastdata:=tempdata;
        tempdata^.nextpntr:=nil;
        tempdata^.prevpntr:=nil;
      end
      {otherwise append to end of list.}
      else
      begin
        lastdata^.nextpntr:=tempdata;
        tempdata^.nextpntr:=nil;
        tempdata^.prevpntr:=lastdata;
        lastdata:=tempdata;
      end;
    end;

  begin {fill_data_list}
    firstdata:=nil;lastdata:=nil;
    {This demo uses simple data in the linked list - a set of
     consecutive integers. Note that list MUST be sorted to use
     the jumping technique.}
    for x:=1 to list_size do
    begin
      new(tempdata);
      tempdata^.num:=x;
      append_to_list;
    end;
  end;

  procedure create_jump_list;
  {Given a sorted linked list, this routine will create a balanced
   jumping list to use for searching.}
  var y,x,jump_distance:integer;

    procedure create_jump_node;
    {creates and links in a new jump node.}
    begin
      new(tempjump);
     {point jump records data pointer at current data item.}
      tempjump^.data_pntr:=tempdata;
     {form linked list of jump records by appending onto end of
      jump list.}
      if firstjump=nil then
        firstjump:=tempjump
      else
        lastjump^.nextjump:=tempjump;
      tempjump^.nextjump:=nil;
      lastjump:=tempjump;
    end;

  begin {create_jump_list}
   {determine optimal jump distance.}
    jump_distance:=trunc(sqrt(list_size));
    x:=1; y:=1;
   {start with first element of data list.}
    tempdata:=firstdata;
    firstjump:=nil; lastjump:=nil;
   {sequence through entire list.}
    while y<list_size do
    begin
      {every sqrt(list_size) create a jump node.}
      if x>=jump_distance then
      begin
        create_jump_node;
        x:=0;
      end;
     {get next data item in list.}
      tempdata:=tempdata^.nextpntr;
      y:=y+1; x:=x+1;
    end;
   {create final jump node at very end of list.}
    create_jump_node;
  end;

  procedure jump_search(num_to_find:integer);
  var found:boolean;

    procedure coarse_search;
    {the coarse search jumps through the jump nodes looking for
     the nearest match to the data to be found. As soon as a
     jump node is found pointing to a data item >= the item
     to be found, the course search stops.}

    var done:boolean;

    begin
     {start at first jump node.}
      tempjump:=firstjump;
      done:=false;
      while not done do
      begin
       {stop when data item >= num to be found.}
        if tempjump^.data_pntr^.num>=num_to_find then
          done:=true
        else
        begin
          {Also stop course search at end of jump list (last
           element in data list).}
          if tempjump^.nextjump=nil then
            done:=true
          else
            tempjump:=tempjump^.nextjump;
        end;
      end;
    end;

    procedure fine_search;

    var stop:boolean;
    {fine search then goes backwards thru every element in data
     list itself until item is found or item can not exist.}

    begin
     {start looking at jump node coarse search stopped at.}
      tempdata:=tempjump^.data_pntr;
      found:=false; stop:=false;
      while not found and not stop do
      begin
       {if beyond possibility, stop search.}
        if num_to_find>tempdata^.num then
          stop:=true
        else
        begin
          if num_to_find=tempdata^.num then
            found:=true
          else
            tempdata:=tempdata^.prevpntr;
        end;
      end;
      if not found then write(' not found ');
    end;

  begin {jump_search}
    coarse_search;
    fine_search;
    {at this point programmer decides what to do with the found data
     item. FOUND will be true if found, and TEMPDATA will point to
     found data item.}
  end;

  procedure sequential_search(num_to_find:integer);
  {standard sequential search routine used
   for comparison in benchmarking.}

  var stop,found:boolean;

  begin
    tempdata:=firstdata;
    found:=false; stop:=false;
    while not found and not stop do
    begin
      if num_to_find<tempdata^.num then
        stop:=true
      else
      begin
        if num_to_find=tempdata^.num then
          found:=true
        else
          tempdata:=tempdata^.nextpntr;
      end;
    end;
  end;

  procedure beep;
  begin
    sound(500);
    delay(1000);
    nosound;
  end;

  procedure get_time(var cx,dx:integer);

  var result:record ax,bx,cx,dx,bp,si,di,ds,es,flags:integer; end;

  begin
    result.ax:=0;
    intr($1a,result);
    cx:=result.cx;dx:=result.dx;
  end;

  procedure calc_time;
  begin
    time:=(timecx-prevtimecx)*65536.0 +
          (hi(timedx)-hi(prevtimedx))*256.0 +
          (lo(timedx)-lo(prevtimedx));

    time:=time/18.2;
  end;

  procedure time_searches;

  var a:integer;jtime:real;

  begin
    write('  Jump Searching list.        ');
    get_time(prevtimecx,prevtimedx);
    a:=1;
    while a<=list_size do
    begin
      jump_search(a);
      a:=a+11;  {use prime number to avoid bias in benchmarks.}
    end;
    get_time(timecx,timedx);
    calc_time;
    writeln('    done. Time =',time:6:2);
    jtime:=time;
    writeln;
    write('  Sequentially Searching list.');
    get_time(prevtimecx,prevtimedx);
    a:=1;
    while a<=list_size do
    begin
      sequential_search(a);
      a:=a+11;  {use prime number to avoid bias in benchmarks.}
    end;
    get_time(timecx,timedx);
    calc_time;
    writeln('    done. Time =',time:6:2);
    writeln;
    if jtime=0 then jtime:=0.05;
    writeln('Jump Searching was ',time/jtime:4:1,
            ' times faster for a ',list_size,
            ' element list');
  end;

  procedure setup;

  var error:boolean;

  begin
    clrscr;
    gotoxy(1,5);
    writeln
    ('This program will produce a benchmark comparing the time to');
    writeln
    ('do a number of sequential searches with a number of identical');
    writeln
    ('Jump Searches. You will be asked to enter a number indicating');
    writeln
    ('the number of elements to be placed in the linked list used');
    writeln
    ('for this test.  Numbers greater that 1000 can produce very');
    writeln
    ('long sequential searches in this test, but results are');
    writeln('more dramatic for longer searches.');
    writeln;
    writeln('Enter the number of items to be in the linked list.  ');
    write('Please type an integer less than 30000 : ');
    readln(list_size);
    writeln;writeln;
  end;

  procedure make_linked_list;
  begin
    writeln;
    writeln('List size for test = ',list_size);
    writeln('Number of searches for test = ',list_size div 11);
    writeln('All times are in seconds.');
    writeln;
    writeln('  Setting up linked list used for testing.');
    fill_data_list;
    writeln;
  end;

  procedure make_jump_list;
  begin
    write('  Creating Jump Nodes.        ');
    get_time(prevtimecx,prevtimedx);
    create_jump_list;
    get_time(timecx,timedx);;
    calc_time;
    writeln('    done. Time =',time:6:2);
    writeln;
  end;

  function size_ok:boolean;

  var x:real;

  begin
    if maxavail<0 then x:=maxavail+65536.0 else x:=maxavail;
    if x*16.0-(list_size*16.0+trunc(sqrt(list_size))*8.0)<0.0 then
      size_ok:=false
    else
      size_ok:=true;
 end;

begin {main}
  setup;
  if size_ok then
  begin
    make_linked_list;
    make_jump_list;
    time_searches;
    beep;
  end
  else
    writeln('Linked list created would be too large',
        ' for your available memory.');
end.