Кольцевой двухсвязный список ограниченного размера

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

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

perldoc -f splice

Месье предлагает копировать память? Месье неправ.

это был коммент на конкретное ложное высказывание, а так в массиве скаляры по мегабайту чтоли? ну-ну.. splice-ом можно вставить undef вместо взятого элемента

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

Месье может представить себе список (массивов-то в Perl нет, но месье ещё не в курсе) в 10^5 элементов, из которого, из его середины, удаляют 2 элемента - после чего всё, что было выше этих 2-х элементов, копируется «на 2 элемента вниз по списку». Месье, однако, знает толк в извращениях. Предложите свою глубокую идею на собеседовании - вам сразу предложат 38000 в месяц на руки с испытательным сроком.

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

Фул-хаус!

К чему этот вымученный сарказм?

Сначала пишешь что Perl не умеет брать элементы из произвольной позиции массива, а теперь еще пишешь что есть списки, но нет массивов?.. - погугли чтоли «perl array list difference»

К тому же тебе написал, что splice позволяет заменить взятые элементы чем угодно, хоть undef-ами

ОК,

Дано: список в 8 (но может быть 10^8) элементов, называется @l

@l=(0..7)

Удаляем, положим, элементы за нумером 3 и 4.

Ты предполагаешь, что:

splice @l, 3, 2;

Это совершенно не то же самое, что и:

@l=(@l[0..2], @l[5..7]);

А на каком, собственно, основании? Есть некая секретная инсайдерская информация? :)

чтож, повторяю в 3-й раз:

splice @l, 3, 2, (undex) x 2;

undex -> undef

ТС, у тебя всегда какие-то вычурные вопросы. Если абстрагироваться от твоей конкретной задачачи (она нахер никому не интересна), то ты просишь показать реализацию удаления произвольного диапазона эелементов из массива. Если так, то, епта, тебе уже указали на функцию splice. Если ее тебе мало, можешь глянуть на всякие там List::MoreUtils::XS и проч. в том же духе. А ты начал лепить горбатого. Вот такие как ты «пионеры» слепят самопальную говняшку стандартных средств, а другим потом разгребать ваше «творчество»...

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

Я лишь упомянул о том, что хотелось бы смоделировать на Perl'е, потому что мне так проще.

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

Если абстрагироваться от твоей конкретной задачачи (она нахер никому не интересна)

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

И что мне даст замена на undef? Как мне потом, например, получить 5 элементов списка, начиная с N? Откуда мне знать, сколько после N будет «дырок»? И до какой степени фрагментации так вообще можно дойти?

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

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

Да ты, я смотрю, совсем упоротый...

Вопрос вообще был без привязки к конкретному ЯП.

1. Это не важно. Удалить диапазон из массива - распространенный случая для любого, относительно современного ЯП. Читай доки по стандартной билиотеке языка X.

Я лишь упомянул о том, что хотелось бы смоделировать на Perl'е, потому что мне так проще.

2. Любая твоя реализация проиграет splice'у сразу или в перспективе. Разве что какя-нибудь вучурная реализация вроде XS-модуля. Но, сдается мне, ты не осилишь низкоуровневую работу с памятью в C.

То, что она тебе неинтересна, старый ворчливый хрен, ещё не значит, что она не является абсолютно общей и встречающейся в каждой второй, если не в каждой первой программе

Ну чего ты тут так раскудахтался, петушок?! См. первый пукнт, анус поросячий.

Это даст неизменяемый размер массива и отсутствие сдвига при удалении - ты же сам приводил 10^8 элементов.

Дойти можно до любой степени фрагментации - всё в твоих мозгах.

Чувак, мне жаль, но «любого относительно современного» пишется вообще без запятой. А если уж ты так хотел обособить что-то (только в данном случае это неуместно ни разу) - то с 2-мя запятыми, да.

Давай ты мне расскажешь про стандартные библиотеки? Я прямо даже послушаю непременно. Вон в стандартной библиотеке Julia где такое? А в стандартной библиотеке Crystal? А между прочим это языки, которыми я активно пользуюсь, и мне-то, что характерно, в общем глубоко плевать, что ты о них думаешь. Чувак, ты видел 2 языка, оба интерпретируемых, и думаешь, что видел их все? Ну так я тебя разочарую.

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

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

Ну так splice, судя по всему, и не делает никаких сдвигов: ты пропустил что ли всё? Я же написал, что splice на минимум 2 порядка быстрее переформирования массива (пробовал на 100_000 элементов). Значит, да, он собственно и оперирует тем двусвязным списком, которым во внутреннем представлении является «массив» в perl'е.

https://docs.julialang.org/en/stable/stdlib/collections/#Dequeues-1

а ты как погляжу знаток Julia как и Perl-a

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

Купил на базаре ящик без инструментов, помогите слепить молоток.

Для меня важно, чтобы при достижении N элементов коллекции новые элементы затирали самые старые.

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

undef $array[$whatever]

Ну и потом проверять на defined, очевидно.

Или если вообще КРИТИЧЕСКИ необходимо именно удалять (А ИНАЧЕ ВИНДУЗЯТНИКИ ЗОХВАТЯТ ЛОР) тогда splice

splice @l, 3, 2, (undef) x 2;

Конечно TMTOWTDI, но я полагаю undef спокойно работает с array-slice

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

Значит, да, он собственно и оперирует тем двусвязным списком, которым во внутреннем представлении является «массив» в perl'е.

Зачем предполагать чушь, если можно почитать perldoc perlguts

Не читал выше написанное, зачем тебе стек?
Почему просто при «удалении» из середины буфера не перемещать его за последний занятый элемент в кольце?

Если делать undef - будет недетерминирована задача «взять N элементов начиная с X» - сколько нужно пропустить, когда будет следующий не undef? В конечном итоге это приведёт к работе со списком не in-place, а к работе с его отфильтрованными копиями.

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

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

Но тут я придумал простой обходной маневр: в этом случае нужно просто сделать полный сброс всей структуры на исходное состояние.

Прав был дед:

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. -- Donald Knuth

Перекладывай «упавшую» задачу (инкрементируя её счётчик попыток) снова в очередь и не морочь голову.

Пока реализовал в тестовом виде так:

https://pastebin.com/fgEQZrkF

Вообще тема интересна скорее с академической точки зрения.

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

Перекладывай «упавшую» задачу (инкрементируя её счётчик попыток) снова в очередь

Вообще речь была немного не о том, что делать с упавшими задачами :)

Классический пример, для которого нужна такая структура - это отправка сообщений об оперативном состоянии устройства в реальном времени (pub/sub):

1) Количество сообщений в очереди на отправку должно быть ограничено. В идеале даже не количеством слотов оно должно ограничиваться, а количеством памяти под структуру данных очереди

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

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

Как это всё учесть?

Ты знаешь какая сложность обращения по индексу у массива и у списка? Если да, то ты можешь несложным экспериментом доказать, что в перле в @ внутри список а не вектор :)

А если не знаешь, то наверное пришло время выяснить

Значит, да, он собственно и оперирует тем двусвязным списком, которым во внутреннем представлении является «массив» в perl'е.

https://github.com/Perl/perl5/blob/blead/av.h
https://github.com/Perl/perl5/blob/blead/pp.c#L5326

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

Вот! В том и суть, что я хотел бы это использовать не в Perl'и поверх статичных структур данных: у меня чётко ограничена память для всех компонентов структуры, кроме payload, для но его я не размещаю ни коим образом, я просто принимаю указать на данные, и он тоже фиксированной длины

массивов-то в Perl нет, но месье ещё не в курсе

да ты шо! пойди расскажи разработчикам perl

https://pastebin.com/fgEQZrkF

О ужс... Твой код жутчайщее говнище. Не выдерживает никакой критики, даже на уровне 'gentle' (man perlcritic, он расскажет какой ты лох).

Вот я про это и говорю. Что такие ушлепки как ты, понаговнокодят своих «тонких реализаций» стандартных средств (думая при этом, что они-то уже точно умнее всех буду, что их реализация зе бест). Но по факту выходит, что их поделия все кривые/косые и неработающие.

слив засчитан

man boost::circular_buffer<>

Воу, воу люди вы чего такие злые?
Напишите свои велосипеды, и _узбагойтесь_.
А то злые вы только потому, что своих велосипедов нет.

вовсе не злые мы
просто пока непонятно, что чувак хочет изобрести — MQ или ESB ?

взять N элементов начиная с X

А тебе оно нужно? Обойти никак?

Все что я хочу сказать — списки просто адски неоптимальны для работы кеша процессора. Даже копирование памяти дешевше.

Если splice не подходит по идейным соображениям, то взять https://metacpan.org/pod/List::DoubleLinked и при достижении макс. размера переписывать элементы с хвоста или головы

Твоего кода, чувак, вообще никто в глаза не видел. И звать тебя никак. А вообще когда hr'ы ищут что-нибудь по чувакам типа тебя - они как на красную тряпку реагируют на быдловатых гопников. Так что ты со своим средним образованием и высочайшим интеллектом, не позволяющим тебе общаться иначе как с использованием лексикона в 10 слов - шёл бы что ли на форум родной зоны по фене балакать.

Сорян, чувак. Я что-то погорячился. Нормальное это дело велосипедить. Сам частенько балуюсь подобным. Но код твой, если честно, далек от идеала.

Совет тебе от «хрыча», если позволишь, - юзай проверенные решения, меньше велосипедь и придерживайся best practices, по возможности. Это сэкономит кучу времени и нервов людям, кто будет вынужден поддерживать код после тебя.

За сим откланиваюсь, удачи!

шёл бы что ли на форум родной зоны по фене балакать.

Правильнее было бы сказать: «по фене ботать». Но это так, к слову. Может пригодится, если будешь в наших краях:).

Все-все, ухожу, удаляюсь...

Есть на го из стандартной библиотеки:

https://golang.org/src/container/ring/ring.go

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

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

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

В реализации на Perl нужны были бы просто: 1) список занятых слотов

2) стек свободных слотов

3) собственно набор слотов

И тогда алгоритм сводился бы в простейшем случае к:

При добавлении:

Если стек «номеров свободных слотов» не пуст - то вытолкнуть из этого стека один номер, втолкнуть его push'ем в список занятых слотов;

Если стек «номеров свободных слотов» исчерпан - сделать shift списка «занятых номеров», записать слот с полученным после shift номером ссылку на данные (перезаписав ту ссылку, которая там была раньше). После этого - остаётся впихнуть номер слота push'ем в «занятые», чтобы он стал в голову списка как «наисвежайший». Таким образом, элемент в хвосте «списка занятых номеров» переместится в его «голову».

При удалении: Просто делается push @stackFreeSlotNums, splice @listUsedSlotNums, $nStart, $amount;

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

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

Моя идея - в том, чтобы не пользуясь никакими магическими пассами с модификацией векторов (ОЗУ не может просто так «испариться» где-то в середине последовательности машинных слов) тем не менее реализовать возможность «удаления» элементов. Пока в моей задумке я вижу один очевидный недостаток: последовательный доступ к элементам двухсвязного списка конечно совсем не последователен - а это, как здесь правильно заметили, может здорово замедлить работу процессора с памятью.

Хотя конечно именно на Perl'е, если уж использовать «магические» преобразования векторов shift, push и splice, то можно и просто сам вектор слотов так на ходу преобразовывать: он же и есть внутри не вектор, а список...

Надо бы это на Crystal написать, да, а то так весь смысл идеи теряется.

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

Вообще ключевым в этой теме было замечание относительно того, что на Perl векторы - это вообще не векторы ни разу, а те же связные списки. И, думаю, даже если компилятор мог бы запросто понять заранее, что список не будет менять свои размеры - всё равно никаких StaticArray'ев он не сделает, поэтому оптимизации за счёт отсутствия изменений размеров списков довольно бесполезны.