LINUX.ORG.RU

Кольцевой массив с доступом по диапазону индексов

 ,


0

1

Нужная такая структура данных. Массив фиксированной длины, с кольцевой индексацией. Из него надо делать выборку и добавление, но не по индексам а по диапазону индексов. Выборка означает получение суммы элементов от указанного до указанного. Добавление, ко всем элементам от указанного до указанного добавить указанное число. Эти две операции надо делать так быстро как возможно. Лишней памяти нет.

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

Есть еще какие-то интересные способы? Могу дать дополнительное условие, добавления не обязательно исполнять немедленно, можно накопить несколько и исполнить их все вместе.

Спасибо.

★★

дерево отрезков, дерево фенвика, да что угодно твоей фантазии

кольцевая индексация

просто считай сумму/прибавляй на двух отрезках в случае l > r

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

f1u77y ★★★ ()
Последнее исправление: f1u77y (всего исправлений: 3)

Как то так:

typedef struct
{
    int len;
    my_element_type_t * buf;
}
ring_buf_t;

//Переход через границу кольца:
i++;
i %= buff->len; //Len - длина массива.

Дальше сам.

shkolnick-kun ★★★★★ ()
Ответ на: комментарий от f1u77y

Дерево слишком сложно, вычислительно. Значительная часть запросов будет длины 1-3 элемента. Пока откатываюсь к тривиальной реализации. А для длинных запросов сумм надо будет наверно делать заранее рассчитанный массив сумм, с учетом выхода за границы, чтобы избавится от условий и разбиения отрезка на два.

amaora ★★ ()
Ответ на: комментарий от amaora

Значительная часть запросов будет длины 1-3 элемента.

так бы сразу и сказал, а то я думал, что длина запроса — O(N)

прибавление тоже на таких маленьких отрезках?

f1u77y ★★★ ()
Ответ на: комментарий от f1u77y

Да, но отрезки не всегда будут такими, могут увеличится до 30, но в этом случае можно ограничится только запросами суммы, а изменения вносить при длинах не больше 5 например. Общая длина пока предполагается 300-600 элементов. Памяти хватило бы и на 6k элементов и больше, но длины тогда станут больше, они считаются как доля от общей длины, а сама длина это лишь разрешение.

amaora ★★ ()
Ответ на: комментарий от amaora

хм, ну тогда можно просто считать суммы на префиксах, как ты и говорил с начала. а насчёт закольцовывания, можно добавить после массива его копию

f1u77y ★★★ ()

Если для некольцевой придумаешь, то для кольцевой потом тривиально. Если умеешь считать суммы всех элементов от нулевого до i-го(обозначи S(i)), то

сумма элементов от i до j-1 если i<j будет S(j)-S(i).

сумма элементов от i до j-1 если i>j (идем по кругу) будет S(n)-S(i)+S(j).

Короче говоря, смысл таков, что если придумаешь эффективную некольцевую структуру, то и для кольцевой все получится.

Waterlaz ★★★★★ ()
Ответ на: комментарий от amaora

Дерево слишком сложно, вычислительно. Значительная часть запросов будет длины 1-3 элемента. Пока откатываюсь к тривиальной реализации. А для длинных запросов сумм надо будет наверно делать заранее рассчитанный массив сумм, с учетом выхода за границы, чтобы избавится от условий и разбиения отрезка на два.

Тогда можно в двумерный массив элементы пихать. При этом запоминать сумму элементов в каждой строчке. Тогда доступ к единичному элементу будет лишь в два раза дольше, но гарантированно любая сумма будет считаться не дольше чем за sqrt(n).

ЗЫ можно элементы поместить в k-мерный массив и тогда доступ к единичным будет в k раз дольше, но любая сумма считаться за n^(1/k)+k

Waterlaz ★★★★★ ()
Ответ на: комментарий от shkolnick-kun

KISS

#define nelem(x) (sizeof(x) / sizeof((x)[0]))

int array[100];

int
sum(int from, int to)
{
        int i, n = 0;

        if (to > from)
                return 0;

        for (i = from; i <= to; i++)
                n += array[i % nelem(array)];

        return n;
}

PS: как же я давно C не трогал! ;)

beastie ★★★★★ ()
Последнее исправление: beastie (всего исправлений: 1)
Ответ на: комментарий от beastie
       if (to > from)
                return 0;

Так ведь в этом случае for и так ни разу не выполнится, n=0, и последний return все правильно отработает?

anonymous ()
Ответ на: комментарий от anonymous

Согласен. Привычка отсеивать corner-cases сыграла злую шутку. Там ещё и переполнение целого, но для демонстрации принципа это не важно.

beastie ★★★★★ ()
Последнее исправление: beastie (всего исправлений: 1)
Ответ на: комментарий от Waterlaz

Тогда можно в двумерный массив элементы пихать. При этом
запоминать сумму элементов в каждой строчке. Тогда доступ к
единичному элементу будет лишь в два раза дольше, но гарантированно
любая сумма будет считаться не дольше чем за sqrt(n).

Что-то не понял, как именно надо надо располагать элементы в двумерном массиве?

amaora ★★ ()
Ответ на: комментарий от amaora

Для n элементов заводишь массив m*m, где m=sqrt(n). Располагаешь подряд. То есть сперва заполняешь первую строчку, потом вторую итд. Считаешь суммы в каждой строке. Получается, что если тебе нужна сумма под диапазону, то те строки, которые в этот диапазон входят, уже пересчитывать не надо.

Waterlaz ★★★★★ ()

взять boost::ring_buffer (или как его там) отнаследовать, добавив операцию выборки n элементов

next_time ★★★★★ ()
Ответ на: комментарий от amaora

Тем не менее, тебе правильно подсказали про дерево фенвика (так называемое Binary Indexed Tree (BIT)). Можно организовать на нем и получение частичной суммы на интервале. Почему дерево сложно?

iVS ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.