Блог

Итак, у одного из наших клиентов (аукциониста) есть набор странных приращений (также известных как лондонские приращения), где по сути они не соответствуют какому-либо делимому числу, поэтому использование чего-то вроде: 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) amp;amp; 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) amp;amp; 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 amp;amp; 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 раз, прежде чем он нашел указанные выше и ниже суммы.

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

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

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

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

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

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

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

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

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

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

 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));