CODEWITHSUNDEEP
delphi
Franz
Franz

Reputation: 2049

understanding TDictionary on IntegerList

can I create a TDictionary directly on a TList class ? It looks a bit double work if I create my TDictionary Class with key and values are always the same data like BlackList.Add(1, 1); 

var
  BlackList: TDictionary<Integer, Integer>;
  ResultList: TDictionary<Integer, Integer>;
  TestListA: TLIst<Integer>;
  TestListB: TLIst<Integer>;
  i: Integer;
begin
  BlackList.Add(1, 1);
  BlackList.Add(2, 2);

  for i := 0 to TestListA.Count - 1 do
  begin
    if BlackList.ContainsValue(TestListA[i]) then
    begin
      // no action ...
    end
    else
    begin
      ResultList.Add(i, TestListA[i]);
    end;
  end;

  for i := 0 to TestListB.Count - 1 do
  begin
    if BlackList.ContainsValue(TestListB[i]) then
    begin
      // no action ...
    end
    else
    begin
      if not(ResultList.ContainsValue(TestListB[i])) then
        ResultList.Add(i, TestListB[i]);

    end;
  end;
end;

The purpose of this algorithm is to compare 2 Integer list's , find all doubles but exclude numbers from a blacklist. The first q is here Find common elements in two Integer List.

Upvotes: 0

Views: 360

Answers (1)

David Heffernan
David Heffernan

Reputation: 613422

The whole purpose, in this particular code, of using TDictionary is to take advantage of O(1) lookup. With TList, which is an array, you do not have that property. Lookup is O(n) in general, O(log n) if sorted. So you cannot extract the O(1) lookup performance from a TList by any means, hence the use of TDictionary.

So it is the performance motivation that is driving the use of TDictionary. As I said in your previous question, the overhead of setting up dictionaries is only worthwhile if the lists are large. You would need to do some benchmarking to quantify what large means in this context.

As for your dictionary, it does not matter what values you use since only the keys are significant. So use zero always. Ideally what you want is a hash set type based on the same algorithm as the dictionary. But I don't believe there is such a thing in the stock RTL. I expect that libraries like Spring4D offer that functionality.

Upvotes: 3

Related Questions