Занятие 5

Практическое занятие 5: еще раз про списки

Цель: Рассмотреть алгоритмы обработки числовых последовательностей с использованием списков Python

Задачи:

  1. Свойства и методы списков в Python
  2. Сортировка вставками
  3. Решето Эратосфена
  4. Частотный анализ

Срезы списков

В практическом занятии 3 мы рассмотрели срезы строк. Аналогично срезы работают для списков:

In [ ]:
a = [1, 2, 3, 4, 5]
print(a[1:3])
In [ ]:
print(a[1:5:2])

Если не указать первый элемент, то срез будет взят с первого элемента:

In [ ]:
print(a[:3])

Если не указать последний элемент — срез будет взят до последнего элемента:

In [ ]:
print(a[3:])

Индексы могут быть отрицательными:

In [ ]:
print(a[:-2])

Объясните результат выше.

In [ ]:
print(a[-3:])

Объясните результат выше.

Отрицательным может быть не только индекс, но и шаг:

In [ ]:
print(a[::-1])

Срез списка представляет собой новый список:

In [ ]:
b = a[-3:-1]
print(a)
print(b)
In [ ]:
b[1] = 8
print(a)
print(b)

Расположив срез списка слева от оператора присваивания мы можем изменить часть элементов списка:

In [ ]:
a[1:4] = [6, 7, 8]
print(a)

Та же операция, но с использованием функции range():

In [ ]:
a[1:4] = range(9, 12)
print(a)

Также можно присвоить в срез значения исходного списка. Например, код ниже осуществляет реверс элементов списка:

In [ ]:
a[::-1] = a[:]
print(a)

Методы списков

Помимо методов append() и count(), рассмотренных в практическом занятии 3, существуют и другие методы списков.

Например, метод insert(i, x) добавляет новый элемент x перед элементом с индексом i в список:

In [ ]:
print(a)
a.insert(3, 20)
print(a)

Удаление элемента из списка

Удалить элемент с индексом i из списка можно несколькими способами.

С помощью инструкции del:

In [ ]:
print(a)
del a[2]
print(a)

С помощью метода pop(i):

In [ ]:
print(a)
a.pop(1)
print(a)

Если не указать аргумент при вызове метода pop(), то будет удален последний элемент:

In [ ]:
print(a)
print(a.pop())
print(a)

Пример выше также демоснтрирует, что метод pop() возвращает значение удаленного из списка элемента.

При использовании списков важно помнить, что наименее трудоемкая операция при удалении элемента — это удаление с конца списка. По возможности, лучше использовать именно ее.

Добавление нескольких элементов

Добавить несколько элементов в конец списка можно с помощью метода extend(), которому в качестве аргумента передается итерируемый объект:

In [ ]:
print(a)
a.extend(range(30, 55, 3))
print(a)

Аналогичного результата можно добиться с помощью оператора +=:

In [ ]:
print(a)
a += range(55, 60)
print(a)

Если при присваивании в срез, длина итерируемого объекта больше среза, то список будет увеличен:

In [ ]:
print(a)
a[-4:-1] = range(60, 66)
print(a)

И наоборот, если при присваивании в срез, длина итерируемого объекта меньше среза, то список будет уменьшен:

In [ ]:
print(a)
a[-7:] = range(66, 68)
print(a)

В частности, при помощи присваивания в срез можно удалить часть списка, если присвоить в срез пустую последовательность:

In [ ]:
print(a)
a[0:6] = []
print(a)

Сортировка списков

В практическом занятии 3 мы рассмотрели сортировку списков в Python с помощью функций sort() и sorted() (используют сортировку TimSort). На этом занятии мы рассмотрим "ручную" сортировку с помощью алгоритма сортировки вставками.

Сортировка вставками

На каждой итерации алгоритма сортировки вставками выполняется сортировка только первых i элементов списка a. Пусть уже первые i − 1 элементов списка a отсортированы (то есть срез a[:i] отсортирован), и мы добавили в конец новый элемент. Этот новый элемент a[i] нужно передвинуть на правильное место, чтобы снова получить отсортированный массив. Будем просто пытаться обменивать его местами с соседом слева, если этот сосед больше нового элемента.

Например, пусть i = 7 и срез a[:i] равен [42, 45, 54, 55, 66, 67], а значение a[i] равно 48. Тогда элемент a[i] нужно поставить после элемента a[1], равного 45, а все элементы, которые больше 48, сдвинуть вправо на 1. Получится cрез a[:i+1], равный [42, 45, 48, 51, 54, 55, 66, 67]. Таким образом, при вставке элемента a[i] в срез a[:i] так, чтобы в результате получился упорядоченный срез, все элементы, которые больше a[i] будут двигаться вправо на одну позицию. А в освободившуюся позицию и будет вставлен элемент a[i]. При этом значение a[i] нужно сохранить в переменной, т. к. на место элемента a[i], возможно, будет записан элемент a[i–1].

Получим следующий алгоритм:

In [ ]:
a = [66, 54, 42, 45, 51, 55, 67, 48]
for i in range(1, len(a)): 
    vrem = a[i] # сохраним текущий элемент во временной переменной 
    j = i - 1 
    # определяем элементы большие vrem 
    while j >= 0 and a[j] > vrem: 
        # сдвигаем вправо на 1 
        a[j+1] = a[j] 
        j -= 1 
    # На свободное место записываем vrem 
    a[j+1] = vrem
print(a)

Решето Эратосфена

При решении практических задач часто возникает необходимость поиска простых чисел не превосходящих натурального числа N. Проверка всех чисел от 2 до N на простоту с помощью алгоритма, рассмотренного на практическом занятии 2 не является эффективным — ассимптотическая сложность такого подхода равна $O(n*\sqrt{n})$.

Более эффективным является алгоритм, предложенный греческим математиком Эратосфеном Киренским, согласно ему необходимо:

  1. Выписать все числа от 2 до N;
  2. Начать с n = 2;
  3. Вычеркнуть все числа, кратные n: 2n, 3n, и т.д.;
  4. Найти следующее невычеркнутой число и присвоить его переменной n;
  5. Повторять шаги 3 и 4 до тех пор, пока n < N.

Для N = 10 алгоритм будет выглядеть следующим образом:

  1. 2 3 4 5 6 7 8 9 10
  2. 2 3 4~ 5 6 7 8 9 10
  3. 2 3 4~ 5 6 7 8 9 10
  4. Чисел кратных 5 и 7 не осталось и в итоге получим список простых чисел: 2, 3, 5 и 7

Заметим, что при вычеркивании чисел, кратных 3 число 6 оказалось вычеркнутым ранее (оно кратно двум — 3*2). Этот факт позволяет улучшить алгоритм, начиная вычеркивать числа на шаге 3 не с 2n, а с $n^2$. При этом получится, что при $n^2 > N$ вычеркивать будет нечего, что мы и увидели для чисел 5 и 7 в примере выше.

С учетом сказанного, алгоритм примет следующий вид:

  1. Выписать все числа от 2 до N;
  2. Начать с n = 2;
  3. Вычеркнуть все числа, кратные n, начиная с $n^2$;
  4. Найти следующее невычеркнутой число и присвоить его переменной n;
  5. Повторять шаги 3 и 4 до тех пор, пока $n^2 \leq N$.

Реалдизация алгоритма на языке Python будет выглядеть следующим образом.

Пусть переменная N содержит исходное число, а массив a — инициирован значениями True. Далее для числа i его элемент a[i] будет содержать значение False, если число i вычеркнуто.

In [ ]:
N = int(input())
a = [True] * (N + 1)

Элементы a[0] и a[1] сразу заполним значением False:

In [ ]:
a[0] = False
a[1] = False

Строки ниже реализуют шаги со 2 по 5 из приведенного выше алгоритма:

In [ ]:
n = 2
while n*n <= N:
    if a[n]:
        i = n*n
        while i <= N:
            a[i] = False
            i += n
    n += 1

Выведем полученную последовательность простых чисел:

In [ ]:
for i in range(2, N+1):
    if a[i]:
        print(i, end=' ')

Задача частотного анализа

В качестве примера задачи, для решения которой используется анализ частоты встречающихся символов, рассмотрим задачу с сайта Константина Полякова.

Задача: На вход программы подается текст на английском языке, заканчивающийся точкой (другие символы “.” в тексте отсутствуют). Требуется написать программу, которая будет определять и выводить на экран английскую букву, встречающуюся в этом тексте чаще всего, и количество там таких букв. Строчные и прописные буквы при этом считаются не различимыми. Если искомых букв несколько, то программа должна выводить на экран первую из них по алфавиту. Например, пусть файл содержит следующую запись: It is not a simple task. Yes! Чаще всего здесь встречаются буквы I, S и T (слово Yes в подсчете не учитывается, так как расположено после точки). Следовательно, в данном случае программа должна вывести два символа, разделенных пробелом: I 3

Для работы алгоритма ниже потребуется файл text.txt. download file text.txt

In [ ]:
# Определим список заглавных английских букв
letters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

# Определим список частоты встречающихся букв в предложении
cnt = [0]*len(letters)

with open('text.txt', 'r') as F:
    s = F.readline().split('.')[0].upper() # выделим предложение, переведя все символы в верхний регистр
    for c in s:
        # подсчет частоты встречающихся букв
        if c in letters:
            cnt[letters.index(c)] += 1
# Выведем результат
print(letters[cnt.index(max(cnt))], max(cnt))

Модифицируйте код приведенный выше так, чтобы в результате на экран выводились 10 наиболее встречаемых букв и их частоты (в порядке убывания).

In [ ]:

Модифицируйте код из предыдущего задания чтобы он анализировал все предложения из исходного текста и проведите частотный анализ разделов History и Education статьи https://en.wikipedia.org/wiki/Moscow_Institute_of_Physics_and_Technology. Сравните полученные результаты.

In [ ]: