这种编程模式叫什么名字？

Question

通常情况下，我们需要处理一系列“块”，这些块从“原子”流中读取，每个块由可变数量的原子组成，并且程序无法知道是否接收到完整的块，直到读取下一个块的第一个原子（或者原子流耗尽）。

一个简单的执行此任务的算法如下：

LOOP FOREVER:
    SET x TO NEXT_ATOM
    IF DONE(x) OR START_OF_CHUNK(x):
        IF NOT EMPTY(accum):
            PROCESS(accum)
        END
        if DONE(x):
            BREAK
        END
        RESET(accum)
    END
    ADD x TO accum
END

因此，我的问题是：

这种一般类别的问题和/或上面显示的编程模式有没有名称？

本帖子的其余部分只是描述上述抽象内容的一些（相当现实的）示例。 （这些示例使用Python编写，尽管它们可以轻松翻译为任何命令式语言。）

第一个示例是生成输入字符串的运行长度编码的函数。 在这种情况下，“原子”是单个字符，“块”是最大的相同字符运行。 因此，程序在读取以下运行的第一个字符之前不知道已经到达了运行的结尾。

def rle(s):
    '''Compute the run-length encoding of s.'''

    n = len(s)
    ret = []
    accum = 0
    v = object()  # unique sentinel; ensures first test against x succeeds
    i = 0
    while True:
        x = s[i] if i < n else None
        i += 1
        if x is None or x != v:
            if accum > 0:
                ret.append((accum, v))
            if x is None:
                break
            accum = 0
        v = x
        accum += 1

    return ret

第二个例子是一个函数，它以读取FASTA格式文件的句柄作为参数，并解析其内容。在这种情况下，原子是文本行。每个块由一个特殊标记的第一行组成，称为“defline”（并以'>'作为其第一个字符），后跟包含核苷酸或蛋白质序列的可变数量的行。同样，只有在读取下一个块的第一个原子（即defline）之后，代码才能明确地检测到块的结束。

def read_fasta(fh):
    '''Read the contents of a FASTA-formatted file.'''

    ret = []
    accum = []
    while True:
        x = fh.readline()
        if x == '' or x.startswith('>'):
            if accum:
                ret.append((accum[0], ''.join(accum[1:])))
            if x == '':
                break
            accum = []
        accum.append(x.strip())

    return ret

- kjo

---

你的问题太具体了，我认为不适合使用设计模式。它们往往更加通用。例如，你可以使用一些回调函数来处理循环，使用策略模式，这样相同的基本代码可以在不同的实例中使用，只需更改回调函数即可。 - James Black

这就是为什么我没有称它为“设计模式”的原因。我使用“编程模式”来避免混淆。 - kjo

Answer 1

我能想到的唯一解释是这是一个非常简单的LL(1)解析器。您正在以一种非常简单的方式从左到右解析数据，并且您需要向前查看一个值才能知道发生了什么。请参见http://en.wikipedia.org/wiki/LL_parser。

- andrew cooke

---

你也可以将其视为修改后的LR分析器，或任何定向、非回溯分析器。 - templatetypedef

Answer 2

我经常在索引中聚合简单统计数据时实现这种模式（特别是与排序结合使用）。 我从未听说过一个正式的名字，但在我们公司内部，我们简单地称之为“批处理”或“分组”，源于SQL GROUP BY子句。

在我们的系统中，批次通常由提取的属性（而不是光秃秃的边界驱动谓词）分隔，我们称之为批次或组键。 相比之下，您的示例似乎检查明确的分隔符。

- phs

Answer 3

我相信你所描述的是一种叫做流算法的算法，这种算法会逐个元素地指定输入，直到触发某个停止条件。流算法可用于建模通过网络接收或从一些生成数据的设备接收数据的算法。通常，流算法假定在任何时间点都有一些固定的内存限制，这意味着算法需要特别小心地保留重要信息同时丢弃无用的数据。

计算机科学中许多有趣的算法在流处理情况下无法正常工作，因此有一大类算法专门设计用于流处理。例如，有很好的流式算法可用于查找流中前k个元素（例如，请参见this question），从流中随机选择k个元素，查找在流中频繁出现的元素等。本问题的另一个答案（来自@andrew cooke）提到这类似于LL分析。实际上，LL分析（以及许多其他分析算法，如LR分析）是用于执行分析的流算法，但它们是更通用的流算法框架的特殊情况。

希望这可以帮助！

- templatetypedef