Fork me on GitHub
Drew Verlee01:06:03

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
  (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?

(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))]
       (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?)})))


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.


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


naming a dynamic var without earmuffs is weird


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.


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

Drew Verlee19:06:53

good suggestions! thanks.