1

在命令式编程时，我经常发现自己编写代码来对这样的项目进行分组：

function group(items):
    groups <- new Groups
    curGroup <- new Group
    for item in items:
        if item doesn't belong in curGroup:
            if curGroup is good:
                add curGroup to groups
            curGroup <- new Group
        add item to curGroup
    if curGroup is good:
        add curGroup to groups
    return groups

不幸的是，这段代码存在一些缺陷：

  • if curGroup is good: add curGroup to groups代码是重复的。虽然条件中的条件可以分解为一个函数，但调用该函数并将 curGroups 添加到组的逻辑仍然出现两次，并且很容易忘记第二次出现。

  • 创建新组的逻辑出现两次。这个逻辑可能是微不足道的，如果不是，那么它可以分解成一个单独的函数，但就像第一个要点一样，它表明流程不正确。

  • 第一项可能无法通过归属检查，在这种情况下，我们会在创建新组后立即创建一个新组。这个问题可能看起来微不足道，但有时需要明确阻止将初始空组添加到groups. 无论如何，它表明所需逻辑的表达不正确。

我想知道是否有一种更简洁的方式来表达这种逻辑。我为这个问题的抽象性质道歉，但这个问题出现在多种情况下。如果有必要在特定编程语言的上下文中解决这个问题，您可以假设 Java。

4

2 回答 2

1

解决此问题的一种方法是将is good组过滤器从分组循环中分离出来——将其视为后期处理或需求驱动的处理。您可能会争辩说，将两者结合起来（如您的问题所示）是过早优化导致笨拙代码的一个示例。

如果你用一个内循环来迭代Group's的外循环while item，你自然可以避免重复你的new Group代码。它还应该有助于解决您对第一个项目的担忧，因为它可以更容易地将组中的第一个项目与其他项目区别对待：

function group(items):
    groups <- new Groups
    while(items not empty):
        curGroup <- new Group
        using items:
            add current item to curGroup
            advance to next item
        while(items not empty):
            using items:
                if current item belongs in curGroup:
                    add current item to curGroup
                    advance to next item
                else exit inner loop
        if(curGroup is good):
            add curGroup to groups
    return groups

请注意，上面的伪代码items用作迭代器。

尽管您的问题是关于命令式编程，但看看 Haskell 的groupBy.

于 2016-03-11T21:12:16.080 回答
1

我处理这个问题的方法是在你的第一个if语句中添加一个额外的条件，这样它就包含了最后一个if语句的逻辑。如果该项目不属于当前组，或者curGroup如果我在.groupitemitems

这不是一个巨大的改进（它仍然是八行代码，而且我不喜欢奇怪的嵌套if语句），但我目前想不出更好的解决方案。

它很好地解决了您的三个问题：

  1. 不再if curGroup is good: add curGroup to groups重复
  2. 添加Group到Groups也不再重复
  3. 这不是我的重组直接解决的。但是，您可以通过确保在组为空时始终说某个项目属于某个组（这对我来说很有意义，但我不知道您的分组实际在做什么的细节）来轻松避免问题 3。

这可能是这样的：

function group(items):
    groups <- new Groups
    curGroup <- new Group
    for item in items: 
        if item doesn't belong in curGroup || item is last item:
            if item is last item:
                add item to curGroup
            if curGroup is good:
                add curGroup to groups
            curGroup <- new Group
        add item to curGroup
    return groups

我很高兴看到比这更好、更精致的解决方案，但我想我会发布这个至少让事情顺利进行

更新：

这是您可以采取的不同方向（如果它在 Java 中工作，我更习惯于 C#）。与其构建一组组，不如构建一个哈希映射（我将其称为字典，因为它在 C# 中就是这样），键是您计算的某个值，以确定项目属于哪个组，并且value 是一组项目。确定项目属于哪个组的功能应该与您当前检查项目是否属于当前组的方式非常相似。

然后您的代码将如下所示：

function group(items):
    groups <- new Dictionary<string, Group>
    for item in items:
        groupKey <- item.FindKey()
        if !groups.ContainsKey(groupKey):
            add new group to groups with key of groupKey
        add item to groups[groupKey]
    return groups

这种方法的优点：

  1. 没有重复的代码
  2. 物品的顺序无关紧要，而在此之前确实很重要（在某些情况下这可能是一个缺点，如果是这样，请告诉我，有办法解决这个问题）。
  3. 易于查看项目为何属于给定组（便于调试）

缺点

  1. 如前所述，保持秩序可能很重要
  2. 使用更复杂的数据结构（尽管 HashMap/Dictionary 并不复杂）
  3. 可能很难FindKey为项目编写函数（尽管我怀疑在大多数情况下不会）
于 2016-03-11T21:21:50.897 回答