Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Да нет, тут сложнее. Напишет он или нет, и если напишет , то что именно — этого я не знаю. Но для него код действительно ужасный. Вот если бы я употребил бы template, перегрузил бы какие-то операторы, сделал бы какой-нибудь итератор, прицепил xyz_ptr и zyx_cast и т.д. — тогда его бы устроило. А когда пишется просто и коротко — это ужасно.
нет, совсем не так.
я хочу чтобы из Reverse были вытащены функции типа head, tail, add, и чтобы Reverse была написала в терминах этих операций, а не состояла их непонятных присваиваний
т.е. я хочу чтобы код был читаемым текстом, типа такого:
void Reverse()
{
List reversedList;
while (ListElement* head = sliceHead())
reversedList.prepend(head);
*this = reversedList;
}
ListElement* sliceHead();
void prepend(ListElement*);
Здравствуйте, vdimas, Вы писали:
I>>Про что и речь — сейчас почти любой проект на С++ это в т.ч. написание всевозможных аллокаторов. V>Кстате, страничный аллокатор или пул объектов — неплохая тестовая задачка для студента или вчерашнего студента. Как раз ему на час-другой работы. V>Попробуй сам да замерь время. При том, что ты давно не брал плюсов в руки, вряд ли у тебя на это уйдет более часа. Т.е. рассуждать даже не о чем.
Решение проблемы с фрагментацией не сводится к написанию аллокатора, это всего лишь необходимая часть. Вопрос — какое условие будет необходимым и достаточным ?
Здравствуйте, Ikemefula, Вы писали:
I>Очевидно — нет. Резерв нужен для экономии физической памяти, она всегда сильно ограничена, а следовательно и для перформанса, иначе своп будет работать постоянно. I>Есть такое соображение — большие блоки очень часто незаполнены до конца. Резерв экономит вагоны физической памяти, а само выделение ускоряется до безобразия.
Во-первых, виндовая куча никаких резервов не делает, она даёт тебе память, а не АП, в которое ты можешь коммитить память...
Так что в сценарии с GC, кучей, std::vector'ом и листом это всё мимо.
Во-вторых, возьми и попрофилируй, что ли. Когда ты память комитишь, она всего лишь получает логическую связь и всё, какие-то реальные действия, вроде зануления новых страниц происходят только при ОБРАЩЕНИИ, так что что так, что сяк всё довольно быстро, пока ты писать/читать саму память не начал...
I>Ты путаешь адресное пространство и память. Когда процесс создан, не надо в нем выделять АП, его винда для тебя выделила — 2гб. Делай с ним что хочешь.
Ну так VA выделяет диапазоны АП на разные нужды внутри процесса.
И кстати, попробуй понять, что я не путаю память и АП. Память -- это то, что ты получаешь из общесистемного пула, когда делаешь комит, а АП -- это то, что ты получаешь, из ассоциированного с процессом пула, когда делаешь резёрв...
I>Резервировать АП != выделять АП.
Почему? Это, похоже, какой-то терминалогический спор...
I>Системные пусть живут сами по себе. А вот приложение может выделять как угодно.
Так они распределяют ОДНО И ТО ЖЕ АП же?..
ну и потом, в приложении бывает несколько независимых компонент...
I>И долго ты до этого доходил ?
Что тебе лично ничегоне поможет? Ну в целом я до последнего надеялся, что ты не безнадёжен, но факты вещь упрямая...
I>Не знаю. 0.5 гига это смотря как выделялось. Иногда сверх этого можно выделить всего 300мб, а иногда и до 400-600, а иногда и больше гига. Иногда — 0. Вот такой вот парадокс. Если вообще все хорошо — то как в С++, исключая 200мб — издержки на все менеджед расходы.
А что значит "всё хорошо"?
I>Ты пойми простую вещь — нативные модули едят АП, нативные функции едят АП, сборки едят АП, джыт ест АП, GC сам ест АП, нативные потоки едят АП, CRL и тот ест АП, интероп снова ест АП.
Я-то, как раз, это понимаю. И они все распредеяют поедаемое АП через механихм его аллокации, доступный пользовательскому коду через VA. Я так и не понял, GC большие куски только в своих банках выделяет или умеет сразу по VA кусать?
I>Поэтому для большого х32 приложения, где все намешано, больше чем на 1гб памяти под твои объекты можно не надеяться, хотя все АП 2гб. Дальше надо вычитать все издержки на фрагментацию и имеющиеся расходы. Что в итоге — не ясно.
То есть типичной картины вообще нет? Для меня это странно
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Это понятно и где и когда и почему же. Это когда что-то тяжёлое и для этого не предназначенное тянут за каким-то хреном инпроц в свой АП...
Нужно искать баланс между стоимостью, сложностью и надежностью. Разносить по разным процессм простые операции — получается целая куча неустранимых проблем. Можешь на хром посмотреть.
I>>Пол-мега может быть, а может и не быть. Именно пол-мега — это редкий случай, практически вырожденый, но я встречал и такие, при чем, что интересно, в коде 3rd party с которыми приходилось иметь дело.
E>А зачем ты лез в АП столь плотно заоптимизированного кода?
Для того, что бы устранить ООМ на конкретных рабочих сценариях приложения.
Здравствуйте, Erop, Вы писали:
I>>Очевидно — нет. Резерв нужен для экономии физической памяти, она всегда сильно ограничена, а следовательно и для перформанса, иначе своп будет работать постоянно. I>>Есть такое соображение — большие блоки очень часто незаполнены до конца. Резерв экономит вагоны физической памяти, а само выделение ускоряется до безобразия.
E>Во-первых, виндовая куча никаких резервов не делает, она даёт тебе память, а не АП, в которое ты можешь коммитить память...
Ты же сам сказал про резерв. Я указал тебе для чего он нужен.
E>Ну так VA выделяет диапазоны АП на разные нужды внутри процесса.
Она ничего не выделяет, все уже выделено. Она тупо _резервирует_.
E>И кстати, попробуй понять, что я не путаю память и АП. Память -- это то, что ты получаешь из общесистемного пула, когда делаешь комит, а АП -- это то, что ты получаешь, из ассоциированного с процессом пула, когда делаешь резёрв...
АП не надо получать, оно уже есть. На него можно отобразить память или резерв. А можно и просто так и использовать , если тебя устраивает AV
I>>Не знаю. 0.5 гига это смотря как выделялось. Иногда сверх этого можно выделить всего 300мб, а иногда и до 400-600, а иногда и больше гига. Иногда — 0. Вот такой вот парадокс. Если вообще все хорошо — то как в С++, исключая 200мб — издержки на все менеджед расходы.
E>А что значит "всё хорошо"?
"близко к идеальному", значит все предыдущие аллокации находятся одной пачкой или близко к этому, чего как правило никогда не бывает.
I>>Ты пойми простую вещь — нативные модули едят АП, нативные функции едят АП, сборки едят АП, джыт ест АП, GC сам ест АП, нативные потоки едят АП, CRL и тот ест АП, интероп снова ест АП. E>Я-то, как раз, это понимаю. И они все распредеяют поедаемое АП через механихм его аллокации, доступный пользовательскому коду через VA. Я так и не понял, GC большие куски только в своих банках выделяет или умеет сразу по VA кусать?
Это совершенно не важно, когда он мапит страницы. И для С++ тоже неактуально.
I>>Поэтому для большого х32 приложения, где все намешано, больше чем на 1гб памяти под твои объекты можно не надеяться, хотя все АП 2гб. Дальше надо вычитать все издержки на фрагментацию и имеющиеся расходы. Что в итоге — не ясно.
E>То есть типичной картины вообще нет? Для меня это странно
Ты наверное читать разучился. Большое х32 приложение само по себе нетипичный случай. Типичный под-случай для нетипичного случая — это нонсенс !
Здравствуйте, Ikemefula, Вы писали:
I>Она ничего не выделяет, все уже выделено. Она тупо _резервирует_.
В смысле? Вот у процесса есть пул доступных пользовательскому коду адресов. Обычно это немного меньше 2 Гб, VA по запросу на резёрв выделяет из этого пула диапазоны адресов для запросивших их сервисов. Что тебе тут кажется странным?
I>АП не надо получать, оно уже есть. На него можно отобразить память или резерв. А можно и просто так и использовать , если тебя устраивает AV
Ну и память не надо получать, она тоже уже есть, в компьютере/ОС. Аллокаторы просто распределяют ресурс из некоторого пула, который где-то уже есть, иногда, правда, ещё умеют запросить расширения пула за счёт аллокатора ещё чего-нибудь. Куча может запросить ещё одну банку памяти через VA у ОС, ОС может запросить расширение файла подкачки и т. п.
I>Это совершенно не важно, когда он мапит страницы. И для С++ тоже неактуально.
Чего? При чём тут страницы-то? Ты вообще про какое АП? Про логическое или про физическое?
Дотнетовский GC что ли на уровне мапинга страниц работает?
I>Ты наверное читать разучился. Большое х32 приложение само по себе нетипичный случай. Типичный под-случай для нетипичного случая — это нонсенс !
Если речь про иникальные расклады, то я не понимаю наезда на лист, с которого ты начал этот топик...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
I>>Она ничего не выделяет, все уже выделено. Она тупо _резервирует_. E>В смысле? Вот у процесса есть пул доступных пользовательскому коду адресов. Обычно это немного меньше 2 Гб, VA по запросу на резёрв выделяет из этого пула диапазоны адресов для запросивших их сервисов. Что тебе тут кажется странным?
Ничего.
I>>АП не надо получать, оно уже есть. На него можно отобразить память или резерв. А можно и просто так и использовать , если тебя устраивает AV
E>Ну и память не надо получать, она тоже уже есть, в компьютере/ОС. Аллокаторы просто распределяют ресурс из некоторого пула, который где-то уже есть, иногда, правда, ещё умеют запросить расширения пула за счёт аллокатора ещё чего-нибудь. Куча может запросить ещё одну банку памяти через VA у ОС, ОС может запросить расширение файла подкачки и т. п.
АП уже выделено, расслабься.
I>>Это совершенно не важно, когда он мапит страницы. И для С++ тоже неактуально. E>Чего? При чём тут страницы-то? Ты вообще про какое АП? Про логическое или про физическое? E>Дотнетовский GC что ли на уровне мапинга страниц работает?
Удивляюсь, как ты умеешь прочесть вот так вот
I>>Ты наверное читать разучился. Большое х32 приложение само по себе нетипичный случай. Типичный под-случай для нетипичного случая — это нонсенс !
E>Если речь про иникальные расклады, то я не понимаю наезда на лист, с которого ты начал этот топик...
В нетипичных х32 приложениях которых где то пятая часть от всех, добавление в лист без задания капасити случается довольно часто.
Здравствуйте, Ikemefula, Вы писали:
I>АП уже выделено, расслабься.
В каком смысле "выделено"? Это же просто отрезок натурального ряда?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
A>нет, совсем не так.
A>я хочу чтобы из Reverse были вытащены функции типа head, tail, add, и чтобы Reverse была написала в терминах этих операций, а не состояла их непонятных присваиваний
Ну да, я примерно это и имею в виду. Только ошибся в наборе элементов. Для реализации двух простых действий ты требуешь написать обязательно head, tail , выделить add и т.д. Потом понадобится выделить итератор все же, или же придется внутри класса сделать next, а это, разумеется, вызовет твою критику (на этот раз справедливую), что итерация в списке не реализована итератором, а находится в самом списке и т.д.
Кстати, насчет add. Вообще-то add есть — AddToBegin. Только вот использовать ее явно при реверсе нельзя, так как она элемент в список добавляет, то есть new ListElement делает, а при Reverse никаких новых ListElement делать не надо. И вообще этот Reverse плохо укладывается в основные примитивы работы со списком, так как по сути "крадет" из одного списка ListElement вместе с его содержимым и переносит этот ListElement в другой список. Обычно класс списка экспонирует интерфейс, в котором фигурируют элементы данных, а не "кирпичики списка" , и это верно, так как нечего показывать внутренние детали наружу. Но я и не показываю.
A>т.е. я хочу чтобы код был читаемым текстом, типа такого:
<skipped>
Такое написать, конечно, можно, только вот код по манипуляциям с next и прочую игру с указателями все равно никуда не денешь, потому что это делать все равно придется. Может, код от этого станет более читаемым (для тебя), ну а ИМХО он и так вполне понятен, если просто посмотреть, что именно там делается.
А впрочем... Давай, допиши свой код до рабочего. Условия знаешь
1) при реверсе никаких new и вообще выделений памяти O(N) где бы то ни было и как бы то ни было.
2) однопроходной по исходному списку алгоритм.
Мой код рабочий. Можешь взять мою тестовую программу. Допиши, посмотрим, насколько это будет понятнее
Здравствуйте, Ikemefula, Вы писали:
I>Правильно. Потому и не надо ничего выделять. Можно отпамить часть АП и этог мапинг оформить нужным образом.
а можно просто зарезервировать, а потом закомитить...
В любом случае разные сервисы запрашивают диапазоны АП через VA или более низкоуровневый аналогичный интерфейс, к тому же самому аллокатору диапазонов АП, и получают или не получают их для использования под свои цели.
Почему идея аллокатора АП кажется тебе странной? В принципе любой аллокатор просто распределяет ресурс из пула же, хоть память, хоть место в файле, хоть ноды списка, хоть диапазоны АП -- разница невелика.
В случае с АП есть особенность, что пул не может расти, ну так он ещё и во многих иных сценариях не может расти же.
Я вообще перестал понимать суть твоей аргументации.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Abyx, Вы писали:
A>я хочу чтобы из Reverse были вытащены функции типа head, tail, add, и чтобы Reverse была написала в терминах этих операций, а не состояла их непонятных присваиваний
В четырёх присваиваниях для простого связного списка нет ничего "непонятного". Может версия со slice/prepend и красивее, но это всё субъективно.
Нужно в первую очередь смотреть на объективные моменты, а не цепляться в грубой форме к субъективным недостаткам.
Например у тебя же получается лишняя операция
, так? slice лишний раз зануляет next.
Возможно компилятор сможет его убрать после inline'а, или даже если не за-inline'ит то это будет скорей всего не критично, но всё же это реальный объективный недостаток.
Другой реальный объективный момент, который относится ко всем трём примерам (или сколько там было) — в том что операция "reverse целого списка" элементарно превращается в "prepend перевёрнутого куска списка к другому списку".
Это тоже — реально объективный критерий.
template <typename I> // I models Linked Iterator
I reverse_append(I first, I limit, I result)
{
while (first != limit) {
I old_successor = successor(first);
set_successor(first, result);
result = first;
first = old_successor;
}
return result;
}
Это тоже по-твоему "ужасный говнокод с мешаниной old_successor, result, first и кучей присваиваний"?
Здравствуйте, Evgeny.Panasyuk, Вы писали:
A>>я хочу чтобы из Reverse были вытащены функции типа head, tail, add, и чтобы Reverse была написала в терминах этих операций, а не состояла их непонятных присваиваний EP>В четырёх присваиваниях для простого связного списка нет ничего "непонятного". Может версия со slice/prepend и красивее, но это всё субъективно.
ListElement * newBegin = NULL;
ListElement * cur = begin;
while(cur)
{
ListElement * next = cur->next;
cur->next = newBegin;
newBegin = cur;
cur = next;
}
begin = newBegin;
здесь 7 присваиваний, а не 4.
когда я смотрю на этот код, я вижу только что какие-то поля и переменные (или может члены класса) присваиваются друг другу, и с первого взгляда мне непонятно что тут делается
если начать читать — то смысла не добавляется: "newBegin = NULL; cur = begin; while cur != NULL: next = cur->next; cur->next = newBegin; newBegin = cur; ..." тут я начинаю думать "может это swap()?"
если нарисовать (в уме или на бумаге) по этому коду картинки, то всё становится понятно, а по тексту — ничего не понятно.
Есть еще один важный момент, который я забыл упомянуть.
Если у списка всетаки есть функции (методы) типа slice, prepend, то если функция reverse их не использует — это нарушение DRY, что для меня является признаком плохого кода.
Плохого уже не в плане читаемости, а в плане сопровождаемости.
EP>Нужно в первую очередь смотреть на объективные моменты, а не цепляться в грубой форме к субъективным недостаткам. EP>Например у тебя же получается лишняя операция
, так? slice лишний раз зануляет next. EP>Возможно компилятор сможет его убрать после inline'а, или даже если не за-inline'ит то это будет скорей всего не критично, но всё же это реальный объективный недостаток.
Да, я видел что slice зануляет next, и написал так потому что считаю что современные компиляторы уберут это лишнее присваивание.
Если же производительность списка будет узким местом, и компилятор не сделает такую оптимизацию, можно будет ввести функцию details::slice_fast()
EP>Другой реальный объективный момент, который относится ко всем трём примерам (или сколько там было) — в том что операция "reverse целого списка" элементарно превращается в "prepend перевёрнутого куска списка к другому списку". EP>Это тоже — реально объективный критерий.
да, но про другие структуры данных речь не шла, значит писать более универсальную функцию было бы нарушением YAGNI.
EP>Вот, например, один из вариантов Александра Степанова. EP>
EP>template <typename I> // I models Linked Iterator
EP>I reverse_append(I first, I limit, I result)
EP>{
EP> while (first != limit) {
EP> I old_successor = successor(first);
EP> set_successor(first, result);
EP> result = first;
EP> first = old_successor;
EP> }
EP> return result;
EP>}
EP>
Это тоже по-твоему "ужасный говнокод с мешаниной old_successor, result, first и кучей присваиваний"?
нет, это не говнокод.
во-первых этот код читается уже значительно лучше, т.к. тут используются функции successor и set_successor.
во-вторых отсюда сложно выделить другие функции, т.е. хотя тут и есть мешанина из присваиваний, с ней ничего не сделать.
основная сложность тут в set_successor, который магическим образом превращает "first" в "result"
можно было бы выделить
template <typename I> // I models Linked Iterator
I set_successor_and_ret_seq(I first, I newSuccessor)
{
set_successor(first, newSuccessor);
return first;
}
и тогда result всегда будет result, а first — начало исходной последовательности (визуально)
template <typename I> // I models Linked Iterator
I reverse_append(I first, I limit, I result)
{
while (first != limit) {
I old_successor = successor(first);
result = set_successor_and_ret_seq(first, result);
first = old_successor;
}
return result;
}
но эта функция set_successor_and_ret_seq опасна своим побочным эффектом, и я наверное не решился бы ее использовать.
возможно рекурсивный вариант кому-то покажется лучше, но ФП vs ИП — это действительно дело субъективное
template <typename I> // I models Linked Iterator
I reverse_append(I first, I limit, I result)
{
if (first == limit)
return result;
I next = successor(first);
result = set_successor_and_ret_seq(first, result);
return reverse_append(next, limit, result);
}
, так? slice лишний раз зануляет next. EP>>Возможно компилятор сможет его убрать после inline'а, или даже если не за-inline'ит то это будет скорей всего не критично, но всё же это реальный объективный недостаток. A>Да, я видел что slice зануляет next, и написал так потому что считаю что современные компиляторы уберут это лишнее присваивание. A>Если же производительность списка будет узким местом, и компилятор не сделает такую оптимизацию, можно будет ввести функцию details::slice_fast()
Скорей всего компиляторы уберут лишнее зануление (так как это элементарно, в этой их SSA). Мой поинт в том, что если абстракция приводит к лишним действиям, то это либо плохая абстракция, либо она не до конца проработана.
EP>>Другой реальный объективный момент, который относится ко всем трём примерам (или сколько там было) — в том что операция "reverse целого списка" элементарно превращается в "prepend перевёрнутого куска списка к другому списку". EP>>Это тоже — реально объективный критерий. A>да, но про другие структуры данных речь не шла, значит писать более универсальную функцию было бы нарушением YAGNI.
Во-первых это делается элементарно, главное только заметить это. Например в std::copy_n — этого не заметили и сделали плохой интерфейс.
Во-вторых этот buzz-word точно также применим к slice и prepend — задача-то была просто список развернуть.
EP>>Вот, например, один из вариантов Александра Степанова. EP>>
EP>>
Это тоже по-твоему "ужасный говнокод с мешаниной old_successor, result, first и кучей присваиваний"?
A>нет, это не говнокод. A>во-первых этот код читается уже значительно лучше, т.к. тут используются функции successor и set_successor.
Мне хоть и нравится как выглядит:
I old_successor = successor(first);
set_successor(first, result);
но по факту, это не так сильно отличается от:
auto next = cur->next;
cur->next = newBegin;
successor(first) — "достаёт next", set_successor — "устанавливает next".
A>возможно рекурсивный вариант кому-то покажется лучше, но ФП vs ИП — это действительно дело субъективное
Только это всё равно тоже самое ИП. Вот если бы set_successor возвращал новый узел.
К тому же не вижу смысла код делать похожим на ФП в тех местах, где он просто органически выражается в ИП. Да и tail-call хоть оптимизируется, но не везде, и не всегда (например может ударить в debug), так как нет гарантии стандарта.
Здравствуйте, Pavel Dvorkin, Вы писали:
A>>я хочу чтобы из Reverse были вытащены функции типа head, tail, add, и чтобы Reverse была написала в терминах этих операций, а не состояла их непонятных присваиваний
PD>Ну да, я примерно это и имею в виду. Только ошибся в наборе элементов. Для реализации двух простых действий ты требуешь написать обязательно head, tail , выделить add и т.д. Потом понадобится выделить итератор все же, или же придется внутри класса сделать next, а это, разумеется, вызовет твою критику (на этот раз справедливую), что итерация в списке не реализована итератором, а находится в самом списке и т.д.
нет, у меня немного другое понимание задачи — "у нас есть список, и мы пишем к нему новую функцию reverse".
т.е. список уже готов, и у него наверняка уже какие-то базовые операции.
поскольку конкретный класс списка не задан, мы придумываем их сами.
PD>Такое написать, конечно, можно, только вот код по манипуляциям с next и прочую игру с указателями все равно никуда не денешь, потому что это делать все равно придется.
манипуляции с next можно спрятать внутрь функций с читаемыми названиями, пусть даже это set_next
PD>ИМХО он и так вполне понятен, если просто посмотреть, что именно там делается.
не согласен.
да, если долго на него смотреть, то можно разобраться что там делается.
но это и есть критерий понятности/непонятности. с "понятным" кодом разбираешься быстро, с "непонятным" долго.
PD>А впрочем... Давай, допиши свой код до рабочего. Условия знаешь
уже писал тут — http://www.rsdn.ru/forum/flame.comp/5327527.1
вот более полная версия, с правильным API списка, С++1y, шаблонами, итераторами, удалением элементов http://coliru.stacked-crooked.com/a/cafe1dd5e6bff3c8
PD>От рекурсии уволь, так как это O(N) по стеку
к сожалению да. хотя все современные компиляторы умеют разворачивать хвостовую рекурсию, в Debug конфигурации они этого делать не будут.
EP>Вот, например, один из вариантов Александра Степанова. EP>[ccode] EP>template <typename I> // I models Linked Iterator EP>I reverse_append(I first, I limit, I result) EP>{ EP> while (first != limit) { EP> I old_successor = successor(first); EP> set_successor(first, result); EP> result = first; EP> first = old_successor; EP> } EP> return result; EP>}
Кстати, соответствующая видео-лекция.
(сам список, точнее пул списков — list_pool начинает разрабатываться в Lecture 8 Part 1)
Здравствуйте, Abyx, Вы писали:
A>я хочу чтобы из Reverse были вытащены функции типа head, tail, add, и чтобы Reverse была написала в терминах этих операций, а не состояла их непонятных присваиваний
Здрас-те приехали, вообще-то это нормальная практика, когда для оперирования ссылочными типами создается несколько переменных.
Это не непонятные присваивания, а операции с ссылками, если они для вас так сложны, срочно качать скилл программирования.
Но я подозреваю, что вам не столько непонятен код, сколько вы просто не хотите видеть такой стиль.
Я только взглянул на решение Павла Дворкина и оно мне сразу стало понятно.
Я бы конечно еще поработал над названиями переменных и вообще над названиями и форматированием, но по большей части это придало бы только видимую красоту.
A>или может функциональный вариант (хотя читаемость хвостовой рекурсии — штука спорная)
Сам ты функциональный! Все там императивно.
Но должен сказать, вариант рекурсии мне понравился.
Ну так как я вообще люблю рекурсию, то мне легко угодить.
И вот кстати, по этому варианту сразу видно, что человек понимает, что такое ссылки(указатели) и как с ними нужно работать.
Здравствуйте, Ikemefula, Вы писали:
I>Решение проблемы с фрагментацией не сводится к написанию аллокатора, это всего лишь необходимая часть.
В плюсах сводится, что оч удобно. Однократно написанный сверхдешевый в разработке и в рантайм аллокатор юзается в сотнях продуктов.
I>Вопрос — какое условие будет необходимым и достаточным ?
Вопрос я уже задавал рядом — нахрена нужен линейный массив в памяти с сотнями миллионов элементов?
PD>>Ну да, я примерно это и имею в виду. Только ошибся в наборе элементов. Для реализации двух простых действий ты требуешь написать обязательно head, tail , выделить add и т.д. Потом понадобится выделить итератор все же, или же придется внутри класса сделать next, а это, разумеется, вызовет твою критику (на этот раз справедливую), что итерация в списке не реализована итератором, а находится в самом списке и т.д.
A>нет, у меня немного другое понимание задачи — "у нас есть список, и мы пишем к нему новую функцию reverse". A>т.е. список уже готов, и у него наверняка уже какие-то базовые операции. A>поскольку конкретный класс списка не задан, мы придумываем их сами.
Ну пусть так. В конце концов мне никто не мешает в моем списке, так сказать, задним числом, добавить традиционные примитивы. А reverse оставлю как есть.
PD>>Такое написать, конечно, можно, только вот код по манипуляциям с next и прочую игру с указателями все равно никуда не денешь, потому что это делать все равно придется. A>манипуляции с next можно спрятать внутрь функций с читаемыми названиями, пусть даже это set_next
Вот объясни мне , пожалуйста, почему наличие в теле функции вызова set_next(a) делает код более понятным, чем присваивание next ? Я решительно не могу этого понять
p->next = cur;
Кажется, все просто и ясно. Из этого оператора следует все, что в нем заложено. А ты предлагаешь что-то вроде
set_next(p,cur)
Ну и чем это лучше. Ладно, о том, что это может быть менее эффективно (если не заинлайнится) — промолчу. Но и просто по стилю — чем это лучше ? Чем это понятнее ? Мне надо отвлечься от чтения reverse, посмотреть код set_next, понять, что она делает, запомнить, что она делает (ее вызов может еще раз повториться, опять ее смотреть ?), потом вернуться к reverse и продолжить изучение. Хоть убей, не понимаю, чем это лучше простого присваивания полю.
PD>>ИМХО он и так вполне понятен, если просто посмотреть, что именно там делается. A>не согласен. A>да, если долго на него смотреть, то можно разобраться что там делается.
Да не надо тут долго смотреть. Берешь листочек, рисуешь список из трех элементов со стрелками, начинаешь выполнять на этом листочке, зачеркивая одни стрелки и рисуя другие. На втором элементе все будет ясно. Займет это минуту от силы.
A>но это и есть критерий понятности/непонятности. с "понятным" кодом разбираешься быстро, с "непонятным" долго.
Более полную смотреть не буду, так как в ней ничего нового в плане нашей дискуссии, как я понимаю, нет.
Что касается исходной, то тебе уже отметили, что ты лишнее присваивание делаешь во имя идеи .
Далее, вот это нельзя назвать очень уж понятным с первого взгляда
Item* slice(Item*& head)
Функция что-то возвращает и при этом меняет свой входной указатель. Как минимум подумать надо. А скорее и потестировать, убедиться, что правильно работает на граничных значениях.
Да, reverse выглядит понятнее, не спорю. Но чтобы убедиться в том, что все тут правильно, мне надо понять логику slice и prepend. Для меня все это отнюдь не более понятно, чем простенькие манипуляции с next в теле моего цикла.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ну пусть так. В конце концов мне никто не мешает в моем списке, так сказать, задним числом, добавить традиционные примитивы. А reverse оставлю как есть.
это будет нарушением DRY, такой код сложно поддерживать.
когда надо будет что-то поменять, придется править больше строчек
PD>>>Такое написать, конечно, можно, только вот код по манипуляциям с next и прочую игру с указателями все равно никуда не денешь, потому что это делать все равно придется. A>>манипуляции с next можно спрятать внутрь функций с читаемыми названиями, пусть даже это set_next
PD>Вот объясни мне , пожалуйста, почему наличие в теле функции вызова set_next(a) делает код более понятным, чем присваивание next ? Я решительно не могу этого понять
PD>
PD> p->next = cur;
PD>
PD>Кажется, все просто и ясно. Из этого оператора следует все, что в нем заложено. А ты предлагаешь что-то вроде
PD>
PD> set_next(p,cur)
PD>
PD>Ну и чем это лучше. Ладно, о том, что это может быть менее эффективно (если не заинлайнится) — промолчу. Но и просто по стилю — чем это лучше ? Чем это понятнее ? Мне надо отвлечься от чтения reverse, посмотреть код set_next, понять, что она делает, запомнить, что она делает (ее вызов может еще раз повториться, опять ее смотреть ?), потом вернуться к reverse и продолжить изучение. Хоть убей, не понимаю, чем это лучше простого присваивания полю.
в "p->next = cur;" используются четыре сущности — p, ->next, operator=, cur.
читается это как "в p, члену класса next, присвоить cur"
а в "set_next(p, cur);" используются три сущности — set_next, p, cur.
читается это примерно как "p set_next cur".
(c "p.set_next(cur)" было бы чуть проще, хотя использование явного или неявного this вобщем-то не важно)
смотреть реализацию set_next ни в коем случае не надо, она должна делать то что написано в ее названии — set next ListElement,
преимущество в том, что вместо примитивных сущностей ->next и operator= мы используем более высокоуровневую операцию set_next (при этом мы не знаем ее реализацию).
и если постоянно использовать высокоуровневые операции, в т.ч. вместо "элемент newBegin присвоить NULL" — "новый список reversedList",
то код будет текстом описывающим операции над сущностями List и ListElement, а не мешаниной из присваиваний потрохов ListElement и каких-то переменных
PD>Да не надо тут долго смотреть. Берешь листочек, рисуешь список из трех элементов со стрелками, начинаешь выполнять на этом листочке, зачеркивая одни стрелки и рисуя другие. На втором элементе все будет ясно. Займет это минуту от силы.
я не хочу брать листочек и тратить минуту. я хочу разбираться с кодом с той скоростью с которой я его читаю
