Carl Love

Carl Love

27579 Reputation

25 Badges

12 years, 59 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

@acer All the iterators in the Iterator package auto-compile by default unless option compile= false is given. For the small case that you tested (7-permutations), the time for this compilation is the vast majority of the measured time. Here is a modified version of your time tests that takes this into account. I needed to increase the size to 9-permutations because the times for smaller cases are too small to be accurately measured (cpu time < 0.16 ms).

# Parameters common to all tests:
#
restart:
n:= 9:
save n, "n.m"

# Kitonum's method: select via ListTools:-Search:
#
restart;
read "n.m":
CodeTools:-Usage(
    select(
        t->ListTools:-Search(2,t)<ListTools:-Search(3,t),
        combinat:-permute(n)
    )
):
nops(%);

memory used=364.54MiB, alloc change=257.04MiB, cpu time=391.00ms, real time=1.97s, gc time=359.38ms

181440

# TopologicalSorts, using precompiled Iterator:
#
restart;
read "n.m":
P:= Iterator:-TopologicalSorts(2, {1<2}): #Force Iterator to compile.
#set-of-vectors form:
CodeTools:-Usage(
    {seq}(p[], p= Iterator:-TopologicalSorts(n, {2<3}))
):
nops(%), type(%, set(rtable));
#set-of-lists form:
CodeTools:-Usage(
    [seq]~({seq}(p[], p= Iterator:-TopologicalSorts(n, {2<3})))
):
nops(%), type(%, set(list));

memory used=58.83MiB, alloc change=37.85MiB, cpu time=109.00ms, real time=296.00ms, gc time=0ns

181440, true

memory used=156.82MiB, alloc change=110.23MiB, cpu time=656.00ms, real time=843.00ms, gc time=234.38ms

181440, true

# TopologicalSorts:
# 1st Iterator is compiled on-the-fly; 2nd continues with compiled version:
#
restart;
read "n.m":
#set-of-vectors form:
CodeTools:-Usage(
    {seq}(p[], p= (P:= Iterator:-TopologicalSorts(n, {2<3})))
):
nops(%), type(%, set(rtable));
#set-of-lists form:
CodeTools:-Usage(
    [seq]~({seq}(p[], p= Iterator:-TopologicalSorts(n, {2<3})))
):
nops(%), type(%, set(list));

memory used=71.75MiB, alloc change=70.85MiB, cpu time=62.00ms, real time=836.00ms, gc time=0ns

181440, true

memory used=156.82MiB, alloc change=110.78MiB, cpu time=125.00ms, real time=906.00ms, gc time=109.38ms

181440, true

# TopologicalSorts, using uncompiled Iterators:
#
restart;
read "n.m":
#set-of-vectors form:
CodeTools:-Usage(
    {seq}(p[], p= Iterator:-TopologicalSorts(n, {2<3}, compile= false))
):
nops(%), type(%, set(rtable));
#set-of-lists form:
CodeTools:-Usage(
    [seq]~(
        {seq}(p[], p= Iterator:-TopologicalSorts(n, {2<3}, compile= false))
    )
):
nops(%), type(%, set(list));

memory used=196.77MiB, alloc change=102.85MiB, cpu time=656.00ms, real time=1.21s, gc time=93.75ms

181440, true

memory used=291.67MiB, alloc change=78.78MiB, cpu time=953.00ms, real time=1.49s, gc time=296.88ms

181440, true

# To answer @mmcdara's request, here is TopologicalSorts timing for various # n:
#
# The first includes the time for compilation:
for n from 3 to 10 do
    printf("\nn = %d:\n======\n", n);
    CodeTools:-Usage([seq](p[], p= Iterator:-TopologicalSorts(n, {2<3})))
od:


n = 3:
======
memory used=9.10MiB, alloc change=0 bytes, cpu time=63.00ms, real time=753.00ms, gc time=0ns

n = 4:
======
memory used=9.42KiB, alloc change=0 bytes, cpu time=0ns, real time=0ns, gc time=0ns

n = 5:
======
memory used=23.84KiB, alloc change=0 bytes, cpu time=0ns, real time=1000.00us, gc time=0ns

n = 6:
======
memory used=105.66KiB, alloc change=0 bytes, cpu time=15.00ms, real time=2.00ms, gc time=0ns

n = 7:
======
memory used=0.70MiB, alloc change=0 bytes, cpu time=0ns, real time=8.00ms, gc time=0ns

n = 8:
======
memory used=5.82MiB, alloc change=0 bytes, cpu time=47.00ms, real time=41.00ms, gc time=0ns

n = 9:
======
memory used=53.44MiB, alloc change=-28.17MiB, cpu time=266.00ms, real time=389.00ms, gc time=93.75ms

n = 10:
======
memory used=0.59GiB, alloc change=399.45MiB, cpu time=3.78s, real time=3.92s, gc time=3.12s

# nutty idea
# (extra operator invocation might cost too much.
restart;
read "n.m":
L:=combinat:-permute([$n]):
CodeTools:-Usage(
    select(LL->ListTools:-SelectFirst(p->p=2 or p=3, LL)=2, L)
):
nops(%);

memory used=0.60GiB, alloc change=4.16MiB, cpu time=438.00ms, real time=3.42s, gc time=203.12ms

181440

# nutty idea 2
# (seems to0 expensive to create the sublists.
#  but allowing offset/stride/num to Search might
#  be a reasonable idea for the future...)
restart;
read "n.m":
L:=combinat:-permute([$n]):
CodeTools:-Usage(select(proc(t) local f2,f3;
                         f2 := ListTools:-Search(2,t);
                         if f2>floor(nops(t)/2) then
                           f3 := ListTools:-Search(3,t[f2+1..]);
                           return evalb(f3=0);
                         else
                           f3 := ListTools:-Search(3,t[..f2-1]);
                           return evalb(f3>0);
                         end if;
                         end proc, L)):
nops(%);

memory used=219.63MiB, alloc change=4.16MiB, cpu time=265.00ms, real time=1.30s, gc time=78.12ms

181440

 

 

 

Download SelectedPermsTiming.mw

@mmcdara You wrote:

  • It feels like everybody took the same direction than @nm's, which is "construct the list of all permutations and select those where 2 appears before 3".
    But It looks more natural to "construct directly the list of permutations for which 2 appears before 3".

No, not everybody. As I explicitly wrote in my Answer above, 

  • This command does not generate all the permutations and then filter them to get the ones that match the pattern. Rather, it generates only the ones that match in the first place.

The TopologicalSorts command is much faster than @acer 's tests indicate. There's an oversight in his timing method (understandable, since it's due to hidden compilation) that I'm about to explain in another Reply (just posted). In that Reply, I've also included the timings for N = 3..10 that you asked for. 

Knuth's "topological sort" algorithm can be found in

  • Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 2 [or, nowadays, simply "volume 4A: Combinatorial Algorithms, part 1" -- Carl]; generating all tuples and permutations, sec. 7.2.1.2, p. 63, generating all permutations, algorithm V, all topological sorts.
     

@sursumCorda Using overload with the seq parameter modifier is a brilliant idea, and I think a quite original idea also. I've expanded on it, in an Answer that I just posted, to get a Maple implementation of Mathematica's Cases (at least to the extent that the OP used in this Question).

@Ronan Disjunctively means that has(e, [x,y]) is equivalent to has(e, x) or has(e, y). If instead it were has(e, x) and has(e, y), then that would be conjunctively.

@charlie_fcl This is the reason that I prefer ifelse (or, equivilently, `if`) over piecewise in this situation: piecewise is a highly symbolic condition-based control structure whose boolean conditions do not need to be evaluated immediately. If the boolean condition can be evaluated immediately, ifelse is much simpler and more efficient.

@Andiguys Here is a completely different way to do the 3D plot. This way does not require the double loop (or any loop):

Cv:= 'Cv': tau0:= 'tau0':
MaxArgs:= op@unapply(
   [TRC(tau2, tau1), `union`(C1,C2,C3)], [tau2, tau1, Cv, tau0]
):
Max:= proc(Cv, tau0)
local tau2, tau1;
    try
        Optimization:-Maximize(
            MaxArgs(tau2, tau1, Cv, tau0), tau2= 0..1, tau1= 0..1,
            assume= nonnegative
        )[1]
    catch: undefined
    end try
end proc
:
plot3d(Max, 50..70, 0.3..0.7, labels= ['Cv', 'tau0', TRC], grid= [5,9]);

The and 9 in the grid option were chosen to correspond to the number and spacing of the values of Cv and tau0 that you used in the double loop. You can increase them if you want.

@Andiguys No, the plot command should not be inside the loop.

In the original double loop, you had s[Cv, tau0]:= Maximize(...). You changed that to s:= Maximize(...). If you change it back to s[Cv, tau0], then you will get the plot.

@charlie_fcl Like this:

(e,f):= ifelse(c<d, [a, 2*b], [3*a, b])[]

You could replace ifelse with piecewise (leaving everything else exactly as is) and get the same result, but IMO ifelse is better.

@charlie_fcl In Maple it can be done as follows, so it's likely to also work in Maple Flow:

(a,b):= (min,max)(c,d)

@Carl Love Okay, I couldn't resist the temptation to make the applyrule work, and I found something that works, although I can't explain why you were getting an infinite loop before.

applyrule(
    x::(anything^And(fraction, 2 &under denom))*y::(Not(1) &under denom)
    = y %* x,
    eq
);

@Carl Love I just added a small change to the code above. I replaced denom(R)=1 with S=1 or denom(R)=1. In other words, if there are no coefficients with denominators OR there are no square roots, then leave the product unchanged.

@SARBAST There is no attached file. Please try uploading it again.

@SARBAST I assume that you want to vary the initial values (x(0), y(0))  over [-6,6] x [-3,6]. We still need initial values z(0) and w(0) in order to do any computation.

@C_R The Wikipedia article "Attractor" contains a definition of basin of attraction. It's the mathematical generalization of the geological / geographical / hydrological concept of drainage basin or watershed.

@C_R I haven't run this yet, but in order to get such a slow and smooth animation to post, the OP very likely included a huge number of extra frames (10 times, or more) in the animation. These extra frames are not needed when viewing in a worksheet because you can slow down the animation with the toolbar controls. Not computing the extra frames should speed up the computation significantly.

4 5 6 7 8 9 10 Last Page 6 of 703