代码之家 › 专栏 › 技术社区 › Saeed Mousazadeh

如何在SML中实现LPT(最长处理时间)调度算法功能

sysml ssml smlnj sml

0

Saeed Mousazadeh · 技术社区 · 8 年前

假设我们有一个包含一些任务处理时间的列表,如[13,8,7,6,4,2,2,1]。我们希望通过LPT调度算法将该列表分成两个列表。以下是算法过程:

对于如上所述的给定降序排序列表,首先我们将最大的元素(排序列表中的第一个元素)放入列表1,然后将第二个元素放入列表2。然后,我们将下一个元素插入两个列表中的一个,元素之和较小。我们做这项工作,直到初始列表中的所有元素都被分成两个列表。

例如,对于上述列表,两个列表将是[13,6,2,1],[8,7,4,2](我们看到元素7已插入第二个列表,因为ListSum([13]>ListSu([8]),然后是ListSum([13])

1 回复 | 直到 6 年前

1

John Coleman 8 年前

您可以使用尾部递归助手函数:

fun lpt xs = let 
    fun lpt' ([],l1,l2,s1,s2) = (rev l1, rev l2)
    |   lpt' (x::xs,l1,l2,s1,s2) = 
            if s1 <= s2 then lpt' (xs,x::l1,l2,s1+x,s2)
            else lpt' (xs,l1,x::l2,s1,s2+x)
    in
        lpt' (xs,[],[],0,0)
    end;

helper函数获取源列表和正在构建的列表,以及它们的和,并将源列表的头部固定到适当的列表上,调整适当的和,然后使用这些调整后的列表/和递归地在列表的尾部调用自己。这种构建列表的方法向后构造它们(在定义尾部递归列表构造函数时并不罕见),因此,没有任何剩余处理的基本情况会使它们反向。main函数只调用具有正确初始化的列表/和的helper函数。