Основные структуры данных

Оперативная память и представление данных

Эффективность программы можно оценить по тому, как она расходует разные типы ресурсов компьютера. Основные из них — процессорное время и оперативная память. А ещё есть пропускная способность сетевых подключений, время работы жёсткого диска и некоторые другие ограниченные ресурсы.

На первом уроке мы говорили о том, как алгоритм использует процессорное время. Теперь нас будет интересовать потребление оперативной памяти — это называется пространственной сложностью алгоритма.

Как устроена оперативная память

Оперативная память, или ОЗУ — это своего рода «черновик», который программа использует для вычислений. В него можно записывать и перезаписывать информацию, и оттуда же её можно считывать.

Современные компьютеры располагают всего несколькими гигабайтами оперативной памяти, и данные исчезают из неё сразу после завершения работы программы. Поэтому эта память не подходит для длительного хранения информации, зато она работает в сотни раз быстрее SSD и во многие тысячи раз быстрее обыкновенного жёсткого диска.

Оперативная память разбита на ячейки размером в 1 байт. У каждой ячейки есть свой порядковый номер, который называется «адрес» (отдельные биты внутри ячейки адресов не имеют). Процессор взаимодействует с оперативной памятью напрямую и использует адреса, чтобы обращаться к данным, — почти как программа обращается к переменным по имени.

Чтобы понять, сколько памяти потребляет программа, нужно выяснить, сколько места занимают отдельные объекты. В разных языках программирования этот объём памяти может отличаться, но основные принципы будут общими. Для начала мы разберём, как используется память в языке C++, так как он позволяет сделать это очень эффективно, гибко и предсказуемо.

Представление базовых типов данных в ОП

Что можно записать в одну ячейку памяти? Как мы уже говорили, размер наименьшей ячейки — 1 байт, состоящий из 8 бит. Каждый бит может принимать одно из двух значений: либо 0, либо 1. Восемь бит позволяют закодировать всего $2^8=2562$ вариантов значений. Получается, что в такую ячейку можно записать, например, целое число в промежутке от 0 до 255.

Если считать эти числа номерами символов, то в 1 байт можно уместить 1 символ текста (тип char): все буквы латиницы и кириллицы, цифры и основные символы вполне умещаются в 256 вариантов.

Самый распространённый тип целых чисел int занимает 4 байта и позволяет закодировать числа от –2 147 483 648 до 2 147 483 647.

Эти границы можно вычислить: в 4 байтах содержится 32 бита. Один бит тратится на то, чтобы закодировать знак. Оставшийся 31 бит позволяет закодировать $2^{31} =2;147;483;6482$ чисел. Число «ноль» тоже нужно закодировать, поэтому положительных чисел остаётся на одно меньше, чем отрицательных.

Если ваши числа не превышают по модулю два миллиарда, можно пользоваться этим типом чисел. Обратите внимание, что всего чисел около четырёх миллиардов, но половина из них отрицательные. Если точно известно, что переменная не может быть отрицательной, можно воспользоваться типом беззнаковых целых unsigned int, он позволяет хранить числа от 0 до 4 294 967 295.

Вещественные (то есть дробные) числа чаще всего кодируются типом double — это «числа с плавающей точкой», которые занимают 8 байт. Они могут кодировать как очень большие числа, такие как $\pm10^{308}$, так и близкие к нулю, например $\pm10^{-308}$.

Составные типы данных

Теперь посчитаем, сколько памяти потребуется для хранения массива из 10 строк по 20 символов каждая.

Во-первых, потребуется хранить сам текст. Это займёт $$10; строк \cdot (20; \frac{символов}{строка}) \cdot (1;\frac{байт}{символ}) = 200; байт$$ Этого было бы достаточно, если бы строки располагались в памяти друг за другом. Но производить с ними какие-либо операции будет сложно.

Поэтому в массивы (и в другие составные структуры) зачастую помещаются не сами объекты, а только указатели на них — адреса, по которым они хранятся в ячейках оперативной памяти.

Во многих других языках каждый объект в программе записан в специальную «обёртку», которая, помимо данных, содержит вспомогательную информацию. Из-за этого, например, в языке Python даже короткие целые числа могут занимать не 4 байта, а почти 30 байт. Для хранения строки требуется около 40 байт вспомогательной информации, для хранения массива — ещё больше. Обычно объекты в таких языках ведут себя подобно строкам из предыдущего примера: они могут находиться в произвольном месте памяти, и любое обращение к ним происходит по сохранённому адресу.

Посчитаем, например, сколько памяти расходует массив из 10 чисел в Python и на что она уходит:

import sys
print(sys.getsizeof(42))  # => 28 байт занимает короткое целое число
print(sys.getsizeof([]))  # => 56 байт занимает пустой массив
print(sys.getsizeof([42]))  # => 64 = (56 + 8) байт занимает массив с одним элементом.
print(sys.getsizeof([1,2,3,5,6,7,8,9,10]))  # => 136 = (56 + 8*10) байт занимает массив
                               # с десятью элементами.
                               # сами данные хранятся отдельно
                               # и добавляют 280 = (28 * 10) байт

Получается, мы тратим 56 байт на то, чтобы создать массив, а дальше по 8 байт на каждый новый объект в массиве — это адреса элементов. Но это ещё не всё. Ведь каждому числу нужно ещё по 28 байт. Итого массив из десяти чисел в Python занимает суммарно 56 + (8 + 28) * 10 байт = 416 байт. Сравните это с 40 байтами в языке C++.

Как освобождается память

Важно понимать, что если вы перестали пользоваться объектом, это ещё не значит, что он освободил занимаемую память. В языке C++ приходится следить за тем, чтобы выделенная память освобождалась. Встроенные контейнеры, такие как std::vector, упрощают задачу: они автоматически выделяют необходимую память при создании контейнера и освобождают её при выходе переменной контейнера из области видимости.

В большинстве других языков за освобождение памяти отвечает сборщик мусора, который время от времени проверяет, может ли объект ещё быть использован. Если оказывается, что на него больше не ссылается никакая переменная и никакой другой объект, то этот объект уничтожается.

Но сборка мусора — трудоёмкая операция, поэтому некоторые языки откладывают её до тех пор, пока свободное пространство не подойдёт к концу. Например, программы на Java (если их специально не ограничить при запуске) часто сталкиваются с проблемой высокого потребления памяти из-за хранения множества старых и уже неиспользуемых объектов.

Массивы постоянного размера

В предыдущих уроках мы говорили о том, как простые и составные типы данных могут храниться в оперативной памяти компьютера. Начиная с этого урока мы будем говорить о различных структурах данных. Структура данных — это способ организации информации в памяти, который позволяет проводить с ней определённый набор операций. Например, быстро искать или изменять данные.

Массив — одна из базовых структур данных. В этом уроке мы посмотрим, какие возможности бывают у разных типов массивов и как они могут быть реализованы.

Самый простой тип массивов имеет фиксированный размер и может хранить элементы одного и того же типа. Например, если мы создадим массив из десяти целых чисел, в него нельзя будет добавить ещё один элемент или записать объект неподходящего типа. Такие массивы вы можете встретить, например, в языке C — int numbers[10], или в С++ — std::array<int, 10> numbers.

С массивами фиксированного размера можно выполнить только две операции:

• узнать значение элемента по индексу,
• перезаписать значение по индексу.

Да, они не слишком функциональные, но зато очень эффективные. Каждая из операций выполняется за $O(1)$. Чтобы понять, как массиву удаётся настолько быстро находить нужный элемент, — разберёмся в его механике работы и посмотрим, как он хранит данные.

Как устроен массив

Массив — это набор однотипных данных, расположенных в памяти друг за другом. Поэтому он всегда занимает один непрерывный участок памяти. Точное местоположение этого участка операционная система сообщает программе в момент создания массива.

В начале выделенного участка памяти находится нулевой элемент, сразу за ним — первый и далее по порядку. Они идут друг за другом, без пропусков. Зная положение элемента в памяти — его адрес, мы можем этот элемент прочитать или записать. Теперь посмотрим, как узнать адрес элемента.

Пусть у нас есть массив numbers из 10 беззнаковых целых чисел. Адрес нулевого элемента нам известен — это 1000. Чтобы узнать положение следующего элемента, нам нужно прибавить к адресу начала размер элемента в байтах. Каждое число занимает по 4 байта, так что первый (нулевой) элемент займёт байты 1000, 1001, 1002, 1003. Значит, элемент с индексом 1 будет записан по адресу 1004.

Сложность вставки и удаления в динамических массивах

В прошлом уроке мы говорили о том, что такое массив и как он устроен. Теперь настало время познакомить вас с динамическими массивами. Иногда их ещё называют «векторами», потому что в C++ они реализуются классом std::vector. В Python динамические массивы реализуются классом list, но пусть вас не обманывает название — это не список, а именно массив.

Сложность вставки в динамический массив

Бывают ситуации, когда невозможно сказать точно, какая длина массива может понадобиться. Поэтому так важно иметь возможность добавлять элементы в массив прямо во время выполнения программы.

Нужно вставить элемент в произвольное место массива? Конечно, вставка в начало и в конец — частные случаи этой задачи. Вставка элемента в начало — худший случай. Сложность этой операции $O(n)$. Добавление элемента в конец — лучший случай. И его сложность $O(1)$.

Сложность удаления из динамического массива

При удалении, как и при вставке в массив, требуется сдвинуть все элементы правее ячейки, в которой происходит операция. При добавлении в массив элементы сдвигаются на один вправо. А при удалении — на один влево.

Реаллокация в динамических массивах

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

Поэтому, как правило, при расширении массива программе приходится произвести «реаллокацию» — выделить новый участок памяти и скопировать туда старое содержимое.

Выделение памяти — долгая операция, но копирование — это ещё большая проблема, ведь оно требует прохода по всем элементам, затратив $O(n)$ операций. Как же мы тогда можем утверждать, что добавление в конец массива стоит $O(1)$?

Напишем программу, которая добавляет в массив тысячу элементов — по одному за раз:

values = []
for i in range(1000):
    values.append(i)

Операция append() может быть представлена как две операции: реаллокация и присваивание значения элементу массива. Для простоты мы не будем учитывать операции присваивания. Их число равно количеству добавляемых элементов; эта часть оптимизации не требует (и не может быть оптимизирована). А вот время, затрачиваемое на реаллокации, может существенно отличаться — в зависимости от выбранного подхода.

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

Во-первых, чтобы не приходилось на каждом шаге выделять дополнительную память, нужно держать запас свободного места в массиве. Например, если мы решим увеличить размер доступного массиву места сразу на 100 элементов, программа будет выделять память в 100 раз реже. Но программа всё ещё будет работать за $O(n^2)$, хотя и с небольшой константой при квадратичном члене.

Теперь у нас есть два разных размера массива: size (количество элементов) и capacity (ёмкость), причём size ≤ capacity.

Во-вторых, чтобы сделать сложность алгоритма линейной, нужно увеличивать размер не на фиксированное количество элементов (арифметическая прогрессия), а в фиксированное число раз (геометрическая прогрессия).

Пусть изначальная ёмкость массива равна 1, а при каждой реаллокации она удваивается. Тогда на первой реаллокации копируется 1 элемент, на второй — 2, на третьей — 4, затем — 8, 16, 32, 64, 128, 256, 512. После этих действий ёмкость массива равна 1024.

Посчитаем, сколько операций копирования нам нужно будет произвести к моменту добавления 1000-го элемента. Общее число копирований: $S = 1 + 2 + 4 + \cdots + 512 = 1024 - 1$.

В общем случае, если нужно добавить $n$ элементов (где $2^k \lt n \le 2^{k+1}$, последнее копирование затронет $2^k$ элементов. Напишем сумму такой геометрической прогрессии: $S = \sum_{i=0}^k 2^i = 2^{k+1} - 1 = 2 \cdot 2^k - 1 \le 2\cdot n$.

Итак, у нас получилось добиться того, что общее количество копирований при реаллокации будет линейно зависеть от числа элементов.

Связные списки

Как вы помните, элементы массива в памяти компьютера расположены последовательно. Чтобы вставить или удалить элемент из начала массива, нужно $O(n)$ операций. Потому что придётся передвинуть каждый последующий элемент.

Хорошо бы иметь структуру данных, в которой при вставке или удалении элемента передвигать остальные было бы не нужно. Такая структура существует. Она называется «связный список» (англ. linked list). Во многих языках программирования реализована в стандартных типах, например, std::list в C++, LinkedList в Java.

Важно помнить, что в языке Python list — это динамический массив, хотя и обозначен словом «список».

Как устроен связный список

В связном списке у каждого элемента, помимо его значения, есть ссылка на следующий элемент списка. За исключением последнего — он ссылается в никуда. В зависимости от языка программирования ссылка в никуда может представлять собой объект None, нулевой указатель или аналогичную сущность. Кроме того, у связного списка принято определять точку старта — её называют «головой списка».

Достоинства и недостатки связного списка

Их элементы расположены в памяти компьютера в произвольных местах, а не по порядку, как в массиве. Это бывает очень удобно, если элементов много и расположить их единым блоком не представляется возможным.

Недостаток в том, что нельзя получить доступ к элементу за $O(1)$ по индексу, так как элементы хранятся в памяти непоследовательно. Для этого нужно пройти по всем элементам, начиная с головы списка, пока не дойдём до нужного. Это займёт $O(n)$ операций.

Двигаться по односвязному списку можно только в одном направлении. Из этого недостатка следует ещё один: мы не можем быстро удалить элемент, так как не знаем, какой элемент на него ссылается. В худшем случае потребуется $O(n)$ операций для поиска предыдущего. А вот вставить элемент после текущего мы можем быстро.

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

Структура данных стек часто встречается в программировании и во многих вещах, связанных с компьютерами. Стек работает по принципу LIFO.

Вы наверняка пользуетесь возможностью браузеров, реализованной с применением стека. Речь идёт о кнопке «назад». Нажмёте на неё один раз — вернётесь на предыдущую страницу, нажмёте снова — попадёте на страницу, где были до неё.

Во многих текстовых редакторах можно отменять последние операции. Эта функция тоже реализована при помощи стека.

Чтобы лучше понять, как устроен стек, представьте себе стопку книг в коробке. Если вам захочется почитать, вы сможете взять только верхнюю книгу. А если она окажется неинтересной, что ж, можно будет отбросить её и попытать удачу, взяв ещё одну книгу сверху, и так далее. Из стека также можно взять только верхний — последний, положенный в стек, — элемент.

Интерфейс стека

В отличие от массивов и связных списков, стек — это прежде всего удобный интерфейс для взаимодействия с данными, а не физическая особенность их хранения. Когда мы говорим про стек, мы подразумеваем структуру данных, которая реализует следующие методы:

• push(item) — добавляет элемент на вершину стека;
• pop() — возвращает элемент с вершины стека и удаляет его;
• size() — возвращает размер стека (количество лежащих в нём элементов).

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

• peek() или top() — возвращает элемент с вершины стека, не удаляя его;
• isEmpty() — определяет, пуст ли стек.

В большинстве случаев стек удобно реализовывать на массиве. Но бывают ситуации, когда стек должен хранить очень много элементов, а выделить единый блок памяти для этого невозможно. Тогда для реализации лучше воспользоваться связным списком.

Реализация стека

Посмотрите, как реализуется стек на основе массива. В конструкторе для экземпляра класса создаётся пустой массив. Далее при вызове методов push() и pop() этот массив будет меняться:

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

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

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[-1]

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

stack = Stack()
stack.push('apple')
stack.push('banana')
stack.push('orange')

stack.pop()

Структуры данных: очередь и дек

В прошлом уроке вы познакомились со стеком и узнали, как он устроен. Ещё одна важная структура данных — «очередь». В отличие от стека, который работает по принципу LIFO, очередь основана на концепции FIFO. То есть первым извлекают элемент, который добавили раньше всех.

В повседневной жизни мы все сталкиваемся с очередями:

• Кассир в магазине обслуживает покупателей по одному: пока кто-то оплачивает свои продукты, остальным приходится стоять в очереди и ждать. И, конечно, вас обслужат не раньше, чем всех тех людей, которые встали в очередь до вашего прихода.
• Если мы звоним на горячую линию и все операторы заняты, нам тоже приходится ждать в очереди.

Подобные сценарии часто встречаются и в мире компьютеров. При их моделировании удобно применять структуру данных очередь.

Интерфейс очереди

Как и стек, очередь — интерфейс общения с данными. Он гарантирует наличие определённых методов, но не даёт никаких обещаний по способу хранения этих данных. То есть «под капотом» может находиться всё что угодно. При том, что интерфейс не накладывает ограничений на внутреннее устройство, очередь принято реализовывать таким образом, чтобы операции вставки и удаления элемента выполнялись за $O(1)$.

Когда мы говорим про очередь, мы ожидаем, что у структуры будут следующие методы:

• push(item) — добавляет элемент в конец очереди;
• pop() — берёт элемент из начала очереди и удаляет его;
• peek() — берёт элемент из начала очереди без удаления;
• size() — возвращает количество элементов в очереди.

Стек вызовов

Код любой сложной программы разделён на множество функций. Поэтому работа всей системы описывается как взаимодействие небольших блоков кода. Базовые функции объединяются в сложные, а те — в ещё более сложные. В результате вся программа может быть представлена как одна сложносоставная функция, которая вызывает множество простых.

Как устроен стек вызовов

Допустим, мы написали программу на С++. Первой вызывается функция main(). В ней вызывается функция A. Она вызывает функцию B, которая, в свою очередь, вызывает C.

Так выглядит стек вызовов этой программы:

После возврата из функции управление должно вернуться туда, откуда эту функцию вызвали. Для этого при вызове функции в стеке вызовов сохраняется адрес той инструкции программы, которая будет выполнена после возврата из функции.

Для примера рассмотрим функцию, которая приветствует пользователя по имени и выдаёт ему гороскоп на сегодняшний день. Для простоты предположим, что пользователь пришёл на сайт, где всем выдают один и тот же гороскоп.

def say_hello(name):
    print(f"Привет, {name}")
    print_horoscope(name.upper())
    print(f"Пока, {name}, хорошего дня!")

def print_horoscope(name):
    print(f"{name}! Сегодня подходящий день для прогулок в парке и изучения рекурсии")

say_hello('Гоша')

Обратите внимание, что в разных частях программы переменная name может хранить разные значения. Например, при входе в функцию say_hello() в переменной name будет записано 'Гоша'. А если мы вызовем print_horoscope(), там появится 'ГОША'. Но, когда мы перейдём обратно в say_hello(), значение вновь вернётся к первоначальному 'Гоша'.

Чтобы добиться такого поведения, программа хранит все локальные переменные на том же стеке. Можно представить это так: на вершине стека находится структура, в которой записаны локальные переменные и аргументы функции, а также адрес возврата. Проследим, как меняется содержимое стека в нашем примере.

Работа стека: шаг за шагом

Первая команда, которая будет выполнена при старте программы, — вызов функции say_hello(). Под этот вызов на стеке выделяется блок памяти.

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

Также в стек помещаются переданные в функцию аргументы. С этих параметров начинается формирование набора локальных переменных функции. В нашем случае есть один аргумент name = 'Гоша', а другие локальные переменные отсутствуют.

Затем выполняется первая инструкция в функции say_hello(), которая выводит сообщение: «Привет, Гоша». Далее происходит вызов метода upper(), который вернёт вызвавшей его функции строку 'ГОША', написанную большими буквами. Эта строка станет параметром функции print_horoscope().

Вызовы функции print() и метода upper() мы для краткости на картинке не показываем, хотя они, конечно же, тоже кладутся на стек при вызове и снимаются с него после завершения выполнения.

Когда вызывается функция print_horoscope() с параметром 'ГОША', под этот вызов выделяется новый блок памяти, куда записываются значения переданных функции параметров и новый адрес возврата, а также выделяется место для других локальных переменных. Блок памяти для функции print_horoscope() помещается поверх блока, отведённого под say_hello(). Помните стопку книг в коробке, о которой мы говорили пару уроков назад? Вот она, перед вами! Только вместо книг — блоки памяти.

Затем исполнится первая инструкция в функции print_horoscope(). Выведется сообщение: «ГОША! Сегодня подходящий день для прогулок в парке и изучения рекурсии!».

В print_horoscope() больше нет инструкций. Настал момент возвращения управления. В блоке памяти функции print_horoscope(), лежащем на стеке, записан адрес возврата, поэтому программе известно, какая инструкция должна исполниться следующей. Блок, отведённый под print_horoscope(), больше не нужен, и теперь извлекается из стека. Значение переменной name восстанавливается.

Затем исполняется инструкция из say_hello(), следующая за вызовом функции print_horoscope(). Эта инструкция — вывод сообщения: «Пока, Гоша, хорошего дня!»

Так как это последняя из инструкций в say_hello(), происходит возврат из функции. Блок памяти, выделенный под неё, освобождается.

Теперь вы знаете, как интерпретатор (или компилятор) языка программирования вызывает функции.

Рекурсия. Переполнение стека вызовов

В этом уроке мы поговорим о функциях, которые вызывают сами себя, но с изменёнными значениями аргументов. Такие функции называются «рекурсивными». И они тоже используют стек вызовов.

Факториал

Посмотрим на примере, в каких случаях могут понадобиться такие функции.

Факториал натурального числа можно вычислить как произведение всех натуральных чисел от 1 до n: $n! = 1 \cdot 2 \cdot ... \cdot (n-1) \cdot n$

Рекурсия и стек вызовов

Теперь напишем код рекурсивной функции вычисления факториала:

def factorial(n):
    if n == 1 or n == 0:
        return 1
    return n * factorial(n - 1)

Проанализируем, что происходит при вызове функции factorial(3).

При каждом вызове функции на стеке создаётся новый набор локальных переменных. Таким образом, переменная n в каждом вызове оказывается новая. Благодаря этому переменные с одним и тем же именем даже в одной и той же функции не конфликтуют между собой. Невозможно обратиться к переменной n, которая относится к другому уровню рекурсии. Ни узнать, ни поменять её значение не получится.

Однако, чтобы хранить локальные переменные и адрес возврата на каждом уровне рекурсии, потребуется $O(d)$ памяти на стеке, где d — глубина рекурсии. При вычислении факториала $n!$ глубина рекурсии равна n, поэтому этот метод расходует $O(n)$ памяти на стеке.

А что будет, если эта память закончится, а рекурсивные вызовы продолжатся?

Стек вызовов переполнится и программа аварийно завершит работу.

Объём памяти, выделяемой под стек, ограничен очень небольшим объёмом — гораздо меньшим, чем общий объём оперативной памяти. Рекурсию нельзя делать больше, чем на несколько десятков тысяч вызовов в глубину, потому что при использовании слишком глубокой рекурсии стек переполнится (англ. stack overflow) и программа завершит работу аварийно с ошибкой. Программы на одних языках при этом выдадут исключение “Stack Overflow”, другие же завершатся с ошибкой “Segmentation Fault”.

factorial(10_000)

Что делать, чтобы стек не переполнялся

Есть несколько способов избежать переполнения стека:

• В некоторых случаях можно вовсе избавиться от рекурсии, заменив её на обыкновенный цикл. Например, вычисление факториала легко переписать следующим образом:

def factorial(n):
    accumulator = 1
    i = n
    while i > 1:
        accumulator *= i
        i -= 1
    return accumulator

• Другой способ заключается в том, чтобы написать свой собственный стек, эмулирующий стек вызовов, но лишённый ограничений встроенного.

Объёмом памяти, который выделяется под стек вызовов, можно управлять. В некоторых языках это можно делать прямо в процессе работы программы. Например, в Python можно применить метод setrecursionlimit() модуля sys. Передаваемый в функцию параметр limit — задаёт максимальную глубину рекурсии. Наибольшее возможное значение зависит от платформы и всё равно существенно ограничено. Можно узнать текущее значение этой величины, вызвав метод getrecursionlimit(). В других языках программирования, таких как Java и JavaScript, размер стека вызовов можно задать настройками виртуальной машины при запуске программы, но в процессе работы программы он остаётся неизменным. Кроме того, размер стека вызовов иногда может быть изменён на уровне операционной системы.

sys.getrecursionlimit()

Практика

Наивное решение. GET

@app.route('/', methods=['GET'])
def paginated_get():
    page = int(request.args.get('page', '0'))
    first = page * PAGE_SIZE
    last = first + PAGE_SIZE
    result = []
    with open(FILE_PATH, 'r') as f:
        for i, line in enumerate(f.readlines()[first:last]):
            result.append( {'id': first + i, 'data': line.strip()})
    return {"result": result}

Наивное решение. POST

@app.route('/', methods=['POST'])
def post():
    data = request.json['data']
    with open(FILE_PATH, 'a') as f:
        f.write('\n' + data)
    return {}, 201

Наивное решение. PUT

@app.route('/<int:data_id>', methods=['PUT'])
def put(data_id):
    data = request.json['data']
    with open(FILE_PATH, 'r') as f:
        new_data = f.readlines()
        new_data[data_id] = data + '\n'
    with open(FILE_PATH, 'w') as f:
        f.writelines(new_data)
    return {}, 204

Наивное решение. DELETE

@app.route('/<int:data_id>', methods=['DELETE'])
def delete(data_id):
    with open(FILE_PATH, 'r') as f:
        new_data = f.readlines()
    del new_data[data_id]
    with open(FILE_PATH, 'w') as f:
        f.writelines(new_data)
    return {}, 204

Фиксированный. GET

@app.route('/', methods=['GET'])
def paginated_get():
    page = int(request.args.get('page', '0'))
    first = page * PAGE_SIZE
    result = []
    with open(FILE_PATH, 'rb') as f:
        f.seek(first * ELEMENT_SIZE)
        data = f.read(PAGE_SIZE * ELEMENT_SIZE)
        for i, n in enumerate(range(PAGE_SIZE)):
            result.append(
                {
                    "id": first + i,
                    "data": (
                        data[n * ELEMENT_SIZE: (n + 1) * ELEMENT_SIZE].
                        strip(FILL_CHAR).decode('utf-8')
                    )
                }
            )
    return {"result": result}

Фиксированный. POST

def post():
    data = str(request.json['data'])
    with open(FILE_PATH, 'a+b') as f:
        f.write(data.encode('utf-8').ljust(ELEMENT_SIZE, FILL_CHAR))
    return {}, 201

Фиксированный. PUT

@app.route('/<int:data_id>', methods=['PUT'])
def put(data_id):
    data = request.json['data']
    with open(FILE_PATH, 'r+b') as f:
        f.seek(data_id * ELEMENT_SIZE)
        f.write(data.encode('utf-8').ljust(ELEMENT_SIZE, FILL_CHAR))
    return {}, 204

Фиксированный. DELETE

@app.route('/<int:data_id>', methods=['DELETE'])
def delete(data_id):
    with open(FILE_PATH, 'r+b') as f:
    point = data_id * ELEMENT_SIZE
    f.seek(point)
    while True:
        f.seek(point + ELEMENT_SIZE)
        complex_data = f.read(ELEMENT_SIZE)
        f.seek(point)
        if len(complex_data):
            f.write(complex_data)
            point += ELEMENT_SIZE
        else:
            f.truncate()
            break
    return {}, 204

Database. GET

@app.route('/', methods=['GET'])
def paginated_get():
    page = int(request.args.get('page', '0'))
    with closing(psycopg2.connect(dbname=dbname, host=host)) as conn:
        with conn.cursor() as cursor:
            cursor.execute(
                'SELECT "id", "todo" FROM "todos" ORDER BY "id" OFFSET %s LIMIT %s;',
                (page * PAGE_SIZE, (page + 1) * PAGE_SIZE)
            )
            return {
                "result": [ {"id": row[0], "data": row[1]} for row in cursor]
            }

Database. POST

@app.route('/', methods=['POST'])
def post():
    data = str(request.json['data'])
    with closing(psycopg2.connect(dbname=dbname, host=host)) as conn:
        with conn.cursor() as cursor:
            cursor.execute(
                'INSERT INTO "todos" ("todo") VALUES (%s) RETURNING "id";',
                (data,)
            )
            conn.commit()
            return {"id": cursor.fetchone()[0]}, 201

Database. PUT

@app.route('/<int:data_id>', methods=['PUT'])
def put(data_id):
    data = request.json['data']
    with closing(psycopg2.connect(dbname=dbname, host=host)) as conn:
        with conn.cursor() as cursor:
            cursor.execute(
                'UPDATE "todos" SET "todo" = %s WHERE "id" = %s;',
                (data, data_id)
            )
            conn.commit()
            return {}, 204

Database. DELETE

@app.route('/<int:data_id>', methods=['DELETE'])
def delete(data_id):
    with closing(psycopg2.connect(dbname=dbname, host=host)) as conn:
        with conn.cursor() as cursor:
            cursor.execute(
                'DELETE FROM "todos" WHERE "id" = %s;',
                (data_id,)
            )
            conn.commit()
            return {}, 204

Cache. GET

@app.route('/', methods=['GET'])
def paginated_get():
    page = int(request.args.get('page', '0’))
                                
    redis_client = redis.StrictRedis(**redis_creds)
    cached_page = redis_client.get(page)
                                
    if cached_page:
        return cached_page
                                
    with closing(psycopg2.connect(**postgres_creds)) as conn:
        with conn.cursor() as cursor:
            cursor.execute(
                'SELECT "id", "todo" FROM "todos" ORDER BY "id" OFFSET %s LIMIT %s;',
                (page * PAGE_SIZE, (page + 1) * PAGE_SIZE)
            )
            result = json.dumps({
                "result": [{"id": row[0], "data": row[1]} for row in cursor]
            })
            redis_client.set(page, result, ex=ttl)
            return result