Clojure

GC Issue 95: max-key and min-key evaluate k multiple times for arguments

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • Patch:
    Code and Test
  • Approval:
    Triaged

Description

max-key or min-key will evaluate (k value) multiple times for arguments if more than 2 arguments are passed. This is undesirable if k is expensive to calculate.

Good perf test:

(apply max-key #(Math/tan %) (range 1000))

Approach: Avoid duplication evaluation of k for any element.

Patch: clj-99-v2.patch

  1. clj-99-v1.diff
    22/Oct/13 7:54 PM
    3 kB
    Andy Fingerhut
  2. clj-99-v2.patch
    09/Feb/15 2:50 PM
    3 kB
    Michael Blume

Activity

Andy Fingerhut made changes -
Field Original Value New Value
Attachment clj-99-min-key-max-key-performance-v1.txt [ 11682 ]
Andy Fingerhut made changes -
Patch Code and Test [ 10002 ]
Priority Minor [ 4 ]
Reporter Andy Fingerhut [ jafingerhut ]
Alex Miller made changes -
Fix Version/s Backlog [ 10035 ]
Andy Fingerhut made changes -
Attachment clj-99-v1.diff [ 12375 ]
Andy Fingerhut made changes -
Attachment clj-99-min-key-max-key-performance-v1.txt [ 11682 ]
Alex Miller made changes -
Labels performance
Michael Blume made changes -
Attachment clj-99-v2.patch [ 13857 ]
Alex Miller made changes -
Approval Triaged [ 10120 ]
Description {code}
 Reported by H.Duerer, Mar 13, 2009

max-key or min-key will evaluate (k value) multiple times for arguments if
more than 2 arguments are passed.

This is undesirable if k is expensive to calculate.

Something like the code below would avoid these double calculations (at the
price of generating more ephemeral garbage)

(defn max-key
  "Returns the x for which (k x), a number, is greatest."
  ([k x] x)
  ([k x y] (if (> (k x) (k y)) x y))
  ([k x y & more]
     (second (reduce (fn [x y] (if (> (first x) (first y)) x y))
                     (map #(vector (k %) %) (cons x (cons y more)))))))


{code}
max-key or min-key will evaluate (k value) multiple times for arguments if more than 2 arguments are passed. This is undesirable if k is expensive to calculate.

Good perf test:

{code}
(apply max-key #(Math/tan %) (range 1000))
{code}

*Approach:* Avoid duplication evaluation of k for any element.

*Patch:* clj-99-v2.patch

People

Vote (3)
Watch (3)

Dates

  • Created:
    Updated: