Recent

Author Topic: TFPObjectHashTable more efficient way to filter objects  (Read 959 times)

y.ivanov

  • Sr. Member
  • ****
  • Posts: 306
TFPObjectHashTable more efficient way to filter objects
« on: September 20, 2021, 02:55:26 pm »
I'm trying to sweep the contents of a TFPObjectHashTable according to some filtering condition. Since it can't be iterated in a linear manner (it is a hash table), the only way I've realized so far is the following:
Code: Pascal  [Select][+][-]
  1. type
  2.   TTagCodeHash = class(TFPObjectHashTable)
  3.   protected
  4.     procedure IsValid(Item: TObject; const Key: string; var Continue: Boolean);
  5.   public
  6.     procedure Sweep1;
  7.     procedure Sweep2;
  8.   end;
  9.  
  10. ...
  11.  
  12. { TTagCodeHash }
  13.  
  14. procedure TTagCodeHash.IsValid(Item: TObject; const Key: string;
  15.   var Continue: Boolean);
  16. begin
  17.   Continue := some_check_for_validity(Item);
  18. end;
  19.  
  20. procedure TTagCodeHash.Sweep1;
  21. var
  22.   Item: THTObjectNode;
  23. begin
  24.   repeat
  25.     Item := ForEachCall(IsValid);
  26.     if Assigned(Item) then
  27.       Delete(Item.Key);
  28.   until not Assigned(Item);
  29. end;

But this will call ForEachCall() from the beginning each time after item was deleted.
The next thing I have tried was:
Code: Pascal  [Select][+][-]
  1. procedure TTagCodeHash.Sweep2;
  2. var
  3.   I, J: LongWord;
  4.   Valid: Boolean;
  5. begin
  6.   for I := Pred(HashTableSize) downto 0 do
  7.     if Assigned(Chain(I)) then
  8.        for J := Pred(Chain(I).Count) downto 0 do
  9.        begin
  10.          IsValid(THTObjectNode(Chain(I)[J]).Data, '', Valid);
  11.          if not Valid then
  12.          begin
  13.            {$IF 0}
  14.            Chain(I).Delete(J);
  15.            Dec(FCount); // <-- Can't access private member FCount
  16.            {$ELSE}
  17.            Delete(THTObjectNode(Chain(I)[J]).Key);
  18.            {$ENDIF}
  19.          end;
  20.        end;
  21. end;
But the Count property is read-only and FCount is private, so the only way to decrement is to call Delete().

Both ForEachCall() and Delete() will start again from the beginning of the table/chain, which is not the most efficient way for filtering.

Does anyone have a better idea how to filter the hash table more efficiently?

ASerge

  • Hero Member
  • *****
  • Posts: 1888
Re: TFPObjectHashTable more efficient way to filter objects
« Reply #1 on: September 20, 2021, 11:14:47 pm »
But the Count property is read-only and FCount is private, so the only way to decrement is to call Delete().
Well, if you really need it :-X:
Code: Pascal  [Select][+][-]
  1. {$MODE OBJFPC}
  2. {$LONGSTRINGS ON}
  3. {$APPTYPE CONSOLE}
  4.  
  5. uses Contnrs;
  6.  
  7. function GetAddressOfReadFieldForProperty(constref Prop: LongWord): PLongWord; inline;
  8. begin
  9.   Result := @Prop;
  10. end;
  11.  
  12. procedure Test;
  13. var
  14.   Hash: TFPObjectHashTable;
  15. begin
  16.   Hash := TFPObjectHashTable.Create;
  17.   try
  18.     Hash.Add('Some', nil);
  19.     Writeln('Hash count: ', Hash.Count);
  20.     GetAddressOfReadFieldForProperty(Hash.Count)^ := 0;
  21.     Writeln('Hash count: ', Hash.Count);
  22.   finally
  23.     Hash.Free;
  24.   end;
  25. end;
  26.  
  27. begin
  28.   Test;
  29.   Readln;
  30. end.

PascalDragon

  • Hero Member
  • *****
  • Posts: 3518
  • Compiler Developer
Re: TFPObjectHashTable more efficient way to filter objects
« Reply #2 on: September 21, 2021, 09:05:43 am »
Does anyone have a better idea how to filter the hash table more efficiently?

Best right now is to filter those you want to keep into a separate list and then readd them. Otherwise use some other container type that's more efficiently filterable than a TFPObjectHashTable.

If you go the route of ASerge I'm going to feel the urge to change the property from a field getter to a method getter in trunk just to spite anyone relying on implementation details. >:D

y.ivanov

  • Sr. Member
  • ****
  • Posts: 306
Re: TFPObjectHashTable more efficient way to filter objects
« Reply #3 on: September 22, 2021, 10:18:52 am »
Well, if you really need it :-X:
I won't need it that much  :D

I can add another property along with the Count to track deletes or simply ignore it.

Best right now is to filter those you want to keep into a separate list and then readd them. Otherwise use some other container type that's more efficiently filterable than a TFPObjectHashTable.

Perhaps you're right. Looking at the code it comes to mind that clearing the hash table and re-adding will be less costly than searching and deleting from chains/lists. I can splice TFPObjectHashTable with TFPObjectList and use the latter just for the iteration.

My question was more whether there is another more suitable map container with a reverse iterator or something like that. I'm a bit confused by the abundance of different types of containers for the same thing, i.e. hashtables, maps, dictionaries, etc.

Thanks for the replies,

 

TinyPortal © 2005-2018