Найти - Пользователи
Полная версия: Не могу найти ошибку
Начало » Python для новичков » Не могу найти ошибку
1 2
Kustodiev_17
Да-с, от переизбытка чувств-с сначала написал посты, а только затем подумал.

Да, уже опробовал в коде:

for patern_some in product("ACGT", repeat = PATTERN_STRING_LENGTH):
    patern_some = (''.join(patern_some))
    if patern_some == "TTT":
        print "Hurray !"

Ещё раз сердечно благодарю, sergeek
Kustodiev_17
Итого:

1) (+) Конечная версия программы стала достаточно компактной (особенно, если исключить часть кода для измерения времени работы программы);

""" Алгоритм решения (версия 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)

2) (+) В среднем время работы программы улучшилось (особенно, если не дышать на ПК-ветеран). Лучшее время (входные данные одинаковы): 20 мин 53 сек;

3) (-) Собственно время исполнения программы существенно больше 5 минут (даже, если учесть что на
нотнике брата код будет исполнятся в 2 раза быстрее и если обратится к другу (я измерял) у которого
комп в 2 раз быстрее брателова нотника, всё равно время исполнения критично.

4) (-) Лично у меня идеи иссякли. Про ускорители Psyco и Shedskin инфы нет.

5) (-) Про отладчик в Python(x,y) инфы не появилось. Хотя в соседней ветке есть инфа об интересном он-лайн отладчике.
sergeek
Kustodiev_17
Про ускорители Psyco и Shedskin инфы нет.
сейчас только PyPy актульно, хотя сам я его не трогал. Да и собирается он вроде бы с большим трудом, так что ПК-ветеран скорей всего пролетает.

Можно через numpy ускорить если получится свести задачу к векторным операциям.

Ну и вообще, оптимизировать обычно желательно алгоритм, а не реализацию. Может тут возможно заменить чем-нибудь полный перебор комбинаций.
Singularity
у меня pypy есть в репозитории
sergeek
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()
вроде бы такой же вывод дает
Kustodiev_17
Всех приветствую.

1)
sergeek
сейчас только PyPy актульно, хотя сам я его не трогал. Да и собирается он вроде бы с большим трудом, так что ПК-ветеран скорей всего пролетает.

Можно через numpy ускорить если получится свести задачу к векторным операциям.

Ну и вообще, оптимизировать обычно желательно алгоритм, а не реализацию. Может тут возможно заменить чем-нибудь полный перебор комбинаций.
У меня есть идея (была! и далее станет понятно, почему она пока не актуальна) изменить алгоритм - идти по Тексту брать каждый Кусок (заданного) размера k и создавать пробники (и запихивать их в словарь), пробники получаются из текущего Куска путём изменения текста Куска (все варианты) в d позициях. И уже с этим словарём (когда пробежимся по всему Тексту) подступаться к вычислениям (по уже известной технологии). Однако: а) (см. п. 2) ) ускорение с помощью PyPy дало показатель 01 мин. 14 сек (дяденьки и тётеньки, я конечно явно это не указывал, но опубликовав полный конечный текст программы с реальными данными - подспудно надеялся на то, что вы у себя её позапускаете и (возможно) сообщите время работы на ваших компьютерах - тем более делов: копи-паст и запустить, можно заниматься другими делами - программа выдаст ответ (он очень красивый) и покажет время, которое затратила) - и это уже результат!; б) Исходя из логики курса на котором я учусь, сначала треннируются “на кошках”, а потом дают реальный геном бактерии (так было с E. coli - кишечной палочкой). Так вот, так как геном бактерии это не 360 нуклеотидов (которые обсчитывает программа), а 4,6 * 10 ** 6, то проще и правильнее использовать нынешний алгоритм, так как полагаю количество вариантов по предполагаемому алгоритму будет сравнимо с полным количеством всех возможных варивантов (это гипотеза, но, лучше использовать плохую гипотезу, чем совсем без гипотезы).

2) Прочитал посты sergeek и Singularity, спасибо. Провёл (поверхностные) изыскания:
а) по Psyco - http://ru.wikipedia.org/wiki/Psyco и http://psyco.sourceforge.net/ (и решил копать в сторону PyPy)
б) по PyPy - http://ru.wikipedia.org/wiki/PyPy и http://pypy.org/

3) Сначала скачал https://bitbucket.org/pypy/pypy/downloads/pypy3-2.1-beta1-win32.zip возился, вконце концов запустил (сначала запуск pypy.exe, потом уже в открывшемся окне в текстовой моде запуск требуемого файла) - программа заглотила задачу, но через секунд 30 выдала “простыню” аглицкого текста - я решил, что дело в несовместимости версий Питонов и скачал далее https://bitbucket.org/pypy/pypy/downloads/pypy-2.2.1-win32.zip - проделал всё в таком же порядке и получил и ответ и время 01 мин 14 сек. А это результат!

Обновление поста: Пока я готовил данный пост - уважаемый мной sergeek опубликовал ещё один, поэтому мой данный пост не учитывает новую информацию.
Kustodiev_17
Доброго времени суток.

1) sergeek, программа выглядит изящно, но мне как новичку многое не понятно по синтаксису, хотя
чую, что речь о матрицах-массивах.

2) По курсу сдал задание (так как в PyPy запуск в текстовом окне, то ответы просто выводятся на экран. Поэтому пришлось дорабатывать программу, чтобы она не только результат выводила на экран, но и структурированно записывала этот же результат в файл. Для этого освоил минимум работы с записью данных в файл.) Получил новое задание. Озабочен тем как выполнить цикл (см. мой конечный вариант программы):

for some_string in product("ACGT", repeat = PATTERN_STRING_LENGTH):

только на половину - ставить счётчик + условие ? => тогда в случае PATTERN_STRING_LENGTH = 10 будет 500 000 сравнений - это производительность алгоритма, если возвращаться к моей первоначальной технологии “деление по модулю степени четвёрки” ? не хотелось бы… есть вариант разобраться с последней версией кода от sergeek….

Всё дело в том, что итоговая задача, которую дадут в рамках курса, ожидается для большого генома, порядка бактерии, PATTERN_STRING_LENGTH скорее всего будет = 9 и поэтому даже с ускорением разбазаривать производительность программы не хочется….
sergeek
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:
    ...
для нечетной длины тут будет округляться в меньшую сторону

** edit
ошибка, степень четверки всегда будет четной, так что все ок
Kustodiev_17
Код опробовал, спасибо, sergeek.
Очередное задание сдал.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB