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

List:       kde-devel
Subject:    Re: Which data structure for random deletion?
From:       Anatoli Gorchetchnikov <anatoli () cns ! bu ! edu>
Date:       2002-01-31 16:24:04
[Download RAW message or body]

I think the point was that you can't choose the same item twice 
accidentally, but your way does not ensure it.

On Thursday 31 January 2002 06:56, Adriaan de Groot wrote:
> 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).
 
>> Visit http://mail.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<
[prev in list] [next in list] [prev in thread] [next in thread]