
Да, уже опробовал в коде:
for patern_some in product("ACGT", repeat = PATTERN_STRING_LENGTH): patern_some = (''.join(patern_some)) if patern_some == "TTT": print "Hurray !"
Ещё раз сердечно благодарю, sergeek

for patern_some in product("ACGT", repeat = PATTERN_STRING_LENGTH): patern_some = (''.join(patern_some)) if patern_some == "TTT": print "Hurray !"
""" Алгоритм решения (версия 2.5): Идём по Тексту (TEXT_STRING) и рубим Куски длиной k (PATTERN_STRING_LENGTH). Формируем Список состоящий из строк соответсвующих кусков. Не отвлекаемся на одинаковые строки (тем более если Текст небольшой, а k близко к максимальной величине и одинаковых строк будет немного). Далее с подсказки sergeek, да будет благословенен он сам и дни его, генерим все возможные варианты строк длиной k используя функцию product из модуля itertools. И последовательно сравниваем их с каждой строкой из Списка. Если не более d (VALUE_OF_VARIABILITY) различий, то заносим этот факт в протокол - формируем индекс количества квази-вхождений строки в Текст. Сравниваем данный индекс с текущим максимумом. Если индекс равен текущему максимуму, то сгенерённую строку заносим в итоговый список, если индекс больше текущего максимума, то обновляем текущий максимум и итоговый список опустошаем, начинаем его формировать заново. В конце печатаем итоговый список - он содержит все строки с одинаково максимальным квази-вхождением в Текст. При данной постановке задачи места вхождения в Текст не интересуют. """ import time from itertools import product """ Импортируем функцию для дальнейшего использования генерации строк - думаю будет эффективно. """ time_ini = 0 time_ini = time.time() # print time_ini time_end = 0 delta_time = 0 hour_t = 0 min_t = 0 sec_t = 0 """ Это начальный блок кода для определения времени исполнения всего кода программы """ TEXT_STRING = "TCACCCAGACCCTCAGTTAGACCCTCACCTCCCCAGAAGACCTCCCCAGACCTCTCACCCCCCCCTCGTTGTTCCTCAGAAGACCCGTTCCCGTTAGAAGACCCGTTCCTCCCTCCCTCAGAAGACCTCAGACCCAGACCTCAGAAGAAGATCATCACCCCCTCTCACCCGTTAGATCATCATCATCACCTCTCAGTTTCAAGAGTTTCATCACCCTCACCCCCTCCCTCCCCCCTCTCAAGACCTCTCAAGAAGAAGACCCAGATCAAGACCTCCCCCCTCAGACCTCAGACCCAGAGTTGTTCCCAGAAGATCA" """ Геномный Текст для поиска. """ TEXT_STRING_LENGTH = len(TEXT_STRING) """ Длина Текста. """ # print "TEXT_STRING_LENGTH = ", TEXT_STRING_LENGTH PATTERN_STRING_LENGTH = 10 """ Длина Образца, то есть k-размерность. """ VALUE_OF_VARIABILITY = 2 """ Допустимое значение Изменчивости при поиске. """ primary_list_of_string = [] """ Наш Хэш-Словарь """ # exit_list = [] """ Список для выходных данных """ def united_function_for_forming_list_of_text_string_genesis_for_all_variants_and_now_processing(): exit_list = [] for i in range(TEXT_STRING_LENGTH - PATTERN_STRING_LENGTH + 1): pattern_some_1 = TEXT_STRING[i : PATTERN_STRING_LENGTH + i] primary_list_of_string.append(pattern_some_1) max_number_of_position = 1 for some_string in product("ACGT", repeat = PATTERN_STRING_LENGTH): some_string = (''.join(some_string)) temp_number_of_positions = 0 for some_list in range(len(primary_list_of_string)): pattern_some = primary_list_of_string[some_list] index_of_pattern_some = 0 for m in range(PATTERN_STRING_LENGTH): if some_string[m] != pattern_some[m]: index_of_pattern_some += 1 if index_of_pattern_some == (VALUE_OF_VARIABILITY + 1): break if index_of_pattern_some <= VALUE_OF_VARIABILITY: temp_number_of_positions += 1 if temp_number_of_positions == max_number_of_position: exit_list.append(some_string) elif temp_number_of_positions > max_number_of_position: max_number_of_position = temp_number_of_positions exit_list = [some_string] print "" print " ".join(exit_list) united_function_for_forming_list_of_text_string_genesis_for_all_variants_and_now_processing() def run_time_total(t_1, t_2): """ Функция вычисляет время прошедшее за время исполнения кода программы и выводит его на консоль. Так как процессор мощный - время на исполнение самой функции практически тривиально """ global hour_t, min_t, sec_t, delta_time delta_time = t_2 - t_1 hour_t = (delta_time - (delta_time % 3600)) / 3600 min_t = (delta_time % 3600 - ((delta_time % 3600) % 60)) / 60 sec_t = float((delta_time % 3600) % 60) print "Total run time: " + str(hour_t) + " Hours " + str(min_t) + " Min " + str(sec_t) + " Sec" time_end = time.time() # print time_end run_time_total(time_ini, time_end)
Kustodiev_17сейчас только PyPy актульно, хотя сам я его не трогал. Да и собирается он вроде бы с большим трудом, так что ПК-ветеран скорей всего пролетает.
Про ускорители Psyco и Shedskin инфы нет.
sergeek
Можно через numpy
import numpy as np from itertools import product PSL = PATTERN_STRING_LENGTH = 10 VOV = VALUE_OF_VARIABILITY = 2 TEXT_STRING = "TCACCCAGACCCTCAGTTAGACCCTCACCTCCCCAGAAGACCTCCCCAGACCTCTCACCCCCCCCTCGTTGTTCCTCAGAAGACCCGTTCCCGTTAGAAGACCCGTTCCTCCCTCCCTCAGAAGACCTCAGACCCAGACCTCAGAAGAAGATCATCACCCCCTCTCACCCGTTAGATCATCATCATCACCTCTCAGTTTCAAGAGTTTCATCACCCTCACCCCCTCCCTCCCCCCTCTCAAGACCTCTCAAGAAGAAGACCCAGATCAAGACCTCCCCCCTCAGACCTCAGACCCAGAGTTGTTCCCAGAAGATCA" def main(): src = as_arrays(tuple(map(ord, TEXT_STRING))) prod = np.array(tuple(product(map(ord, 'ACGT'), repeat=PSL))) valid_vov_sums = np.vstack((prod != seq).sum(axis=1) <= VOV for seq in src).sum(axis=0) print(' '.join(map(lambda res : ''.join(map(chr, res)), prod[valid_vov_sums == np.max(valid_vov_sums)]))) def as_arrays(seq): x, xs = seq[:PSL], seq[PSL:] array = np.array(tuple(x)) if xs: return np.vstack([array, as_arrays(x[1:] + xs)]) return array main()
sergeekУ меня есть идея (была! и далее станет понятно, почему она пока не актуальна) изменить алгоритм - идти по Тексту брать каждый Кусок (заданного) размера k и создавать пробники (и запихивать их в словарь), пробники получаются из текущего Куска путём изменения текста Куска (все варианты) в d позициях. И уже с этим словарём (когда пробежимся по всему Тексту) подступаться к вычислениям (по уже известной технологии). Однако: а) (см. п. 2) ) ускорение с помощью PyPy дало показатель 01 мин. 14 сек (дяденьки и тётеньки, я конечно явно это не указывал, но опубликовав полный конечный текст программы с реальными данными - подспудно надеялся на то, что вы у себя её позапускаете и (возможно) сообщите время работы на ваших компьютерах - тем более делов: копи-паст и запустить, можно заниматься другими делами - программа выдаст ответ (он очень красивый) и покажет время, которое затратила) - и это уже результат!; б) Исходя из логики курса на котором я учусь, сначала треннируются “на кошках”, а потом дают реальный геном бактерии (так было с E. coli - кишечной палочкой). Так вот, так как геном бактерии это не 360 нуклеотидов (которые обсчитывает программа), а 4,6 * 10 ** 6, то проще и правильнее использовать нынешний алгоритм, так как полагаю количество вариантов по предполагаемому алгоритму будет сравнимо с полным количеством всех возможных варивантов (это гипотеза, но, лучше использовать плохую гипотезу, чем совсем без гипотезы).
сейчас только PyPy актульно, хотя сам я его не трогал. Да и собирается он вроде бы с большим трудом, так что ПК-ветеран скорей всего пролетает.
Можно через numpy ускорить если получится свести задачу к векторным операциям.
Ну и вообще, оптимизировать обычно желательно алгоритм, а не реализацию. Может тут возможно заменить чем-нибудь полный перебор комбинаций.
for some_string in product("ACGT", repeat = PATTERN_STRING_LENGTH):

Kustodiev_17
только на половину
from itertools import product, islice half_product = islice(product("ACGT", repeat=PATTERN_STRING_LENGTH), 4**PATTERN_STRING_LENGTH // 2) for some_string in half_product: ...