Что вы, наличие более простого способа решения проблемы - всегда хорошая новость! Жаль, никто не смог в данном случае этого сделать... Так что, увы, хорошей новости не случилось.
В этом случае (deadlock баг в реализации conditional variable в glibc), похоже, простой способ почему-то не сработал. Сложный - сработал. И это не единственный случай, когда для решения реальной проблемы пришлось прибегнуть к сложному способу.
Для меня это (необходимость применения в некоторых сложных случаях сложных способов) - не новость. Для вас - плохая новость?
Я не хотел бы ввязываться в жаркий спор о рантайме Go, с которым я не знаком и не собираюсь знакомиться в ближайшее время. Тем не менее, считаю беседу достаточно содержательной для добавлении ещё одной реплики.
Я бегло просмотрел информацию про "go test -race" - вещь, безусловно, полезная и доступная - однако, насколько я понял, она хороша настолько, насколько хорошо тестовое покрытие. Да, документация с осторожностью рекомендует возможность запускать каких-то случаях (поиск production багов, не пойманных тестами?) и в production - предупреждая, что "The cost of race detection varies by program, but for a typical program, memory usage may increase by 5-10x and execution time by 2-20x."
Насчёт баланса стоимости и эффекта статического анализа: просмотрел довольно объёмную статью про использование MC-анализа для real world проблемы (не вникая в детали - я сам TLA+ не использовал, знаком с этим инструментом вприглядку - но кое-где не очень далеко от моего места работы этот инструмент содержательно использовался). Идёт речь о ловле и исправлении deadlock бага в реализации condition variable в стандартной библиотеке C. Может, вам тоже будет любопытно просмотреть. Стандартная библиотека C - довольно критически важная и стабильная база кода (впрочем, я подозреваю, что корректность реализации mutex.go тоже довольно критически важна, а последнее изменение в mutex.go было внесено 3 года назад). Статья годичной давности: Using TLA+ in the Real World to Understand a Glibc Bug | Probably Dance. Автор, скорее всего, работает в геймдеве, и с проблемой работал не из досужего интереса.
Ну вот, 226 строк низкоуровневого Go плюс внизу 6 строк на ассемблере - проверены вручную или формально, разница существенна. Про смайлик - в очном разговоре иронию легче уловить благодаря интонации и мимике, на письме (особенно в общении с случайным собеседником) - сложнее; да, смайлик я пропустил.
Автору - спасибо, интересно - про GenMC раньше не слышал (последний раз искал по теме - нашлись книги по TLA+ и Alloy, довольно старые системы).
Скорее, MC полезен для авторов библиотек - тех самых высокоуровневых примитивов. Угадайте, что внутри реализаций высокоуровневых примитивов? Код на Go, высокоуровневые примитивы, вы думаете? И так turtles all the way down? Я так не думаю.
Интересно, спасибо. Однако, не могу удержаться от того, чтобы оставить здесь пару рекомендаций.
При просмотре кода бросилось в глаза использование оператора new (второй фрагмент, класс Vertice) - подумал, что, если рассматривать этот фрагмент автономно, он может быть правильным только при использовании какой-либо библиотеки сборки мусора. Однако, потом нашёл разъяснение в этой фразе:
"Здесь ничего сложного, но нужно помнить, что ребра создаются в классе вершин, а значит они должны и удаляться там же."
Послушайте, ничего помнить не нужно было бы, если бы вы пользовались не C указателем на ребро, а std::unique_ptr - и неявный автоматический деструктор, не удлинняя кода, избавил бы от забот; код был бы правилен без дополнительный пояснений о том, что кое-что важное опущено и что о чём-то нужно помнить. Вместо "сырого" new рекомендуется использовать std::make_unique - и воспросов в голове читателя не возникает, всё понятно. Явное использование delete становится ненужным, код упрощается.
Перескакиваю в конец, к breadthPassCommon - здесь история с тем, кто чем владеет, более запутанная. Visitor передаётся как сырой C указатель, в конце функции выясняется, что владение этим объектом тоже передано (вызывается delete, и ещё владение отслеживается хитрой логикой с флагом visitotPassed)! Использование std::unque_ptr здесь тоже бы выручило, сделало бы код менее запутанным, легче читаемым и поддерживаемым, хитрая логика и флаги были бы заменены перемещением std::unique_ptr (явно указывающим на перемещение владения).
Пожалуйста также, обратите внимание на синтаксис range loop ( for (auto&& edge : *vertice->getEdges()) ). Я лично стараюсь указатели использовать как можно реже, помогает в долгой перспективе.
У меня ровно сейчас, к сожалению, нет времени проверить легкодоступные статистические анализаторы, но, кажется, проверка на отсутствие модификации локальной переменной (если нет модификаций - диагностика "добавьте const!") может существовать, она технически нетрудна. Обращу на это внимание между делом - но в моём текущем проекте всё-таки практика применять const только в public APIs. Спасибо за дискуссию! По существу - продолжайте, пожалуйста, такие публикации, полезное для сообщества дело!
Нет у меня претензий к названиям переменных (мне даже в голову не пришло бы начинать разговоры на эту тему). Я рад, что мой длинный комментарий показался вам полезным. Не уверен, что вы сочтёте ещё один относительно длинный комментарий ниже применимым в рамках текущей беседы; печатаю его, опять же, чтобы ещё немного порефлексировать.
Моё отношение к coding guidelines довольно прагматично. Я открыт к кодификации в coding guidelines сложившегося по тем или иным причинам стиля, но мне важна внутренняя непротиворечивость такого стиля. Обсуждая с коллегами аспекты вроде рассматриваемого здесь (про желательность / нежелательность спецификатора const при объявлении локальных переменных: параметры -- локальные переменные в реализации функции) я выясняю их мотивы и подталкиваю к рефлексии на тему, насколько логичны их привычки? В случае с вашей привычкой некая поименованная величина в теле функции может оказаться констатной только из-за того, что она -- параметр, а не локальная переменная. Вы не находите сочетание строгости в отношении одних локальных переменных (параметров функции) и расслабленность в отношении других локальных переменных (не-параметров) нелогичным?
Я несколько лет назад задал самому себе такой вопрос и решил, что у меня, как у сторонника логичных самосогласованных практик, два варианта -- писать const по возможности везде (в том числе при объявлении локальных переменных и да, членов классов -- во имя самосогласованности данного правила) или писать const только там, где этот спецификатор реально детализирует контракт (как в типах параметров const T&). Порефлексировал и принял выбор в пользу второго варианта. Подтверждение нахожу в стандартной библиотеке и других пакетах, коде коллег -- поэтому удивился, увидев типа параметров const T у вас (для меня это -- ухудшение читабельности, глаз запнулся), после чего напечатал предыдущий длинный комментарий.
Упомянутый вами случай с shared_ptr, конечно, прискорбен (я, безусловно, предпочитаю unique_ptr и проработку дизайна компонент так, чтобы необходимости использования shared_ptr не было). Опять же, порефлексировав некоторое время назад, я пришёл к практике инкапсуляции деталей реализации сколь-либо сложного класса в pimpl (последнее время использую zero-cost "fast pimpl" после того, как написал поддерживающий fast impl темплейтный код, до этого использовал pimpl на unique_ptr) и запрете (= delete;) у него copy costructor, copy assignment operator. Тогда передача по значению такого сколь-нибудь сложного класса оказывается намеренно запрещена (чтобы не платить за копирование), для использования класса в функции передаётся const T& (отлично) или T& (что сигналит в сигнатуре-контракте о мутациях параметра, выполняемых в функции, о коде становится сложнее рассуждать -- цена за предполагаемую или доказанную замерами оптимизацию производительности... лучше бы доказанную). Просто T -- передача по значению (отличный выбор для лёгких "скалярных" типов, небольших struct-ов, POD). Добавление в этом случае const T -- ненужный шум в контракте и нелогичное ограничение на стороне реализации функции (нелогичное - при использовании достаточно широко принятой практике не вставлять const в объявление почти каждой локальной переменной, это и ваша практика тоже).
Возвращаясь к coding guidelines. С другой стороны, я не хочу фиксировать в coding guidelines чьи-то (мои в том числе) идеосинкразии, обусловленные индивидуальным профессиональным опытом (как ваша печальная история с shared_ptr внутри переданного по значению параметра). Вместо этого я пытаюсь отслеживать тренды в развитии языка, пытаюсь делать coding guidelines, к которым прикладываю руки, как можно более future-proof. С++ Core Guidelines -- хороший источник информации на этот счёт, на мой взгляд. Движение в сторону более частого использования практик функционального программирования (пример из Core Guidelines: "F.8: Prefer pure functions") прослеживается и там, и в современных UI библиотеках, и в практиках безопасного многопоточного программирования, поэтому я стараюсь сам и подталкиваю коллег использовать типы параметров T и const T& - избегая T& (предпочитая стиль чистых функций с немутирующими аргументами и возвратом всего через результат -- пока выигрыш в производительности от in-out стиля с T& не доказан замерами).
Вдогонку добавлю (заглянув в другую ветку комментариев) про преимущество static_cast. Для меня очевидное преимущество -- в том, что такая практика согласована с C++ Core Guidelines, конкретно -- с "ES.49: If you must use a cast, use a named cast".
"Я привык ставить const в аргументах, чтобы только по заголовку было понятно, что есть вход, что есть выход. Конечно же, никаких особых преимуществ это для аргумента get(i, j) не даёт (кроме читабельности)."
Отличная мотивация, а для меня - удобный момент снова разобрать элементы общих рекомендации по типам аргументов функций, заглянув в раздел Functions C++ Core Guidelines (и конкретно пересмотрев рекомендации F.15 и F.16).
Начнём с того, что наиболее простой способ передачи данных в функцию и получения результатов - передача по значению (тип аргумента T) и получение всех выходов функции только в возвращаемом значении (результате) - который при множественности результатов становится композитным, например, пара, кортеж (tuple) или простая структура (лучший вариант, на мой взгляд, благодаря содержательным названиям полей). Современный C++ предоставляет удобную деконструкцию композитного результата в вызывающем контексте, нампример auto [ x, y, z ] = get_coordinates(a); (этот приём используется в фрагментах кода к C++ Core Guidelines I.10, F.21, ES.10, ES.11, ES.20).
Недостаток: если тип T - достаточно крупного размера, копирование значения при передаче по значению может сказаться на производительности (что всегда не мешает проверить замерами). В этом случае помогает ссылка на константное значение, const T& - заметьте присутствие '&'. Только при наличии & появляется риск изменить внутри функции внешнее значение, и const помогает это предотвратить, а также просигналить о намереньях в сигнатуре функции: этот const T& параметр - входной, с той же подразумеваемой семантикой, как передача по значению (просто T), а ссылочность заведена для оптимизации производительности.
Поставив const T (без '&') при передаче по значению вы не меняете семантику отношений вызывающего кода с функцией - и так и так параметр, передаваемый по значению, только входной (in). В этом случае const ограничивает набор действий с параметром в реализации функции (вы не сможете обновить его значение, это сходно константным локальным переменный вроде sprite_w и sprite_h в одном из фрагментов вашего кода. Лично я рассматриваю такую типизацию как неполезную - добавляет ненужный шум в сигнатуру, накладывает ограничение на реализующий функцию код (иногда приводящее к более длинной и менее читабельной форме этого кода).
При передаче по ссылке ('&') спецификатор const действительно важен! Без него функция имеет право поменять значение переданной переменной в вызывающем контексте, таким образом параметр становится входным/выходным (in-out, описанный в рекомендации F.17) -- чего лично я стараюсь избегать, предпочитая все выходы функции возвращать в результате.
Кроме этого усложнения передача по ссылке может привнести подводные камни, так что прибегать к ней имеет смысл только убедившись, что копирование крупного значения T действительно влияет на производительность. Здесь я имею в виду возможные проблемы с aliasing. При получинии параметра const T& код функции может резонно положиться на соглашение, что данный параметр - входной, его значение в момент вызова функции таковым и остаётся до момента выхода из функции. Однако, если функция обращается к другим функциям, имеющим (другим путём) доступ к той же переменной в вызывающем контексте, это значение неожиданно может поменяться. С этой проблемой можно бороться, предотвращая aliasing с помощью &&, но, увы, такой подход усложняет код.
Спасибо за разбор! Путаница n с 2n случилась у меня в голове с формулировкой задачи - представлял коробку с n концами шнурков слева и n концами шнурков справа, и случайное связывание левых с правыми. Исходное условие проще формулируется, а я, похоже, переключился на другое условие, которое мне было проще решать.
(вы уже второй раз помещаете новый комментарий в корень обсуждения :) ) Исправляю догадку, теперь сделав аналитические выкладки с рекурсивным вычислением величины от n. Теперь у меня получается Hn, частичная сумма первых n элементов гармонического ряда. Асимптотическая формула есть, log n + 0.5772... (постоянная Эйлера-Маскерони). Посчитаю моделированием для проверки - в следующий раз. Рекурсивные выкладки: данный шнурок с вероятностью 1/n добавляет новую петлю, а с вероятностью (n-1)/n не добавлет петлю к ситуации с n-1 шнурками. После приведения получаем X(n) = 1/n + X(n-1). Кажется, у меня есть на полке книга, в которой я мог бы подсмотреть похожие рассуждения - в одном из трёх томов "Искусства программирования" Кнута попадалось. Сейчас должен заняться другими вопросами - буду проверять тред на днях, не появилось ли что-либо от вас.
Я тоже, наверно, порешаю. Пока догадка (после беглой ручной проверки n от 1 до 3, в которой я мог допустить ошибку) такая: 2 - 1/n!. Реализую и погоняю перебор проверить или заменить догадку, потом буду разбираться с результатом. Не припомню, чтобы такую задачу встречал, но вспомнились задачи с похожими формулировками - про подброшенные в воздух шляпы и про сумасшедшую старушку и прочих пассажиров авиарейса.
Между прочим, неплохая тема для школьного математического кружка (и я проводил такое занятие один раз, лет 20 назад, кажется, взяв идею из старой советской книги, там были цыплята :) ), поскольку решаемая в конце задача на экстремум может быть разобрана без производных - на уровне квадратных уравнений или неравенства о среднем арифметическом и среднем геометрическом. У вас небольшая опечатка в "... ½С1∙T∙q+RСs/q. После дифференцирования по q находим ½С1∙T+RСs/q2" - конечно, после дифференцирования между слагаемыми минус, а не плюс!
Изящное и, по-моему, правильное решение, не вижу изъянов - лучший комментарий здесь (я, правда, пролистал бегло)! Бонус - очевидная линейная асимптотика в результирующей компактной формуле (автор заметки упоминает этот аспект, хорошо понятный при "физическом" рассмотрении того, что происходит при масштабировании N, например, рассмотрении испытания с 2N шарами как двух испытаний с N шарами).
Меня этот вывод от pavelgein не убеждает (наоборот, вижу путаницу в определениях случайных величин, а "догадаться, что хотел сказать автор, но оговорился" нет времени, желания), а вот разбор от Pavgran ниже по комментарием выглядит корректно, плюс, в результате - компактная формула с очевидной линейной асимптотикой. Кстати, догадка о линейности асимптотики - довольно "физическая", можно рассматривать, как ведёт себя величина при возрастании N вдвое при больших значениях N - разделив испытание с 2N шарами на комбинацию двух испытаний с N шарами. При больших N одной возможной серией белых шаров, продолжающейся с первого N-испытания на второе можно пренебречь, посчитав её два раза - линейность тогда становится наглядной (что не умаляет необходимости доказать её строго, с формулой от Pavgran).
Интуиция подсказывает мне, что прав Pavgran, попробую найти время / силы перепроверить.
Автор ничего не упрощал (у вас, может быть, есть на руках более сложный пример, который автор упростил?), он предоставил относительно простую демонстрацию возможной обвязки без многопоточности. Сопрограммы хорошо работают с многопоточностью, но могут быть использованы и в простом однопоточном контексте, как представлено здесь. И так уже нужно довольно повозиться. Я этим занимался, теперь (на другом проекте) не хочу торопиться -- к сожалению, стандартная библиотека не включает удобную поддержку в C++20.
Скажите, если вы изложили (наглядно!) два алгоритма, сводящихся к жадному перебору рёбер, не рассматривали ли вы возможность сравнить какие-либо характеристики (память, время, логическая сложность реализации)? Также любопытен (мне лично) аспект набора практических задач, в которых возникает необходимость находить остовное дерево (так как мне лично за многолетнюю карьеру программиста не попадалось сколь-либо близко, задача кажется довольно академичной). На лекцию "клик" не делаю, если есть возможность общения в текстовом режиме.
Понятно, спасибо! У меня сложилось мнение, что эту языковую возможность (виртуальное наследование) скорее принято обходить (не в последнюю очередь - из-за сложного лэйаута объектов и дополнительного кода, генерируемого компилятором для доступа из объекта-наследника к базовому объекту, наследованному веритуально). Сам за годы программирования на C++ использовал, наверно, пару раз (причем первый раз - в самом начале карьеры, было интересно освоить эту возможность языка - сейчас бы скомпоновал тот код по-другому).
Спасибо, интересно. Скажите пожалуйста, почему наследование от базового класса Turn - виртуальное? Все классы-наследники финальны, проблемы ромба не возникает. Таким образом, объявляя базовый класс виртуальным базовым классом вы платите за то, что вам не нужно в этом проекте. Других случаев наследования в хедерах я не нашёл, бегло просмотрев, и предполагаю, что это - следствие какого-то внешнего влияния (так принято наследовать в Qt?).
Что вы, наличие более простого способа решения проблемы - всегда хорошая новость! Жаль, никто не смог в данном случае этого сделать... Так что, увы, хорошей новости не случилось.
В этом случае (deadlock баг в реализации conditional variable в glibc), похоже, простой способ почему-то не сработал. Сложный - сработал. И это не единственный случай, когда для решения реальной проблемы пришлось прибегнуть к сложному способу.
Для меня это (необходимость применения в некоторых сложных случаях сложных способов) - не новость. Для вас - плохая новость?
Я не хотел бы ввязываться в жаркий спор о рантайме Go, с которым я не знаком и не собираюсь знакомиться в ближайшее время. Тем не менее, считаю беседу достаточно содержательной для добавлении ещё одной реплики.
Я бегло просмотрел информацию про "go test -race" - вещь, безусловно, полезная и доступная - однако, насколько я понял, она хороша настолько, насколько хорошо тестовое покрытие. Да, документация с осторожностью рекомендует возможность запускать каких-то случаях (поиск production багов, не пойманных тестами?) и в production - предупреждая, что "The cost of race detection varies by program, but for a typical program, memory usage may increase by 5-10x and execution time by 2-20x."
Насчёт баланса стоимости и эффекта статического анализа: просмотрел довольно объёмную статью про использование MC-анализа для real world проблемы (не вникая в детали - я сам TLA+ не использовал, знаком с этим инструментом вприглядку - но кое-где не очень далеко от моего места работы этот инструмент содержательно использовался). Идёт речь о ловле и исправлении deadlock бага в реализации condition variable в стандартной библиотеке C. Может, вам тоже будет любопытно просмотреть. Стандартная библиотека C - довольно критически важная и стабильная база кода (впрочем, я подозреваю, что корректность реализации mutex.go тоже довольно критически важна, а последнее изменение в mutex.go было внесено 3 года назад). Статья годичной давности: Using TLA+ in the Real World to Understand a Glibc Bug | Probably Dance. Автор, скорее всего, работает в геймдеве, и с проблемой работал не из досужего интереса.
Ну вот, 226 строк низкоуровневого Go плюс внизу 6 строк на ассемблере - проверены вручную или формально, разница существенна. Про смайлик - в очном разговоре иронию легче уловить благодаря интонации и мимике, на письме (особенно в общении с случайным собеседником) - сложнее; да, смайлик я пропустил.
Автору - спасибо, интересно - про GenMC раньше не слышал (последний раз искал по теме - нашлись книги по TLA+ и Alloy, довольно старые системы).
Скорее, MC полезен для авторов библиотек - тех самых высокоуровневых примитивов. Угадайте, что внутри реализаций высокоуровневых примитивов? Код на Go, высокоуровневые примитивы, вы думаете? И так turtles all the way down? Я так не думаю.
Про range loop можно прочитать, например, здесь: https://docs.microsoft.com/ru-ru/cpp/cpp/range-based-for-statement-cpp?view=msvc-160 - этот синтаксис более удобен в большинстве случаев при итерировании по контейнерам.
Интересно, спасибо. Однако, не могу удержаться от того, чтобы оставить здесь пару рекомендаций.
При просмотре кода бросилось в глаза использование оператора new (второй фрагмент, класс Vertice) - подумал, что, если рассматривать этот фрагмент автономно, он может быть правильным только при использовании какой-либо библиотеки сборки мусора. Однако, потом нашёл разъяснение в этой фразе:
"Здесь ничего сложного, но нужно помнить, что ребра создаются в классе вершин, а значит они должны и удаляться там же."
Послушайте, ничего помнить не нужно было бы, если бы вы пользовались не C указателем на ребро, а std::unique_ptr - и неявный автоматический деструктор, не удлинняя кода, избавил бы от забот; код был бы правилен без дополнительный пояснений о том, что кое-что важное опущено и что о чём-то нужно помнить. Вместо "сырого" new рекомендуется использовать std::make_unique - и воспросов в голове читателя не возникает, всё понятно. Явное использование delete становится ненужным, код упрощается.
Перескакиваю в конец, к breadthPassCommon - здесь история с тем, кто чем владеет, более запутанная. Visitor передаётся как сырой C указатель, в конце функции выясняется, что владение этим объектом тоже передано (вызывается delete, и ещё владение отслеживается хитрой логикой с флагом visitotPassed)! Использование std::unque_ptr здесь тоже бы выручило, сделало бы код менее запутанным, легче читаемым и поддерживаемым, хитрая логика и флаги были бы заменены перемещением std::unique_ptr (явно указывающим на перемещение владения).
Пожалуйста также, обратите внимание на синтаксис range loop ( for (auto&& edge : *vertice->getEdges()) ). Я лично стараюсь указатели использовать как можно реже, помогает в долгой перспективе.
У меня ровно сейчас, к сожалению, нет времени проверить легкодоступные статистические анализаторы, но, кажется, проверка на отсутствие модификации локальной переменной (если нет модификаций - диагностика "добавьте const!") может существовать, она технически нетрудна. Обращу на это внимание между делом - но в моём текущем проекте всё-таки практика применять const только в public APIs. Спасибо за дискуссию! По существу - продолжайте, пожалуйста, такие публикации, полезное для сообщества дело!
Нет у меня претензий к названиям переменных (мне даже в голову не пришло бы начинать разговоры на эту тему). Я рад, что мой длинный комментарий показался вам полезным. Не уверен, что вы сочтёте ещё один относительно длинный комментарий ниже применимым в рамках текущей беседы; печатаю его, опять же, чтобы ещё немного порефлексировать.
Моё отношение к coding guidelines довольно прагматично. Я открыт к кодификации в coding guidelines сложившегося по тем или иным причинам стиля, но мне важна внутренняя непротиворечивость такого стиля. Обсуждая с коллегами аспекты вроде рассматриваемого здесь (про желательность / нежелательность спецификатора const при объявлении локальных переменных: параметры -- локальные переменные в реализации функции) я выясняю их мотивы и подталкиваю к рефлексии на тему, насколько логичны их привычки? В случае с вашей привычкой некая поименованная величина в теле функции может оказаться констатной только из-за того, что она -- параметр, а не локальная переменная. Вы не находите сочетание строгости в отношении одних локальных переменных (параметров функции) и расслабленность в отношении других локальных переменных (не-параметров) нелогичным?
Я несколько лет назад задал самому себе такой вопрос и решил, что у меня, как у сторонника логичных самосогласованных практик, два варианта -- писать const по возможности везде (в том числе при объявлении локальных переменных и да, членов классов -- во имя самосогласованности данного правила) или писать const только там, где этот спецификатор реально детализирует контракт (как в типах параметров const T&). Порефлексировал и принял выбор в пользу второго варианта. Подтверждение нахожу в стандартной библиотеке и других пакетах, коде коллег -- поэтому удивился, увидев типа параметров const T у вас (для меня это -- ухудшение читабельности, глаз запнулся), после чего напечатал предыдущий длинный комментарий.
Упомянутый вами случай с shared_ptr, конечно, прискорбен (я, безусловно, предпочитаю unique_ptr и проработку дизайна компонент так, чтобы необходимости использования shared_ptr не было). Опять же, порефлексировав некоторое время назад, я пришёл к практике инкапсуляции деталей реализации сколь-либо сложного класса в pimpl (последнее время использую zero-cost "fast pimpl" после того, как написал поддерживающий fast impl темплейтный код, до этого использовал pimpl на unique_ptr) и запрете (= delete;) у него copy costructor, copy assignment operator. Тогда передача по значению такого сколь-нибудь сложного класса оказывается намеренно запрещена (чтобы не платить за копирование), для использования класса в функции передаётся const T& (отлично) или T& (что сигналит в сигнатуре-контракте о мутациях параметра, выполняемых в функции, о коде становится сложнее рассуждать -- цена за предполагаемую или доказанную замерами оптимизацию производительности... лучше бы доказанную). Просто T -- передача по значению (отличный выбор для лёгких "скалярных" типов, небольших struct-ов, POD). Добавление в этом случае const T -- ненужный шум в контракте и нелогичное ограничение на стороне реализации функции (нелогичное - при использовании достаточно широко принятой практике не вставлять const в объявление почти каждой локальной переменной, это и ваша практика тоже).
Возвращаясь к coding guidelines. С другой стороны, я не хочу фиксировать в coding guidelines чьи-то (мои в том числе) идеосинкразии, обусловленные индивидуальным профессиональным опытом (как ваша печальная история с shared_ptr внутри переданного по значению параметра). Вместо этого я пытаюсь отслеживать тренды в развитии языка, пытаюсь делать coding guidelines, к которым прикладываю руки, как можно более future-proof. С++ Core Guidelines -- хороший источник информации на этот счёт, на мой взгляд. Движение в сторону более частого использования практик функционального программирования (пример из Core Guidelines: "F.8: Prefer pure functions") прослеживается и там, и в современных UI библиотеках, и в практиках безопасного многопоточного программирования, поэтому я стараюсь сам и подталкиваю коллег использовать типы параметров T и const T& - избегая T& (предпочитая стиль чистых функций с немутирующими аргументами и возвратом всего через результат -- пока выигрыш в производительности от in-out стиля с T& не доказан замерами).
Вдогонку добавлю (заглянув в другую ветку комментариев) про преимущество static_cast. Для меня очевидное преимущество -- в том, что такая практика согласована с C++ Core Guidelines, конкретно -- с "ES.49: If you must use a cast, use a named cast".
"Я привык ставить const в аргументах, чтобы только по заголовку было понятно, что есть вход, что есть выход. Конечно же, никаких особых преимуществ это для аргумента
get(i, j)не даёт (кроме читабельности)."Отличная мотивация, а для меня - удобный момент снова разобрать элементы общих рекомендации по типам аргументов функций, заглянув в раздел Functions C++ Core Guidelines (и конкретно пересмотрев рекомендации F.15 и F.16).
Начнём с того, что наиболее простой способ передачи данных в функцию и получения результатов - передача по значению (тип аргумента T) и получение всех выходов функции только в возвращаемом значении (результате) - который при множественности результатов становится композитным, например, пара, кортеж (tuple) или простая структура (лучший вариант, на мой взгляд, благодаря содержательным названиям полей). Современный C++ предоставляет удобную деконструкцию композитного результата в вызывающем контексте, нампример auto [ x, y, z ] = get_coordinates(a); (этот приём используется в фрагментах кода к C++ Core Guidelines I.10, F.21, ES.10, ES.11, ES.20).
Недостаток: если тип T - достаточно крупного размера, копирование значения при передаче по значению может сказаться на производительности (что всегда не мешает проверить замерами). В этом случае помогает ссылка на константное значение, const T& - заметьте присутствие '&'. Только при наличии & появляется риск изменить внутри функции внешнее значение, и const помогает это предотвратить, а также просигналить о намереньях в сигнатуре функции: этот const T& параметр - входной, с той же подразумеваемой семантикой, как передача по значению (просто T), а ссылочность заведена для оптимизации производительности.
Поставив const T (без '&') при передаче по значению вы не меняете семантику отношений вызывающего кода с функцией - и так и так параметр, передаваемый по значению, только входной (in). В этом случае const ограничивает набор действий с параметром в реализации функции (вы не сможете обновить его значение, это сходно константным локальным переменный вроде
sprite_wиsprite_hв одном из фрагментов вашего кода. Лично я рассматриваю такую типизацию как неполезную - добавляет ненужный шум в сигнатуру, накладывает ограничение на реализующий функцию код (иногда приводящее к более длинной и менее читабельной форме этого кода).При передаче по ссылке ('&') спецификатор const действительно важен! Без него функция имеет право поменять значение переданной переменной в вызывающем контексте, таким образом параметр становится входным/выходным (in-out, описанный в рекомендации F.17) -- чего лично я стараюсь избегать, предпочитая все выходы функции возвращать в результате.
Кроме этого усложнения передача по ссылке может привнести подводные камни, так что прибегать к ней имеет смысл только убедившись, что копирование крупного значения T действительно влияет на производительность. Здесь я имею в виду возможные проблемы с aliasing. При получинии параметра const T& код функции может резонно положиться на соглашение, что данный параметр - входной, его значение в момент вызова функции таковым и остаётся до момента выхода из функции. Однако, если функция обращается к другим функциям, имеющим (другим путём) доступ к той же переменной в вызывающем контексте, это значение неожиданно может поменяться. С этой проблемой можно бороться, предотвращая aliasing с помощью &&, но, увы, такой подход усложняет код.
Спасибо за разбор! Путаница n с 2n случилась у меня в голове с формулировкой задачи - представлял коробку с n концами шнурков слева и n концами шнурков справа, и случайное связывание левых с правыми. Исходное условие проще формулируется, а я, похоже, переключился на другое условие, которое мне было проще решать.
(вы уже второй раз помещаете новый комментарий в корень обсуждения :) )
Исправляю догадку, теперь сделав аналитические выкладки с рекурсивным вычислением величины от n. Теперь у меня получается Hn, частичная сумма первых n элементов гармонического ряда. Асимптотическая формула есть, log n + 0.5772... (постоянная Эйлера-Маскерони). Посчитаю моделированием для проверки - в следующий раз. Рекурсивные выкладки: данный шнурок с вероятностью 1/n добавляет новую петлю, а с вероятностью (n-1)/n не добавлет петлю к ситуации с n-1 шнурками. После приведения получаем X(n) = 1/n + X(n-1). Кажется, у меня есть на полке книга, в которой я мог бы подсмотреть похожие рассуждения - в одном из трёх томов "Искусства программирования" Кнута попадалось. Сейчас должен заняться другими вопросами - буду проверять тред на днях, не появилось ли что-либо от вас.
Я тоже, наверно, порешаю. Пока догадка (после беглой ручной проверки n от 1 до 3, в которой я мог допустить ошибку) такая: 2 - 1/n!. Реализую и погоняю перебор проверить или заменить догадку, потом буду разбираться с результатом. Не припомню, чтобы такую задачу встречал, но вспомнились задачи с похожими формулировками - про подброшенные в воздух шляпы и про сумасшедшую старушку и прочих пассажиров авиарейса.
Между прочим, неплохая тема для школьного математического кружка (и я проводил такое занятие один раз, лет 20 назад, кажется, взяв идею из старой советской книги, там были цыплята :) ), поскольку решаемая в конце задача на экстремум может быть разобрана без производных - на уровне квадратных уравнений или неравенства о среднем арифметическом и среднем геометрическом. У вас небольшая опечатка в "... ½С1∙T∙q+RСs/q. После дифференцирования по q находим ½С1∙T+RСs/q2" - конечно, после дифференцирования между слагаемыми минус, а не плюс!
Хорошее объяснение, спасибо!
Изящное и, по-моему, правильное решение, не вижу изъянов - лучший комментарий здесь (я, правда, пролистал бегло)! Бонус - очевидная линейная асимптотика в результирующей компактной формуле (автор заметки упоминает этот аспект, хорошо понятный при "физическом" рассмотрении того, что происходит при масштабировании N, например, рассмотрении испытания с 2N шарами как двух испытаний с N шарами).
Меня этот вывод от pavelgein не убеждает (наоборот, вижу путаницу в определениях случайных величин, а "догадаться, что хотел сказать автор, но оговорился" нет времени, желания), а вот разбор от Pavgran ниже по комментарием выглядит корректно, плюс, в результате - компактная формула с очевидной линейной асимптотикой. Кстати, догадка о линейности асимптотики - довольно "физическая", можно рассматривать, как ведёт себя величина при возрастании N вдвое при больших значениях N - разделив испытание с 2N шарами на комбинацию двух испытаний с N шарами. При больших N одной возможной серией белых шаров, продолжающейся с первого N-испытания на второе можно пренебречь, посчитав её два раза - линейность тогда становится наглядной (что не умаляет необходимости доказать её строго, с формулой от Pavgran).
Интуиция подсказывает мне, что прав Pavgran, попробую найти время / силы перепроверить.
Автор ничего не упрощал (у вас, может быть, есть на руках более сложный пример, который автор упростил?), он предоставил относительно простую демонстрацию возможной обвязки без многопоточности. Сопрограммы хорошо работают с многопоточностью, но могут быть использованы и в простом однопоточном контексте, как представлено здесь. И так уже нужно довольно повозиться. Я этим занимался, теперь (на другом проекте) не хочу торопиться -- к сожалению, стандартная библиотека не включает удобную поддержку в C++20.
Скажите, если вы изложили (наглядно!) два алгоритма, сводящихся к жадному перебору рёбер, не рассматривали ли вы возможность сравнить какие-либо характеристики (память, время, логическая сложность реализации)? Также любопытен (мне лично) аспект набора практических задач, в которых возникает необходимость находить остовное дерево (так как мне лично за многолетнюю карьеру программиста не попадалось сколь-либо близко, задача кажется довольно академичной). На лекцию "клик" не делаю, если есть возможность общения в текстовом режиме.
Понятно, спасибо! У меня сложилось мнение, что эту языковую возможность (виртуальное наследование) скорее принято обходить (не в последнюю очередь - из-за сложного лэйаута объектов и дополнительного кода, генерируемого компилятором для доступа из объекта-наследника к базовому объекту, наследованному веритуально). Сам за годы программирования на C++ использовал, наверно, пару раз (причем первый раз - в самом начале карьеры, было интересно освоить эту возможность языка - сейчас бы скомпоновал тот код по-другому).
Спасибо, интересно. Скажите пожалуйста, почему наследование от базового класса Turn - виртуальное? Все классы-наследники финальны, проблемы ромба не возникает. Таким образом, объявляя базовый класс виртуальным базовым классом вы платите за то, что вам не нужно в этом проекте. Других случаев наследования в хедерах я не нашёл, бегло просмотрев, и предполагаю, что это - следствие какого-то внешнего влияния (так принято наследовать в Qt?).
Ссылка по теме вопроса:
https://en.wikipedia.org/wiki/Virtual_inheritance