commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ted Dunning <ted.dunn...@gmail.com>
Subject Re: [Bag] random pick
Date Sun, 17 Mar 2013 02:02:59 GMT
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".

On Sat, Mar 16, 2013 at 6:25 PM, Othmen Tiliouine <
tiliouine.othmen@gmail.com> wrote:

> This is an example of use of pick from Bag
>
> https://github.com/influence160/flera
>
> see the classes
>
> https://github.com/influence160/flera/blob/master/flera-core/src/main/java/com/otiliouine/flera/SuccessionBasedWordGenerator.javaand
>
> https://github.com/influence160/flera/blob/master/flera-core/src/main/java/com/otiliouine/flera/analyzer/SuccessionBasedDictionaryAnalyzer.java
>
>
> 2013/3/13 Othmen Tiliouine <tiliouine.othmen@gmail.com>
>
> > I remplaced the patch
> >
> > 2013/3/13 Ted Dunning <ted.dunning@gmail.com>
> >
> >> You seem to have reformatted the entire file.  This makes it nearly
> >> impossible to review your suggested change.
> >>
> >> Can you make a diff that doesn't involve changing every line in the
> file?
> >>
> >> On Tue, Mar 12, 2013 at 3:48 PM, Othmen Tiliouine <
> >> tiliouine.othmen@gmail.com> wrote:
> >>
> >> > i puted the suggestion and attached the patch
> >> >
> >> > https://issues.apache.org/jira/browse/COLLECTIONS-448
> >> >
> >> > 2013/3/12 Thomas Neidhart <thomas.neidhart@gmail.com>
> >> >
> >> > > On 03/12/2013 08:58 AM, Othmen Tiliouine wrote:
> >> > > > Thank you Ted,
> >> > > >
> >> > > > I understand from your mail that there is no particular reason
> that
> >> > makes
> >> > > > that the interface Bag no contains these methods and that this
> >> subject
> >> > > has
> >> > > > never been discussed in the mailing list.
> >> > > >
> >> > > > I'll see if I can create this patch this weekend, but i want
to
> >> know,
> >> > > what do
> >> > > > you think what are the methods I should add
> >> > > >
> >> > > > public Object pick(); //pick random element (with remove)
> >> > > > public Object pickAndRemit() ; //pick random element (without
> >> remove)
> >> > > > public Collection pick(int n); //pick random n element (with
> remove)
> >> > > > public Collection pickAndRemit(int n) ; //pick random n element
> >> > (without
> >> > > > remove)
> >> > > > public Iterator pick(int n); //pick random n element (with remove)
> >> > > > public Iterator pickAndRemit(int n) ; //pick random n element
> >> (without
> >> > > > remove)
> >> > > > public List pick(int n); //pick random n element (with remove)
> >> > > > public List pickAndRemit(int n) ; //pick random n element (without
> >> > > remove)
> >> > > > public Bag pick(int n); //pick random n element (with remove)
> >> > > > public Bag pickAndRemit(int n) ; //pick random n element (without
> >> > remove)
> >> > > >
> >> > > > maby i must provide the two kind of methods  ( Bag pick(int n)
and
> >> > > Iterator
> >> > > > pickOrdered(int n) ) ?
> >> > > >
> >> > > >
> >> > > > there is something I do not understand why the bag does not use
> >> > generics
> >> > > ?
> >> > >
> >> > > the current version of collections in the trunk is already adapted
> to
> >> > > generics. We are currently in the process of preparing a release
> >> (4.0).
> >> > >
> >> > > So when you provide a patch, please align it to the version in the
> >> trunk.
> >> > >
> >> > > Thomas
> >> > >
> >> > >
> ---------------------------------------------------------------------
> >> > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> >> > > For additional commands, e-mail: dev-help@commons.apache.org
> >> > >
> >> > >
> >> >
> >>
> >
> >
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message