Многие программисты могут по памяти реализовать односвязные и двусвязные списки, хэш-таблицы или алгоритм быстрой сортировки. Это классика алгоритмов и структур данных, которая к тому же часто используется на практике. Но если вдруг понадобится написать кучу или реализовать пирамидальную сортировку, то, не знаю как вы, а я по памяти вряд ли смогу это сделать. Давайте же освежим знания в этой области. А чтобы думалось непосредственно об алгоритмах, а не об управлении памятью, писать будем на Python.
Чтобы честно вычислить значение медианы для множества каких-то значений, необходимо взять эти значения, сложить в массив, отсортировать его, после чего взять средний элемент массива. Аналогично вычисляются и прочие процентили. Если значений много, то процесс выходит долгим и/или может не хватить памяти. Поэтому есть интерес к алгоритмам, вычисляющим приблизительные значения процентилей. Рассмотрим некоторые из них.
Большинство программистов не раз сталкивались с задачей, где нужно выбрать случайный элемент из массива. Может потребоваться выбрать не один элемент, а несколько, что не намного сложнее. Но что делать, если вместо массива на входе у нас поток данных неизвестной длины, а то и вовсе бесконечный?
SciPy — это библиотека для языка Python, содержащая различные методы для инженерных и научных расчетов. При помощи SciPy можно считать интегралы, решать задачи оптимизации, обрабатывать изображения, и не только. Особый интерес представляют методы для расчета DSP-фильтров. Давайте разберемся, как ими пользоваться.
При погружении в цифровую обработку сигналов (DSP, digital signal processing) на начинающего разом сваливается изрядное количество информации. По своему опыту могу сказать, что разобраться в ней не так-то просто. Также непросто понять, какая информация является ключевой, а какая — второстепенной, которую при первом прочтении можно и пропустить. Давайте же познакомимся с основными действующими лицами в мире DSP, рассмотрим связи между ними, и попытаемся понять, зачем все это нужно.
Системный каталог, или просто каталог — это таблицы, в которых PostgreSQL хранит информацию обо всех остальных объектах, хранящихся в базе данных. К ним относятся таблицы, функции, триггеры, и т.д. Обращение к системному каталогу происходит часто, поэтому для него предусмотрен кэш. Давайте же разберемся, как этот кэш устроен.
Мне захотелось попробовать разные программы для Микроши. В наши дни они распространяются в виде файлов RKM. Существуют готовые конвертеры из RKM в аудио, но они имеют различные проблемы. Например, WRKWIN32.EXE как будто работает, но мой Микроша отказывается загружать результирующее аудио. То ли не та версия Wine, то ли не та звуковая карта — об истинной причине остается лишь гадать. В общем, долго ли, коротко ли, было решено написать свой конвертер.
Карта свободного пространства, она же free space map или FSM — это структура в PostgreSQL, предназначенная для быстрого поиска страницы c заданным количеством свободного места. Без FSM при записи новых данных СУБД приходилось бы сканировать всю кучу, либо записывать данные в ее конец.
Ранее в постах серии «Внутренности PostgreSQL» несколько раз упоминалось нечто под названием visibility map, или карта видимости (случай один, случай два и далее по ссылкам). Однако не сообщалось, что это за штука такая и почему она важна. Пришло время заполнить данный пробел.
Благодаря посту Внутренности PostgreSQL: ProcArray и CLOG мы узнали, как PostgreSQL определяет состояние транзакции по ее идентификатору, или XID. Однако из статьи Внутренности PostgreSQL: страницы и кортежи мы также помним, что XID является 32-х битным числом. Несложными математическими расчетами несложно понять, что даже при скромных нагрузках (~1000 TPS), уникальные XID’ы могут закончится за несколько месяцев. Давайте разберемся, как PostgreSQL решает эту проблему.
