Recent

Author Topic: [SOLVED] Reinventing the wheel: bisect_left Python analog  (Read 784 times)

lucamar

  • Hero Member
  • *****
  • Posts: 1485
Re: Reinventing the wheel: bisect_left Python analog
« Reply #15 on: May 14, 2019, 03:23:37 am »
You also stated a sorted list, that is a linear search.

Quite the contrary, isn't it? A linear search is (almost) the unique option only with an unsorted list. When the list is sorted there are quite a lot of alternative strategies.

Not for nothing that particular "branch" of computing is almost always called "sorting and searching" :)
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus 1.8.4 & 2.0.2 w/FPC 3.0.4 on:
(K|L)Ubuntu 12..16, Windows XP SP3, various DOSes.

jamie

  • Hero Member
  • *****
  • Posts: 1460
Re: Reinventing the wheel: bisect_left Python analog
« Reply #16 on: May 14, 2019, 03:38:20 am »
he never specify how large of  a data chuck he is dealing with...

 Any ways, I know how to do that , its a simple matter of splitting the data  half between the two ranges, test the value
and decide in which direct one must go to split that in half and keep repeating that until you find a match then
split that in half in the left direction until you run out of matches or hit the low limit set..

 In the case of running out of matches, you then go back the previous index and then do a linear traverse backwards to find
the first match in the range...

 I've been around the soup kitchen far too long!

  :D

jamie

  • Hero Member
  • *****
  • Posts: 1460
Re: Reinventing the wheel: bisect_left Python analog
« Reply #17 on: May 14, 2019, 03:48:44 am »
Binary search methods come in many different colors.. The most common is to simply split the ranges in half and
start at the center point, then create another split from that and keep repeating it.

  That's all well and good but if the list is short the basic linear is faster because the compile code can use a
string ASM function to make things skip a long very fast. Just Load SI reg and do a compstr function in ASM with the
CX reg as the count.



lucamar

  • Hero Member
  • *****
  • Posts: 1485
Re: Reinventing the wheel: bisect_left Python analog
« Reply #18 on: May 14, 2019, 03:51:36 am »
Any ways, I know how to do that , its a simple matter of splitting the data half between the two ranges, test the value and decide in which direct one must go to split that in half and keep repeating that until you find a match then split that in half in the left direction until you run out of matches or hit the low limit set..

In the case of running out of matches, you then go back the previous index and then do a linear traverse backwards to find
the first match in the range...

What you're describing is a binary search ... well ... kinda' ... a strange one that doesn't stop when it should and keeps trying ... to the point of reverting to a linear search? That is dedication to a task! :)

[Yes, I see what you're trying to do: find a range of multiple matches. It just made me smile]
« Last Edit: May 14, 2019, 03:53:07 am by lucamar »
Turbo Pascal 3 CP/M - Amstrad PCW 8256 (512 KB !!!) :P
Lazarus 1.8.4 & 2.0.2 w/FPC 3.0.4 on:
(K|L)Ubuntu 12..16, Windows XP SP3, various DOSes.

440bx

  • Hero Member
  • *****
  • Posts: 796
Re: Reinventing the wheel: bisect_left Python analog
« Reply #19 on: May 14, 2019, 05:28:44 am »
he never specify how large of  a data chuck he is dealing with...
he didn't give a specific number but...

IndexDWord is useful function, but it uses linear search not binary search (it works on any input not only ordered (sorted)),
so on huge input and heavy usage it will be slow.
"huge input" does suspiciously sound like a large data chunk.  I bolded it for you to help ensure the sentence doesn't get lost in the soup (or the kitchen.)

That soup seems fairly potent.. the OP is looking for an equivalent to Python's cushy bisect_left and you offer CPU registers and scanning instructions.  That is some heavy duty soup... :)




using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

jamie

  • Hero Member
  • *****
  • Posts: 1460
Re: [SOLVED] Reinventing the wheel: bisect_left Python analog
« Reply #20 on: May 15, 2019, 02:20:49 am »
Well here is my version of it..

Seems to work if I have it fully understood, it inserts left to the value found or below a value in the list..

Code: Pascal  [Select]
  1. Function Bisectleft( Var A:Array of LongInt; Val:LongInt;LoIndex:LongInt=0;HiIndex:LongInt=-1):LongInt;
  2. var
  3.   I:Integer;
  4.       Function BinIndex(aA:Array of LongInt;AValue, AStart, AEnd:LongInt):LongInt;
  5.       var
  6.         Center:LongInt;
  7.         SearchDone :Boolean = false;
  8.        Begin
  9.          Result := -1;
  10.          Repeat;
  11.            Center := AStart+(AEnd-AStart) Div 2;
  12.  
  13.            If AValue = aA[Center] Then {Found direct match}
  14.              Begin
  15.                While (aA[Center] = AValue)and(Center > AStart) do Dec(Center);
  16.                IF aA[Center]<>AValue Then Inc(Center);
  17.                Result := Center;
  18.                SearchDone := True;
  19.              End else
  20.            If AValue < aA[Center] Then {Value is above below index }
  21.              Begin
  22.               SearchDone := AStart=Center;
  23.               If SearchDone Then Result :=Center else AEnd := Center;
  24.              End Else
  25.              Begin   { Value is above index }
  26.                if (AEnd-Center < 2) Then { are we at the end ? }
  27.                  Begin
  28.                   SearchDone := True;
  29.                   If AValue = aA[AEnd] Then Result := AEnd;
  30.                  end;
  31.                AStart := Center;
  32.              End;
  33.          until SearchDone;
  34.        end;
  35.  
  36. Begin
  37.   if HiIndex = -1 then HiIndex := High(A);
  38.   Result := BinIndex(A,Val, LoIndex, HiIndex);
  39.   If Result <> -1 then  { Insert "VAL" if found before end "}
  40.    begin
  41.      Result +=LoIndex;
  42.      Move(PLongInt(@A[Result])^, PLongInt(@A[Result+1])^,(Length(A)-Result)*SizeOf(LongInt));
  43.      A[Result] := Val;
  44.    end;
  45. end;
  46.  

I tested a bunch of numbers, it inserts the value to the left of the equal or above it.
all it does not do is cause an overflow of the array if you happen to find the a value at the end cause there is no place
to put it.
 I suppose an exception would be warranted there.

VTwin

  • Hero Member
  • *****
  • Posts: 655
  • Former Turbo Pascal 3 user
Re: [SOLVED] Reinventing the wheel: bisect_left Python analog
« Reply #21 on: May 15, 2019, 02:48:46 am »
Not sure if this is quite relevant, but I have a sorted dictionary that uses a binary search to locate the insert position if the key is not found:

Code: Pascal  [Select]
  1. { TVDict.BinarySearch
  2.   Does a binary search for key in an array of Objects. The array must be
  3.   sorted. Returns the index if found, or the position to insert the key into a
  4.   sorted list as -i-1 if not found, so (i > -1) = found. }
  5. function TVDict.BinarySearch(key: string): integer;
  6. var
  7.   left, right, middle, comp, i: integer;
  8. begin
  9.   left := 0; // Low
  10.   right := Count-1; // High
  11.   if right < 0 then begin
  12.     result := -1; // insert at -i-1 = 0
  13.     exit;
  14.   end;
  15.   while (right - left > 0) do begin
  16.     middle := (left + right) div 2;
  17.     if CompareKey(fItems[middle].Key, key) < 0 then
  18.       left := middle + 1
  19.     else
  20.       right := middle;
  21.   end;
  22.   comp := CompareKey(fItems[left].Key, key);
  23.   if comp = 0 then // found
  24.     i := left
  25.   else if comp > 0 then
  26.     i := -left - 1 // insert at -i-1
  27.   else
  28.     i := -(left + 1) - 1; // insert at -i-1
  29.   result := i;
  30. end;
“Talk is cheap. Show me the code.” -Linus Torvalds

macOS 10.11.6: Lazarus 2.1.0 svn 61174M (64 bit Cocoa trunk)
Ubuntu 18.04.2: Lazarus 2.0.0 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.0 (64 bit on VBox)