Вопрос к алгоритмистам

кольцевой буфер + курсор на текущую ячейку

Когда же вы уже по-русски сможете писать, что хотите.

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

Как ты будешь произвольно удалять элементы не получая в итоге время N?

Что тут непонятно? Ну ок специально для тебя напишу что мне нужен пример эффективной реализации такого функционала

Как ты будешь произвольно удалять элементы не получая в итоге время N?

А где это в условиях задачи было? Если кольцевой буфер - это двухсвязный список, то в чем проблема извлечь любой элемент вне зависимости от других элементов. Или имеется ввиду, что на входе - номер элемента?

то есть любой элемент можно извлечь вне зависимости от других элементов - это в условии, а вот пример с проблемой массив на 5 элементов заполнен следующим образом 1___5 _ это типо удаленный элемент, здесь самый старый это 1 и нам нужно добавить новый после 5, смещать 1 к 5 не вариант так как там может стопицот чисел

А связный список не вариант

Так как доступ к произвольному элементу в таком списке сам по себе может быть N

А если делать ассоциативный массив где ключ это номер элемента а значение указатель, то проблема во времени работы уже с ассоциативны массивом

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

КОльцевой буфер хорош если только добавляем (на место самого старого элемента), а вот как в его случае учитывать свободные места от удаленных элементов?

Наск я понял задачу, порядок следования элементов не важен (т.е. это коллекция).

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

И нужно с каждым элементов ассоциировать время добавления. Когда массив забивается, сортируем массив по времени добавления (или не массив а таблицу времен) и переходим к кольцеовму буфеур с курсором. Как только кого то удалили - переходим к пред. режиму.

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

А что ключем то является???

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

Ключ Id элемента

КОльцевой буфер хорош если только добавляем (на место самого старого элемента), а вот как в его случае учитывать свободные места от удаленных элементов?

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

Выше прочти я писал почему нельзя просто перетирать

Как ты будешь произвольно удалять элементы не получая в итоге время N?

а где у тебя в постановке задачи написано про удаление элементов?

Ну под извлечением я имел ввиду удаление

Просто когда говорят и стеках и очередях и тд то при получении доступа к элементу он автоматически удаляется из этой структуры, ну я это всегда подразумеваю

<sarcasm>а под массивом ты не имел в виду многомерное kd-дерево?</sarcasm>

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

Просто когда говорят и стеках и очередях

но ты же про них не говорил, у тебя там написано - массив, нет?

массив это довольно абстрактное понятие

вполне себе конкретное понятие

а вообще, с учетом выяснившегося, я бы ввел понятие пустой ячейки и просто перетирал бы извлекаемый элемент пустой ячейкой

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

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

тогда у меня там будет список

Ну и как ты поступишь в случае который я описал выше массив 1___5 там где подчеркнуто это пусто, 1 самый старый 5 самый молодой элемент, добавь без нарушения логики работы и перемещений еще один элемент и тогда да, задача решена очень просто очень эффективно

Что тут непонятно?

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

Ну ок специально для тебя напишу что мне нужен пример эффективной реализации такого функционала

Какого еще функционала?

массив это группа как-то связанных между собой элементов

не-не-не, не «как-то связанных между собой», а вполне определенным образом расположенных в памяти элементов, а именно подряд

Ок список, произвольный доступ тогда долгий

Что значит добавить эелемент? Указать пару (ключ, значение) или что?

То есть список это уже не массив?

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

То есть список это уже не массив?

конечно, список - это не массив, как минимум у них разная семантика использования, для типа список не определена, например, операция достать n-ный элемент

PS и это не важно, что список может быть реализован на основе массива

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

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

1) надо определить что есть «время работы»
2) надо выбрать все же критерий - «время поиска» или «время работы», сейчас указано неконкретно, и это 2 разные задачи

Нууу ок, ты используешь слово массив в частном случае(а именно тех массивов с которыми мы знакомились когда начинали кодить), хотя забываешь что на жестких дисках давным давно инфа читалась последовательно, то есть нельзя начать читать файл с середины, и тогда всё равно применялся термин массив данных, хотя технически это частный случай списка

Нууу ок, ты используешь слово массив в частном случае(а именно тех массивов с которыми мы знакомились когда начинали кодить), хотя забываешь что на жестких дисках давным давно инфа читалась последовательно, то есть нельзя начать читать файл с середины, и тогда всё равно применялся термин массив данных, хотя технически это частный случай списка

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

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

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

ок... решение: любая структура данных на твой вкус(красно-черное дерево?) + очередь элементов для удаления при переполнении.

Асимптотически лучше решение сделать нельзя, как нетрудно доказать.

Вопрос к алгоритмистам ......бла-бла-бла......я знаю решение со средним временем поиска равным константе.

ожидаешь что подскажут решение с 0 временем? :-)

я устал печатать с планшета

а ты сразу нормально пиши, ты думаешь это интересно играть в ребусы с тобой?

вот ты сейчас обозвал функции сигналами - с какой целью тиы это сделал, чтобы подчеркнуть, что мы рассмариваем некоторую асинхронную модель, так это надо понимать?

Да асинхронную, это так правдоподобно в данном случае лойс

В точку ;)

0 время - это если линковать с libastral.so; тогда результат функции появляется непосредственно перед её вызовом

Ага, только как ты собрался удалять произвольные элементы из очереди? В этом вся проблема. И причем тут rd-tree когда map из stl и так его использует, а произвольный доступ так рука-лицо

Ага точно) а скачать эту либо можно с astral.ru да?)