Clojure China

求一个排序算法, 依据依赖关系

#1

因为要生成代码, 中间代码的顺序是缺失的, 需要手动生成,
先来看 Clojure 本身的情况, 如果是这样的代码, 定义的顺序是必要的:

(def a 1)
(def b (inc a))
(def c (inc b))

(defn f1 []
  (inc c))

(defn f2 []
  (inc (f1)))

(defn f3 []
  (+ (f2) c a))


(declare g2)

(defn g1 []
  (inc (g2)))

(defn g2 []
  (inc (g1)))

这个例子当中含有这些变量名:

a b c f1 f2 f3 g1 g2

以及这样的依赖关系:

b -> a
c -> b
f1 -> c
f2 -> f1
f3 -> f2 a c
g1 -> g2
g1 -> g2

现在我的问题是我得到的代码定义的顺序是乱的, 我可以通过分析代码判断每个定义依赖什么.
但是我怎么样能从这布局的依赖信息推导出一个正确的顺序呢? 而且要写成一个通用的算法…

#2

这个就是拓扑排序问题。你可以Google一下

2赞
#3

后面用它的套路做了一个简单的版本
https://github.com/Cirru/boot-stack-server/blob/master/compiled/src/stack_server/analyze.clj#L65

#4

还是发现问题了, 某些特殊情况会出错. 排查了一遍, 原因大概是排序算法本身有一个假设, 就是任何两个数字都有固定的大小关系. 但是我的情况当中是没有的, 可能两个元素之间就无法确定顺序, 任一种顺序都可以, 结果是某些元素之间的关系没有被排序算法处理到, 就出现了错误的顺序.

#5

撸了一个插入排序, 也不管性能变差了…

#6

依赖关系可以看做一种图结构.
A 依赖 B ,则可以看做 A->B 有个单向关系.

然后 你从一堆依赖信息里找到一个正确的顺序.
可以看做, 从一堆节点和边里面找一条无环最长路.
找路算法呢… 我就不知道了…