[SOLVED] Reinventing the wheel: bisect_left Python analog lazarus / 61-Beginners ---------------------------------------------------------------------- julkas · 2019-05-11 11:42 Is there an analog of the Python bisect_left function in Pascal? Something like - algorithm generic. Thanks. Quotebisect.bisect_left(a, x, lo=0, hi=len(a))     Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.     The returned insertion point i partitions the array a into two halves so that all(val < x for val in a[lo:i]) for the left side and all(val >= x for val in a[i:hi]) for the right side. My code: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function BisectLeft(s: array of LongInt; x: LongInt): LongInt;var  l, h, m: LongInt;begin  l := 0;  h := Length(s);  while l < h do  begin    m := (l+h) div 2; // Can overflow, but in my case it's OK!    if s[m] < x then      l := m + 1    else      h := m  end;      Result := lend; ---------------------------------------------------------------------- jamie · 2019-05-11 16:35 there are a couple of things you can do.. Use the IndexDword for example and use the MOVE which moves memory on the array to insert your new value .. I didn't see a memory management insert but there is a Insert function for other things. ---------------------------------------------------------------------- julkas · 2019-05-12 13:53 I want only insert position. Python has powerful bisect module, C has bsearch() - standard library function, C++ - std::lower_bound(), std::upper_bound(). What is Pascal RTL analogs for binary search? ---------------------------------------------------------------------- Thaddy · 2019-05-12 14:41 Pascal string handling is considerably more powerful than either Python or C++: Pos() PosEx() ReplaceStr() And many, many more... And all standard. ---------------------------------------------------------------------- julkas · 2019-05-12 15:53 @Thaddy my question is about general binary search algorithm, not about string handling ... ---------------------------------------------------------------------- 440bx · 2019-05-12 15:53 Quote from: julkas on May 12, 2019, 03:53:47 pmI want only insert position. C has bsearch() - standard library function, What is Pascal RTL analogs for binary search? Maybe I missed what you were trying to say but, a bsearch doesn't return any information that helps determine the insert position to keep a list sorted.  It only returns a pointer to the match if there is one, otherwise nil. As far as Pascal's analog for bsearch, if you're using Windows, just use NTDLL's bsearch and qsort (if you need it.)   The prototypes are identical to the C rtl's (quite a few of NTDLL functions are replacements for C rtl functions.) For what you want, determine the insert position in a sorted table, you'll have to write the routine yourself. ---------------------------------------------------------------------- julkas · 2019-05-12 17:41 Quote from: 440bx on May 12, 2019, 05:53:32 pmMaybe I missed what you were trying to say but, a bsearch doesn't return any information that helps determine the insert position to keep a list sorted.  It only returns a pointer to the match if there is one, otherwise nil. Yes, exactly. Python bisect_left is more powerful. 1. It gives insertion position. 2. You can get match with one line of code. Code: Python  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i pos = bisect_left(seq, val)if pos != len(seq) and seq[pos] == val: print("MATCH") Anyway, thanks for response. ---------------------------------------------------------------------- 440bx · 2019-05-12 19:29 Quote from: julkas on May 12, 2019, 07:41:16 pmYes, exactly. Python bisect_left is more powerful. 1. It gives insertion position. 2. You can get match with one line of code. Anyway, thanks for response. Undoubtedly, it is a nice feature. Anyway, you're welcome. ---------------------------------------------------------------------- jamie · 2019-05-13 00:54 Don't look that hard, hmmm Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Function Bisectleft( A:Array of LongInt; Val:LongInt):LongInt;Begin  Result := IndexDWord(A,Length(A)*SizeOf(LongInt), Val) ; End;   Assuming we are talking about dWORD types here, since LongInt is that size. ---------------------------------------------------------------------- jamie · 2019-05-13 01:25 here is a more complete function Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Function Bisectleft( Var A:Array of LongInt; Val:LongInt):LongInt;var  I:Integer;Begin  Result := IndexDWord(A,Length(A)*SizeOf(LongInt), Val);  If Result <> -1 then   begin     Move(PLongInt(@A[Result])^, PLongInt(@A[Result+1])^,(Length(A)-Result)*SizeOf(LongInt));   end;end;                       This does not grow the Array but will move all items up one notch if it finds it which creates a duplicate. ---------------------------------------------------------------------- jamie · 2019-05-13 01:44 Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Function Bisectleft( Var A:Array of LongInt; Val:LongInt;LoIndex:LongInt=0;HiIndex:LongInt=-1):LongInt;var  I:Integer;Begin  if HiIndex = -1 then HiIndex := High(A);  Result := IndexDWord(PlongInt(@A[loIndex])^,(HiIndex-LoIndex)*SizeOf(LongInt), Val);  If Result <> -1 then   begin     Result +=LoIndex;     Move(PLongInt(@A[Result])^, PLongInt(@A[Result+1])^,(Length(A)-Result)*SizeOf(LongInt));   end;end;                                         One that has optional LO and HIGH Range! ---------------------------------------------------------------------- julkas · 2019-05-13 08:45 Quote from: jamie on May 13, 2019, 02:54:55 amDon't look that hard, hmmm Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Function Bisectleft( A:Array of LongInt; Val:LongInt):LongInt;Begin  Result := IndexDWord(A,Length(A)*SizeOf(LongInt), Val) ; End;   Assuming we are talking about dWORD types here, since LongInt is that size. 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. https://www.freepascal.org/docs-html/rtl/system/indexdword.html ---------------------------------------------------------------------- julkas · 2019-05-13 12:28 I see two options 1. Bindings to C library, from stdlibh.inc Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Type  __compar_fn_t = function (_para1:pointer; _para2:pointer):longint;cdecl;  comparison_fn_t = __compar_fn_t; function bsearch(__key:pointer; __base:pointer; __nmemb:size_t; __size:size_t; __compar:__compar_fn_t):pointer;cdecl;external clib name 'bsearch'; BTW - from http://wiki.freepascal.org/libc_unit QuoteThe libc unit is deprecated, and frozen in time for Kylix compatibility, and won't be ported to other architectures or operating systems. 2. Make your own ! ---------------------------------------------------------------------- jamie · 2019-05-13 20:50 I ran with the specs you gave.. You are using a Longint, that is 4 bytes worth of info.. You also stated a sorted list, that is a linear search. IndexDWord finds the first value that matches, if not it returns -1 From the help file IndexDWord Search for a DWord value in a memory range. Declaration Source position: systemh.inc line 748 function IndexDWord(   const buf;   len: SizeInt;   b: DWord ):SizeInt; Description IndexDWord searches the memory at buf for maximally len positions for the DWord DW and returns it's position if it found one. If DW is not found then -1 is returned. The position is zero-based. Errors Buf and Len are not checked to see if they are valid values. This looks like it does exactly as you need, so I don't know where you are coming from. ---------------------------------------------------------------------- 440bx · 2019-05-13 21:49 Quote from: jamie on May 13, 2019, 10:50:53 pmYou also stated a sorted list, that is a linear search. How do you figure a linear search ? A linear search has an average O(n)/2 performance.  A binary search O(log n) in the worst case.  That makes a _big_ difference as n gets larger and/or the number of times the list is searched for an element. ---------------------------------------------------------------------- lucamar · 2019-05-14 01:23 Quote from: jamie on May 13, 2019, 10:50:53 pmYou 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" ---------------------------------------------------------------------- jamie · 2019-05-14 01:38 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! ---------------------------------------------------------------------- jamie · 2019-05-14 01:48 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 · 2019-05-14 01:51 Quote from: jamie on May 14, 2019, 03:38:20 amAny 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] ---------------------------------------------------------------------- 440bx · 2019-05-14 03:28 Quote from: jamie on May 14, 2019, 03:38:20 amhe never specify how large of  a data chuck he is dealing with... he didn't give a specific number but... Quote from: julkas on May 13, 2019, 10:45:59 amIndexDWord 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... ---------------------------------------------------------------------- jamie · 2019-05-15 00:20 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Function Bisectleft( Var A:Array of LongInt; Val:LongInt;LoIndex:LongInt=0;HiIndex:LongInt=-1):LongInt;var  I:Integer;      Function BinIndex(aA:Array of LongInt;AValue, AStart, AEnd:LongInt):LongInt;      var        Center:LongInt;        SearchDone :Boolean = false;       Begin         Result := -1;         Repeat;           Center := AStart+(AEnd-AStart) Div 2;            If AValue = aA[Center] Then {Found direct match}             Begin             While (aA[Center] = AValue)and(Center > AStart) do Dec(Center);               IF aA[Center]<>AValue Then Inc(Center);             Result := Center;               SearchDone := True;           End else           If AValue < aA[Center] Then {Value is above below index }             Begin              SearchDone := AStart=Center;              If SearchDone Then Result :=Center else AEnd := Center;             End Else             Begin   { Value is above index }               if (AEnd-Center < 2) Then { are we at the end ? }                 Begin                  SearchDone := True;                If AValue = aA[AEnd] Then Result := AEnd;                 end;               AStart := Center;             End;         until SearchDone;       end; Begin  if HiIndex = -1 then HiIndex := High(A);  Result := BinIndex(A,Val, LoIndex, HiIndex);  If Result <> -1 then  { Insert "VAL" if found before end "}   begin     Result +=LoIndex;     Move(PLongInt(@A[Result])^, PLongInt(@A[Result+1])^,(Length(A)-Result)*SizeOf(LongInt));     A[Result] := Val;   end;end;  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 · 2019-05-15 00:48 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i { TVDict.BinarySearch  Does a binary search for key in an array of Objects. The array must be  sorted. Returns the index if found, or the position to insert the key into a  sorted list as -i-1 if not found, so (i > -1) = found. }function TVDict.BinarySearch(key: string): integer;var  left, right, middle, comp, i: integer;begin  left := 0; // Low  right := Count-1; // High  if right < 0 then begin    result := -1; // insert at -i-1 = 0    exit;  end;  while (right - left > 0) do begin    middle := (left + right) div 2;    if CompareKey(fItems[middle].Key, key) < 0 then      left := middle + 1  else      right := middle;  end;  comp := CompareKey(fItems[left].Key, key);  if comp = 0 then // found    i := left  else if comp > 0 then    i := -left - 1 // insert at -i-1  else    i := -(left + 1) - 1; // insert at -i-1  result := i;end;