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

nponeccop — 06.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.

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

Популярные посты:

• Архив