Как я могу определить, охватывает ли список диапазонов данный диапазон? - PullRequest
Новая
       21

Как я могу определить, охватывает ли список диапазонов данный диапазон?

0 голосов
/ 22 мая 2019

Я хочу эффективно определить, охватывает ли список диапазонов данный диапазон.Например, список диапазонов [(0-3), (3-5), (4-8), (6-10)] охватывает диапазон (0-10), а [(5-10), (0-3)] нет.Список может содержать наложения и не обязательно упорядочен.

Я попытался реализовать функцию Continuous, показанную ниже, которая проверяет, содержит ли диапазон диапазонов байтов заданные значения start и end пройденного диапазона.

type byteRange struct {
    start int64
    end   int64
}

type byteRanges []*byteRange

func (brs byteRanges) Len() int {
    return len(brs)
}

func (brs byteRanges) Swap(i, j int) {
    brs[i], brs[j] = brs[j], brs[i]
}

func (brs byteRanges) Less(i, j int) bool {
    return brs[i].start < brs[j].start
}

func (brs byteRanges) Continuous(start int64, end int64) bool {
    curPos := start
    sort.Sort(brs)

    for _, br := range brs {
        if br.start > curPos+1 {
            return false
        }

        if curPos < br.end {
            curPos = br.end
        }

        if curPos >= end {
            return true
        }
    }

    return false
}

Функция работает правильно, но она не очень эффективна при работе с большим списком диапазонов и при частом ее вызове.Может кто-нибудь порекомендовать алгоритм / реализацию, которая может ускорить эту логику?

Ответы [ 2 ]

2 голосов
/ 22 мая 2019

Поскольку вы будете неоднократно вызывать Continuous в одном и том же наборе диапазонов, будет хорошей идеей создать метод Condense (или как вы хотите его называть), который возьмет срез и вернет новый срез с диапазоны отсортированы и все перекрывающиеся диапазоны объединены. Вам нужно только один раз вызвать Condense для любого заданного набора диапазонов. Continuous может потребовать, чтобы он вызывался только по результату Condense. (Чтобы выполнить это требование, было бы неплохо, чтобы Condense фактически возвращал struct пользовательского типа, который является просто оберткой вокруг среза, и определял Continuous только для этого типа struct. Если Вы хотите & mdash; для удобства & mdash; затем вы можете определить отдельный метод Continuous, который можно вызывать непосредственно на срезах, который вызывает Condense и затем Continuous. Этот вспомогательный метод будет медленным опять же, конечно, но это может быть удобно для наборов, которые проверяются только один раз.)

Логика слияния в Condense довольно проста:

  • Если срез пустой, просто верните его (выходя рано).
  • Сортировка диапазонов по их start.
  • Создайте свежий срез под названием result.
  • Инициализировать prevRange первым диапазоном.
  • Итерация по диапазонам. Для каждого:
    • Если текущий диапазон начинается после prevRange.end + 1, добавьте prevRange к result, затем установите prevRange в текущий диапазон.
    • В противном случае, если текущий диапазон заканчивается после prevRange.end, установите prevRange.end на end текущего диапазона.
  • Добавить prevRange к result.

Логика в Continuous теперь может быть:

  • Выполните двоичный поиск по диапазонам, найдя последний диапазон, у которого start меньше или равно start.
  • Если end этого диапазона больше или равно end, вернуть true; в противном случае верните false.
0 голосов
/ 22 мая 2019

Решение, которое проще? 

package main

import (
    "fmt"
    "sort"
)

type byteRange struct {
    start int64
    end   int64
}

type byteRanges []*byteRange

func (brs byteRanges) Continuous(start int64, end int64) bool {
    sort.Slice(brs, func(i, j int) bool {
        return brs[i].start < brs[j].start
    })

    var (
        longestReach int64
        in           bool
    )

    for _, br := range brs {
        if !in {
            // first br satrts laying over the target
            if br.start <= start && br.end >= start {
                longestReach = br.end
                in = true
            }
            continue
        }
        if in && longestReach < br.start-1 {
            break
        }
        if longestReach < br.end {
            longestReach = br.end
        }
    }

    return in && longestReach >= end
}

func main() {
    brs := byteRanges{{5, 9}, {6, 10}}
    fmt.Println(brs.Continuous(8, 10))
}
...