[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-devel
Subject:    Re: Which data structure for random deletion?
From:       Adriaan de Groot <adridg () sci ! kun ! nl>
Date:       2002-01-31 11:56:15
[Download RAW message or body]

On Thu, 31 Jan 2002, Erik Sigra wrote:
> Which container should I use to chose K elements from N?

Assumption 1: K is small compared to N.

> Items[index] must be removed from the container so that it will not be chosen
> again.
>
> I could use a QPtrList and it would be easy to delete the item, but it would
> take too long time to find it.

Do it backwards: use a QList<int> or QList<index_t> and fill the list
first with K distinct elements. Since that list is short compared to the
list of size N, operations on it are relatively quick.

	/* A quick hack */
	QValueList<int> l;

	for (int i = 0; i<K; i++)
	{
		int j = random() % N;
		if (!l.contains(j)) l.append(j);
	}

Now perform the operations you need on the indexed elements you have
found. Heck, you could even l.sort() and then you'd need only one
iteration though the list of N items.

Note that this approach may not proviude you with very random selections
of elements and in pathological cases it may not terminate, either. (this
is just /me covering my algorithmic butt, eh).

-- 
+------------------------------+--------------------------------------------+
+ Adriaan de Groot             + Project: FRESCoS                           +
+ adridg@cs.kun.nl             + Private: adridg@sci.kun.nl                 +
+ Kamer A6020 tel. 024 3652272 + http://www.cs.kun.nl/~adridg/frescos/      +

 
>> Visit http://mail.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<
[prev in list] [next in list] [prev in thread] [next in thread]