На этом шаге мы рассмотрим его реализацию.

    Одна из основных операций, которую мы можем захотеть выполнить с геном, - это поиск определенного кодона. Цель состоит в том, чтобы просто выяснить, существует ли в гене такой кодон.

    Линейный поиск перебирает все элементы в пространстве поиска в порядке исходной структуры данных до тех пор, пока не будет найден искомый объект или не достигнут конец структуры данных. По сути, линейный поиск - это самый простой, естественный и очевидный способ поиска чего-либо. В худшем случае линейный поиск потребует проверки каждого элемента в структуре данных, поэтому он имеет сложность O(n), где n - количество элементов в структуре (рисунок 1).

Рис.1. В худшем случае при линейном поиске нужно последовательно просмотреть каждый элемент массива

    Определить функцию, которая выполняет линейный поиск, очень легко. Она просто должна перебрать все элементы структуры данных и проверить каждый из них на эквивалентность искомому элементу. В примере ниже такая функция определяется для Gene и Codon, а затем применяется к my_gene и объектам Codon с именами acg и gat.

def linear_contains(gene: Gene, key_codon: Codon) -> bool:
    for codon in gene:
        if codon == key_codon:
            return True
    return False


acg: Codon = (Nucleotide.A, Nucleotide.C, Nucleotide.G)
gat: Codon = (Nucleotide.G, Nucleotide.A, Nucleotide.T)
print(linear_contains(my_gene, acg))  # True
print(linear_contains(my_gene, gat))  # FaLse

Эта функция имеет демонстрационное назначение. Для всех встроенных типов последовательностей Python (list, tuple, range) реализован метод __contains__(), который позволяет выполнять поиск определенного элемента с помощью оператора in. Фактически оператор in можно использовать для любого типа, для которого реализован метод __contains__(). Например, мы могли бы найти acg в my_gene и вывести результат, написав строку print(acg in my_gene).

    На следующем шаге мы рассмотрим бинарный поиск.

Предыдущий шаг Содержание Следующий шаг