Домашняя работа по курсу

Как сдавать домашнюю работу

  1. Зарегистрироваться на факультетском Ejudge

  2. Выбрать 5-й «турнир» (UNИX Python 2014)
    • Возможно, придётся пойти по ссылке «Confirm registration» («Подтвердить регистрацию»)
    • Возможно, придётся пойти по ссылке «Participate» («Участвовать»)
  3. Выбрать соответствующую задачку

    • Задачу под названием «1» решать не надо :)

  4. Загрузить решение
    • Прежде, чем загружать решение, убедитесь, что оно правильное. Не надо вместо этого делать много различных вариантов решения в надежде, что какой-то один всё-таки пройдёт тесты.

    • Если возникают вопросы — спрашивайте, для этого есть и интерфейс eJudge, и почта (FrBrGeorge, PavelSutyrin)

  5. Дождаться конца проверки (как правило, несколько секунд) и обновить страницу браузера

Как оформлять решение

По умолчанию, т. е. если иное не указано отдельно:

⇒ Для ввода можно пользоваться input() (без строки-подсказки), а для вывода — print.

Сводный список домашних заданий

См. ../HomeworkRules

  1. Установить и настроить подходящий текстовый редактор или IDE (пример: настройка Geany)

  2. (AndOr) Условное выражение

    Ввести два объекта Python и вывести первый ненулевой из них. Если оба нулевые, вывести NO.

    Input: 

    []
123
    Output: 

    123

  4. (SecondMax) Найти второй максимум

    Ввести список и вывести второй максимум этого списка, т. е. элемент a∈S : ∃ b∈S : b>a и a⩾c ∀c∈S, c≠b. Если второго максимума нет, вывести NO.

    Input: 

    3,4,5,6,7
    Output: 

    6

  • Прочитать:

  • <!> Передать input() что-нибудь действительно нехорошее :)

  • (ParallelSegments) Параллельные отрезки

    Ввести восемь чисел через запятую — целочисленные координаты 4-х попарно несовпадающих точек A1, A2, A3 и A4: X1, Y1, X2, Y2, X3, Y3, X4, Y4. Вывести YES, если прямая A1A2 параллельна прямой A3A4 (или совпадает с ней), и NO — если не параллельна.

    Input: 

    1,2,7,14,8,8,18,28
    Output: 

    YES

  • (SectionShuffle) Перетасовать кортеж

    Ввести последовательность A объектов Python через запятую и вывести кортеж, состоящий из элементов последовательности, стоящих на чётных местах — в обратном порядке (включая A[0]), после которых идут элементы последовательности, стоящие на нечётных местах.

    Input: 

    '0', 1, 2, '3', 4, 5, '6', 7, 8, '9', 10, 11
    Output: 

    (10, 8, '6', 4, 2, '0', 1, '3', 5, 7, '9', 11)

  • <!> ввести W, H — размеры лабиринта и вывести представление достаточно случайного проходимого лабиринта для предыдущей задачи (обратите внимание на нескучные обои красивые неслучайные стены :) )

Задачи для EJudge не могут включать в себя работу с ОС или модулями, так что просто упражнения:

  • Прочитать:

  • (SimpleVector) Вектора на плоскости

    Реализовать класс Vector, позволяющий

    • задавать двумерный вектор (из двух чисел)
    • вычислять вектор — сумму двух векторов
    • вычислять вектор — результат умножения вектора на число (или числа на вектор)
    • скалярно умножать вектор на вектор

    • преобразовывать вектор в строку вида |x,y|

    Input: 

       1 A = mod.Vector(1,2)
   2 B = mod.Vector(3,4)
   3 print A
   4 print A+B
   5 print A*B
   6 print 7*A
    Output: 

    |1,2|
|4,6|
11
|7,14|

  • Прочитать:

    • Раздел Data model (весь, можно несколько раз)

    • Всё по ссылкам выше

  • Очередная алгоритмическая задачка, поупражнять мозг:

(необязательное)

  • FunctionCachier. Написать декоратор function_cachier, который возвращает функцию, значения которой не вычисляются заново при повторных обращениях. 

def f1(n):
  print 'f1 called'
  return n*n

@mod.function_cachier
def f2(n):
  print 'f2 called'
  return n*n*n

print len([ f1(n) for n in range(3)])
print len([ f1(n) for n in range(3)])
print len([ f2(n) for n in range(4)])
print len([ f2(n) for n in range(4)])

f1 called
f1 called
f1 called
3
f1 called
f1 called
f1 called
3
f2 called
f2 called
f2 called
f2 called
4
4
  • Усложнение: научить его работать с рекурсивными функциями. 

def f1(n):
  print 'f1 called'
  return n*n

def f2(n):
  print 'f2 called'
  return n*n*n

print len([ f1(n) for n in range(3)])

with mod.with_function_cachier(f2) as f:
  print len([ f(n) for n in range(5)])

f1 called
f1 called
f1 called
3
5
  • Усложнение: Сделать его повторно используемым между вызовами with, чтобы сохранялся однажды накопленный кэш функций.

  • Усложнение: Сделать его повторно используемым между вызовами программы ;)

Include: Ничего не найдено по регулярному выражению «== Д/З ==$».

Что дальше?

Мелочи и подчистка

Вопросы быстродействия

  • 1 ms vs. 1 µs
  • Быстродействие и ЗБЧ
  • Быстродействие и вычислительная сложность
  • Быстродействие и дзен Python (см. далее)
  • Действительные случаи потери быстродействия

Python Patterns - An Optimization Anecdote (довольно старое эссе Гвидо, здесь он ещё любил reduce() ;) ):

  • Rule number one: only optimize when there is a proven speed bottleneck. Only optimize the innermost loop. (This rule is independent of Python, but it doesn't hurt repeating it, since it can save a lot of work. :) )

  • Small is beautiful. Given Python's hefty charges for bytecode instructions and variable look-up, it rarely pays off to add extra tests to save a little bit of work.

  • Use intrinsic operations. An implied loop in map() is faster than an explicit for loop; a while loop with an explicit loop counter is even slower.

  • Avoid calling functions written in Python in your inner loop. This includes lambdas. In-lining the inner loop can save a lot of time.
  • Local variables are faster than globals; if you use a global constant in a loop, copy it to a local variable before the loop. And in Python, function names (global or built-in) are also global constants!

  • Try to use map(), filter() or reduce() to replace an explicit for loop, but only if you can use a built-in function: map with a built-in function beats for loop, but a for loop with in-line code beats map with a lambda function!

  • Check your algorithms for quadratic behavior. But notice that a more complex algorithm only pays off for large N - for small N, the complexity doesn't pay off. In our case, 256 turned out to be small enough that the simpler version was still a tad faster. Your mileage may vary - this is worth investigating.

  • And last but not least: collect data. Python's excellent profile module can quickly show the bottleneck in your code. if you're considering different versions of an algorithm, test it in a tight loop using the time.clock() function.

/!\ Разбор каких-то задач?

Дзен Python

import this:

  • The Zen of Python, by Tim Peters (structured by FrBrGeorge CO)

    1. Beautiful is better than ugly.
    2. Explicit is better than implicit.
    3. Simple is better than complex.
      • Complex is better than complicated.
    4. Flat is better than nested.
    5. Sparse is better than dense.
    6. Readability counts.
    7. Special cases aren't special enough to break the rules.
      • Although practicality beats purity.
    8. Errors should never pass silently.
      • Unless explicitly silenced.
    9. In the face of ambiguity, refuse the temptation to guess.
    10. There should be one — and preferably only one — obvious way to do it.
      • Although that way may not be obvious at first unless you're Dutch.
    11. Now is better than never.

      • Although never is often better than right now.

    12. If the implementation is hard to explain, it's a bad idea.

      • If the implementation is easy to explain, it may be a good idea.

    13. Namespaces are one honking great idea -- let's do more of those!

Дальнейшее движение

  • Изучение алгоритмического программирования на Python:
  • Инструментальная разработка и промышленное программирование
  • «Академическое» программирование
  • Сам Python и его реализации

EE: import antigravity