Возможно, вы ищете что-то вроде:
#!/usr/bin/env python
def match_prefix(pfx,seq):
'''return subset of seq that starts with pfx'''
results = list()
for i in seq:
if i.startswith(pfx):
results.append(i)
return results
def extract_prefixes(lngth,seq):
'''return all prefixes in seq of the length specified'''
results = dict()
lngth += 1
for i in seq:
if i[0:lngth] not in results:
results[i[0:lngth]] = True
return sorted(results.keys())
def gen_prefix_indexed_list(depth,seq):
'''return a dictionary of all words matching each prefix
up to depth keyed on these prefixes'''
results = dict()
for each in range(depth):
for prefix in extract_prefixes(each, seq):
results[prefix] = match_prefix(prefix, seq)
return results
if __name__ == '__main__':
words='''Apple Ape Arc Abraid Bridge Braide Bray Boolean'''.split()
test = gen_prefix_indexed_list(2, words)
for each in sorted(test.keys()):
print "%s:\t\t" % each,
print ' '.join(test[each])
То есть вы хотите сгенерировать все префиксы, которые присутствуют в списке слов между одним и некоторым числом, которое вы укажете (2 в этом примере). Затем вы хотите создать индекс всех слов, соответствующих каждому из этих префиксов.
Я уверен, что есть более элегантные способы сделать это. Для быстрого и легко объясненного подхода я только что построил это из простой восходящей функциональной декомпозиции кажущейся спецификации. Значения конечного результата представляют собой списки, каждый из которых соответствует заданному префиксу, затем мы начнем с функции отфильтровывать такие совпадения из наших входных данных. Если все ключи конечного результата представляют собой префиксы от 1 до N, которые появляются в нашем вводе, то у нас есть функция для их извлечения. Тогда наша спец. очень простой вложенный цикл вокруг этого.
Конечно, этот гнездовой цикл может быть проблемой. Такие вещи обычно приравнивают к эффективности O (n ^ 2). Как показано, это будет повторять исходный список C * N * N раз (C - это постоянное число, представляющее префиксы длины 1, 2 и т. Д .; тогда как N - длина списка).
Если это разложение обеспечивает желаемую семантику, тогда мы можем посмотреть на повышение эффективности. Очевидный подход заключается в том, чтобы лениво генерировать ключи словаря, когда мы выполняем итерацию один раз по списку ... для каждого слова, для каждой длины префикса, генерировать ключ ... добавлять это слово к списку / значению, сохраненному в этом ключе и переходите к следующему слову.
Есть еще вложенный цикл ... но это короткий цикл для каждой длины ключа / префикса. Преимущество этого альтернативного дизайна состоит в том, что он позволяет перебирать списки слов из любого итерируемого, а не только из списка в памяти. Таким образом, мы можем выполнять итерации по строкам файла, результатам, сгенерированным из запроса к базе данных, и т. Д. - без лишних затрат памяти на хранение всего исходного списка слов в памяти.
Конечно, мы все еще храним словарь в памяти. Однако мы также можем изменить это, отделив логику от ввода и хранения. Когда мы добавляем каждый вход к различным значениям префикса / ключа, нам все равно, являются ли они списками в словаре, или строками в наборе файлов, или значениями, извлекаемыми из (и возвращаемыми обратно) в DBM или другое хранилище ключей / значений (например, какой-то CouchDB или другой «кластер / база данных noSQL».
Выполнение этого оставлено читателю в качестве упражнения.