code-reviews

2019-06-20T01:57:03.028600Z

I would appreciate some feedback on the approach i took to solving a problem. The problem is that i have a function which might run for unacceptable long time, at a certain amount of time i wanted to give up on it and have it report failure. My approach was to add a timeout predicate to the function. That predicate is a dynamic var to avoid muddling the recursive calls. It checks against an atom that stores the end-time to see if the function has timed out. The biggest downside i see here is that now this function contains logic about timing out, which i can't deiced if it should be its responsibility. The fill function solves the knapsack problem, in a very inefficient way, i'm aware of how to do that part better from an algorithmic stand point.

(defn timeout-in
  [min]
  (let [start-time (jtime/local-time)
        end-time (atom (jtime/plus start-time (jtime/minutes min)))]
     #(jtime/after? (jtime/local-time) @end-time)))

(defn ^:dynamic timeout?
  []
  false)

(defn fill-v2
  ([capacity items] (fill-v2 capacity [] items))
  ([capacity taken items]
   (let [by-value #(->> % (map :value) (reduce +))
         {:keys [weight] :as item} (first items)
         dont-take #(fill-v2 capacity taken (rest items))
         do-take #(fill-v2 (- capacity weight) (conj taken item) (rest items))]
     (cond
       (or (nil? item) (timeout?)) taken
       (< capacity weight) (dont-take) 
       :else (max-key by-value (do-take) (dont-take))))))

(let [{:keys [capacity items]} (num-of-items->args 100)]
  (binding [timeout? (timeout-in 1)]
     (let [result (fill-v2 capacity items)]
       {:result result :timed-out? (timeout?)})))

jumar 2019-06-20T06:05:01.030700Z

Normally, you would have this problem with some kind of IO -> in that case I'd use future and future-cancel. In this particular case it's harder since it's a "pure" computation. I guess I'd prefer passing the timeout as a parameter instead of using dynamic binding.

2019-06-20T17:19:03.031Z

what's the utility of end-time being an atom?

2019-06-20T17:20:02.031400Z

naming a dynamic var without earmuffs is weird

2019-06-20T17:23:12.032300Z

there's no expensive operation before checking timeout, I think the algorithm would be clearer if you checked for timeout before the let block. You can also check item for nil before the let block.

2019-06-20T17:23:34.032900Z

that way you also don't need to create lambdas for dont-take and do-take - if you get past those conditions they always need evaluation

2019-06-20T19:02:53.034700Z

good suggestions! thanks.