Часто требуется обработать последовательность «чанков», которые считываются из потока «атомов», где каждый чанк состоит из переменного числа атомов, и у программы нет возможности узнать, что она имеет получил полный кусок, пока он не прочитает первый атом следующего фрагмента (или поток атомов не исчерпается).
Простой алгоритм выполнения этой задачи будет выглядеть так:
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» (и отмеченной «>» в качестве первого символа), за которой следует переменное число строк, содержащих отрезки нуклеотидной или белковой последовательности. Опять же, код может однозначно определить конец фрагмента только после чтения первого атома (т. Е. Отклонения) следующего фрагмента.
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