* rewrite function ^ so that vectors are only allocated

[jlapeyre]

once rather than each time the routine is called recursively. On branch powlessalloc modified: src/Permutations.jl

Hi, I did some tests that show this "^" is more efficient in general. But, the code is a bit (not much) more complicated. So you may want this commit, but maybe not. If used at the command line, say for teaching, you won't notice a difference. If it is called many times in some algorithm, then it may make a difference.

[scheinerman]

Thanks for this. I have not yet had an opportunity to try it out, but I'll try to get to that soon and then merge. I appreciate the input!

[scheinerman]

Hi John,

Thanks for your input on this. I see that the exponentiation work is orchestrated this function:

function ^(p::Permutation, n::Integer) n == 0 && return [one(T):convert(T,length(p))] n == 1 && return copy(p) # for consistency, don't return ref, rather copy pret = similar(p.data) ptmp = similar(p.data) permpower!(p.data,pret,ptmp,n) return Permutation(pret) end

But I wonder if the n==0 line (red) will return a Permutation object ... looks like it would return an array And since Permutation objects are immutable, is there any call for making a copy (blue)?

-Ed

---

From: John Lapeyre [notifications@github.com] Sent: Thursday, December 18, 2014 11:01 To: scheinerman/Permutations.jl Subject: [Permutations.jl] * rewrite function ^ so that vectors are only allocated (#3)

once rather than each time the routine is called recursively. On branch powlessalloc modified: src/Permutations.jl

Hi, I did some tests that show this "^" is more efficient in general. But, the code is a bit (not much) more complicated. So you may want this commit, but maybe not. If used at the command line, say for teaching, you won't notice a difference. If it is called many times in some algorithm, then it may make a difference.

---

You can merge this Pull Request by running

git pull https://github.com/jlapeyre/Permutations.jl powlessalloc

Or view, comment on, or merge it at:

https://github.com/scheinerman/Permutations.jl/pull/3

Commit Summary

• * rewrite function ^ so that vectors are only allocated

File Changes

• M src/Permutations.jlhttps://github.com/scheinerman/Permutations.jl/pull/3/files#diff-0 (42)

Patch Links:

• https://github.com/scheinerman/Permutations.jl/pull/3.patch
• https://github.com/scheinerman/Permutations.jl/pull/3.diff

— Reply to this email directly or view it on GitHubhttps://github.com/scheinerman/Permutations.jl/pull/3.

[scheinerman]

In my last comment, the colorized text lost its color :-( I hope, though, my questions are clear.

[jlapeyre]

(you can use "three backticks"julia to colorize the code) You are correct, the line

n == 0 && return [one(T):convert(T,length(p))]

is wrong. (I copied it from other code.) It is ok to simply delete the line, since it's also handled in permpower! Regarding p^1, I don't know if it matters, and what it standard in Julia, but there is a difference. If we use this:

n == 1 && return p,

then

julia> p = Permutation([1,2,4,3])
(1)(2)(3,4)
julia> q = p^1
(1)(2)(3,4)
julia> p.data[4];
julia> p.data[3] = 3;
julia> q
(1)(2)(3)(4)

[scheinerman]

Thanks John. I'll pull.

[scheinerman]

By the way, I removed the extra copy when the power is 1. Folks should not be accessing the :data field of a Permutation anyhow. I would have thought that immutability would have blocked that, but I understand this only prevents things like p.data=[1,2,3] but not p.data[1]=2.

[jlapeyre]

Not copying makes sense, as it was clearly your intent not to change the content. Strings are immutable, but you can do this

julia> s = "abc";
julia> s.data[1] = 0x62;
julia> s
"bbc"

The Julia docs explain what an immutable type like Permutation is and call it "immutable". They also call strings immutable. But, they clearly mean something else. In the case of strings, they mean that not only changing the pointer to array of characters is disallowed, but also that the provided interface disallows changing the content of the array.

In fact, I just looked, and your treatment of p^1 agrees with how Julia treats strings. This is the code in "strings.jl" for converting a string to a string

string(s::String) = s

Still, it makes me a bit uncomfortable because

julia> q = "cat";
julia> r = "cat";
julia> s = string(q);
julia> q === r
false
julia> s === q
true

I guess it was a conscious decision and that some thought went into it.