LINUX.ORG.RU

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

 dllist,


0

2

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

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

У меня реализация с 2-мя структурами данных: стек свободных элементов и кольцевой двухсвязный список, к которому есть отдельная переменная-указатель на ноду-голову списка (управляет добавлением новых элементов). «К голове» либо создаётся и привязывается новый узел (будущая голова), если ссылка на следующий элемент ведёт в NULL, либо происходит перезапись ссылки на данные в том элементе, на который голова указывает как на следующий и происходит смещение указателя головы на этот следующий элемент (за счёт этого старые данные по достижении границ буфера перетираются новыми).

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

Условно - если размер кольца 5 элементов, то на стеке изначально будут лежать : [4,3,2,1,0] - и первый pop возьмёт индекс 0, создаст в nodes_list[0] узел с NULL-ссылками на next и prev ноды.

Может, на Ruby что-то такое есть, например? Ну или ещё на каком языке с не-Rust и не-C++ подобным синтаксисом?

★★★★★

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

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

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

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

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

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

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

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

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

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

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

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

Фул-хаус!

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

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

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

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

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

ОК,

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

@l=(0..7)

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

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

splice @l, 3, 2;

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

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

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

DRVTiny ★★★★★
() автор топика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

KernelPanic
()
Последнее исправление: KernelPanic (всего исправлений: 3)
Ответ на: комментарий от DRVTiny

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

undef $array[$whatever]

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

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

KennyMinigun ★★★★★
()
Ответ на: комментарий от anonymous
splice @l, 3, 2, (undef) x 2;

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

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

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

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

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

anonymous
()

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

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

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

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

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

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

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

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

Прав был дед:

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

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

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

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

https://pastebin.com/fgEQZrkF

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

https://pastebin.com/fgEQZrkF

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

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

KernelPanic
()
Последнее исправление: KernelPanic (всего исправлений: 2)

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

anonymous
()

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

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

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

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

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

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

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

KennyMinigun ★★★★★
()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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