8 ключевых алгоритмов и структур данных на Python: гайд для разработчиков

def bubble_sort(arr):
n = len(arr)
# Проходим по всем элементам списка
for i in range(n):
# Последние i элементов уже на месте
for j in range(0, n – i – 1):
# Сравниваем соседние элементы
if arr[j] > arr[j + 1]:
# Если они в неправильном порядке, меняем их местами
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

# Пример использования
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(unsorted_list)
print(sorted_list) # [11, 12, 22, 25, 34, 64, 90]

def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)

# Пример использования
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = quick_sort(unsorted_list)
print(sorted_list) # [11, 12, 22, 25, 34, 64, 90]

def binary_search(arr, target):
low = 0
high = len(arr) – 1

while low <= high:
mid = (low + high) // 2
# Проверяем средний элемент
if arr[mid] == target:
return mid
# Если искомый элемент меньше среднего, ищем в левой половине
elif arr[mid] > target:
high = mid – 1
# Если искомый элемент больше среднего, ищем в правой половине
else:
low = mid + 1

# Элемент не найден
return -1

# Пример использования
sorted_list = [11, 12, 22, 25, 34, 64, 90]
position = binary_search(sorted_list, 25)
print(position) # 3 (индексация с 0)

class Stack:
def __init__(self):
self.items = []

def push(self, item):
self.items.append(item)

def pop(self):
if not self.is_empty():
return self.items.pop()
return None

def peek(self):
if not self.is_empty():
return self.items[-1]
return None

def is_empty(self):
return len(self.items) == 0

def size(self):
return len(self.items)

# Пример использования
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) # 3
print(stack.peek()) # 2
print(stack.size()) # 2

from collections import deque

class Queue:
def __init__(self):
self.items = deque()

def enqueue(self, item):
self.items.append(item)

def dequeue(self):
if not self.is_empty():
return self.items.popleft()
return None

def peek(self):
if not self.is_empty():
return self.items[0]
return None

def is_empty(self):
return len(self.items) == 0

def size(self):
return len(self.items)

# Пример использования
queue = Queue()
queue.enqueue("A")
queue.enqueue("B")
queue.enqueue("C")
print(queue.dequeue()) # A
print(queue.peek()) # B
print(queue.size()) # 2

class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None

class BinarySearchTree:
def __init__(self):
self.root = None

def insert(self, key):
if not self.root:
self.root = TreeNode(key)
else:
self._insert_recursive(self.root, key)

def _insert_recursive(self, node, key):
if key < node.key:
if node.left is None:
node.left = TreeNode(key)
else:
self._insert_recursive(node.left, key)
else:
if node.right is None:
node.right = TreeNode(key)
else:
self._insert_recursive(node.right, key)

def search(self, key):
return self._search_recursive(self.root, key)

def _search_recursive(self, node, key):
if node is None or node.key == key:
return node
if key < node.key:
return self._search_recursive(node.left, key)
return self._search_recursive(node.right, key)

def inorder_traversal(self):
result = []
self._inorder_recursive(self.root, result)
return result

def _inorder_recursive(self, node, result):
if node:
self._inorder_recursive(node.left, result)
result.append(node.key)
self._inorder_recursive(node.right, result)

# Пример использования
bst = BinarySearchTree()
keys = [50, 30, 70, 20, 40, 60, 80]

for key in keys:
bst.insert(key)

print(bst.inorder_traversal()) # [20, 30, 40, 50, 60, 70, 80]
print(bst.search(40).key) # 40
print(bst.search(90)) # None

class Graph:
def __init__(self):
self.graph = {}

def add_vertex(self, vertex):
if vertex not in self.graph:
self.graph[vertex] = []

def add_edge(self, vertex1, vertex2):
if vertex1 in self.graph:
if vertex2 not in self.graph[vertex1]:
self.graph[vertex1].append(vertex2)
else:
self.graph[vertex1] = [vertex2]

# Для неориентированного графа:
if vertex2 in self.graph:
if vertex1 not in self.graph[vertex2]:
self.graph[vertex2].append(vertex1)
else:
self.graph[vertex2] = [vertex1]

def get_vertices(self):
return list(self.graph.keys())

def get_edges(self):
edges = []
for vertex in self.graph:
for neighbor in self.graph[vertex]:
if {neighbor, vertex} not in edges:
edges.append({vertex, neighbor})
return edges

def __str__(self):
return str(self.graph)

# Пример использования
g = Graph()
g.add_vertex("A")
g.add_vertex("B")
g.add_vertex("C")
g.add_edge("A", "B")
g.add_edge("B", "C")
print(g) # {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}

from collections import deque

def bfs(graph, start_vertex):
visited = set()
queue = deque([start_vertex])
visited.add(start_vertex)

while queue:
vertex = queue.popleft()
print(vertex, end=" ") # Обрабатываем вершину

# Посещаем всех не посещенных соседей
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

# Пример использования
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}

print("BFS starting from vertex A:")
bfs(graph, 'A') # Вывод: A B C D E F

def dfs(graph, start_vertex, visited=None):
if visited is None:
visited = set()

visited.add(start_vertex)
print(start_vertex, end=" ") # Обрабатываем вершину

# Рекурсивно посещаем всех не посещенных соседей
for neighbor in graph[start_vertex]:
if neighbor not in visited:
dfs(graph, neighbor, visited)

# Пример использования
print("\nDFS starting from vertex A:")
dfs(graph, 'A') # Вывод: A B D E F C

import heapq

def dijkstra(graph, start_vertex):
# Инициализация расстояний
distances = {vertex: float('infinity') for vertex in graph}
distances[start_vertex] = 0

# Приоритетная очередь для выбора вершины с минимальным расстоянием
priority_queue = [(0, start_vertex)]

while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)

# Если текущее расстояние больше уже найденного, пропускаем
if current_distance > distances[current_vertex]:
continue

# Проверяем всех соседей текущей вершины
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight

# Если найден более короткий путь, обновляем расстояние
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))

return distances

# Пример использования
weighted_graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'D': 2, 'E': 7},
'C': {'A': 4, 'F': 5},
'D': {'B': 2},
'E': {'B': 7, 'F': 1},
'F': {'C': 5, 'E': 1}
}

distances = dijkstra(weighted_graph, 'A')
print("\nShortest distances from A:")
for vertex, distance in distances.items():
print(f"A -> {vertex}: {distance}")

def prim(graph):
# Выбираем произвольную начальную вершину
start_vertex = list(graph.keys())[0]

# Множество вершин, уже включенных в MST
mst_vertices = {start_vertex}

# Список рёбер в MST
mst_edges = []

# Продолжаем, пока не включим все вершины
while len(mst_vertices) != len(graph):
min_edge = None

# Находим ребро с минимальным весом, соединяющее вершину из MST и вершину вне MST
for vertex in mst_vertices:
for neighbor, weight in graph[vertex].items():
if neighbor not in mst_vertices:
if min_edge is None or weight < graph[min_edge[0]][min_edge[1]]:
min_edge = (vertex, neighbor)

if min_edge:
u, v = min_edge
mst_edges.append((u, v, graph[u][v]))
mst_vertices.add(v)

return mst_edges

# Пример использования
mst = prim(weighted_graph)
print("\nMinimum Spanning Tree edges:")
for edge in mst:
u, v, weight = edge
print(f"{u} -- {v}: {weight}")

def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# Пример использования
print(fibonacci_recursive(10)) # 55

def fibonacci_dp(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_dp(n-1, memo) + fibonacci_dp(n-2, memo)
return memo[n]

# Пример использования
print(fibonacci_dp(10)) # 55
print(fibonacci_dp(100)) # 354224848179261915075 (невозможно вычислить за разумное время с наивным подходом)

def fibonacci_iterative(n):
if n <= 1:
return n

a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b

return b

# Пример использования
print(fibonacci_iterative(10)) # 55
print(fibonacci_iterative(100)) # 354224848179261915075

def knapsack(weights, values, capacity):
n = len(values)
# Создаем таблицу для хранения решений подзадач
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

# Заполняем таблицу dp
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
# Если текущий предмет можно положить, выбираем максимум:
# либо положить его, либо оставить как есть
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
else:
# Если текущий предмет нельзя положить, оставляем как есть
dp[i][w] = dp[i-1][w]

# Восстанавливаем решение (какие предметы взяли)
result = []
w = capacity
for i in range(n, 0, -1):
if dp[i][w] != dp[i-1][w]:
result.append(i-1)
w -= weights[i-1]

return dp[n][capacity], result

# Пример использования
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50

max_value, selected_items = knapsack(weights, values, capacity)
print(f"Максимальная ценность: {max_value}")
print(f"Выбранные предметы (индексы): {selected_items}")

def longest_common_subsequence(X, Y):
m, n = len(X), len(Y)
# Создаем таблицу для хранения решений подзадач
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

# Заполняем таблицу dp
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i-1] == Y[j-1]:
# Если текущие символы совпадают, увеличиваем длину LCS
dp[i][j] = dp[i-1][j-1] + 1
else:
# Иначе берем максимум из двух предыдущих подзадач
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

# Восстанавливаем LCS
i, j = m, n
lcs = []
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs.append(X[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1

return dp[m][n], ''.join(reversed(lcs))

# Пример использования
X = "ABCDGH"
Y = "AEDFHR"
length, sequence = longest_common_subsequence(X, Y)
print(f"Длина LCS: {length}")
print(f"LCS: {sequence}")

def grid_paths(m, n):
# Создаем таблицу для хранения решений подзадач
dp = [[0 for _ in range(n)] for _ in range(m)]

# Базовые случаи: путь в первую строку или первый столбец
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1

# Заполняем таблицу dp
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]

return dp[m-1][n-1]

# Пример использования
m, n = 3, 3
print(f"Количество путей в сетке {m}x{n}: {grid_paths(m, n)}")

import cProfile
import pstats

def algorithm_to_optimize(n):
# Ваш алгоритм здесь
result = 0
for i in range(n):
for j in range(n):
result += i * j
return result

# Профилирование
cProfile.run('algorithm_to_optimize(1000)', 'profile_stats')

# Анализ результатов
p = pstats.Stats('profile_stats')
p.sort_stats('cumulative').print_stats(10)

# Неэффективно для больших n
def sum_squares_list(n):
squares = [i**2 for i in range(n)]
return sum(squares)

# Более эффективно
def sum_squares_generator(n):
return sum(i**2 for i in range(n))

# Еще эффективнее
def sum_squares_formula(n):
# Используем математическую формулу: sum(i²) = n(n+1)(2n+1)/6
return n * (n + 1) * (2 * n + 1) // 6

print(sum_squares_list(10000))
print(sum_squares_generator(10000))
print(sum_squares_formula(10000))

import numpy as np
import time

# Вычисление произведения матриц с использованием циклов
def matrix_multiply_loops(A, B):
n = len(A)
C = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j] += A[i][k] * B[k][j]
return C

# Вычисление произведения матриц с использованием NumPy
def matrix_multiply_numpy(A, B):
return np.dot(np.array(A), np.array(B))

# Генерация случайных матриц
n = 100
A = [[random.random() for _ in range(n)] for _ in range(n)]
B = [[random.random() for _ in range(n)] for _ in range(n)]

# Сравнение времени выполнения
start = time.time()
C1 = matrix_multiply_loops(A, B)
end = time.time()
print(f"Время циклов: {end – start} секунд")

start = time.time()
C2 = matrix_multiply_numpy(A, B)
end = time.time()
print(f"Время NumPy: {end – start} секунд")

from functools import lru_cache

# Неэффективная рекурсивная функция
def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# Оптимизированная с помощью кеширования
@lru_cache(maxsize=None)
def fibonacci_cached(n):
if n <= 1:
return n
return fibonacci_cached(n-1) + fibonacci_cached(n-2)

import time

# Сравнение времени выполнения
n = 35
start = time.time()
result1 = fibonacci_recursive(n)
end = time.time()
print(f"Время без кеширования: {end – start} секунд")

start = time.time()
result2 = fibonacci_cached(n)
end = time.time()
print(f"Время с кешированием: {end – start} секунд")

import concurrent.futures
import math

def is_prime(n):
if n < 2:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True

def count_primes_sequential(limit):
count = 0
for i in range(2, limit):
if is_prime(i):
count += 1
return count

def count_primes_parallel(limit, workers=4):
chunks = [range(2 + i, limit, workers) for i in range(workers)]

count = 0
with concurrent.futures.ProcessPoolExecutor() as executor:
futures = [executor.submit(lambda chunk: sum(1 for n in chunk if is_prime(n)), chunk) for chunk in chunks]
for future in concurrent.futures.as_completed(futures):
count += future.result()

return count

# Сравнение времени выполнения
limit = 100000
start = time.time()
count1 = count_primes_sequential(limit)
end = time.time()
print(f"Последовательное время: {end – start} секунд, найдено {count1} простых чисел")

start = time.time()
count2 = count_primes_parallel(limit)
end = time.time()
print(f"Параллельное время: {end – start} секунд, найдено {count2} простых чисел")

# Неэффективный способ проверки, есть ли дубликаты в списке
def has_duplicates_naive(arr):
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
if arr[i] == arr[j]:
return True
return False

# Эффективный способ с использованием множества
def has_duplicates_efficient(arr):
seen = set()
for item in arr:
if item in seen:
return True
seen.add(item)
return False

# Пример использования
import random
import time

# Генерация большого списка с одним дубликатом
n = 10000
arr = list(range(n))
arr.append(random.randint(0, n-1))
random.shuffle(arr)

# Сравнение времени выполнения
start = time.time()
result1 = has_duplicates_naive(arr)
end = time.time()
print(f"Наивное время: {end – start} секунд")

start = time.time()
result2 = has_duplicates_efficient(arr)
end = time.time()
print(f"Эффективное время: {end – start} секунд")

# Пример: вычисление всех пар с заданной суммой в массиве

# Решение O(n²) без дополнительной памяти
def find_pairs_naive(arr, target_sum):
n = len(arr)
pairs = []
for i in range(n):
for j in range(i + 1, n):
if arr[i] + arr[j] == target_sum:
pairs.append((arr[i], arr[j]))
return pairs

# Решение O(n) с использованием дополнительной памяти
def find_pairs_efficient(arr, target_sum):
seen = set()
pairs = []
for num in arr:
complement = target_sum – num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs

# Пример использования
arr = [1, 5, 7, 9, 2, 3, 8, 4, 6]
target_sum = 10

print(find_pairs_naive(arr, target_sum))
print(find_pairs_efficient(arr, target_sum))