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

Ну и надо написать 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 сократилось вдвое
- но легко видеть что нет
- и перфоманс наш подсел
- такой код совершенно вне досягаемости Клода
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.
|
</> |