Kotlin:以函数的方式组合列表中的某些元素

这里有一个实用的方法。其思想是在一个列表中获得所有的会议端点,然后比较相邻的endTime和startTime对,过滤掉那些相等的端点。 然后将结果分组,并根据结果列出会议列表。

fun combine(meetings: List<Meeting>): List<Meeting> {
    return meetings
        .zipWithNext { current, next -> listOf(current.endTime, next.startTime) }
        .filterNot { (end, start) -> end == start }
        .flatten()
        .let { listOf(meetings.first().startTime) + it + listOf(meetings.last().endTime) }
        .chunked(2) { (start, end) -> Meeting(start, end) }
}

它适用于非空的会议列表;处理空的会议是一个额外的问题 if (meetings.isEmpty()) return meetings 在开头签入。

然而,我并不觉得它更优雅,因为它需要为大量会议分配更多的对象。转弯 meetings 与 .asSequence() 操作链开始时的函数可能会有一点帮助,但不会有多大帮助。

递归的和不可变的。

fun combine(meetings: List<Meeting>): List<Meeting> {
    return if (meetings.isEmpty()) meetings
    else combineRecurse(emptyList(), meetings.first(), meetings.drop(1))
}

fun combineRecurse(tail: List<Meeting>, head: Meeting, remaining: List<Meeting>): List<Meeting> {
    val next = remaining.firstOrNull()
    return when {
        next == null -> tail + head
        next.startTime == head.endTime -> combineRecurse(tail, Meeting(head.startTime, next.endTime), remaining.drop(1))
        else -> combineRecurse(tail + head, next, remaining.drop(1))
    }
}

递归函数有3个参数:

• tail:已处理的不能再合并的会议
• 负责人:我们目前正在进行的会议,并试图尽可能延长
• 剩余:未处理的会议

我找到了解决办法 fold 最优雅的,它也不分配任何多余的对象。不过,我还是简化了:

fun combine(meetings : List<Meeting>) : List<Meeting> {
    return meetings.fold(mutableListOf()) { combined: MutableList<Meeting>, meeting: Meeting ->
        val prevMeeting = combined.lastOrNull()
        if (prevMeeting == null || prevMeeting.endTime < meeting.startTime) {
            combined.add(meeting)
        } else {
            combined[combined.lastIndex] = Meeting(prevMeeting.startTime, meeting.endTime)
        }
        combined
    }
}

请注意,这不必搜索列表来删除以前的会议。它只是将以前的会议替换为会议的组合。

它确实需要一个可变列表,因为这个解决方案应该是有效的。

老实说,我相信在创建/插入地图时处理这个问题会更好,而不是在以后试图压缩它。但是,这似乎可以避免使用折叠和其他您似乎不喜欢使用的功能。

另外,根据原始会议列表的大小,创建一个扩展会议列表(与stripped相反)并使用它来代替 meetings 在里面 findLastLinkedMeeting . 但不确定是否会有很大的不同。

    fun combine(): List<Meeting> {
        val stripped = meetings.filter { meeting -> meetings.none { isContinuation(it, meeting) } }

        return stripped.map { stripped ->
            val fromMeeting = findLastLinkedMeeting(stripped)
            if (fromMeeting == stripped) stripped else Meeting(stripped.startTime, fromMeeting.endTime)
        }
    }

    private tailrec fun findLastLinkedMeeting(fromMeeting: Meeting): Meeting {
        val nextMeeting = meetings.find { toMeeting -> isContinuation(fromMeeting, toMeeting) }
        return if (nextMeeting != null) findLastLinkedMeeting(nextMeeting) else fromMeeting
    }

    private fun isContinuation(fromMeeting: Meeting, toMeeting: Meeting) =
        fromMeeting.endTime == toMeeting.startTime

使用可变性 里面 一个“功能性”的电话是公平的,只要我们不暴露它。

这与您的第一个版本非常相似,但有一些可以说是细微的差别。

• 计算出聚合函数。
• 聚合函数为 几乎 以单一的表达形式。
• 有趣的案件 when 只是一个表达式。

fun combine(meetings: List<Meeting>): List<Meeting> {
    fun add(ms: MutableList<Meeting>, m: Meeting) : MutableList<Meeting> {
        ms.lastOrNull().let {
            when {
                it == null ->
                    ms.add(m)
                it.endTime == m.startTime ->
                    ms[ms.lastIndex] = Meeting(it.startTime, m.endTime)
                else ->
                    ms.add(m)
            }
        }

        return ms
    }

    return meetings.fold(mutableListOf(), ::add)
}

再往前走一步,我们可以用 reduce 而不是 fold ,代价是可能引入许多短期列表(但由于使用序列,一次不会引入很多;我希望JIT能够优化该部分),但增加了并行化的可能性:

fun combine(meetings: List<Meeting>): List<Meeting> {
    fun add(ml: MutableList<Meeting>, mr: MutableList<Meeting>) : MutableList<Meeting> {
        val leftLast = ml.lastOrNull()
        val rightFirst = mr.firstOrNull()

        when {
            leftLast == null || rightFirst == null || leftLast.endTime != rightFirst.startTime ->
                ml.addAll(mr)
            else -> {
                // assert(leftLast.endTime == rightFirst.startTime)
                ml[ml.lastIndex] = Meeting(leftLast.startTime, rightFirst.endTime)
                mr.removeAt(0)
                ml.addAll(mr)
            }
        }

        return ml
    }

    return meetings.asSequence().map { mutableListOf(it) }.reduce(::add)
}

当然,同样的原则也适用于不可变列表:

fun combine(meetings: List<Meeting>): List<Meeting> {
    fun add(ml: List<Meeting>, mr: List<Meeting>) : List<Meeting> {
        val leftLast = ml.lastOrNull()
        val rightFirst = mr.firstOrNull()

        return when {
            leftLast == null || rightFirst == null || leftLast.endTime != rightFirst.startTime ->
                ml + mr
            else -> {
                // assert(leftLast.endTime == rightFirst.startTime)
                ml.dropLast(1) + Meeting(leftLast.startTime, rightFirst.endTime) + mr.drop(1)
            }
        }
    }

    return meetings.asSequence().map { listOf(it) }.reduce(::add)
}

这可能是最实用的样式变体,但可能会增加更多对象创建的成本。当然,对于实际的性能考虑,我们必须进行基准测试。