Forum > General

Sets of LongInt

(1/3) > >>

Spribo:
I recently made a program that has to store uniquely some numbers greater than 255 (LongInt). I couldn't use sets of LongInt so I used arrays, but elements were repeated and, when I had to check if a given number was in that array, it took ages to execute! The greater index of this array should be 6546, but instead was 35578! How could I use sets of LongInt or solve this problem in general? Any help will be greatly appreciated!

Martin_fr:
That depends on the usage pattern of the data.

If you do a lot of lookups, but very, very few inserts (or updates/changes), then you can have a sorted array/list => and use binary search for the lookup/search.
- easy to implement
- fast lookup
- slow insert/update

Otherwise you can look at structures like hashes.

A hash can perform very quickly. But you must handle clashes correctly.
Unless you work on a fixed set of numbers, and you can guarantee a perfect hashing http://en.wikipedia.org/wiki/Hash_function#Perfect_hashing

There may/should be some implementations already, but I don't know where...

bflm:

--- Quote from: Spribo on July 17, 2010, 02:12:18 pm ---I recently made a program that has to store uniquely some numbers greater than 255 (LongInt). I couldn't use sets of LongInt so I used arrays, but elements were repeated and, when I had to check if a given number was in that array, it took ages to execute! The greater index of this array should be 6546, but instead was 35578! How could I use sets of LongInt or solve this problem in general? Any help will be greatly appreciated!

--- End quote ---

A possible solution (not tested):

--- Code: ---uses
  fgl;

type

  { TMySet }

  TMySet = class(specialize TFPGMap<Integer, Boolean>)
  public
    function IsMember(const N: Integer): Boolean;
    procedure Include(const N: Integer);
    procedure Exclude(const N: Integer);
  end;

implementation

  { TMySet }

  function TMySet.IsMember(const N: Integer): Boolean;
  begin
    Result := IndexOf(N) >= 0;
  end;

  procedure TMySet.Include(const N: Integer);
  begin
    KeyData[N] := True;
  end;

  procedure TMySet.Exclude(const N: Integer);
  begin
    Remove(N);
  end;

--- End code ---

Might require FPC >=2.5.1

marcov:
Have a look at Classes.TBits.

Spribo:
Thank you very much for your help! I have a question: what does "specialize TFPGMap<Integer, Boolean>" mean?

Navigation

[0] Message Index

[#] Next page