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 を追加するロジックは 2 回表示され、2 回目の出現を忘れがちです。

  • 新しいグループを作成するロジックが 2 回表示されます。このロジックは自明かもしれません。そうでない場合は、別の関数に分割できますが、最初の箇条書きと同様に、フローが正しくないことを示しています。

  • 最初のアイテムが所属チェックに失敗する可能性があります。その場合、新しいグループを作成した直後に新しいグループを作成します。この問題は些細なことのように思えるかもしれませんが、最初の空のグループが に追加されるのを明示的に防止する必要がある場合がありgroupsます。とにかく、それは望ましいロジックの誤った表現を示唆しています。

このロジックを表現するためのよりクリーンな方法があるかどうか疑問に思っています。この質問の抽象的な性質をお詫びしますが、この問題は複数のコンテキストで発生します。特定のプログラミング言語のコンテキストでこの問題に対処する必要がある場合は、Java.

4

2 に答える 2

1

これにアプローチする 1 つの方法は、is goodグループ フィルターをグループ化ループから切り離すことです。つまり、後処理または需要主導型として扱います。（質問に示されているように）2つを組み合わせることは、時期尚早の最適化が厄介なコードを引き起こす例であると主張できます。

Group外側のループを内側のループで繰り返すようにすると、コード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

これは大幅な改善ではありません (コードはまだ 8 行であり、奇妙なネストされたifステートメントは好きではありません) が、現時点ではこれ以上の解決策は思いつきません。

それはあなたの3つの懸念をかなりうまく解決します：

  1. はif curGroup is good: add curGroup to groups複製されなくなりました
  2. add GrouptoGroupsも複製されなくなりました
  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# にあるため、辞書と呼びます)。値は項目のグループです。アイテムが属するグループを決定する機能は、アイテムが現在のグループに属しているかどうかを現在確認する方法と非常に似ている必要があります。

次に、コードは次のようになります。

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 に答える