RingBuffer реализация Java

Нужно реализовать что-то по типу структуры RingBuffer, но специфический, но я уставший.

Подскажите плиз, почему при полностью заполненом массиве, я уже не добавляю елементы по oldestElementIndex, а постоянно к index=0.

https://pastebin.com/RS0kdgB3

 

Логика получения oldestElementIndex на строке 26.

Зачем в методе setElement() ты обявляешь переменную oldestelementindex? 

•   if ((lastEntryIndex == data.length - 1) || !isFull()) {

 

            oldestEntryIndex = 0;

Проблема вот здесь.

Armagedonby_ZERGS сказал(а):↑

Зачем в методе setElement() ты обявляешь переменную oldestelementindex? 

•   if ((lastEntryIndex == data.length - 1) || !isFull()) {

            oldestEntryIndex = 0;

Проблема вот здесь.

Нажмите, чтобы раскрыть...

В плане зачем? Это так важно?)

MutedReported сказал(а):↑

В плане зачем? Это так важно?)

Нажмите, чтобы раскрыть...

Лишняя строчка кода

Armagedonby_ZERGS сказал(а):↑

Лишняя строчка кода

Нажмите, чтобы раскрыть...

я так привык, если нигде больше не понадобится, я ее уберу...)

 

Armagedonby_ZERGS сказал(а):↑

•   if ((lastEntryIndex == data.length - 1) || !isFull()) {

            oldestEntryIndex = 0;

Проблема вот здесь.

Нажмите, чтобы раскрыть...

А по конкретней?) 

MutedReported сказал(а):↑

Подскажите плиз, почему при полностью заполненом массиве, я уже не добавляю елементы по oldestElementIndex, а постоянно к index=0.

Нажмите, чтобы раскрыть...

Потому что вот это

Цитата:

 for (int i = 0; i < data.length; i++) {                 if (data == null) {                     data = element;                     lastEntryIndex = i;                     break;                 }             }

Нажмите, чтобы раскрыть...

Выполнится только единожды.

Ринг буфер пишется с двумя указателями (в жабе индексами) на первый и последний елемент, и они просто инкрементируются по вызову get/set

Java нету, на на питоне подход думаю понятен будет

Цитата:

class Ring:
    def __init__(self, l):
        self.l = l
        self._tail = l
        self._head = 0
        self.data = [None] * self.l
    def get(self, value):
        self._tail = (self._tail+1) % self.l
        self.data[self._tail] = value
    def set(self):
        self._head = (self._head + 1) % self.l
        return self.data[self._head]
    @property
    def lenght(self):
        return self.l
    @property
    def is_full(self):
        return self._head == self._tail
    def resize(self, new_l):
        new = [None] * new_l
        new[:len(self.data)] = self.data[:]
        self.data = new
        self.l = new_l

Нажмите, чтобы раскрыть...

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

Вообще я конечно не эксперт, но кольца это больше для каких-нибудь низкоуровневых сей. Зачем, если есть очереди и прочие ГОТОВЫЕ решения?

Salovar сказал(а):↑

Вообще я конечно не эксперт, но кольца это больше для каких-нибудь низкоуровневых сей. Зачем, если есть очереди и прочие ГОТОВЫЕ решения?

Нажмите, чтобы раскрыть...

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

saw_tooth сказал(а):↑

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

Нажмите, чтобы раскрыть...

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

saw_tooth сказал(а):↑

Потому что вот это

Выполнится только единожды.

Ринг буфер пишется с двумя указателями (в жабе индексами) на первый и последний елемент, и они просто инкрементируются по вызову get/set

Java нету, на на питоне подход думаю понятен будет

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

Нажмите, чтобы раскрыть...

Я +- понял как работает эта структура, хоть и любые статьи по алгоритмам для меня это вырви глаз, мозг, нервы))

 

Salovar сказал(а):↑

Вообще я конечно не эксперт, но кольца это больше для каких-нибудь низкоуровневых сей. Зачем, если есть очереди и прочие ГОТОВЫЕ решения?

Нажмите, чтобы раскрыть...

Да нет, вот у меня задача - 1ый запрос получает создает большое количество объектов, а 2ой запрос читает потом стату по ним за последнюю минуту(а так как старые данные уже не нужны, мне нет смысла расширять память для мусора). То-есть скармливать обычной структуре - память растет. А нужна такая структура, которая позволяет с О(1) памятью работать с большим количеством транзакций вне зависимости от количества этих данных.

 

Ну и мне же не нужен прям точь в точь этот алгоритм.  Я делал под свою задачу.

saw_tooth сказал(а):↑

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

Нажмите, чтобы раскрыть...

Я не новичек , просто код на коленке, оторванный от жизни, чтобы понять как это будет выглядеть)

 

MutedReported сказал(а):↑

Я +- понял как работает эта структура, хоть и любые статьи по алгоритмам для меня это вырви глаз, мозг, нервы))

 

Да нет, вот у меня задача - 1ый запрос получает создает большое количество объектов, а 2ой запрос читает потом стату по ним за последнюю минуту(а так как старые данные уже не нужны, мне нет смысла расширять память для мусора). То-есть скармливать обычной структуре - память растет. А нужна такая структура, которая позволяет с О(1) памятью работать с большим количеством транзакций вне зависимости от количества этих данных.

 

Ну и мне же не нужен прям точь в точь этот алгоритм.  Я делал под свою задачу.

Я не новичек , просто код на коленке, оторванный от жизни, чтобы понять как это будет выглядеть)

 

Нажмите, чтобы раскрыть...

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

MutedReported сказал(а):↑

Я +- понял как работает эта структура, хоть и любые статьи по алгоритмам для меня это вырви глаз, мозг, нервы))

 

Да нет, вот у меня задача - 1ый запрос получает создает большое количество объектов, а 2ой запрос читает потом стату по ним за последнюю минуту(а так как старые данные уже не нужны, мне нет смысла расширять память для мусора). То-есть скармливать обычной структуре - память растет. А нужна такая структура, которая позволяет с О(1) памятью работать с большим количеством транзакций вне зависимости от количества этих данных.

 

Ну и мне же не нужен прям точь в точь этот алгоритм.  Я делал под свою задачу.

Я не новичек , просто код на коленке, оторванный от жизни, чтобы понять как это будет выглядеть)

 

Нажмите, чтобы раскрыть...

Хз. По-моему ты выбрал не самое логичное и подходящее решение своей задачи

MutedReported сказал(а):↑

Да нет, вот у меня задача - 1ый запрос получает создает большое количество объектов, а 2ой запрос читает потом стату по ним за последнюю минуту(а так как старые данные уже не нужны, мне нет смысла расширять память для мусора). То-есть скармливать обычной структуре - память растет. А нужна такая структура, которая позволяет с О(1) памятью работать с большим количеством транзакций вне зависимости от количества этих данных.

Нажмите, чтобы раскрыть...

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

2. Если 2-й запрос зависит от первого, типа (аналог чата) прочли идшники сообщений 1-м и загрузили сообщения вторым, то логичнее делать кольцо с FILO с контролем времени при добавлении. Понадобится как хранилище вектор. Показываю:

Цитата:

class Item:
    data: str
    timestamp: datetime
class Ring2:
    PRELOAD = 5
    def __init__(self, t_cutoff):
        self.t_cutoff = t_cutoff
        self.data = [] * self.PRELOAD
    def get(self) -> Item:
        return self.data.pop()
    def set(self, v: Item):
        # тупой перебор
        now = datetime.now().timestamp()
        for k, i in enumerate(self.data):
            if now - i.timestamp.timestamp() > self.t_cutoff:
                self.data.pop(k)
        # можно через фильтр
        self.data = list(filter(lambda x: now - i.timestamp.timestamp() < self.t_cutoff, self.data))
        # можно через while, учитывая что все елементы упорядочены по времени
        i = 0
        while now - self.data.timestamp.timestamp() > self.t_cutoff:
            self.data.pop(i)
        return self.data.pop()
    @property
    def lenght(self) -> int:
        return len(self.data)

Нажмите, чтобы раскрыть...

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

Мой пример использует просто массив что бы ты понял логику.

MutedReported сказал(а):↑

Я не новичек

Нажмите, чтобы раскрыть...

Не новички знают как написать кольцевой буфер, не надо мне врать.

saw_tooth сказал(а):↑

Не новички знают как написать кольцевой буфер, не надо мне врать.

Нажмите, чтобы раскрыть...

Ты что мне папа, что я тебе вру?

Ты что-то путаешь))) Что для тебя не новичек? 10 лет опыта решений хакерранка?)

Salovar сказал(а):↑

Хз. По-моему ты выбрал не самое логичное и подходящее решение своей задачи

Нажмите, чтобы раскрыть...

Я уже полностью переделываю, забейте)

saw_tooth сказал(а):↑

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

2. Если 2-й запрос зависит от первого, типа (аналог чата) прочли идшники сообщений 1-м и загрузили сообщения вторым, то логичнее делать кольцо с FILO с контролем времени при добавлении. Понадобится как хранилище вектор. Показываю:

Цитата:

class Item:
    data: str
    timestamp: datetime
class Ring2:
    PRELOAD = 5
    def __init__(self, t_cutoff):
        self.t_cutoff = t_cutoff
        self.data = [] * self.PRELOAD
    def get(self) -> Item:
        return self.data.pop()
    def set(self, v: Item):
        # тупой перебор
        now = datetime.now().timestamp()
        for k, i in enumerate(self.data):
            if now - i.timestamp.timestamp() > self.t_cutoff:
                self.data.pop(k)
        # можно через фильтр
        self.data = list(filter(lambda x: now - i.timestamp.timestamp() < self.t_cutoff, self.data))
        # можно через while, учитывая что все елементы упорядочены по времени
        i = 0
        while now - self.data.timestamp.timestamp() > self.t_cutoff:
            self.data.pop(i)
        return self.data.pop()
    @property
    def lenght(self) -> int:
        return len(self.data)

Нажмите, чтобы раскрыть...

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

Мой пример использует просто массив что бы ты понял логику.

Нажмите, чтобы раскрыть...

Спасибо за примеры

MutedReported сказал(а):↑

Ты что мне папа, что я тебе вру?

Ты что-то путаешь))) Что для тебя не новичек? 10 лет опыта решений хакерранка?)

 

Я уже полностью переделываю, забейте)

 

Спасибо за примеры

Нажмите, чтобы раскрыть...

Не, ну ты спросил, я высказал свое мнение