Понесло не в ту степь

топ 100 блогов nponeccop06.09.2024 Я тут внезапно понял, что я не хотел никаких сегмент трей, а хотел двухуровневое bucket tree (так его называют жепетя). Если у нас есть 50 точек, берем 2 массива. В lower из 50 элементов кидаем все точки, а в upper из 5 групп - максимумы для групп по 10 точек. Ну и для длинных ренжей делаем 3 линейных сканирования: правое и левое в большом массиве и среднее в маленьком. Если 5 заменить на 2 то получим нижние 2 уровня segment tree.
Ну и надо написать 2 страшные функции: по диапазону (left, right) первая возвращает диапазон левого кусочка, а вторая - диапазон правого.
const roundUp = x => x - x % 10 + 10
const getLeftRange = [left, right] => [left, roundUp(left)]


А чтобы из нее получить getRightRange, нам надо всего лишь взять копеечный дедовский... HoTT-путь между массивами и перевернутыми массивами. Ну то есть:
const transportIdx = x => x - lowerArr.length - 1
const transportRange = [left, right] => [transportIdx(right), transportIdx(left)] 
const composePrePost = (f, g, h) => x => f(g(h(x))
const transportRangeToRange = f => composePrePost(transportRange, f, transportRange)
const getRightRange = transportRangeToRange(getLeftRange)


Эта ебанина преподает нам аж 4 важных урока:

  • хаскелисты объявили неделю алгебраического кода, количество off-by-one errors сократилось вдвое

  • но легко видеть что нет

  • и перфоманс наш подсел

  • такой код совершенно вне досягаемости Клода

Ну то есть нас всех ждет self-fulfilling prophecy в виде моделей, плодящих говнокод, используемый для обучения все новых моделей. Я жду, пока не придумают спец-язык, на котором моделям будет максимально просто писать. А также спец-обвес вроде протокола редактирования. То, что внутри у Аидера в промптах, меня повергает в отчаяние.

Upd: рабочий PoC этой идеи выглядит так. Уберите детей от голубых экранов:
function subRangeSum(arr, [start, end]) {
    if (start >= end) return []; // Invalid or empty range
    let sum = arr[start]; // Initialize sum with the first element in the range
    for (let i = start + 1; i < end; i++) { // Start from the next element
        sum += arr[i]; // Accumulate subsequent elements
    }
    return [sum]; // Return a one-element array containing the sum
}

class DecimalTree {
    constructor(arr) {
        this.lowerLevel = arr;
        this.upperLevel = Array.from({ length: arr.length / 10 }, (_, i) =>
            subRangeSum(this.lowerLevel, [i * 10, (i + 1) * 10])[0] // Semi-open range [i*10, (i+1)*10)
        );
    }

    // Sum query function: find sum from range [left, right) (semi-open)
    query(left, right) {
        // For small ranges (less than 20 elements), we do linear scanning
        if (right - left < 20) {
            return subRangeSum(this.lowerLevel, [left, right]);  // Semi-open
        }
        const roundUp = x => x % 10 === 0 ? x : x - (x % 10) + 10;
        const getLeftRange = ([left, right]) => [left, roundUp(left)];
        const composePrePost = (f, g, h) => x => f(g(h(x)));
        const transportIdx = idx => this.lowerLevel.length - idx - 1;
        const transportRange = ([left, right]) => [transportIdx(right - 1), transportIdx(left - 1)];
        const transportRangeToRange = f => composePrePost(transportRange, f, transportRange);
        const leftRange = getLeftRange([left, right])
        const rightRange = transportRangeToRange(getLeftRange)([left, right]);
        const middleRange = [leftRange[1] / 10, rightRange[0] / 10];
        const leftPart = subRangeSum(this.lowerLevel, leftRange);
        const rightPart = subRangeSum(this.lowerLevel, rightRange);
        const middlePart = subRangeSum(this.upperLevel, middleRange);
        const concatenatedParts = [].concat(leftPart ,middlePart, rightPart);
        return subRangeSum(concatenatedParts, [0, concatenatedParts.length]);
    }
}
Некая, с позволения сказать, простота, налицо. Но 4о настойчиво предлагает вернуть все взад. Ну и непонятно что делать с middlePart.

Оставить комментарий

Архив записей в блогах:
Вышел новый учебник по истории России для 11 класса. Мединскому и Торкунову - НЕ ВЕРЮ. В. Мединский: "В новых учебниках истории полностью переписаны разделы о 70-х, 80-х, 90-х и "нулевых" годах." Горбачёва они винят за конец СССР. Да Горбачёв с Ельциным вас сделали миллионерами, ...
А пока у нас не было мороза и целых полсантиметра снега, а были два теплых дня 2 и 3 числа, я убирала во дворе листья и мусор. Да, за работу дворников мы платим, но дворников уже года полтора, если не два, не видели. Самое интересное, что соседям отсутствие дворников не мешает бросать во ...
Андрей Стифеев (capivar) начал работать в кафе "Стоп-кадр" кем-то, кто называется проджект-менеджером. Плохо знаю, что это такое, да не суть. Вот несколько его зарисовок, сделанных в первые дни. В целом отвечают на один из аспектов проблемы "почему в ...
Туточки знакомые питерские сороки принесли на хвосте свежую новость: [...] Президент России Владимир Путин поддержал начало проектирования высокоскоростной железнодорожной магистрали (ВСМ) Москва—Санкт-Петербург. По данным “Ъ”, соответствующее предложение поступило от врио ...
С каждым годом уходит все дальше ставший историей Советский Союз. Многие и сегодня полагают, что в то время продукты питания были высочайшего качества и предлагались населению в избытке. Естественно, все было далеко не так сказочно, как мы себе это представляем, но были и такие товары ...