Asp Forum - An algorithm questions

dutour

5/31/2011 1:06:00 PM

I want to be able to store some numbers (in an interval [1..N] with N small
about 200) in a set X and be able to do the following
---test if a number i is inside
---remove an element of X
---add an element to X.
---get one element from X if it is non-empty.
And I want the maximum speed.

Right now, I am using the following structure

typedef struct {
int MaxElement;
int *ListElementInSubset;
int *ListNext;
int *ListPrev;
} IntegerSubsetStorage;

That is the code reads as
---MaxElement is the number N
---ListElementInSubset has size N and is a 0/1 vector to answer to the
first question.
---ListNext and ListPrev are array of size N+2 that indicate what is the
next element in X and what is the previous element in X (this allows
to answer the last 3 questions).

All this works fine and I can answer all questions without any iterative
loop. But can it be done better?

Mathieu

9 Answers

ram

5/31/2011 1:25:00 PM

dutour@quatramaran.ens.fr (Mathieu Dutour) writes:
>I want to be able to store some numbers (in an interval [1..N] with N small
>about 200) in a set X and be able to do the following
>---test if a number i is inside

inline int contains( int const set[], int const i ){ return set[ i ]; }

>---remove an element of X

inline void remove( int set[], int const i ){ set[ i ]= 0; }

>---add an element to X.

inline void add( int set[], int const i ){ set[ i ]= 1; }

>---get one element from X if it is non-empty.

int get( int set[], int const n )
{ int i = -1; set[ n ]= -1;
while( !set[ ++i ]); return set[ i ]; }

China Blue Veins

5/31/2011 1:43:00 PM

In article <set-20110531152335@ram.dialup.fu-berlin.de>,
ram@zedat.fu-berlin.de (Stefan Ram) wrote:

> dutour@quatramaran.ens.fr (Mathieu Dutour) writes:
> >I want to be able to store some numbers (in an interval [1..N] with N small
> >about 200) in a set X and be able to do the following
> >---test if a number i is inside
>
> inline int contains( int const set[], int const i ){ return set[ i ]; }
>
> >---remove an element of X
>
> inline void remove( int set[], int const i ){ set[ i ]= 0; }
>
> >---add an element to X.
>
> inline void add( int set[], int const i ){ set[ i ]= 1; }
>
> >---get one element from X if it is non-empty.
>
> int get( int set[], int const n )
> { int i = -1; set[ n ]= -1;
> while( !set[ ++i ]); return set[ i ]; }

Keep the the least and greatest element with bit vector. Tests, adds, and
selects are all O(1). Deletes of the least or greatest are O(n) otherwise O(1).
Other set operations are O(n).

--
I remember finding out about you, | I survived XYZZY-Day.
Everyday my mind is all around you,| I'm whoever you want me to be.
Looking out from my lonely room |Annoying Usenet one post at a time.
Day after day. | At least I can stay in character.

cri

5/31/2011 2:12:00 PM

On 31 May 2011 13:24:56 GMT, ram@zedat.fu-berlin.de (Stefan Ram)
wrote:

>dutour@quatramaran.ens.fr (Mathieu Dutour) writes:
>>I want to be able to store some numbers (in an interval [1..N] with N small
>>about 200) in a set X and be able to do the following
>>---test if a number i is inside
>
>inline int contains( int const set[], int const i ){ return set[ i ]; }
>
>>---remove an element of X
>
>inline void remove( int set[], int const i ){ set[ i ]= 0; }
>
>>---add an element to X.
>
>inline void add( int set[], int const i ){ set[ i ]= 1; }
>
>>---get one element from X if it is non-empty.
>
>int get( int set[], int const n )
>{ int i = -1; set[ n ]= -1;
> while( !set[ ++i ]); return set[ i ]; }
>

Your get is a O(n) linear search. The original code is O(1). That
said, your code might very well be faster in the context of the
problem.

Roberto Waltman

5/31/2011 4:41:00 PM

Gene

6/1/2011 4:28:00 AM

On May 31, 9:06 am, dut...@quatramaran.ens.fr (Mathieu Dutour) wrote:
> I want to be able to store some numbers (in an interval [1..N] with N small
> about 200) in a set X and be able to do the following
> ---test if a number i is inside
> ---remove an element of X
> ---add an element to X.
> ---get one element from X if it is non-empty.
> And I want the maximum speed.
>
> Right now, I am using the following structure
>
> typedef struct {
> int MaxElement;
> int *ListElementInSubset;
> int *ListNext;
> int *ListPrev;
>
> } IntegerSubsetStorage;
>
> That is the code reads as
> ---MaxElement is the number N
> ---ListElementInSubset has size N and is a 0/1 vector to answer to the
> first question.
> ---ListNext and ListPrev are array of size N+2 that indicate what is the
> next element in X and what is the previous element in X (this allows
> to answer the last 3 questions).
>
> All this works fine and I can answer all questions without any iterative
> loop. But can it be done better?
>
> Mathieu

The advice to use bitmaps for N=200 is good.
I'll point out however, that your method can be made simpler and
probably faster by implementing the linked list in the same array you
use to indicate membership.

in other words, use something like the following (UNTESTED) cod:

// Sets hold 1 .. SET_SIZE
#define SET_SIZE 200

typedef unsigned char INDEX; // big enough for N < 256

typedef struct {
INDEX next, prev;
} SET_NODE;

// Use 0'th element for list header...
typedef SET_NODE SET[SET_SIZE];

// Initialize each item to a self-circular list. There are other
// possibilities, but this has a nice symmetry, and 0 won't work.
void init(SET set)
{
INDEX i;
for (i = 0; i < SET_SIZE; i++)
set[i].next = set[i].prev = i;
}

// If item is not self-circular, it's in the set.
int is_member(SET set, int item)
{
return set[item].next != item;
}

// Join item's list to head's list.
void add(SET set, int item)
{
if (!is_member(set, item)) {
INDEX head = set[0].next;
set[item].prev = (INDEX)0;
set[item].next = head;
set[0].next = set[head].prev = (INDEX)item;
}
}

// Unlink item from head's list and restore it's self-loop.
void remove(SET set, int item)
{
if (is_member(set, item)) {
set[set[item].next].prev = set[item].prev;
set[set[item].prev].next = set[item].next;
set[item].prev = set[item].next = (INDEX)item;
}
}

// Returns 0 if there is no member, else the last member added.
int get_member(SET set)
{
return set[0].next;
}

cri

6/3/2011 2:00:00 PM

cri

6/3/2011 9:43:00 PM

On Tue, 31 May 2011 13:06:21 +0000 (UTC), dutour@quatramaran.ens.fr
(Mathieu Dutour) wrote:

>I want to be able to store some numbers (in an interval [1..N] with N small
>about 200) in a set X and be able to do the following
>---test if a number i is inside
>---remove an element of X
>---add an element to X.
>---get one element from X if it is non-empty.
>And I want the maximum speed.
>
>Right now, I am using the following structure
>
>typedef struct {
> int MaxElement;
> int *ListElementInSubset;
> int *ListNext;
> int *ListPrev;
>} IntegerSubsetStorage;
>
>That is the code reads as
>---MaxElement is the number N
>---ListElementInSubset has size N and is a 0/1 vector to answer to the
> first question.
>---ListNext and ListPrev are array of size N+2 that indicate what is the
> next element in X and what is the previous element in X (this allows
> to answer the last 3 questions).
>
>All this works fine and I can answer all questions without any iterative
>loop. But can it be done better?

Nice little problem. Here is a list of the different answers you got
plus a couple not mentioned.

Storage:
Mathieu Dutour -- Doubly linked list in two arrays + a {1,0} array
Gene -- Doubly linked list in one array
Stefan Ram -- Int array with {1,0} entries with linear search
China Blue Angels -- Bit vector, keep min and max
Roberto Waltman -- Bit vector, short search for get
Richard Harter -- Tiered bit vector (see below)
Richard Harter -- The devil's list algorithm (see below)
Richard Harter -- The packed set algorithm

One of the problems with asking for the "best" solution is that there
is no best solution for all environments. "Fast" depends upon sundry
considerations. Thus in the past century execution times were roughly
proportional to instructions. In this century cache misses are often
the dominant factor affecting execution times. In algorithm analysis
it is customary to characterize algorithms by their big O behaviour.
However this often is inappropriate for small n. Another factor is
that the cost of very simple functions is dominated by context
switching costs. Etc.

All of that said, it is useful to look at (a) the instruction cost,
and (b) the storage used. The storage costs are:

Storage use:
Devil's list algorithm: 3 words per item
Doubly linked list: 3 words per item (Dotour)
Doubly linked list: 2 words per item (Gene)
Packed set algorithm: 2 words per item
Int list, {0,1} entries: 1 word per item
Bit vector: 1 bit per item

Instruction costs:

The linked list variants are all O(1); however they all take about 5
statements per operation with dereferencing costs. The integer list
with all entries 0 or 1 requires the fewest statements per operation
except for "get" which has a potential O(n) cost. (See below).

The bit vector variants all have about 3-5 bit manipulations per
operation. They are cheaper than the linked list variants because
they have lower dereferencing costs. The "keep min and max" variant
has O(n) costs and cannot be recommended. The others are O(1) for all
operations.

Manipulating bit vectors:

One disadvantage of using bit vectors is that they can be word size
dependent; I prefer to use unsigned char arrays for that reason; YMMV.
Another is that you need to be familiar with the bit hacks. Frex
(check these, it's been ages and I probably have goofed.)

unsigned char v[25];
v[x>>3] |= 1<<(x&7); // Sets the x'th bit 1
v[x>>3] &= ~(1<<(x&7)); // Unsets the x'th bit

The formula for finding the lowest bit in x that is set is

x & ~(x-1)

Use this for the "get" operation.

Tiered bit vectors:

The idea here is to a bit vector for the set/unset elements, and a
second bit vector for the zero/non-zero chars/words in the base bit
vector. Thus if you are setting a bit in the j'th char, also set the
j'th bit in the upper bit vector (one char in this case). If you are
unsetting a bit in the j'th char and doing so clears the j'th char,
then unset the j'th bit in the upper bit vector.

For the get operation use the lowest bit formula to find a set bit in
upper bit vector; this tells you which char to extract an int from.

Tiered bit vectors are more expensive per operation (get excepted)
than a simple bit vector but they are O(log n) for gets rather than
the O(n) search needed for a simple bit vector. For n ~= 200 a tiered
bit vector is overkill.

The Devil's list algorithm:

The devil's algorithm for deleting an item from a singly linked list
is as follows: Let x be the the node holding the item; replace the
contents of x by the contents of x->link. This actually works
provided two conditions are met: (a) the list is terminated with a
node that will never be deleted, and (b) all references to the former
x->link node must be updated.

For this problem we need a singly linked list with nodes {i,link} and
an array of node pointers that, for each element, holds a pointer to
the corresponding list node. When an item is deleted the entry for
the deleted integer is cleared and the entry moved integer is updated.

It turns out that the Devil's list algorithm uses slightly fewer
statements than a doubly linked list implementation; however it uses
more storage.

The packed set algorithm:

In the packed set algorithm the integers in the set are kept in an
array without gaps. When an item is added it is added to the end of
the array and the array length is incremented. When an item is
deleted the item at the end replaces the deleted item and the array
length is decremented.

In this context we need a second array. Each location in the second
array holds the location of the integer in the packed array. When an
item is deleted/added the entry in the second array is updated.

The packed set algorithm is an O(1) algorithm. It uses fewer
statements per operation than using a doubly linked list and no more
space.

Behaviour of the integer list search algorithm:

Briefly, the search tend to take O(m) probes where m is the number of
empty slots in the array. The reason is that the search scans from
one side to the other. Over time the end not searched becomes full.
New additions are made into the empty end are rapidly removed. This
effect is minimal if m is small or if the ratio of delete to gets is
large.

Conclusions:

The choices from best to worst probably are:

Simple bit vector
Tiered bit vector
* Array of {0,1} integers
Packed set array
Doubly linked list
Devil's list algorithm

* "Get" may be expensive

In any particular situation the results may be different.

Gene

6/3/2011 11:48:00 PM

On Jun 3, 5:43 pm, c...@tiac.net (Richard Harter) wrote:
> On Tue, 31 May 2011 13:06:21 +0000 (UTC), dut...@quatramaran.ens.fr
>
>
>
>
>
> (Mathieu Dutour) wrote:
> >I want to be able to store some numbers (in an interval [1..N] with N small
> >about 200) in a set X and be able to do the following
> >---test if a number i is inside
> >---remove an element of X
> >---add an element to X.
> >---get one element from X if it is non-empty.
> >And I want the maximum speed.
>
> >Right now, I am using the following structure
>
> >typedef struct {
> > int MaxElement;
> > int *ListElementInSubset;
> > int *ListNext;
> > int *ListPrev;
> >} IntegerSubsetStorage;
>
> >That is the code reads as
> >---MaxElement is the number N
> >---ListElementInSubset has size N and is a 0/1 vector to answer to the
> > first question.
> >---ListNext and ListPrev are array of size N+2 that indicate what is the
> > next element in X and what is the previous element in X (this allows
> > to answer the last 3 questions).
>
> >All this works fine and I can answer all questions without any iterative
> >loop. But can it be done better?
>
> Nice little problem. Here is a list of the different answers you got
> plus a couple not mentioned.
>
> Storage:
> Mathieu Dutour -- Doubly linked list in two arrays + a {1,0} array
> Gene -- Doubly linked list in one array
> Stefan Ram -- Int array with {1,0} entries with linear search
> China Blue Angels -- Bit vector, keep min and max
> Roberto Waltman -- Bit vector, short search for get
> Richard Harter -- Tiered bit vector (see below)
> Richard Harter -- The devil's list algorithm (see below)
> Richard Harter -- The packed set algorithm
>
> One of the problems with asking for the "best" solution is that there
> is no best solution for all environments. "Fast" depends upon sundry
> considerations. Thus in the past century execution times were roughly
> proportional to instructions. In this century cache misses are often
> the dominant factor affecting execution times. In algorithm analysis
> it is customary to characterize algorithms by their big O behaviour.
> However this often is inappropriate for small n. Another factor is
> that the cost of very simple functions is dominated by context
> switching costs. Etc.
>
> All of that said, it is useful to look at (a) the instruction cost,
> and (b) the storage used. The storage costs are:
>
> Storage use:
> Devil's list algorithm: 3 words per item
> Doubly linked list: 3 words per item (Dotour)
> Doubly linked list: 2 words per item (Gene)

Just saying... The array implementation of the linked list can use
indexes sized for the set. Thus the items in my code only use half as
word (2 bytes) if N < 256, and of course 1 word (4 bytes) would
suffice for N < 2^16.

This is an old space-saving trick. Back in the day, gcc allocated
syntax tree nodes in arrays so "pointers" could be 2 bytes rather than
4. Doubt that's still true because it limited syntax trees to 64K
nodes.

cri

6/4/2011 4:11:00 PM

On Fri, 3 Jun 2011 16:47:47 -0700 (PDT), Gene <gene.ressler@gmail.com>
wrote:

>On Jun 3, 5:43=A0pm, c...@tiac.net (Richard Harter) wrote:
[snip long winded article]
>>
>> Storage use:
>> Devil's list algorithm: 3 words per item
>> Doubly linked list: =A0 =A0 3 words per item (Dotour) =A0
>> Doubly linked list: =A0 =A0 2 words per item (Gene)
>
>Just saying... The array implementation of the linked list can use
>indexes sized for the set. Thus the items in my code only use half as
>word (2 bytes) if N < 256, and of course 1 word (4 bytes) would
>suffice for N < 2^16.

>
>This is an old space-saving trick. Back in the day, gcc allocated
>syntax tree nodes in arrays so "pointers" could be 2 bytes rather than
>4. Doubt that's still true because it limited syntax trees to 64K
>nodes.

Just so. Of course you have to be careful about stumbling over corner
cases, but that's part of the job description. I speak as a man who
missed a corner case once upon a time.

A nice thing about uses indices rather than pointers is that they are
relative addresses - offsets if you like. Data structures that use
indices are much easier to relocate and serialize.

comp.lang.c

An algorithm questions

dutour

ram

China Blue Veins

cri

Roberto Waltman

Gene

cri

cri

Gene

cri

x Login to ForumsZone