Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Re: Re: generating submultisets with

• To: mathgroup at smc.vnet.net
• Subject: [mg103836] Re: [mg103814] Re: [mg103799] Re: generating submultisets with
• From: Leonid Shifrin <lshifr at gmail.com>
• Date: Thu, 8 Oct 2009 07:52:30 -0400 (EDT)
• References: <hadc3d$bjo$1@smc.vnet.net> <200910061202.IAA19756@smc.vnet.net>

Kurt,

I disagree. If a solution based on efficient Mathematica built-ins turns out
to be inefficient, this usually means either that some underlying data
structures are used improperly (say, arrays instead of linked lists like
with Append etc in loops), or that the  algorithm does a lot of unnecessary
moves or creates vastly more objects than needed and then utilizes only a
small subset of them.

My experience is that  for many efficient algorithms it may take
considerable effort to translate them to Mathematica in a way which takes
the maximal performance advantage of idiomatic Mathematica programming.
Conversely, I feel that the  programming based exclusively on operations
which deal with entire lists often  provokes one to create succinct  but
inefficient solutions, whose inefficiency for smaller lists is often hidden
by the efficiency of underlying built-ins used. For many such cases, Compile
(and associated with it shift towards a more procedural programming style)
seems to offer a good alternative - this is where I agree with you. Perhaps
also, Mathematica might benefit from efficient built-in linked lists in
addition to standard Mathematica lists (implemented as arrays, as we know).

But at the end,  large problems just test the true complexity of the algorithm,
so a dramatic difference in efficiency (especially if it scales with the
size of the problem) of two implementations would mean to me that the real
algorithms implemented  are just different algorithms with  different
complexities. This has nothing to do directly with the efficiency of
Mathematica built-ins in terms of time, memory, or both - it is up to us to
use them in a proper way.

Regards,
Leonid



On Wed, Oct 7, 2009 at 3:03 PM, Kurt TeKolste <tekolste at fastmail.us> wrote:

> It would seem that the emphasis in the Mathematica literature on using
> the allegedly highly efficient functions available in Mathematica might
> be a bit overstated.  Limitations of memory and time seem to require
> falling back to something more akin to the classical procedural
> programming style when the problem gets large.
>
> On Tue, 06 Oct 2009 08:02 -0400, "Ray Koopman" <koopman at sfu.ca> wrote:
> > Here's some "roll your own nested loops" code.
> > It's faster than the "accumulator" approach.
> >
> > subsets[n_,1] := Transpose@{Range@n};
> > subsets[n_,k_] := ToExpression["Flatten[Table["<>
> > StringTake[ToString@Table[Which[
> > j==0, "i"<>ToString@#& /@ Range@k,
> > j==1, {"i1",n},
> > True, {"i"<>ToString@j,"i"<>ToString[j-1],n}],
> > {j,0,k}],{2,-2}]<>"],"<>ToString[k-1]<>"]"]
> >
> > coinsets[s_,k_] := s[[#]]& /@ Join@@(subsets[Length@s,#]&/@Range@k)
> >
> > coinSets[s_,k_] := Flatten[Table[subMultiSets[s,i],{i,k}],1];
> > subMultiSets[s_,k_] := smsLoop[{},s,k];
> > smsLoop[{ts___},{x_},1] := {{ts,x}};
> > smsLoop[t:{ts___},{x_,xs___},1] := Prepend[smsLoop[t,{xs},1],{ts,x}];
> > smsLoop[{ts___},s:{x_},k_] := smsLoop[{ts,x},s,k-1];
> > smsLoop[t:{ts___},s:{x_,xs___},k_] := Join[smsLoop[{ts,x},s,k-1],
> >                                            smsLoop[t,{xs},k]]
> >
> > coinsets[{1,3,4,9},3]
> > % == coinSets[{1,3,4,9},3]
> >
> > {{1},{3},{4},{9},{1,1},{1,3},{1,4},{1,9},{3,3},{3,4},{3,9},{4,4},
> >  {4,9},{9,9},{1,1,1},{1,1,3},{1,1,4},{1,1,9},{1,3,3},{1,3,4},{1,3,9},
> >  {1,4,4},{1,4,9},{1,9,9},{3,3,3},{3,3,4},{3,3,9},{3,4,4},{3,4,9},
> >  {3,9,9},{4,4,4},{4,4,9},{4,9,9},{9,9,9}}
> > True
> >
> > Timing@Length@coinsets[Range@20,7]
> > {6.69 Second,888029}
> >
> > Timing@Length@coinSets[Range@20,7]
> > {11.03 Second,888029}
> >
> > On Oct 5, 10:58 am, David Bevan <david.be... at pb.com> wrote:
> > > Dan, Adriano, Kurt,
> > >
> > > Thanks for the feedback.
> > >
> > > Here are some performance results:
> > >
> > > (* Dan *)
> > >
> > > Length[multiSetsUpToK[Range[20],7]]//Timing
> > >
> > > {18.14,888029}
> > >
> > > (* Adriano *)
> > >
> > > Length[coinSetsAdriano[Range[20],7]]//Timing
> > >
> > > {9.516,888029}
> > >
> > > (* Kurt *)
> > >
> > > Length[coinSetsKurt[Range[20],7]]//Timing
> > >
> > > Subsets::toomany: The number of subsets (189407486533) indicated by
> Subsets=
> > > [{1,1,1,1,1,1,1,2,2,2,<<130>>},{1,7}] is too large; it must be a
> machine in=
> > > teger.
> > >
> > > And with my code:
> > >
> > > Length[coinSets[Range[20],7]]//Timing
> > >
> > > {5.063,888029}
> > >
> > > My 'accumulator' approach seems to be quite effective!
> > >
> > > However, I'm sure this can be improved significantly with the technique
> use=
> > > d for KSubsets without too much difficulty.
> > >
> > > David %^>
> >
> Regards,
> Kurt Tekolste
>
>
>

• References:
  • Re: generating submultisets with repeated elements
    • From: Ray Koopman <koopman@sfu.ca>