Timefold排课约束文件优化咨询：评估速度过慢问题

以下是我编写的Timefold排课约束Kotlin代码：

class Constraints : ConstraintProvider {

    override fun defineConstraints(factory: ConstraintFactory): Array<Constraint> {
        return arrayOf(
            roomClash(factory),
            preferPriorityRooms(factory),
            sequenceViolation(factory),
            avoidEvening(factory),
            sessionConflict(factory),
            moduleProximity(factory),
            roomUnderused(factory),
            threadOverloaded(factory),
            clearStaffDay(factory),
            staffDaysFairness(factory),
            threadDaysFairness(factory),
            threadProximity(factory),
            unnecessaryRoomChange(factory),
            threadUnderloaded(factory),
            instantRoadCrossing(factory)
        )
    }

    fun ConstraintFactory.forEachMappingPairUnifilter(unifilter: Predicate<Mapping>?,
                                                      vararg joiners: BiJoiner<Mapping, Mapping>) =
        when (unifilter) {
            null -> this.forEachUniquePair(Mapping::class.java, *joiners)
            else -> this.forEach(Mapping::class.java).filter(unifilter)
                .join(this.forEach(Mapping::class.java).filter(unifilter),
                    lessThan(Mapping::ID),
                    *joiners)
        }


    fun ConstraintFactory.forEachOverlappingMapping(unifilter: Predicate<Mapping>?,
                                                    vararg joiners: BiJoiner<Mapping, Mapping>) =
        this.forEachMappingPairUnifilter(unifilter,
            equal(Mapping::semester),
            overlapping(Mapping::start, Mapping::end),
            *joiners,
            filtering { a, b -> a.session.sharesWeekWith(b.session) })

    fun ConstraintFactory.forEachModulePair(unifilter: Predicate<Mapping>?,
                                            vararg joiners: BiJoiner<Mapping, Mapping>) =
        this.forEachMappingPairUnifilter(unifilter,
            equal(Mapping::semester),
            equal(Mapping::module),
            *joiners,
            filtering { a, b -> a.session.sharesWeekWith(b.session) })

    fun ConstraintFactory.forEachDirectlyFollowingModulePair(unifilter: Predicate<Mapping>?,
                                                             vararg joiners: BiJoiner<Mapping, Mapping>) =
        forEachModulePair(unifilter,
            equal(Mapping::end, Mapping::start),
            *joiners
        )

    private fun roomClash(factory: ConstraintFactory): Constraint {
        return factory.forEachOverlappingMapping(null,
            equal(Mapping::room))
            .penalize(HardMediumSoftScore.ONE_HARD)
            .asConstraint("Room Clash")
    }

    private fun preferPriorityRooms(factory: ConstraintFactory): Constraint {
        return factory.forEach(Mapping::class.java)
            .filter { !it.room.priority
                    && it.session.students <= 108
                    && it.session.viableRooms.size > 1 }
            .penalize(HardMediumSoftScore.ONE_SOFT) { m -> m.session.students }
            .asConstraint("Prefer Priority Rooms")
    }

    private fun sequenceViolation(factory: ConstraintFactory): Constraint {
        return factory.forEachModulePair( { it.sequence() > 0 },
            greaterThanOrEqual(Mapping::slotOrdinal),
            lessThan(Mapping::sequence))
            .penalize(HardMediumSoftScore.ONE_HARD)
            .asConstraint("Sequence Violation")
    }

    private fun avoidEvening(factory: ConstraintFactory): Constraint {
        return factory.forEach(Mapping::class.java)
            .filter { it.slot.hour + it.session.length > 17 }
            .penalize(HardMediumSoftScore.ofSoft(2)) { m -> m.session.students * 2 }
            .asConstraint("Avoid Evening Slots")
    }

    private fun sessionConflict(factory: ConstraintFactory): Constraint {
        return factory.forEachOverlappingMapping(null)
            .ifExists(
                SessionConflict::class.java,
                filtering { a, b, c -> c.contains(a.session) && c.contains(b.session) })
            .penalize(HardMediumSoftScore.ONE_HARD)
            .asConstraint("Session Conflict")
    }


    private fun moduleProximity(factory: ConstraintFactory): Constraint =
        factory.forEachModulePair({it.sequence() > 0},
            equal(Mapping::sequence, {it.sequence() - 1}))
            .penalize(HardMediumSoftScore.ONE_MEDIUM)
            { a, b -> a.effectiveProximity(b) * min(a.session.students, b.session.students) }
            .asConstraint("Module Session Proximity")


    private fun threadProximity(factory: ConstraintFactory): Constraint {
        return factory.forEach(SetThread::class.java)
            .join(Mapping::class.java, Joiners.filtering { a, b -> a.takesMapping(b) })
            .join(Mapping::class.java, Joiners.filtering { a, b, c -> a.takesMapping(c) && c.ID > b.ID })
            .penalize(HardMediumSoftScore.ONE_MEDIUM) { a, b, c -> b.effectiveProximity(c) * a.size }
            .asConstraint("Thread Proximity")
    }

    private fun roomUnderused(factory: ConstraintFactory): Constraint =
        factory.forEach(Mapping::class.java)
            .filter { it.room.priority == false
                    && it.session.module.code != "ENGR4003"
                    && it.room.capacity > it.session.students
                    && it.session.viableRooms.size > 1
                    && it.room.capacity != 9999 } // Specialist rooms
            .penalize(HardMediumSoftScore.ONE_SOFT) { it.room.capacity - it.session.students }
            .asConstraint("Room Underused")

    private fun unnecessaryRoomChange(factory: ConstraintFactory): Constraint =
        factory.forEachDirectlyFollowingModulePair({it.session.module.code != "ENGR4003"},
            equal(Mapping::type),
            filtering{a, b ->
                (b.session.allStaff.containsAll(a.session.allStaff) && a.session.allStaff.containsAll(b.session.allStaff)) &&
                (a.room != b.room) &&
                (a.room.priority || !b.room.priority)}
        ).penalize(HardMediumSoftScore.ofMedium(100)) { a, b -> min(a.session.students, b.session.students) }
            .asConstraint("Unnecessary Room Change")

    private fun threadOverloaded(factory: ConstraintFactory): Constraint =
        factory.forEach(SetThread::class.java)
            .join(Mapping::class.java, Joiners.filtering { a, b -> a.takesMapping(b) && b.session.module.code != "ENGR4003" } )
            .groupBy( {a,b -> a}, {a, b -> b.slot.day + (10*b.session.semester) }, ConstraintCollectors.sum { a, b -> b.session.length })
            .filter { cohort, day, length -> length >= 8 }
            .penalize(HardMediumSoftScore.ONE_HARD)
            .asConstraint("Thread Overloaded")

    private fun clearStaffDay(factory: ConstraintFactory): Constraint =
        factory.forEach(Staffer::class.java)
            .join(Mapping::class.java, Joiners.filtering { a, b -> b.session.allStaff.contains(a)} )
            .groupBy( {a, b -> a}, {a, b -> b.session.semester}, ConstraintCollectors.countDistinct { a, b -> b.slot.day } )
            .filter { staffer, semester, days -> days == 5 }
            .penalize(HardMediumSoftScore.ONE_HARD)
            .asConstraint("Clear Staff Day")

    private fun staffDaysFairness(factory: ConstraintFactory): Constraint =
        factory.forEach(Staffer::class.java)
            .join(Mapping::class.java, Joiners.filtering { a, b -> b.session.allStaff.contains(a)} )
            .groupBy( {a, b -> a}, {a, b -> b.session.semester}, ConstraintCollectors.countDistinct { a, b -> b.slot.day } )
            .penalize(HardMediumSoftScore.ONE_SOFT) { staffer, semester, days -> days * days }
            .asConstraint("Staff Attendance Days Fairness")

    private fun threadDaysFairness(factory: ConstraintFactory): Constraint =
        factory.forEach(SetThread::class.java)
            .join(Mapping::class.java, Joiners.filtering { a, b -> a.takesMapping(b) } )
            .groupBy( {a, b -> a}, {a, b -> b.session.semester}, ConstraintCollectors.countDistinct { a, b -> b.slot.day } )
            .penalize(HardMediumSoftScore.ofSoft(5)) { cohort, semester, days -> days * days }
            .asConstraint("Thread Attendance Days Fairness")

    private fun threadUnderloaded(factory: ConstraintFactory): Constraint =
        factory.forEach(SetThread::class.java)
            .join(Mapping::class.java, Joiners.filtering { a, b -> a.takesMapping(b) } )
            .groupBy( {a, b -> a}, {a, b -> b.slot.day + (10*b.session.semester) }, ConstraintCollectors.sum { a, b -> b.session.length })
            .filter { cohort, day, length -> (length == 1) }
            .penalize(HardMediumSoftScore.ONE_HARD)
            .asConstraint("Thread Underloaded")

    private fun instantRoadCrossing(factory: ConstraintFactory): Constraint =
        factory.forEachDirectlyFollowingModulePair( { it.session.module.code != "ENGR4003" },
            filtering { a,b -> a.room.areaID != b.room.areaID })
            .penalize(HardMediumSoftScore.ONE_SOFT) { a, b -> min(a.session.students, b.session.students) }
            .asConstraint("Instant Road Crossing")

}

当前约束评估速度约为255次/秒，符合官方文档中"过慢"的标准。我怀疑threadProximity是主要性能瓶颈，但由于takesMapping是多对多关系，不清楚如何处理实体多分组的groupBy问题，求可行的优化方案。

一、核心瓶颈threadProximity优化 #

当前threadProximity的实现是遍历每个SetThread，关联其所有Mapping后两两配对，会产生**O(n²)**的配对数量，当SetThread关联的Mapping较多时性能急剧下降。优化思路是将多对多关系的遍历转为基于Mapping的直接关联，减少无效配对：

1. 替换多对多join为Mapping间的关联 #

给Mapping添加threads: Set<SetThread>字段（初始化时预计算缓存该排课项所属的所有线程），直接遍历Mapping的唯一配对，同时过滤属于同一SetThread的项：

private fun threadProximity(factory: ConstraintFactory): Constraint {
    return factory.forEachUniquePair(Mapping::class.java,
        // 过滤出属于同一SetThread的配对
        Joiners.filtering { a, b -> a.threads.intersect(b.threads).isNotEmpty() },
        // 避免重复配对
        lessThan(Mapping::ID)
    )
    .penalize(HardMediumSoftScore.ONE_MEDIUM) { a, b ->
        // 计算共同线程的总学生数乘以 proximity
        a.threads.intersect(b.threads).sumOf { it.size } * a.effectiveProximity(b)
    }
    .asConstraint("Thread Proximity")
}

2. 增加前置过滤条件 #

如果仅需对同一学期、同一周的Mapping计算 proximity，添加额外joiner减少配对数量：

factory.forEachUniquePair(Mapping::class.java,
    equal(Mapping::semester),
    Joiners.filtering { a, b -> a.session.sharesWeekWith(b.session) },
    Joiners.filtering { a, b -> a.threads.intersect(b.threads).isNotEmpty() },
    lessThan(Mapping::ID)
)

二、通用约束优化技巧 #

1. 替换自定义遍历方法为原生forEachUniquePair #

当前forEachMappingPairUnifilter在有unifilter时，手动join两个流的效率低于原生forEachUniquePair，修改为：

fun ConstraintFactory.forEachMappingPairUnifilter(unifilter: Predicate<Mapping>?,
                                                  vararg joiners: BiJoiner<Mapping, Mapping>) =
    this.forEachUniquePair(Mapping::class.java, *joiners)
        .let { stream ->
            unifilter?.let { stream.filter { pair -> unifilter.test(pair.a) && unifilter.test(pair.b) } } ?: stream
        }

2. 预计算静态属性 #

将约束中频繁计算的静态值提前缓存到实体字段，避免重复计算：

• 给Session添加weekGroup字段，预计算每周标识，sharesWeekWith直接比较该字段
• 给Mapping添加sequenceValue字段，缓存sequence()的结果
• 预计算Room间的proximity矩阵，存储为Map，effectiveProximity直接查表

3. 简化filter中的复杂逻辑 #

• unnecessaryRoomChange中的allStaff双向包含检查，预计算session.staffHash（拼接staff ID的哈希值），直接比较哈希值代替containsAll的O(n)检查
• roomUnderused中的条件按判断速度排序，优先过滤room.capacity != 9999、room.priority == false这类快速判断的条件

4. 优化groupBy操作 #

• threadOverloaded和threadUnderloaded中的b.slot.day + (10*b.session.semester)预计算为Mapping的semesterDay字段，避免每次groupBy时计算
• 对于countDistinct的groupBy（如clearStaffDay），给Staffer添加semesterDays字段，预记录每个学期已排天数，约束中直接读取判断

5. 调整约束顺序 #

将硬约束（Hard）放在约束数组最前面，Timefold会优先优化硬约束，减少后续软约束的无效评估；同时将计算成本低的约束前置，快速过滤无效解。

内容的提问来源于stack exchange，提问作者Mark Green