tag:blogger.com,1999:blog-29331675.post116198400390014714..comments2024-03-05T17:37:00.995+01:00Comments on The Delphi Geek: Faster than the speed of binary searchgabr42http://www.blogger.com/profile/06903558857617342477noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-29331675.post-74106678582987466482022-09-10T09:32:39.196+02:002022-09-10T09:32:39.196+02:00Hi - Check-out NoChop/STree on www.agdresearch.com...Hi - Check-out NoChop/STree on www.agdresearch.com - its already 350% faster than binary-search since being recently discoveredAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-29331675.post-42964889656016420532013-02-16T05:43:44.251+01:002013-02-16T05:43:44.251+01:00A binary search is going to be O(log n), whereas a...A binary search is going to be O(log n), whereas a hash lookup will be O(1), amortized. You would have to have a pretty terrible hash function to get worse performance than a binary search.Roberthttp://selfbookpublishers.com/noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-53823278907598576722012-05-06T20:35:27.944+02:002012-05-06T20:35:27.944+02:00<> In that case, I think you mean 'check...<> In that case, I think you mean 'check A[m] and A[m+1]'Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-29331675.post-74917494667265541852012-04-19T14:02:03.834+02:002012-04-19T14:02:03.834+02:00"This approach is very simple to use if data ..."This approach is very simple to use if data in the array is distributed uniformly."<br /><br />Here's an idea how to make any data uniformly distributed. Instead of using raw keys, use hashed keys. Hash functions like MD5 will convert any type of data to a random uniformly distributed one. Of course this adds some overhead as hash values need to be computed.Indriushttp://www.indrius.lt/noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-40236821368301547502011-05-10T21:12:04.543+02:002011-05-10T21:12:04.543+02:00I just did the same thing, both binary and interpo...I just did the same thing, both binary and interpolation search are logn, but interpolation is about 3~4 times faster than binary search. Hard to beat the logn bound.Jingerhttps://www.blogger.com/profile/03713335551561855147noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-65235548406298349042007-03-01T17:40:00.000+01:002007-03-01T17:40:00.000+01:00hy!have you to optimize this code?the most importa...hy!<BR/><BR/>have you to optimize this code?<BR/><BR/>the most important things is to find if a value in "in the list", when not insert with with a new rangeitem or "expand" an already exists range.<BR/><BR/>unit Unit_Int64List;<BR/><BR/>interface<BR/><BR/>uses<BR/> Classes;<BR/><BR/>type<BR/> TInt64RangeItem = class<BR/> private<BR/> public<BR/> StartIndex: Int64;<BR/> Start: Int64;<BR/> Stop: Int64;<BR/> class function NewInstance: TObject; override;<BR/> procedure FreeInstance; override;<BR/> protected<BR/> constructor Create(const _Start: Int64; const _Stop: Int64);<BR/> published<BR/> end;<BR/><BR/>type<BR/> TInt64List = class<BR/> private<BR/> FList: TList;<BR/> FUpdateCount: Integer;<BR/> FCount: Int64;<BR/> function GetCount: Int64;<BR/> function GetRangeCount: Integer;<BR/> function FindRangeIndex(const Value: Int64; var Index: Integer): Boolean;<BR/> procedure CalcStartIndex;<BR/> function GetRange(Index: Integer): TInt64RangeItem;<BR/> public<BR/> constructor Create;<BR/> destructor Destroy; override;<BR/> function Add(const Value: Int64): Int64;<BR/> procedure DeleteRange(const Index: Integer);<BR/> function Find(const Value: Int64; var Index: Int64): Boolean;<BR/> function FindGetPath(const Value: Int64): String;<BR/> function IndexOf(const Value: Int64): Int64;<BR/> procedure Clear;<BR/> procedure Compact(const ReCalcStartIndex: Boolean = False);<BR/> procedure SaveToStream(F: TStream);<BR/> procedure LoadFromStream(F: TStream);<BR/> //<BR/> property Count: Int64 read GetCount;<BR/> property RangeCount: Integer read GetRangeCount;<BR/> property Ranges[Index: Integer]: TInt64RangeItem read GetRange;<BR/> end;<BR/><BR/>implementation<BR/><BR/>uses<BR/> SysUtils, Unit_Utils;<BR/><BR/>const<BR/> TIntegerSize = SizeOf(Integer);<BR/><BR/>// -----------------------------------------------------------------------------<BR/>class function TInt64RangeItem.NewInstance: TObject;<BR/>type<BR/> PClass = ^TClass;<BR/>var<BR/> P: Pointer;<BR/>begin<BR/> GetMem(P, Self.InstanceSize); //Allocate Memory for this object<BR/> Result := TObject(P); // Set the result<BR/> InitInstance(P); // Initialise the Instance<BR/> PClass(Result)^ := Self; // Init VMT, don't init fields.<BR/>end;<BR/><BR/>procedure TInt64RangeItem.FreeInstance;<BR/>begin<BR/> CleanupInstance; // Clean Up<BR/> FreeMem(Pointer(Self), Self.InstanceSize); // Free Memeory<BR/>end;<BR/><BR/>constructor TInt64RangeItem.Create(const _Start: Int64; const _Stop: Int64);<BR/>begin<BR/> inherited Create;<BR/> Start := _Start;<BR/> Stop := _Stop;<BR/>end;<BR/><BR/>// -----------------------------------------------------------------------------<BR/>constructor TInt64List.Create;<BR/>begin<BR/> inherited Create;<BR/> FList := TList.Create;<BR/> FUpdateCount := 0;<BR/> FCount := 0;<BR/>end;<BR/><BR/>destructor TInt64List.Destroy;<BR/>begin<BR/> Clear;<BR/> FreeAndNil(FList);<BR/> inherited Destroy;<BR/>end;<BR/><BR/>function TInt64List.Add(const Value: Int64): Int64;<BR/>var<BR/> R: TInt64RangeItem;<BR/> RangePos: Integer;<BR/>begin<BR/> if (FindRangeIndex(Value, RangePos) = True) then<BR/> begin<BR/> R := FList.List^[RangePos];<BR/> Result := R.StartIndex + (Value - R.Start);<BR/> end else<BR/> begin<BR/> Result := 0;<BR/> if (FList.Count > 0) then<BR/> begin<BR/> if (RangePos < FList.Count) then<BR/> begin<BR/> R := FList.List^[RangePos];<BR/> if ((Value+1) = R.Start) then<BR/> R.Start := Value<BR/> else<BR/> if (RangePos > 0) then<BR/> begin<BR/> R := FList.List^[RangePos-1];<BR/> if ((R.Stop+1) = Value) then<BR/> R.Stop := Value<BR/> else<BR/> FList.Insert(RangePos, TInt64RangeItem.Create(Value, Value));<BR/> end else<BR/> FList.Insert(0, TInt64RangeItem.Create(Value, Value));<BR/> end else<BR/> begin<BR/> R := FList.List^[RangePos-1];<BR/> if ((R.Stop+1) = Value) then<BR/> R.Stop := Value<BR/> else<BR/> FList.Add(TInt64RangeItem.Create(Value, Value));<BR/> end;<BR/> end else<BR/> FList.Add(TInt64RangeItem.Create(Value, Value));<BR/> Inc(FCount);<BR/> end;<BR/>end;<BR/><BR/>procedure TInt64List.DeleteRange(const Index: Integer);<BR/>var<BR/> R: TInt64RangeItem;<BR/>begin<BR/> if (Index >= 0 ) and<BR/> (Index < FList.Count) then<BR/> begin<BR/> R := FList.List^[Index];<BR/> FList.Delete(Index);<BR/> FreeAndNil(R);<BR/> end;<BR/>end;<BR/><BR/>function TInt64List.FindRangeIndex(const Value: Int64; var Index: Integer): Boolean;<BR/>var<BR/> Low,High,Mid: Integer;<BR/> RangeCursor: TInt64RangeItem;<BR/>begin<BR/> Low := 0;<BR/> High := FList.Count - 1;<BR/> Mid := 0;<BR/> Result := False;<BR/> while not Result and ( Low <= High ) do<BR/> begin<BR/> Mid := (Low + High) shr 1;<BR/> RangeCursor := FList.List^[Mid];<BR/> if (RangeCursor.Start <= Value) and (Value <= RangeCursor.Stop) then<BR/> Result := True<BR/> else<BR/> if (Value < RangeCursor.Start) then High := Mid - 1 else<BR/> if (Value > RangeCursor.Stop ) then Low := Mid + 1;<BR/> end;<BR/> if Result then Index := Mid<BR/> else Index := Low;<BR/>end;<BR/><BR/>function TInt64List.Find(const Value: Int64; var Index: Int64): Boolean;<BR/>var<BR/> R: TInt64RangeItem;<BR/> RangePos: Integer;<BR/>begin<BR/> Index := -1;<BR/> Result := FindRangeIndex(Value, RangePos);<BR/> if (Result = True) then<BR/> begin<BR/> R := FList.List^[RangePos];<BR/> Index := R.StartIndex + (Value - R.Start);<BR/> end;<BR/>end;<BR/><BR/>function TInt64List.FindGetPath(const Value: Int64): String;<BR/>var<BR/> Low,High,Mid: Int64;<BR/> RangeCursor: TInt64RangeItem;<BR/> F: Boolean;<BR/> V: Int64;<BR/>begin<BR/> Result := '';<BR/> // Find range index ----------------------------------------------------------<BR/> F := False;<BR/> High := FList.Count - 1;<BR/> Low := 0;<BR/> Mid := 0;<BR/> while not F and ( Low <= High ) do<BR/> begin<BR/> Mid := (Low + High) div 2;<BR/> RangeCursor := FList.List^[Mid];<BR/> if (RangeCursor.Start <= Value) and (Value <= RangeCursor.Stop) then<BR/> begin<BR/> Result := Result + '11';<BR/> F := True;<BR/> end else<BR/> if (Value < RangeCursor.Start) then<BR/> begin<BR/> Result := Result + '10';<BR/> High := Mid - 1;<BR/> end else<BR/> if (Value > RangeCursor.Stop ) then<BR/> begin<BR/> Result := Result + '01';<BR/> Low := Mid + 1;<BR/> end;<BR/> end;<BR/> if (F = True) then<BR/> begin<BR/> // Find index IN range -----------------------------------------------------<BR/> Result := Result + '|';<BR/> F := False;<BR/> Low := 0;<BR/> High := TInt64RangeItem(FList.List^[Mid]).Stop - TInt64RangeItem(FList.List^[Mid]).Start;<BR/> while not F and ( Low <= High ) do<BR/> begin<BR/> Mid := (Low + High) div 2;<BR/> V := TInt64RangeItem(FList.List^[Mid]).Start + Mid;<BR/> if (Value = V) then<BR/> begin<BR/> Result := Result + '11';<BR/> F := True;<BR/> end else<BR/> if (Value < V) then<BR/> begin<BR/> Result := Result + '10';<BR/> High := Mid - 1;<BR/> end else<BR/> if (Value > V) then<BR/> begin<BR/> Result := Result + '01';<BR/> Low := Mid + 1;<BR/> end;<BR/> end;<BR/> end else<BR/> Result := '|';<BR/>end;<BR/><BR/>function TInt64List.IndexOf(const Value: Int64): Int64;<BR/>begin<BR/> Find(Value, Result);<BR/>end;<BR/><BR/>procedure TInt64List.Clear;<BR/>var<BR/> I: Integer;<BR/>begin<BR/> if (FList.Count > 0) then<BR/> for I := (FList.Count-1) downto 0 do<BR/> begin<BR/> TInt64RangeItem(FList.List^[I]).Free;<BR/> //Dispose(FList.List^[I]);<BR/> FList.Delete(I);<BR/> end;<BR/> FList.Pack;<BR/> FList.Clear;<BR/>end;<BR/><BR/>procedure TInt64List.Compact(const ReCalcStartIndex: Boolean = False);<BR/>var<BR/> I: Integer;<BR/> C,N: TInt64RangeItem;<BR/>begin<BR/> if (FList.Count > 1) then<BR/> begin<BR/> I := 0;<BR/> repeat<BR/> C := TInt64RangeItem(FList.List^[I ]);<BR/> N := TInt64RangeItem(FList.List^[I+1]);<BR/> //<BR/> if (N.Start <= (C.Stop+1)) then<BR/> begin<BR/> if (N.Start <= C.Start) then<BR/> C.Start := N.Start;<BR/> C.Stop := N.Stop;<BR/> DeleteRange(I+1);<BR/> end else<BR/> Inc(I);<BR/> until (I = (FList.Count-1));<BR/> if (RecalcStartIndex = True) then<BR/> CalcStartIndex;<BR/> end;<BR/>end;<BR/><BR/>function TInt64List.GetCount: Int64;<BR/>begin<BR/> Result := FCount;<BR/>end;<BR/><BR/>function TInt64List.GetRangeCount: Integer;<BR/>begin<BR/> Result := FList.Count;<BR/>end;<BR/><BR/>procedure TInt64List.CalcStartIndex;<BR/>var<BR/> I: Integer;<BR/> R: TInt64RangeItem;<BR/>begin<BR/> FCount := 0;<BR/> if (FList.Count > 0) then<BR/> for I := 0 to (FList.Count-1) do<BR/> begin<BR/> R := FList.List^[I];<BR/> R.StartIndex := FCount;<BR/> Inc(FCount, (R.Stop - R.Start + 1));<BR/> end;<BR/>end;<BR/><BR/>function TInt64List.GetRange(Index: Integer): TInt64RangeItem;<BR/>begin<BR/> Result := nil;<BR/> if (0 <= Index) and (Index < FList.Count) then<BR/> Result := FList.List^[Index];<BR/>end;<BR/><BR/>procedure TInt64List.SaveToStream(F: TStream);<BR/>var<BR/> I: Integer;<BR/> R: TInt64RangeItem;<BR/> V: packed record<BR/> V1: Int64; // +8<BR/> V2: Int64; // +8<BR/> end;<BR/> M: TMemoryStream;<BR/><BR/> procedure FlushBuffer;<BR/> begin<BR/> M.Seek(0,0);<BR/> F.CopyFrom(M, M.Size);<BR/> M.Size := 0;<BR/> end;<BR/><BR/>begin<BR/> Compact;<BR/> if (FList.Count > 0) then<BR/> begin<BR/> M := TMemoryStream.Create;<BR/> for I := 0 to (FList.Count-1) do<BR/> begin<BR/> R := FList.List^[I];<BR/> V.V1 := R.Start;<BR/> V.V2 := R.Stop;<BR/> M.Write(V, 16);<BR/> if (M.Size > 65536) then<BR/> FlushBuffer;<BR/> end;<BR/> FlushBuffer;<BR/> FreeAndNil(M);<BR/> end;<BR/>end;<BR/><BR/>procedure TInt64List.LoadFromStream(F: TStream);<BR/>var<BR/> I,C: Integer;<BR/> V: packed record<BR/> V1: Int64; // +8<BR/> V2: Int64; // +8<BR/> end;<BR/> M: TMemoryStream;<BR/>begin<BR/> Clear;<BR/> M := TMemoryStream.Create;<BR/> M.Size := F.Size;<BR/> M.CopyFrom(F, F.Size);<BR/> M.Seek(0,0);<BR/> C := (M.Size div 16);<BR/> if (C > 0) then<BR/> begin<BR/> FList.Capacity := C;<BR/> for I := 1 to C do<BR/> begin<BR/> M.Read(V, 16);<BR/> FList.Add(TInt64RangeItem.Create(V.V1, V.V2));<BR/> end;<BR/> end;<BR/> FreeAndNil(M);<BR/> CalcStartIndex;<BR/>end;<BR/><BR/>end.<BR/><BR/>thx:<BR/>xclusterAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-29331675.post-1162061066269610062006-10-28T20:44:00.000+02:002006-10-28T20:44:00.000+02:00Why do you think it is a subset search? It just se...Why do you think it is a subset search? It just selects a midpoint that is "slightly" off the center.<BR/><BR/>But in general I do agree. However, tricks like this are a great way to quickly narrow down the search range and then use a binary search to find the data.gabr42https://www.blogger.com/profile/06903558857617342477noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-1162011486394700902006-10-28T06:58:00.000+02:002006-10-28T06:58:00.000+02:00Binary searchs are complete searches, where as you...Binary searchs are complete searches, where as your routine is a subset search. If you can be 100% sure that the data you seek will always be in that subset, it makes no sense to search elsewhere.<BR/><BR/>If you have ANY doubt at all, stick with the complete search. IN fact, if you fail, you might want to fall back to complete search anyways just to make sure you don't have faulty assumption about your dataset.<BR/><BR/>Data can be notioriously tricky that way.Anonymousnoreply@blogger.com