Uploaded image for project: 'math.combinatorics'
  1. MCOMB-4

Performance enhancement for sorted-numbers?

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Trivial
    • Resolution: Completed
    • Labels:
    • Approval:
      Accepted
    • Patch:
      Code

      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

        Attachments

          Activity

            People

            • Assignee:
              markengelberg Mark Engelberg
              Reporter:
              dmarjenburgh Daniel Marjenburgh
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: