commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Neidhart <thomas.neidh...@gmail.com>
Subject Re: [Bag] random pick
Date Sun, 17 Mar 2013 09:18:39 GMT
On 03/17/2013 03:02 AM, Ted Dunning wrote:
> I think that this implementation is a problem.
> 
> Bag implementations tend to fall into different categories, according to
> whether they provide unit (or log) time random access, random deletion and
> ordered traversal.  Most implementations don't provide unit time for all
> operations.
> 
> I think that your implementation assumes multiple operations have unit
> time.  Otherwise sampling all of the items will take quadratic time.
> 
> Also, your implementations alter the underlying collections.  That seems
> like a bad policy.
> 
> Sampling without replacement can be implemented as iteration over a
> permutation with unit amortized time.  A trivial implementation uses
> an auxiliary array.  It is also possible to do without the auxiliary.  You
> can get unit amortized time for linked list permutations as well, but it is
> difficult to do without the extra storage.
> 
> Finally, the names should not consist of combinations of "pick" and
> "remit".  The correct English terms are "sample" and "replacement".

additionally, I would prefer this feature to be a decorator rather than
altering the bag interface for it.

Thomas

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message