Всех с наступающим новым годом!

В этот год наш канал вырос в разы, достиг 350+ подписчиков, мы узнали много нового.

В этот день хочется поблагодарить каждого из вас, за участие в нашем канале Дальше - больше!

Желаем вам счастья, радостей, исполнения желаний и планов, чтобы код писался без багов, чтобы девопсы не спали когда падают сервера. А также желаем повышения грейда, улучшения денежного довольствия и личного уровня счастья!

С наступающим новым годом!

Мы вместе спускались в кроличью нору, и каждый раз казалось, что вот оно — дно, но неожиданно со дна стучались. Си — невероятно простой и сложный язык одновременно.

Наши первые 5 статей показали, что математика и низкоуровневые оптимизации могут быть не только полезными, но и по‑настоящему увлекательными.

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


https://habr.com/ru/companies/timeweb/articles/977208/

Хабр лёг! #хабр_не_торт

Полезные алиасы для GIT

Алиасы для git можно делать как стандартным внешним путём через конфиг вашего шелла:

alias gga="git add"
alias ggc="git commit"
alias ggcm="git commit -m"
alias ggs="git status"
alias ggl="git log"
alias gglo="git log --oneline"
alias ggd="git diff"
alias ggds="git diff --staged"
alias ggr="git restore"

Так и через конфигурирование файла ~/.gitconfig:

[alias]
    st = status -b
    c = commit
    co = checkout
    br = branch
    slog = log --pretty=format:"%C(auto)%h%C(auto)%d\\ %C(auto,reset)%s\\ \\ [%C(auto,blue)%an%C(auto,reset),\\ %C(auto,cyan)%ar%C(auto,reset)]"
    glog = log --graph --pretty=format:"%C(auto,yellow)%h%C(auto)%d\\ %C(auto,reset)%s\\ \\ [%C(auto,blue)%an%C(auto,reset),\\ %C(auto,cyan)%ar%C(auto,reset)]"
    wlog = log --pretty=format:"%C(auto,yellow)%h%C(auto)%d%C(auto,reset)\\ by\\ %C(auto,blue)%an%C(auto,reset),\\ %C(auto,cyan)%ar%C(auto,reset)%n\\ %s%n" --stat
    gr = log --graph --abbrev-commit --decorate --format=format:'%C(bold blue)%h%C(reset) - %C(bold green)(%ar)%C(reset) %C(white)%s%C(reset) %C(dim white)- %an%C(reset)%C(bold yellow)%d%C(reset)' --all
    wt = worktree

Я достаточно часто пользуюсь этими алиасами для быстрой работы с репозиториями, получения логов и графов веток и коммитов.

Давайте попробуем импортозаместить стандартный pow нашим алгоритмом, а точнее — бинарным возведением в степень. Сложность — O(log n).

Широко известный алгоритм для возведения любого числа в целую степень с абсолютной точностью. Принцип действия прост: есть целая степень e, чтобы получить число b в этой степени нужно возвести это число во все степени 1, 2, 4, … 2n (в коде этому соответствует b *= b), каждый раз сдвигая биты e вправо (e >>= 1) пока оно не равно 0 и тогда, когда последний бит e не равен нулю ((e & 1) != 0), домножать результат v на полученное b. Этот метод позволяет возвести число в целую степень за логарифмическое время, что особенно важно при работе с большими числами.

Возьмём 2⁵. Вместо 2×2×2×2×2 мы представляем 5 в двоичном виде (101) и идем по битам справа налево. Первый бит (1) равен 2, второй бит (0) равен 2 в квадрате, и в последнем третьем биту (1) результат (2) умножаем на текущее значение (4²=16) → 32.

Технически, при каждом проходе цикла, мы проверяем младший бит степени e. Если этот бит равен 1 (e & 1 != 0), мы умножаем текущий результат v на основание b. После этого мы умножаем b на само себя (квадрат), что соответствует следующей степени двоичного представления. Уменьшая e с помощью побитового сдвига вправо, мы продолжаем цикл, пока e не достигает нуля, в результате чего получаем финальный результат.

double binary_pow(double b, unsigned long long e) {
    double v = 1.0;
    while(e != 0) {
            if((e & 1) != 0) {
                    v *= b;
            }
            b *= b;
            e >>= 1;
    }
    return v;
}

И при выполнении мы можем получить 10.00 ^ 2.00 = 100.00, 10.50 ^ 2.00 = 110.25. Но если экспонента не целое число, то данный способ не подойдет (10.50^2.50 вычисляется как 110.25). Так что важно отметить, что этот алгоритм применим только к целым числам.

Согласно википедии, Код Мортона (называемый также Z-порядок, кривая Мортона, кривая Лебега) - это функция, которая отоброжает многомерные данные в одномерные. Идея — чередовать биты координатных значений.

Bit Interleaving (перемежение битов, интерливинг) — процесс изменения порядка следования битов в передаваемой последовательности. Цель — разнести ошибки так, чтобы они влияли на разбросанные биты, а не на последовательные.

static uint32_t split_bits(uint16_t x) {
    x = (x | (x << 8)) & 0x00FF00FF;
    x = (x | (x << 4)) & 0x0F0F0F0F;
    x = (x | (x << 2)) & 0x33333333;
    x = (x | (x << 1)) & 0x55555555;
    return x;
}

uint32_t morton_encode(uint16_t x, uint16_t y) {
    return split_bits(x) | (split_bits(y) << 1);
}

void morton_decode(uint32_t code, uint16_t *x, uint16_t *y) {
    uint32_t x_code = code & 0x55555555;
    uint32_t y_code = code & 0xAAAAAAAA;

    x_code = (x_code | (x_code >> 1)) & 0x33333333;
    x_code = (x_code | (x_code >> 2)) & 0x0F0F0F0F;
    x_code = (x_code | (x_code >> 4)) & 0x00FF00FF;
    x_code = (x_code | (x_code >> 8)) & 0x0000FFFF;

    y_code = (y_code | (y_code >> 1)) & 0x33333333;
    y_code = (y_code | (y_code >> 2)) & 0x0F0F0F0F;
    y_code = (y_code | (y_code >> 4)) & 0x00FF00FF;
    y_code = (y_code | (y_code >> 8)) & 0x0000FFFF;

    *x = (uint16_t)x_code;
    *y = (uint16_t)(y_code >> 1);
}

Битовый интерливинг перемешивает биты двух чисел. Для координат x и y мы берем их бинарные представления и создаем некое новое число, куда поочередно будем записывать биты из x и y. К примеру, если x = 10 (1010) и y=12 (1100), то процесс будет таким: возьмем младшие биты x (0) и y (0), соединив их получаем 00. Затем следующий бит y (0) и следующий бит x (1), получаем 01. Затем бит y (1) и бит x (0), получаем 10. Наконец, старший бит y (1) и старший бит x (1), получаем 11. Итоговый код Мортона: 11 10 01 00 = 11100100₂ = 228.

Функция split_bits выполняет ключевую операцию - она раздвигает биты числа, вставляя между ними нули. Для 4-битного числа 1010 после split_bits получается 01000100 в бинарном виде.

Функция morton_encode вызывает функцию split_bits для x и y, после сдвигает результат для y на один бит влево и объедяняет XOR'ом.

Функция morton_decode выполняет обратную операцию. Сначала она разделяет код на биты, принадлежащие x (нечетные позиции) и y (четные позиции), используя маски 0x55555555 и 0xAAAAAAAA. Затем сжимает биты обратно в 16-битные числа, выполняя операции, обратные split_bits.

Основное преимущество кода Мортона - сохранение пространственной локальности. Точки, близкие в двумерном пространстве, обычно имеют близкие значения кодов Мортона. Это свойство используется в пространственных индексах, квадродеревьях, компьютерной графике и GIS системах для эффективной организации данных.

Давайте попробуем запустить и проверить алгоритм:

int main() {
    uint16_t x = 10;
    uint16_t y = 13;

    uint32_t code = morton_encode(x, y);
    printf("x=%u, y=%u\n", x, y);
    printf("Morton code: %u (0x%08X)\n", code, code);

    uint16_t decoded_x, decoded_y;
    morton_decode(code, &decoded_x, &decoded_y);
    printf("Decoded: x=%u, y=%u\n", decoded_x, decoded_y);

    return 0;
}

При запуске получаем:

x=10, y=12
Morton code: 228 (0x000000E4)
Decoded: x=10, y=6

Сам код мортона благодаря тому что упаковывает 2D/3D координаты в 1D число, используется в ГИС, базах данных, играх и прочих системах где нужна упаковка координат.

Бьюсь об заклад, что вы крайне редко видели код на GNU-стандартах. В качестве примера я хочу показать пример рабочей программы с устаревшими и специфичными вещами.

??=include <stdio.h>

int $func(int array[static 10]) <%
    int sum = 0;
    for (int i = 9; i --> 0;) <%
        sum += array<:i:>;
    %>
    return sum;
%>

int $print_func(int array[static 10]) <%
    for (int i = 9; i >= 0; --i) <%
        printf("Value %i with index %i\n", array[i], i);
    %>
    return 0;
%>


int main() ??<
    int arr<:10:> = {[0]=1, [5]=5, [9]=9};

    $print_func(arr);

    int result = (<%
        int temp = $func(arr);
        printf("Sum: %d??/n", temp);
        temp;
    %>);

    void *ptr = ??< &&label ??>;
    goto *ptr;

    label:
    return result;
??>

Скомпилировав код выше через gcc gnustd_fun.c -o gnustd_fun -std=gnu11 -trigraphs, мы получим:

Value 9 with index 9
Value 0 with index 8
Value 0 with index 7
Value 0 with index 6
Value 5 with index 5
Value 0 with index 4
Value 0 with index 3
Value 0 with index 2
Value 0 with index 1
Value 1 with index 0
Sum: 6

Этот код использует такие вещи, как триграфы ??= вместо символа #, ??< для открывающей фигурной скобки и ??> для закрывающей. Триграфы и диграфы (<% и %> также заменяют фигурные скобки, а <: и :> служат заменой квадратных скобок) были созданы для замены возможных несуществующих на клавиатуре символов скобок в стародавние времена.

Имена функций func и print_func начинаются с символа $ (php-разработчики должны пустить слезу), что является допустимым расширением компилятора.

Цикл в функции $func записан в необычной форме: for (int i = 9; i --> 0;). Оператор --> на самом деле комбинация постфиксного декремента i-- и оператора сравнения >. В функции main массив инициализируется следующим образом: {[0]=1, [5]=5, [9]=9}, где явно задаются значения только для конкретных индексов.

Далее используется составное выражение в круглых скобках ({ ... }), которое является расширением GCC и называется statement expression. Оно выполняет блок кода, а значением всего выражения становится результат последнего оператора внутри блока, в данном случае temp;. Это позволяет совместить вычисление суммы, её вывод через printf и передачу значения в переменную result.

Наиболее экзотическая часть кода — это использование указателей на метки. Конструкция &&label берет адрес метки в памяти, сохраняя его в указатель void *ptr. Затем с помощью оператора косвенного перехода goto *ptr; выполняется прыжок по этому адресу. Это нестандартное расширение GCC. После перехода на метку label: функция main возвращает ранее вычисленную сумму.

Floyd's Tortoise and Hare

Алгоритм придуман Робертом Флойдом и используется для обнаружения циклов в последовательностях, чаще всего в связных списках, но идея применима и к другим структурам, где есть переход по индексам или указателям.

Суть алгоритма: Два указателя ("черепаха" и "заяц") движутся по последовательности с разной скоростью. Заяц делает два шага за итерацию, черепаха — один. Если в последовательности есть цикл, то заяц неизбежно "догонит" черепаху внутри цикла. Если цикла нет, заяц первым достигнет конца последовательности.

#include <stdio.h>

int findCycle(int nums[], int numsSize) {
    if (numsSize <= 1) return -1;

    int tortoise = nums[0];
    int hare = nums[0];

    do {
        tortoise = nums[tortoise];
        hare = nums[nums[hare]];
        if (hare < 0 || hare >= numsSize) return -1;
    } while (tortoise != hare);

    tortoise = nums[0];
    while (tortoise != hare) {
        tortoise = nums[tortoise];
        hare = nums[hare];
    }

    return tortoise;
}

Код использует два указателя — медленный (черепаха) и быстрый (заяц). Оба стартуют с начала массива. Медленный движется на 1 шаг: tortoise = nums[tortoise]. Быстрый — на 2 шага: hare = nums[nums[hare]]. Если массив содержит цикл, быстрый рано или поздно догонит медленного внутри цикла. Это первая фаза — обнаружение факта цикла.

После встречи медленного возвращаем в начало массива. Теперь оба движутся синхронно, по 1 шагу. Точка их новой встречи будет точкой входа в цикл. Это вторая фаза — нахождение начала цикла.

Проверка hare < 0 || hare >= numsSize отлавливает выход за границы, что означает отсутствие цикла. Алгоритм работает за O(n) времени и O(1) памяти, не меняя исходные данные. В примере {1,3,4,2,2} последовательность индексов 0→1→3→2→4→2 зацикливается на значениях 2 и 4, а начало цикла — значение 2.

Давайте протестируем код:

int main() {
    int arr[] = {1, 3, 4, 2, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = findCycle(arr, size);

    if (result != -1) {
        printf("Cycle starts at value: %d\n", result);
    } else {
        printf("No cycle found\n");
    }

    return 0;
}

Как мы видим, массив становится цикличным на 2: Cycle starts at value: 2.

Если хотите больше контента по PostgreSQL и SQL, СУБД, ставьте реакции, тогда я пойму что тема интересна вам.

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

Простейший алиас в .bashrc или .zshrc кажется небольшим открытием. Первый рабочий скрипт, сохранённый в ~/.local/bin, ощущается как прорыв. Это не просто про лень — это про эффективность, про оптимизацию работы.

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

https://habr.com/ru/companies/timeweb/articles/983418/

Всем привет! Небольшой отход от основной темы канала, я решил попробовать себя в перевод и перевел статью "Raspberry Pi Drag Race: Pi 1 to Pi 5 – Performance Comparison" с Hacker News.

Сегодня мы хотим рассмотреть на практике 13 летнюю историю разработки Raspberry Pi. У меня есть экземпляры каждого поколения Pi, от оригинальной модели из 2012 года, до Pi 5, которая вышла чуть больше года назад.

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

Читать статью - https://habr.com/ru/articles/988770/

Буду рад фидбеку по качеству перевода и по заинтересованности в теме КПК.

Индексы в PostgreSQL — это специальные структуры данных, которые ускоряют поиск информации в таблицах, но требуют определённых затрат. Работают они, грубо говоря, как указатель в книге: вместо того чтобы листать все страницы (читать всю таблицу с диска), система быстро находит нужные строки по специальной карте — индексу.

Когда вы создаёте индекс, PostgreSQL строит по выбранному столбцу упорядоченную структуру (чаще всего B-дерево), которая связывает значение в столбце с физическим адресом строки в таблице. Это позволяет находить данные за логарифмическое время, даже в огромных таблицах. Например, поиск одного игрока в таблице из миллиона строк без индекса заставляет систему прочитать все строки (последовательное сканирование), что занимает сотни миллисекунд. С индексом — только несколько страниц и доли миллисекунд.

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

PostgreSQL предлагает несколько типов индексов под разные задачи. B-tree — самый универсальный и часто используемый, подходит для сравнений и сортировок. Hash — компактный и быстрый для точного совпадения, но не для диапазонов. BRIN — очень компактный, идеален для больших упорядоченных данных (например, временных рядов), где значения коррелируют с их расположением на диске. GIN — специализируется на поиске внутри составных данных: текста, массивов, JSON. GiST и SP-GiST — это, скорее, frameworks для создания индексов под сложные типы данных, вроде геометрических объектов или полнотекстового поиска.

Важно помнить, что индекс помогает только если запрос обращается к проиндексированным столбцам, и если выбирается небольшая доля строк (обычно до 15-20%). Иначе планировщик может проигнорировать индекс и просканировать таблицу целиком. Также есть продвинутые техники: частичные индексы (индексирующие только часть строк по условию), многоколонные индексы (порядок столбцов в них критичен) и покрывающие индексы (которые содержат все данные для запроса, избавляя от обращений к таблице).

Читать подробнее оригинал на английском

Алгоритм XOR Swap

Классический алгоритм, который позволяет обменивать значения двух переменных с помощью трёх операций XOR без создания временной третьей.

void xor_swap(int *a, int *b) {
    if (a != b) {
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}

Классический, но всегда впечатляющий новичков трюк: обмен значений двух переменных с помощью трёх операций XOR. Это демонстрирует симметрию и свойства операции XOR. Хотя на современных процессорах это часто медленнее, чем использование временной переменной (из-за параллелизма), трюк остаётся красивым и поучительным.

Первая операция сохраняет разность a и b в a, вторая, используя исходное b и новое a, получает исходное a и сохраняет в b, и последняя, используя новое a и новое b, получает исходное b и сохраняет в a.

Алгоритм Ричардса (Richards’ Curve) — это метод оценки параметров нелинейной кривой роста (generalized logistic curve). Модель была предложена британским биологом Ф. Дж. Ричардсом в 1959 году. Она показывает тенденцию количественного роста: в начале она небольшая (стадия бурного роста), затем быстро увеличивается (стадия быстрого роста) и, наконец, стабилизируется в диапазоне значений (стадия насыщения).

Давайте реализуем быструю версию этого алгоритма:

float fast_sin(float x) {
    const float a = 4.0f / (M_PI * M_PI);
    const float p = 0.225f;
    x = a * x * (M_PI - fabs(x));
    return p * (x * fabs(x) - x) + x;
}

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

Сначала он делает базовую параболическую волну: x = a * x * (π - |x|). Эта простая формула уже похожа на синус. Затем идёт коррекция погрешности через полином третьей степени: p * (x * |x| - x) + x. Это эквивалентно x + p*x³ - p*x. Коэффициент p=0.225 подобран, чтобы финальная кривая максимально близко легла на настоящий синус, используя минимум вычислений. Всё сводится к нескольким умножениям и сложениям.