Hi there,
The other day, I wanted to write a code to memorize and search some
values (something like the following):
MyMap := TIntIntMap.Create;
for i := 1 to ABigNumber do
MyMap.Insert(AnIncreasingFunction(i),
ComputationallyExpensiveFunction(AnIncreasingFunction(i)));
To have fast lookup, I had to set myMap.Sorted := True. But then noticed
that setting this property, in the worst case, requires O(ABigNumber^2)
step: TFPSMap.SetSorted is implemented as:
if Value = FSorted then exit;
FSorted := Value;
if Value then Sort;
The keys are sorted and Sort is a quick sort (which sucks if the input
data is already sorted).
Wondering if it makes sense to change the implementation to
if Value = FSorted then exit;
FSorted := Value;
if Value and not IsSortedFunc then
Sort;
The other option could be to add a new read-only MyMap.IsSorted where
the getter is implemented as:
if FSorted then
Exit(True);
FSorted := IsSortedFunc;
Result := FSorted;
Thanks,
Amir
_______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
