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:
    None
  • Patch:
    Code and Test

Description

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

Activity

Hide
Assembla Importer added a comment -
Show
Assembla Importer added a comment - Converted from http://www.assembla.com/spaces/clojure/tickets/99
Hide
Assembla Importer added a comment -

richhickey said: Updating tickets (#8, #19, #30, #31, #126, #17, #42, #47, #50, #61, #64, #69, #71, #77, #79, #84, #87, #89, #96, #99, #103, #107, #112, #113, #114, #115, #118, #119, #121, #122, #124)

Show
Assembla Importer added a comment - richhickey said: Updating tickets (#8, #19, #30, #31, #126, #17, #42, #47, #50, #61, #64, #69, #71, #77, #79, #84, #87, #89, #96, #99, #103, #107, #112, #113, #114, #115, #118, #119, #121, #122, #124)
Hide
Andy Fingerhut added a comment -

clj-99-min-key-max-key-performance-v1.txt dated Nov 15 2012 changes min-key and max-key to evaluate the function k on each of its other arguments at most once.

Show
Andy Fingerhut added a comment - clj-99-min-key-max-key-performance-v1.txt dated Nov 15 2012 changes min-key and max-key to evaluate the function k on each of its other arguments at most once.
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 ]
Hide
Andy Fingerhut added a comment -

Patch clj-99-v1.diff is same as previously attached patch, but with .diff suffix for easier diff-style viewing in some editors.

Show
Andy Fingerhut added a comment - Patch clj-99-v1.diff is same as previously attached patch, but with .diff suffix for easier diff-style viewing in some editors.
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 ]
Hide
Steve Kim added a comment -

sort-by is similarly inefficient. It calls keyfn for every comparison in sort, not once for every element to be sorted.

I'm not familiar with this project's preferred workflow, so I have to ask: Do you want me to open a separate ticket for sort-by, or do you prefer to consolidate that issue into this ticket?

Show
Steve Kim added a comment - sort-by is similarly inefficient. It calls keyfn for every comparison in sort, not once for every element to be sorted. I'm not familiar with this project's preferred workflow, so I have to ask: Do you want me to open a separate ticket for sort-by, or do you prefer to consolidate that issue into this ticket?
Hide
Alex Miller added a comment -

Separate.

Show
Alex Miller added a comment - Separate.
Hide
Steve Kim added a comment -

I created CLJ-1402 for sort-by

Show
Steve Kim added a comment - I created CLJ-1402 for sort-by

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated: