Forum > General

Sets of LongInt

**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