Перекрестный алгоритм диапазона лучше, чем O (n)?

Редактирование: Это кажется, что это решение более или менее Дерево Интервала . Больше полноценного внедрения Дерева Интервала может быть найдено здесь .

class TreeNode
{
public:
    long pivot;
    List<Range> leaves;  //Any ranges that intersect the pivot
    TreeNode left;        //Tree nodes that fall to the left of the pivot
    TreeNode right;       //Tree nodes that fall to the right of the pivot
};

Подготовительная школа O (n регистрируют n):

1. Создают список диапазонов
2. Выбор точки опоры (возможно при помощи отсортированного списка дат окончания.)??
3. Сборка Ваше дерево.

Поиск:

1. двоичный поиск Использования для нахождения первого центра, который является> = TestRange. Конец

2. Пересечение дерево до центра> TestRange. Запустите

   2a. Добавьте листы к своему результату.

Пример:

Диапазоны:

• 0 - 2
• 1 - 2
• 2 - 3
• 1 - 4
• 2 - 4
• 0 - 5
• 4 - 5
• 2 - 6
• 3 - 7

Дерево:

                             4
               --------------+------------------
               3             |                 7
               |            1-4                |
               |            2-4                |
               |            0-5                |
               |            4-5                |
      ---------+------                 --------+--------
      2        |    null              6        |       null
 -----+----   2-3                 ----+----   3-7
null  |  null                   null  |  null    
     0-2                             2-6
     1-2

Не Перекрывающиеся Диапазоны:

Подготовительная школа O (n регистрируют n):

1. Делают массив / вектор диапазонов.
2. Сортируют вектор к концу диапазона (связи повреждения путем сортировки по запуску диапазона)

Поиск:

1. двоичный поиск Использования для нахождения первого диапазона со значением Конца> = TestRange. Запустите

2. Итератор, запускающийся при двоичном поиске, пока Вы не найдете Запуск> TestRange. Конец:

   2a. Если диапазон, если текущий диапазон в TestRange, добавляет его к Вашему результату.

Перекрывающиеся Диапазоны:

Подготовительная школа O (n регистрируют n):

1. Делают массив / вектор диапазонов.
2. Сортируют вектор к концу диапазона (связи повреждения путем сортировки по запуску диапазона)

3. Делают второй вектор ints. Это представляет точку, в которой можно прекратить искать.

   int stop[size];
   stop[size-1] = Ranges[size - 1].start;
   for (int i = size - 2; i >= 0; i--)
   {
       stop[i] = min(Ranges[i].start, stop[i+1]);
   }
   

Поиск:

1. двоичный поиск Использования для нахождения первого диапазона со значением Конца> = TestRange. Запустите

2. Итератор, запускающийся при двоичном поиске до остановки [я]> TestRange. Конец:

   2a. Если диапазон, если текущий диапазон в TestRange, добавляет его к Вашему результату.

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

Теперь просто делают binsearch для Вашего целевого нижнего значения (или меньший если не точным) и один для целевого верхнего значения (или больше если не точный). Получающиеся индексы являются диапазонами, которые покрыты. Необходимо проверить, являются ли диапазоны в индексах самостоятельно в - или исключенный, но которые являются всего 2 проверками. Полная сложность O (регистрируют n).

Кажется, что Вам нужен класс, который реализует интерфейс SortedSet. TreeSet является реализацией, которая поставлется с базовым API.

Имеют набор того, содержащий диапазоны, отсортированные по самому низкому значению и одному отсортированному самым высоким значением.

можно тогда реализовать эквивалент алгоритма базы данных с помощью наборов в оперативной памяти.

Что касается того, быстрее ли это на самом деле, чем O (n), я не мог бы сказать.

Так же, как дерево квадрантов работает на ряд 2-х точек, простое двоичное дерево должно работать на этот случай. Создайте дерево со своими диапазонами.

Для объяснения далее: Каждый узел в дереве содержит два целых числа, начало и конец диапазона и два ребенка, если это не вершина. Для нахождения диапазонов, которые входной диапазон охватывает затем запускающийся наверху дерева

  - if the node range intersects the input range:
     - if it's a leaf node, then add the range to your result list
     - if it's not a leaf node, then traverse down to the child nodes and repeat this process.

, Это должен быть O (logN)

Более подробная информация: двоичное дерево было бы структурировано как 1-d версия дерева квадрантов. Каждый узел имел бы три целых числа (извините, я сказал два выше, но теперь я понимаю, что Вам нужно три), самое низкое представление самого низкого значения самого низкого диапазона, который это ниже этого узла, самое высокое представление самого высокого значения самого высокого диапазона, который это ниже этого узла и центра. Покинутый ребенок охватил бы от этого узла, самого низкого к его центру. Правильный ребенок охватил бы от центра этого узла до этого самого высокого узла. Если существует только один диапазон, который идет от "самого низкого" до "самого высокого", у Вас не было бы центра, и это будет листом. Идеально Вы выбрали бы центры для каждого узла для хранения дерева сбалансированным.

Когда у меня была эта проблема, я использовал сортированный массив диапазонов и двоичного поиска для поиска пересечений. Это (я верю), O (зарегистрируйте n), производительность, с определенными издержками для контакта с наложением диапазонов.

ответ на Ваш вопрос, я думаю, получаемый от кода ниже, но внезапная остановка до вставки. Я представляю весь код для предотвращения беспорядка отличающимся контекстом - я должен был вставить диапазон кодовых точек Unicode в список диапазонов кодовой точки.

- РЕДАКТИРОВАНИЕ -

Адаптация кода ниже для определения пересечений нескольких диапазонов включает тривиальное, вперед ищут от точки вставки, пока диапазон не найден, который больше не пересекается.

- РЕДАКТИРОВАНИЕ КОНЦА -

класс Диапазона содержит:

final int                               lower;                                  // lower end of range
final int                               upper;                                  // upper end of range

public int compareTo(Object obj) {
    if(obj==null) { return -1; }

    Range                           oth=(Range)obj;

    if(lower<oth.lower) { return -1; }
    if(lower>oth.lower) { return  1; }
    if(upper<oth.upper) { return -1; }
    if(upper>oth.upper) { return  1; }
    return 0;
    }

Вставка Диапазона:

public Builder addRange(int fir, int las) {
    if(fir!=-1) { fir&=0x001FFFFF; }
    if(las!=-1) { las&=0x001FFFFF; }

    if(codepoints==null || codepoints.length==0) {
        codepoints=new Range[]{new Range(fir,las)};
        }
    else {
        int                         idx=Range.findChar(codepoints,fir);
        int                         ins=(idx<0 ? -(idx+1) : idx);

        if(idx<0) {
            if     (ins>0                 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); }  // new range adjoins the following range (can't overlap or idx would be >=0)
            else if(ins<codepoints.length && las>=(codepoints[ins  ].lower-1)) { idx=ins;     }  // new range overlaps or adjoins the following range
            }

        if(idx<0) {
            codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
            }
        else {
            boolean                 rmv=false;

            for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
                if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
                codepoints[xa]=null;
                rmv=true;
                }
            if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
                codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
                }
            if(rmv) { codepoints=Range.removeNulls(codepoints); }
            }
        }
    return this;
    }

Двоичный поиск:

static int findChar(Range[] arr, int val) {
    if(arr.length==1) {
        if     (val< arr[0].lower) { return -1; }                             // value too low
        else if(val<=arr[0].upper) { return  0; }                             // value found
        else                       { return -2; }                             // value too high
        }
    else {
        int                             lowidx=0;                               // low index
        int                             hghidx=(arr.length-1);                  // high index
        int                             mididx;                                 // middle index
        Range                           midval;                                 // middle value

        while(lowidx<=hghidx) {
            mididx=((lowidx+hghidx)>>>1);
            midval=arr[mididx];
            if     (val< midval.lower) { hghidx=(mididx-1); }                   // value too low
            else if(val<=midval.upper) { return mididx;     }                   // value found
            else                       { lowidx=(mididx+1); }                   // value too high
            }
        return -(lowidx+1);                                                     // value not found.
        }
    }

Если диапазоны перекрываются, и нужно получить все диапазоны, которые перекрывают (или содержат) заданный целевой диапазон, большая часть вышеупомянутые решения не работают.

Как отмечали некоторые, если (наихудший случай) все диапазоны случайно пересекают целевой диапазон (например, если целевой диапазон равен {0..MAXINT} или аналогичный), то из Конечно, для возврата n диапазонов требуется O (n).

Но разве это не интересный и типичный / средний случай, когда только очень небольшой% из n общих диапазонов действительно пересекает целевой диапазон? Наберите номер, который действительно пересекает «m» - в этом случае вы, вероятно, сможете сделать так же хорошо, как O (m). И если n = 10 ^ 9 и m = 10, это принципиальная разница.

Рассмотрим простой случай текстового документа, в котором различные области размечены для их «типа» - возможно, вы хотите найти все размеченные блоки, которые содержат или пересекают заданный непрерывный диапазон текста (например, пункт). В HTML, XML или аналогичных они могут быть только предками текстовых узлов, содержащих хотя бы некоторые символы целевого диапазона. В типичных представлениях с родительскими указателями в каждом узле это O (m) - намного лучше, чем O (n), особенно потому, что m (для коротких или синхронных целевых диапазонов) просто глубина вложения дерева, которая имеет тенденцию быть даже ниже, чем ln (n), потому что большие XML-документы на практике становятся не глубже, а пышнее.

Интересный случай сложнее: что, если ваши «элементы» не образуют дерево, как в XML, но могут перекрываться, как в MECS, CLIX, LMNL и некоторых других системах? Вы по-прежнему хотите найти все регионы / «элементы», которые перекрывают вашу цель, но их не так легко организовать.

С другой стороны, у вас должно получиться очень хорошо, потому что размеченные диапазоны во многих приложениях чаще всего маленькие - в книге гораздо больше слов, предложений и абзацев, чем глав. Таким образом, даже если может быть огромное количество диапазонов, которые начинаются до цели, и огромное количество, которые заканчиваются после нее, пересечение в среднем будет очень маленьким.

Я думаю, что это то, что имел в виду первоначальный вопрошающий, и, боюсь, я не нашел ответа на эту проблему. Если исходный вопрос не об этом, то я хотел бы сформулировать его как новый вопрос.