<< Back to previous view

[MCOMB-4] Performance enhancement for sorted-numbers? Created: 12/Jul/14  Updated: 19/Jul/14  Resolved: 19/Jul/14

Status: Resolved
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Trivial
Reporter: Daniel Marjenburgh Assignee: Mark Engelberg
Resolution: Completed Votes: 0
Labels: enhancement, patch, performance

Attachments: File sorted-numbers-perf-enh.diff    
Patch: Code
Approval: Accepted

 Description   

Hi,

Came upon this as I was trying to improve performance. The implementation of sorted-numbers? (only used by permutations) is:
(defn- sorted-numbers?
"Returns true iff s is a sequence of numbers in non-decreasing order"
[s]
(and (every? number? s)
(every? (partial apply <=) (partition 2 1 s))))

<= and similar operators are variadic, so partitioning into pairs is unneeded.
(apply <= s) is a lot faster, but breaks for empty sequences, so an additional check is needed.

The implementation can be changed to:

(and (every? number? s)
(or (empty? s) (apply <= s)))

I benched this to be 10 to 15 times faster. A regression test with test.check was done to verify that the behaviour was not changed under any input.
A patch is also included.

Cheers,

Daniel



 Comments   
Comment by Andy Fingerhut [ 13/Jul/14 7:39 PM ]

Thanks for the submission. I don't know whether Mark would be interested in taking the test.check regression test you developed, too, but if you would be willing to share it as a patch, it might be considered for inclusion as well.

Comment by Daniel Marjenburgh [ 18/Jul/14 5:43 AM ]

Hm, I don't know how I could include the regression test as a patch. Because:
1) The current project does not use external libraries or Leiningen (yet). How do I add dependencies when not using Leiningen?
2) I tested the old implementation vs the new one with generated inputs. If the old implementation is gone, there's no test to add...

Comment by Mark Engelberg [ 19/Jul/14 5:06 PM ]

Since this function is only called once at the beginning of the permutations process, on a sequence that is usually 10 or fewer items, I can't imagine this improvement will have any meaningful impact on the overall running time of the permutations algorithm. Nevertheless, it's an improvement, so I've gone ahead and added it.





[MCOMB-1] math.combinatorics README should be updated to conform to contrib standard Created: 17/Sep/12  Updated: 17/Sep/12  Resolved: 17/Sep/12

Status: Resolved
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Trivial
Reporter: Christian Romney Assignee: Mark Engelberg
Resolution: Completed Votes: 0
Labels: documentation, patch

Attachments: Text File 0001-Updated-README-to-conform-to-new-contrib-standard.patch    
Patch: Code

 Description   

As per Sean Corfield's suggestion here: https://groups.google.com/forum/?fromgroups=#!searchin/clojure-dev/math/clojure-dev/p5oz42gR_sk/cesMHO9cDWEJ
the math.combinatorics README.md should be updated to be more useful, especially to newbies.



 Comments   
Comment by Sean Corfield [ 17/Sep/12 11:35 AM ]

Patch applied.





Generated at Thu Jul 31 16:47:20 CDT 2014 using JIRA 4.4#649-r158309.