Реализация дерева сегментов в Python

Я решаю эту проблему с помощью дерева сегментов, но получаю ошибку ограничения времени. Ниже мой необработанный код для минимального диапазона запроса и путем изменения min в max в моем коде вышеупомянутая проблема может быть решена. Я не знаю, как я могу улучшить производительность своего кода. Можете ли вы помочь мне с его проблемами производительности?

t = [None] * 2 * 7      # n is length of list


def build(a, v, start, end):
    '''
    A recursive function that constructs Segment Tree for list a.
    v is the starting node
    start and end are the index of array
    '''

    n = len(a)
    if start == end:
        t[v] = a[start]
    else:
        mid = (start + end) / 2
        build(a, v * 2, start, mid)     # v*2 is left child of parent v
        # v*2+1 is the right child of parent v
        build(a, v * 2 + 1, mid + 1, end)
        t[v] = min(t[2 * v], t[2 * v + 1])
    return t

print build([18, 17, 13, 19, 15, 11, 20], 1, 0, 6)

inf = 10**9 + 7


def range_minimum_query(node, segx, segy, qx, qy):
    '''
    returns the minimum number in range(qx,qy)
    segx and segy represent the segment index

    '''
    if qx > segy or qy < segx:      # query out of range
        return inf
    elif segx >= qx and segy <= qy:  # query range inside segment range
        return t[node]
    else:
        return min(range_minimum_query(node * 2, segx, (segx + segy) / 2, qx, qy), range_minimum_query(node * 2 + 1, ((segx + segy) / 2) + 1, segy, qx, qy))

print range_minimum_query(1, 1, 7, 1, 3)

# returns 13

Может ли это быть реализовано итеративно?

Источник

2 ответа

Решение

Выбор языка

Во-первых, вы, вероятно, никогда не пройдете грейдер, если будете использовать Python. Если вы посмотрите на статус всех прошлых решений здесь, http://www.spoj.com/status/GSS1/start=0, то увидите, что почти каждое принятое решение написано на C++. Я не думаю, что у вас есть выбор, кроме как использовать C++. Обратите внимание, что ограничение по времени составляет 0,115 с -0,230 с. Это ограничение времени "только для C/C++". Для задач, которые будут принимать решения на других языках, ограничение по времени будет "круглым" числом, например, 1 секунда. Python примерно в 2-4 раза медленнее, чем C++ в среде такого типа.

Проблемы реализации дерева сегментов...?

Во-вторых, я не уверен, что ваш код на самом деле строит дерево сегментов. В частности, я не понимаю, почему эта строка есть:

t[v]=min(t[2*v],t[2*v+1])

Я почти уверен, что узел в дереве сегментов хранит сумму своих дочерних элементов, поэтому, если ваша реализация близка к правильной, я думаю, что вместо этого следует прочитать

t[v] = t[2*v] + t[2*v+1]

Если ваш код "правильный", то я бы спросил, как вы находите максимальную сумму интервала в пределах диапазона [x_i, y_i] если вы даже не храните интервальные суммы.

Итеративное дерево сегментов

В-третьих, дерево сегментов может быть реализовано итеративно. Вот учебник на C++: http://codeforces.com/blog/entry/18051.

Сегментное дерево не должно быть достаточно быстрым для этого...

Наконец, я не понимаю, как дерево сегментов поможет вам решить эту проблему. Сегментное дерево позволяет запрашивать сумму диапазона в log(n), Эта проблема требует максимально возможной суммы любого диапазона. Я не слышал о дереве сегментов, которое допускает "запрос минимального диапазона" или "запрос максимального диапазона".

Наивным решением будет O(n^3) (попробуйте все n^2 возможных начальных и конечных точек и вычислите сумму в O(n) операциях) для 1 запроса. И, если вы используете дерево сегментов, вы можете получить сумму в O(log(n)) вместо O(n). Это только ускоряет вас до O(n^2 log(n)), что не может работать для N = 50000.

Альтернативный алгоритм

Я думаю, что вы должны смотреть на это вместо этого, который выполняется в O(n) для запроса: http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/. Напишите это на C / C++ и будьте эффективны с IO, как предложил один комментатор.

Источник

Вы можете попробовать с генераторами, так как вы можете обойти множество ограничений. Однако вы не предоставили набор данных, который ясно показывает ваши проблемы с производительностью. Можете ли вы предоставить проблемный набор данных?

Здесь вы можете попробовать:

t=[None]*2*7
inf=10**9+7

def build_generator(a, v, start, end):
    n = len(a)

    if start == end:
        t[v] = a[start]
    else:
        mid = (start + end) / 2
        next(build_generator(a, v * 2, start, mid))
        next(build_generator(a, v * 2 + 1, mid + 1, end))
        t[v] = min(t[2 * v], t[2 * v + 1])
    yield t



def range_minimum_query_generator(node,segx,segy,qx,qy):
    if qx > segy or qy < segx:
        yield inf
    elif segx >= qx and segy <= qy:
        yield t[node]
    else:
        min_ = min(
            next(range_minimum_query_generator(node*2,segx,(segx+segy)/2,qx,qy)),
            next(range_minimum_query_generator(node*2+1,((segx+segy)/2)+1,segy,qx,qy))
        )
        yield min_

next(build_generator([18,17,13,19,15,11,20],1,0,6))
value = next(range_minimum_query_generator(1, 1, 7, 1, 3))
print(value)

РЕДАКТИРОВАТЬ

На самом деле это не может исправить ваши проблемы. Существует еще один способ обойти любые ограничения рекурсии (как описано Д. Бизли в его учебнике по генераторам - https://www.youtube.com/watch?v=D1twn9kLmYg&t=9588s вокруг временного кода 2h00)

Источник
Другие вопросы по тегам