树搜索保存执行状态

Question

我有一棵树,

     A
    / \
   B   C
  /\    \
 D  E    F

表示为列表,

(A (B (D) (E)) (C (F)))

它实际上是一棵非常大的树,所以我想做的就是开始搜索,如果我找不到我要找的东西说100毫秒保存状态,返回,做一些家务,然后再次呼叫搜索并继续我离开了.基本上我正在使用的模拟给了我一定的时间来完成搜索.我正在寻找关于如何实现这一目标的想法/技巧？(在Clojure,Java)

Answer 1

线程可能是最简单的解决方案,但在单个线程上自己管理它并不是很困难.只给你100ms的"模拟"环境通常不允许任何新线程,所以这是另一种选择.

基本思想是创建一个闭包,表示完成任务需要完成的工作,如果没有时间完成,则返回结果而不是结果.这是一个草图:它增加了一系列数字,并且每十次操作而不是每100ms被中断.

(let [timer (atom 9)]
  (defn keep-going? []
    (not= 0 (swap! timer #(mod (inc %) 10)))))

(defn saving-addition [sum xs]
  (if-let [[x & more] (seq xs)]
    (let [next-thunk (fn [] (saving-addition (+ x sum) more))]
      (if (keep-going?)
        (next-thunk)
        next-thunk))
    sum))

(defn monitor [xs]
  (loop [thunk (saving-addition 0 xs)]
    (if (fn? thunk)
      (do
        (println "Saving execution state")
        (recur (thunk)))
      thunk)))

user> (monitor (range 25))
Saving execution state
Saving execution state
Saving execution state
300

编辑:因为Clojure没有尾部调用优化,所以创建一个thunk然后调用它会占用堆栈.如果您可能在需要中断之前执行超过几千步,则会出现堆栈溢出.唯一现实的解决方案是在a recur和in中继续复制thunk的主体,就像

(defn saving-addition [sum xs]
  (if-let [[x & more] (seq xs)]
    (let [sum (+ x sum)]
      (if (keep-going?)
        (recur sum more)
        #(saving-addition sum more)))
    sum))

如果你不得不编写多个这样的"可挂起"函数,你可以用宏来抽象出来.