Оптимизировать функцию округления вверх / вниз

Question

Таким образом, у одного из наших клиентов (аукциониста) есть набор странных приращений (также известных как лондонские приращения), где по существу они не соответствуют ни одному делимому числу, поэтому использование чего-то вроде: Math.round(number / increment) * increment не будет работать.

Приращения

From: 100, To: 299, Increment: 10
From: 300, To: 319, Increment: 20
From: 320, To: 379, Increment: 30
From: 380, To: 419, Increment: 20

И подобные вещи продолжаются.

Так что взятие числа типа: 311 должно округляться до 320.Теперь у меня есть этот код, и он отлично работает, он также округляет вверх / вниз 321 => 350 и 363 => 380, как и ожидалось.

Меня беспокоит то, что он не быстрый и / или устойчивый и требует больших чиселокругляться будет медленнее.Эта функция должна быть настолько быстрой, как Math.round(), очевидно, зная, что она не будет, но настолько быстрой, насколько это возможно.Теперь, несмотря на то, что у меня все получилось, способ, которым я это сделал, по сути зацикливает количество X раз (x - любое число, поэтому я установил его на 9999999, и я надеюсь, что кто-то знает лучший способ сделать это.

// Get increment amount
window.getIncrement = (num) => {
    var num = parseInt(num);
    for (var i = 0; i < window.increments.length; i++) {
        if (num >= parseInt(window.increments[i].from) && num <= parseInt(window.increments[i].to)) {
            return parseInt(window.increments[i].increment);
        }
    }
}

// Get increment start value
window.getIncrementStartValue = (num) => {
    var num = parseInt(num);
    for (var i = 0; i < window.increments.length; i++) {
        if (num >= parseInt(window.increments[i].from) && num <= parseInt(window.increments[i].to)) {
            return parseInt(window.increments[i].from);
        }
    }
};

// Custom round up function
const roundToNearestIncrement = (increment, number, roundDown) => {
    var incrementStart = parseInt(window.getIncrementStartValue(number));
    var increment = parseInt(increment), number = parseInt(number);
    console.log(incrementStart, increment, number);

    // So now we have a start value, check the direction of flow
    var lastBelow = false, firstAbove = false;
    for (var i = 0; i < 9999999; i++) {
        var incrementRounder = incrementStart + (increment * i);
        if (incrementRounder === number) { return number; }
        if (incrementRounder < number) { lastBelow = incrementRounder; }
        if (incrementRounder > number) { firstAbove = incrementRounder; }
        if (lastBelow !== false && firstAbove !== false) { break; }
        console.log('Loop #' + i + ', Below: ' + lastBelow + ', Above: ' + firstAbove);
    }
    return !roundDown ? firstAbove : lastBelow;
}

Затем вы используете это так:

// Example usage
var num = 329;
var inc = getIncrement(num);
console.log('Rounded: ' + roundToNearestIncrement(inc, num) + ', Expected: 350');

Теперь, как я уже сказал, это прекрасно работает, но меня беспокоит то, что это замедлит процесс узла, если число использует что-то большоекак 1,234,567, или просто наибольшее число из этого набора приращений, потому что код будет зацикливаться, пока не найдет выше и ниже число, поэтому, если у кого-то есть лучшая идея о том, как это сделать, он будет работать, но не зацикливаться?

Смотрите скриншот того, что я делал раньше:

Вы можете видеть, что он должен был зацикливаться 1865 раз, прежде чем нашел выше иниже суммы.

В любом случае, любые ваши идеи будут оценены.

Answer 1

Если я правильно понимаю проблему:

1. Предварительно создайте массив всех порогов в порядке возрастания.Я думаю, это будет выглядеть примерно так: [0, 1, 2, ..., 320, 350, 380, 400, 420, ...];
2. Тогда поиск будет простым:

const findNearestThreshold = (number) => thresholdsArray
   .find(threshold => (threshold >= number));

Answer 2

Решение, основанное только на массиве приращений.

const steps = [
   { from: 100, increment: 10}, // I don't need 'to' property here
   { from: 300, increment: 20},
   { from: 320, increment: 30},
   { from: 380, increment: 20},   
]

const roundUp = x => {
   const tooLargeIndex = steps.findIndex(({from}) => from > x);
   const { from, increment } = steps[tooLargeIndex - 1];
   const difference = x - from;
   return from + Math.ceil(difference / increment) * increment;
}

console.log(300, roundUp(300));
console.log(311, roundUp(311));
console.log(321, roundUp(321));

Answer 3

Есть несколько способов сделать это быстрее

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

rounded = []; rounded[0]=0 ... rounded[100] = rounded[101] = ... = rounded[109] = 110 ... and so on.

Конечно, это решение зависит от размера таблицы.

2.Создайте дерево двоичного поиска на основе точек прорыва и поиска по этому дереву.Если дерево сбалансировано, для поиска потребуется O (log (n)).