Эффективное вычисление совокупного процента диапазона - PullRequest
Новая
       53

Эффективное вычисление совокупного процента диапазона

0 голосов
/ 13 февраля 2020

У меня есть набор диапазонов, и мне нужно найти, в какой момент процент совокупного диапазона пересекает данный порог.

Например, у меня есть 0..20 с 3 непересекающимися диапазонами, которые должны возвращать точки, где 2/3 последовательности до этой точки идет выше или ниже этого диапазона покрытия: 

-          +,-                      +                 -
|           |                       |                 |
v           v                       v                 v
0---1---2---3---4---5---6---7---8---9---10--11--12--13--14--15--16--17--18--19--20
    |-------|       |---------------------------|               |---|

В приведенном выше сценарии при 3 диапазон достиг 2 единиц из 3, что составляет порог 2/3, но затем сразу же пересекает порог. При 9 совокупный диапазон достигает 6/9, что составляет порог 2/3. Затем, на 13.5, он снова падает ниже порогового значения (9 / 13.5 == 2/3).

Идеальным выходным значением будет преобразование числа в логическое значение с фиксированной десятичной точкой: 

{
  00.000: false,
  03.000: true,
  03.001: false,
  09.000: true,
  13.500: false,
}

Это простой пример, когда в действительности это могут быть десятки диапазонов в последовательности, достигающей 100 миллионов. Диапазоны могут касаться, но не перекрываться.

Один из подходов состоит в том, чтобы найти покрытие, обеспечиваемое суммой диапазонов в точке, где заканчивается каждый диапазон. Итак, первый диапазон заканчивается на 3, где сумма диапазонов равна 2, обеспечивая покрытие до 3. Второй диапазон заканчивается на 12, где сумма диапазонов равна 9, обеспечивая покрытие до 13,5. Это найдет места, где покрытие падает. Чтобы определить, где встречается покрытие, можно сделать обратное, суммируя непокрытие в начале каждого диапазона. Таким образом, на 1 сумма непокрытия равна 1, что будет выполнено на 3, если и только если тот же диапазон заканчивается на или после 3 (что и происходит). На 5 сумма непокрытия равна 3, что означает, что покрытие достигнуто на уровне 9 (что и есть). При 16 кумулятивное отсутствие покрытия равно 7, что соответствует 21, но диапазон не достигает этого значения, поэтому его можно игнорировать.

Функция может выглядеть примерно так ( машинопись игровая площадка ): 

class SequenceRange {
    startsAt: number
    endsAt: number

    constructor(startsAt: number, endsAt: number) {
        this.startsAt = startsAt
        this.endsAt = endsAt
    }
}

const getThresholdCrossings = (threshold: number, start: number, end: number, orderedRanges: SequenceRange[]): Map<number, boolean> => {
    let coverage: number = 0
    let pointInSequence: number
    let mapping: Map<number, boolean> = new Map()

    orderedRanges.forEach((range: SequenceRange) => {
        pointInSequence = range.endsAt
        coverage += (range.endsAt - range.startsAt)
        const nonCoverage: number = pointInSequence - coverage

        const expiringCoverage: number = coverage * (1 / (1 - threshold))
        const coverageMet: number = nonCoverage / threshold

        if (expiringCoverage >= pointInSequence && expiringCoverage <= end) { 
            mapping.set(expiringCoverage, false)
        }

        console.log('----------------------------------')
        console.log('range: ' + range.startsAt + '..' + range.endsAt)
        console.log('coverage: ' + coverage)
        console.log('nonCoverage: ' + nonCoverage)
        console.log('expiringCoverage: ' + expiringCoverage)
        console.log('coverageMet: ' + coverageMet)

        if (coverageMet <= range.endsAt && coverageMet <= end && coverageMet ) { 
            mapping.set(coverageMet, true)
        }
    })

    return mapping
}

console.log(getThresholdCrossings((1 / 3), 0, 20, [new SequenceRange(1,3), new SequenceRange(5, 12), new SequenceRange(16, 17)]))

Вышеприведенное выложит это на консоль: 

----------------------------------
range: 1..3
coverage: 2
nonCoverage: 1
expiringCoverage: 2.9999999999999996
coverageMet: 3
----------------------------------
range: 5..12
coverage: 9
nonCoverage: 3
expiringCoverage: 13.499999999999998
coverageMet: 9
----------------------------------
range: 16..17
coverage: 10
nonCoverage: 7
expiringCoverage: 14.999999999999998
coverageMet: 21

{
  03.000 => true,
  09.000 => true,
  13.499 => false,
}

Одна из проблем заключается в том, что она не обрабатывает 0. Он также не очень хорошо обрабатывает 3. В журнале на консоли вы можете видеть, что срок действия покрытия должен истечь в 2.99.., но это покрытие также встречается в 3. Если охват достигнут на 3, то срок его действия должен истечь на 3.00000001. Что я делаю неправильно? И есть ли более эффективный способ go об этом?

...