/algo_intro

Introduction to Algorithms

Primary LanguagePython

Зачем нужны алгоритмы?

Задача

Подсчитать, какое количество сочетаний по три элементов входного массива даст в сумме 0.

Зачем нужны алгоритмы?

def counter(a: List[int]) -> int:
    N:int = len(a)
    counter:int = 0
    for i in range(N):
        for j in range(i+1, N):
            for k in range(j+1, N):
                s = a[i] + a[j] + a[k]
                if s == 0:
                    counter += 1
    return counter

Результат наивной реализации

% python ./first_try.py 1K
2 вызовов для 1K данных: лучший результат равен 42.02
% python ./first_try.py 2K
2 вызовов для 2K данных: лучший результат равен 340.84

Бинарный поиск

def binary_search(
        lst:List[int], target:int
) -> int:
    start:int = 0
    end:int = len(lst) - 1
    while(start <= end):
        mid = (start + end) // 2
        if(lst[mid] > target):
            end = mid - 1
        elif(lst[mid] < target):
            start = mid + 1
        else:
            return mid
    return -1

Быстрый ThreeSum

def counter(a: List[int]) -> int:
  # O(NlogN)
  arr:List[int] = sorted(a)
  N:int = len(arr)
  counter:int = 0
  for i in range(N):
    for j in range(i+1, N):
      # O(logN)
      if binary_search(
        arr, -(arr[i]+arr[j])
      ) > j:
        counter += 1
  return counter

Результат быстрого ThreeSum

% python fast_threesum.py 1K
2 вызовов для 1K данных: лучший результат равен 1.64
% python fast_threesum.py 2K
2 вызовов для 2K данных: лучший результат равен 7.36
% python fast_threesum.py 4K
2 вызовов для 4K данных: лучший результат равен 31.31

Алгоритмическая сложность

img

Нужны ли алгоритмы backend-разработчику?

img

Какие алгоритмы нужнее всего?

Зависит от задачи, области применения

  • алгоритмы на строках
    нужны например биоинформатикам, для работы с последовательностями ДНК
  • алгоритмы на деревьях
    • компиляторы
    • машинное обучение
    • построение маршрутов
    • парсинг сайтов

Структуры данных. Очередь

  • FIFO: First In First Out

img

Структуры данных. Стек

  • LIFO: Last In First Out

img

Структуры данных. Граф

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

img

Поиск вглубину. Depth-First Search

def dfs(graph, start, goal):
  stack = [(start, [start])]
  while stack:
    (v, p) = stack.pop()
    paths = set(graph[v]) - set(p)
    for nxt in paths:
      if nxt == goal:
        yield p + [nxt]
      else:
        stack.append((nxt, p+[nxt]))
print(list(dfs(graph, 'A', 'F')))
[['A', 'C', 'F'], ['A', 'B', 'E', 'F']]

Глупая сортировка / сортировка дурака

def sort_alg(l):
  while True:
    c = 0
    for i in range(len(l)-1):
      if l[i] > l[i+1]:
        l[i+1],l[i] = l[i],l[i+1]
      else:
        c += 1
    if c == (len(l) - 1): return l
print(sort_alg([1, 3, 2, 0]))
[0, 1, 2, 3]

Результат глупой сортировки

  • Эффективность глупой сортировки: $\mathcal{O}(N^{3})$

% ./fool_sort.py 1K
2 вызовов для 1K данных: лучший результат равен 0.12
% ./fool_sort.py 2K
2 вызовов для 2K данных: лучший результат равен 0.53
% ./fool_sort.py 4K
2 вызовов для 4K данных: лучший результат равен 2.15

Пузырьковая сортировка

def sort_alg(l):
  for i in range(len(l)):
    for j in range(len(l[i+1:])):
      if l[j] > l[j+1]:
        l[j], l[j+1] = (l[j+1], l[j])
  return l

print(sort_alg([1, 3, -1, 2, 0]))
[-1, 0, 1, 2, 3]

Результат пузырьковой сортировки

  • Эффективность пузырьковой сортировки: $\mathcal{O}(N^{2})$

% ./bubble_sort.py 1K
2 вызовов для 1K данных: лучший результат равен 0.11
% ./bubble_sort.py 2K
2 вызовов для 2K данных: лучший результат равен 0.45
% ./bubble_sort.py 4K
2 вызовов для 4K данных: лучший результат равен 1.86

Сортировка слиянием (Merge Sort)

Сортировка слиянием позволяет нам распараллелить процесс сортировки. Это очень эффективно на больших данных и широко используется в алгоритмах map/reduce.

Результат Merge Sort

  • Эффективность Merge Sort: $\mathcal{O}(NlogN)$

% ./merge_sort.py 1K
2 вызовов для 1K данных: лучший результат равен 0.01
% ./merge_sort.py 4K
2 вызовов для 4K данных: лучший результат равен 0.03
% ./merge_sort.py 8K
2 вызовов для 8K данных: лучший результат равен 0.07
% ./merge_sort.py 32K
2 вызовов для 32K данных: лучший результат равен 0.31

Сравнение алгоритмов сортировки

img

Умножение двух чисел

\begin{equation} \opmul{5678}{1234}\qquad \end{equation}

Умножение двоичных чисел

img
Можно ли лучше?

Алгоритм Каратцубы

x = 5678
y = 1234

a = 56; b = 78
c = 12; d = 34

Алгоритм Каратцубы

# step1
step1 = a * c
# step2
step2 = b * d
# step3
a_b = a + b
c_d = c + d
step3 = a_b * c_d
# step4:
# step3 - step2 - step1
step4 = step3 - step2 - step1

Алгоритм Каратцубы

line1 = step1 * 10**4
line2 = step2
line3 = step4 * 10**2
result = (
    line1
    + line2
    + line3
)
print(result)
7006652

Умножение матриц

\begin{equation} \left[ \begin{array}{ccc} A & B \ C & D \ \end{array} \right] \times \left[ \begin{array}{ccc} E & F \ G & H \ \end{array} \right] = \left[ \begin{array}{ccc} AE + BG & AF + BH \ CE + DG & CF + DH \ \end{array} \right] \end{equation}

Умножение матриц

def mxm(A, X):
  n = len(A)    # A: n×m
  m = len(A[0])
  p = len(X[0]) # X: m×p
  B = [[0] * p] * n
  for i in range(n):
    for j in range(p):
      for k in range(m):
        B[i][j] += A[i][k]*X[k][j]
  return B

Где ошибка в этом коде?

Умножение матриц

def mxm(A, X):
  n = len(A)    # A: n×m
  m = len(A[0])
  p = len(X[0]) # X: m×p
  B = [[0] * p for _ in range(n)]
  for i in range(n):
    for j in range(p):
      for k in range(m):
        B[i][j] += A[i][k]*X[k][j]
  return B

\(O(n^{3})\)
Можно ли лучше?

Алгоритм Штрассена

\begin{normalsize} \left[ \begin{array}{cccc} 11 & 12 & 13 & 14 \ 21 & 22 & 23 & 24 \ 31 & 32 & 33 & 34 \ 41 & 42 & 43 & 44 \ \end{array} \right] = \left[ \begin{array}{cc} A & B \ C & D \ \end{array} \right] \end{normalsize}

\begin{normalsize} \left[ \begin{array}{cccc} 11 & 21 & 31 & 41 \ 12 & 22 & 32 & 42 \ 13 & 23 & 33 & 43 \ 14 & 24 & 34 & 44 \ \end{array} \right] = \left[ \begin{array}{cc} E & F \ G & H \ \end{array} \right] \end{normalsize}

Алгоритм Штрассена

\begin{array}{l} P_{1} = A(F - H), \ P_{2} = (A + B)H, \ P_{3} = (C + D)E, \ P_{4} = D(G - E), \ P_{5} = (A + D)(E + H), \ P_{6} = (B - D)(G + H), \ P_{7} = (A - C)(E + F) \ \end{array}

\begin{footnotesize} \left[ \begin{array}{cc} AE+BG & AF+BH \ CE+DG & CF+DH \end{array} \right] = \left[ \begin{array}{ll} P_{5} + P_{4} - P_{2} + P_{6} & P_{1} + P_{2} \ P_{3} + P_{4} & P_{1} + P_{5} - P_{3} + P_{7} \end{array} \right] \end{footnotesize}

векторизация

  • Большинство операций процессора это SISD: Single Instruction Single Data

    | 0 | 1 | 2 | 3 | | a[0]= | not used | not used | not used | | b[0]+ | not used | not used | not used | | c[0] | not used | not used | not used |

  • Процессор может поддерживать специальные регистры для SIMD: Single Instruction Multiple Data

    | 0 | 1 | 2 | 3 | | a[0]= | a[1]= | a[2]= | a[3]= | | b[0]+ | b[1]+ | b[2]+ | b[3]+ | | c[0] | c[1] | c[2] | c[3] |

Пример умножения матриц

Article

img

Логистическая регрессия

$z = w_{0}x + w_{1}x + \dots + w_{n}x + b$
$a = \frac{1}{1+e^{-z}}$

img

Котики!

GitHub

Tensorflow

Colab

Как изучать алгоритмы

Вопросы-ответы

img