math.combinatorics

Performance enhancement for sorted-numbers?

Details

  • Type: Enhancement Enhancement
  • Status: Resolved Resolved
  • Priority: Trivial Trivial
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • 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

Activity

Hide
Andy Fingerhut added a comment -

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.

Show
Andy Fingerhut added a comment - 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.
Hide
Daniel Marjenburgh added a comment -

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...

Show
Daniel Marjenburgh added a comment - 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...
Hide
Mark Engelberg added a comment -

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.

Show
Mark Engelberg added a comment - 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.

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
    Resolved: