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

libastral

Ага, только как ты собрался удалять произвольные элементы из очереди? В этом вся проблема.

Значит, сделай двусвязный список. А в красно-черном дереве ссылка на элемент в списке.

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

И что с того, что использует?

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

Значит, сделай двусвязный список.

у него в задаче написано «массив фиксированного размера», я не знаю почему он это игнорирует

А двусвязный список не может быт ограничен?

Ну то, что хеш мапа быстрее будет при случайном доступе к элементу)

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

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

А двусвязный список не может быт ограничен?

ограничен != фиксированного размера

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

ммм?

Могу предположить, что изобретение чего-то принципиально нового потянет на научное достижение

проблема, на мой взгляд, в том, что путем не обращения внимания на «несущественные детали» задача была переформулирована в нечто непонятное

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

Почему не константное? Время добавления в кольцевом буфере всегда будет равно времени выполнения операции:

• Переместить указатель на следующий элемент в кольце (тем самым, самый старый элемент будет перезаписан)
• записать данные по новому указателю

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

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

• cur_ptr = cur_ptr - start_ptr + index % queue_size
• чтение данных по новому указателю

Но, здесь появится фрагментация, как сказал Onito, плюс, изменить длину очереди динамически сложнее

Явная задачка с собеседования.

Если говорить человеческим языком:

Смоделировать в массиве двусвязный список. Эффективно решить проблему отслеживания пустых ячеек.

А зачем произвольный доступ если удаление объекта делает невалидными все id объектов лежащих следом? По какому ключу доступ то будет?

Плюсую.

Хранить индексы самого старого и самого нового элементов, у каждого элемента хранить индексы предыдущего и следующего. Хранить индексы начала и конца списков пустых элементов (для поиска пустой ячейки за О(1) при вставке). Т.о. в массиве будет два списка: пустые и непустые элементы. Вставка-удаление делаются так же, как у двусвязного списка, при этом элементы просто перекидываются между списками пустых и заполненных. Выборка элемента по индексу - как у массива, за О(1).

Замени индекс на пойнтер - и вот уже не нужен массив. Или я неправильно понял задачу?

Каждый понял задачу по своему. Если не можете нормально сформулировать задачу не надо пушить тут хвост.

Проблема у человека с изложением своих мыслей, бывает. А хочет он список с произвольным доступом. Нечто подобное видел у интела, наработки по стеками и спискам с произвольной выборкой.

Доступ по номеру элемента? Ну так в общем случае это быстро не будет. Но мне кажется он другого хочет...

ну можешь её запомнить для собеседования, я её сам придумал :)

ладно ещё раз сформулирую задачу на примере: в некоторую структуру данных элементы могут удаляться с одного конца и добавляться только с другого конца, так же мне нужно в случае когда число элементов достигает определённого числа сбрасывать самый «старый» на данный момент времени элемент, и таким образом появится место для нового. Решение этой задачи с условием что доступ к элементам только на концах это очередь. Простая очередь решает эту задачу. Теперь изменим условие: элементы могут удаляться из любой части структуры данных, а как они будут добавляться нужно уже указать в процессе решения задачи. На этот раз лучше описал задачу? :)

да и эффективность решения задачи с новым условием должна стремиться к эффективно решения задачи со старым условием

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

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

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

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

осиль уже русский язык, наконец.

Сумбур в твоей голове, я не предлагал решение. Я сформулировал краткое ТЗ. И правда плохо говорить умеешь.

Массив + двусвязный список по времени + список свободных

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

в чём проблема написать для списка аллокатор, который будет размещать элементы компактно?

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

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

сложность удаления из «списка по времени»?

ну опиши решение с отметками

краткое тз это где двусвязный список с произвольным доступом? Я написал почему не стал выносить в условие этот список, а напиши я «структура данных» мне скажут юзай вектор там произвольный доступ О(1)

сложность удаления из «списка по времени»?

O(1) - просто удаляем из головы/хвоста. При добавлении элемента в массив, добавляем его с головы списка по времени, при удалении - удаляем с хвоста. Всегда доступ только к 1 элементу.

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

кури амортизацию

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

например_например:: обычный кольцевой буфер с затиранием и двухсвязностью(это для произвольных удалений) ну и некая перекошенность(splaine? спискота древесина) для постепенного(через амортизация) дороговизны поиска худшего варианта при обычном кольцевом буфере.

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

до слова перекошенность я понял :) на таком подходе и остановлюсь в итоге, а что после слова перекошенность можешь написать подробнее?

То, что ты хочешь, называется LRU Cache. Есть масса готовых реализаций на любом языке программирования. Для начала погугли и почитай, как оно бывает устроено.

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

http://habrahabr.ru/post/136758/ первый коммент:А чем двусвязный список + hash не угодил, зачем хранить время? Вот это решение тут и предлагали. А наиболее эффективная реализация как предлагал товарищ qulinxao

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

хорошее обращение, да

отвечу в твоём духе: посмотри на планировщик задач в ядре или продвинутые сборщики мусора.

удаляем из середины... ?

могу.

(тут выше картинка сравнений и там имя списки пропусков)

вот можно например декартовым_деревом? отслеживать количество использованных буфером элементов среди всех ячеек массива_пула.

тогда все действия logn получаются .

дерево фенвика в смысле - т.е с его помощью двухсвязный список идёт лесом

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

упоролся? удаление элемента из середины — перестроение всего дерева

там log n битовых.

дерево используется поверх памяти а не буфера

в дереве счётчики сколько в данной (кратной степени двойки) области элементов занятато буфером в самом низу это по сути флаги занята или нет ячейка- т.е это можно не хранить а извлекать разности - иначе требования к памяти не N-счётчиков а 2N

тогда любое удаление/добавление затрагивает не более logn счётчиков.

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

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

т.е или спискоту добавить - для облегчения поитеров на голову-хвост либо интенсивно через суммы каждый раз за logn находить где находится текущий buf(k) элемент а для получения места для вставки запрашивать buf((t+1)mod N) где t уже сколько элементов в структуре.