Да, со строками тоже неплохо, но область применимости узковата. Такое нужно только когда мы по процессору упираемся в производительность strcpy () и/или часто нужно делать strlen (). Если такого нет - то уменьшение читабельности уже не оправдывается. Так что в качестве "общего правила" - совсем не катит. Еще мне assert () через __builtin_unreachable понравилось, я такое через typedef массива с положительной или отрицательной (в зависимости от аргумента assert-а) длиной делаю, а это тоже gcc-изм и вообще коряво. Может, даже перейду на __builtin_unreachable. Но это мелочь, отдельная капля меда в бочке понятно чего.
Какой-то список антипаттернов - как делать ни в коем случае нельзя. Из существенного, случайно затесалась единственная идея, которую поддержу - возврат структур, явно описывающих полный результат выполнения, включая ошибки.
Похоже, я что-то не то называю алгоритмом Дейкстры :) В том, что у меня всю жизнь было в голове, он идет вширь и переписывает метки узлов, до которых добирается. Причем добирается до них разными путями - соседом нового узла может оказаться давно посещенный. Надо подумать, возможно, проход по пути в направлении сначала ближних узлов гарантирует непосещение второй раз. Никогда об этом не задумывался. Спасибо за наводку, без пинка я бы так и не узнал бы, что тут еще есть о чем подумать.
Опять я что-то либо не так понимаю, либо не так называю... Дейкстра ведь приходит в каждый узел с разных направлений, и дальше из этого узла идет только когда метка узла изменилась? И выбор ребра с минимальным весом только позволяет улучшить среднее время, несколько уменьшив количество приходов в узлы, изменивших их метку? А так все равно для поиска кратчайшего пути придется посетить все достижимые вершины по всем входящим путям, просто после первого нахождения целевой вершины можно немного соптимизировать и больше не ходить путями, которые длиннее уже найденного.
Да, я уже понял свою ошибку. Дейкстра посещает узлы более чем по одному разу, эти алгоритмы неэквивалентны. Насчет сложных структур данных: так вроде там нигде нет операций поиска? Что там можно улучшить кучей или другими структурами? Вроде бы обычного списка с исключением и вставкой по O(1) достаточно.
Поправка: как улучшить среднее время выполнения с помощью продвинутых структур данных - понятно, но худший случай выбором других структур данных вместо списков можно только ухудшить.
Понял! Действительно, эти алгоритмы не эквивалентны. При волновом алгоритме за счет поколений волн и, кстати, за счет одинакового веса ребер, обеспечивается гарантия отсутствия необходимости ходить по одному ребру более одного раза. Соответственно, и асимптотика лучше. Но и полезные свойства по легкому натягиванию на распределенный случай тоже уходят, их не обеспечить, так как есть те самые поколения волн, а соответственно, нужны "общие часы" какого-то вида.
Кажется, у меня проблема с названиями. У того, что я в своей голове называю алгоритмом Дейкстры, асимптотика O(N*N), так как мы гарантированно не будем осуществлять "выход из узла" больше чем M раз (где M - диаметр графа, и он гарантированно <= N), и будем делать это в худшем случае для N узлов (где N - количество узлов).
Работает не особо дольше, асимптотика у него та же, и константа тоже близкая, и зависящая только от способа хранения структуры данных в памяти. Сложнее? Тоже не кажется так. Клетчатое поле со стенками - это частный случай графа. Вес всегда единица - ну так нет особой разницы, единицу прибавлять к "дальности" или вес ребра. Обход делается одинаково, тоже в ширину.
Я этот алгоритм знал под названием "Алгоритм Дейкстры".
Кстати, у этого алгоритма есть еще неочевидное крайне полезное для некоторых применений свойство: он очень легко натягивается на распределенный случай (когда каждая клетка содержит процессор, и нет "общей шины" и "общих часов" - все общаются только со своими соседями и не знают общей картины).
Прямо ностальгией накрыло :) Вспомнился Norton Guide из начала-середины девяностых. Он сидел в памяти под DOS как резидентная программа, всплывал и убирался по горячим клавишам, и показывал документацию в своем простом формате. Я тогда всю имеющуюся доку в его формат перевел. Потом, уже году в 98-м, когда на линукс пересел, настроил в fvwm2 горячие клавиши и управление окнами и рабочими столами, чтобы от окна с кодом мгновенно переключаться на окна с разной документацией и обратно. Тот конфиг fvwm2 до сих пор со мной, под ним и живу.
Подтверждаю, на трассе большинство фур с глушением. Частота L1 пропадает в районе заправок/стоянок и при обгоне практически каждой фуры. Расстояние, на котором сигнал спутников становится недостаточным для слежения, обычно порядка 50-100 метров.
Я бы даже сказал, что больше полутора порядков, если не больше двух. 800МБ/с для конечного пользователя стоят порядка $12, а гигабит магистрали для провайдера - порядка $300. И это разница между розницей и оптом, да еще розница включает в себя уйму операционных расходов. Так что доводы автора как минимум в этом вопросе явно неправильные.
Не подскажете модель трафаретного принтера? У нас безымянный китаец, сетка отверстий и столбики присутствуют, но люфты все-таки сильно мешают, ни о каких 0.1 и речи не идет, аж приходится на каждой плате визуально "по блеску" довыравнивать и рукой прижимать.
Самое страшное — это эксплуатация человека государством.
Коммунисты — это те, кто применили ультранасилие. Поэтому никакого разговора с ними быть не может.
Ну и еще меня тошнит от принципиальной иррациональности коммунистической идеологии, ее религиозного характера. Весь этот речекряк, ритуалы, принципиальная антинаучность (на фоне демагогических утверждений о якобы научности и рациональности).
Имхо, тут надо идти не со стороны законодательства о навигации, а со стороны законодательства об электромагнитном спектре. Не думаю, что ГКРЧ давала лицензию на совместное использование соответствующего диапазона частот тем, кто там на этих частотах излучает.
Так если перечень секретный, то он не действует. Юристы поправят, но вроде как считается, что публичные нормы права на то и публичные, чтобы действовать, в числе прочих условий, только будучи должным образом опубликованными.
Ну так сейчас уже не CPM-овские времена с расстановкой 0x1A в неиспользуемом месте последнего сектора файла. Так что нет там никакого стирания EOF, просто к концу дописывают. Правда, если последняя строка не заканчивается переводом строки — то может сконкатенировать последнюю старую строку с первой новой.
Так если VCS используется, то виноват не тот, кто к правилу раслабленно относится, а тот, кто коммитит содержательные изменения вместе со стилевыми. Ну просто несопоставимо. И если претензии к тому, кто пробелы не так ставит, лично я сочту придиркой (ну, если это не совсем уж кровь из глаз с отягчающими обстоятельствами), то коммит со стилевыми правками вперемешку с содержательными — это уже реально очень крутой продолб.
Я где-то выше уже писал, что если не нравится чей-то не соответствующий общепроектному стиль — то возьми и поправь, и закоммить отдельным коммитом, причем по возможности убедившись, что ни в чьих ветках не будет проблем слияния.
Вот именно поэтому я и не люблю энфорсинг чего угодно на уровне коммит-хуков, и поэтому же не люблю непрошенные или слишком легко делаемые "reformat code". Если это небольшая локальная правка в легаси-файле — то надо просто поправить, придерживаясь стиля, принятого в этом конкретном файле. Даже если это неудобно и нужно руками в нужных местах пробелы добавлять. А не выдавать коммит, в котором мешанина.
Или отбиться от получения кем-то за мой счет выгоды и мсти от него. Как раз рассматриваемый случай.
Да, со строками тоже неплохо, но область применимости узковата. Такое нужно только когда мы по процессору упираемся в производительность strcpy () и/или часто нужно делать strlen (). Если такого нет - то уменьшение читабельности уже не оправдывается. Так что в качестве "общего правила" - совсем не катит.
Еще мне assert () через __builtin_unreachable понравилось, я такое через typedef массива с положительной или отрицательной (в зависимости от аргумента assert-а) длиной делаю, а это тоже gcc-изм и вообще коряво. Может, даже перейду на __builtin_unreachable. Но это мелочь, отдельная капля меда в бочке понятно чего.
Какой-то список антипаттернов - как делать ни в коем случае нельзя.
Из существенного, случайно затесалась единственная идея, которую поддержу - возврат структур, явно описывающих полный результат выполнения, включая ошибки.
Похоже, я что-то не то называю алгоритмом Дейкстры :)
В том, что у меня всю жизнь было в голове, он идет вширь и переписывает метки узлов, до которых добирается. Причем добирается до них разными путями - соседом нового узла может оказаться давно посещенный. Надо подумать, возможно, проход по пути в направлении сначала ближних узлов гарантирует непосещение второй раз. Никогда об этом не задумывался.
Спасибо за наводку, без пинка я бы так и не узнал бы, что тут еще есть о чем подумать.
Опять я что-то либо не так понимаю, либо не так называю...
Дейкстра ведь приходит в каждый узел с разных направлений, и дальше из этого узла идет только когда метка узла изменилась? И выбор ребра с минимальным весом только позволяет улучшить среднее время, несколько уменьшив количество приходов в узлы, изменивших их метку? А так все равно для поиска кратчайшего пути придется посетить все достижимые вершины по всем входящим путям, просто после первого нахождения целевой вершины можно немного соптимизировать и больше не ходить путями, которые длиннее уже найденного.
Да, я уже понял свою ошибку. Дейкстра посещает узлы более чем по одному разу, эти алгоритмы неэквивалентны.
Насчет сложных структур данных: так вроде там нигде нет операций поиска? Что там можно улучшить кучей или другими структурами? Вроде бы обычного списка с исключением и вставкой по O(1) достаточно.
Поправка: как улучшить среднее время выполнения с помощью продвинутых структур данных - понятно, но худший случай выбором других структур данных вместо списков можно только ухудшить.
Понял! Действительно, эти алгоритмы не эквивалентны. При волновом алгоритме за счет поколений волн и, кстати, за счет одинакового веса ребер, обеспечивается гарантия отсутствия необходимости ходить по одному ребру более одного раза. Соответственно, и асимптотика лучше.
Но и полезные свойства по легкому натягиванию на распределенный случай тоже уходят, их не обеспечить, так как есть те самые поколения волн, а соответственно, нужны "общие часы" какого-то вида.
Кажется, у меня проблема с названиями. У того, что я в своей голове называю алгоритмом Дейкстры, асимптотика O(N*N), так как мы гарантированно не будем осуществлять "выход из узла" больше чем M раз (где M - диаметр графа, и он гарантированно <= N), и будем делать это в худшем случае для N узлов (где N - количество узлов).
Работает не особо дольше, асимптотика у него та же, и константа тоже близкая, и зависящая только от способа хранения структуры данных в памяти.
Сложнее? Тоже не кажется так. Клетчатое поле со стенками - это частный случай графа. Вес всегда единица - ну так нет особой разницы, единицу прибавлять к "дальности" или вес ребра. Обход делается одинаково, тоже в ширину.
Я этот алгоритм знал под названием "Алгоритм Дейкстры".
Кстати, у этого алгоритма есть еще неочевидное крайне полезное для некоторых применений свойство: он очень легко натягивается на распределенный случай (когда каждая клетка содержит процессор, и нет "общей шины" и "общих часов" - все общаются только со своими соседями и не знают общей картины).
Прямо ностальгией накрыло :)
Вспомнился Norton Guide из начала-середины девяностых. Он сидел в памяти под DOS как резидентная программа, всплывал и убирался по горячим клавишам, и показывал документацию в своем простом формате. Я тогда всю имеющуюся доку в его формат перевел.
Потом, уже году в 98-м, когда на линукс пересел, настроил в fvwm2 горячие клавиши и управление окнами и рабочими столами, чтобы от окна с кодом мгновенно переключаться на окна с разной документацией и обратно. Тот конфиг fvwm2 до сих пор со мной, под ним и живу.
Подтверждаю, на трассе большинство фур с глушением. Частота L1 пропадает в районе заправок/стоянок и при обгоне практически каждой фуры. Расстояние, на котором сигнал спутников становится недостаточным для слежения, обычно порядка 50-100 метров.
Я бы даже сказал, что больше полутора порядков, если не больше двух. 800МБ/с для конечного пользователя стоят порядка $12, а гигабит магистрали для провайдера - порядка $300. И это разница между розницей и оптом, да еще розница включает в себя уйму операционных расходов. Так что доводы автора как минимум в этом вопросе явно неправильные.
Не подскажете модель трафаретного принтера? У нас безымянный китаец, сетка отверстий и столбики присутствуют, но люфты все-таки сильно мешают, ни о каких 0.1 и речи не идет, аж приходится на каждой плате визуально "по блеску" довыравнивать и рукой прижимать.
Самое страшное — это эксплуатация человека государством.
Коммунисты — это те, кто применили ультранасилие. Поэтому никакого разговора с ними быть не может.
Ну и еще меня тошнит от принципиальной иррациональности коммунистической идеологии, ее религиозного характера. Весь этот речекряк, ритуалы, принципиальная антинаучность (на фоне демагогических утверждений о якобы научности и рациональности).
Имхо, тут надо идти не со стороны законодательства о навигации, а со стороны законодательства об электромагнитном спектре. Не думаю, что ГКРЧ давала лицензию на совместное использование соответствующего диапазона частот тем, кто там на этих частотах излучает.
Так если перечень секретный, то он не действует. Юристы поправят, но вроде как считается, что публичные нормы права на то и публичные, чтобы действовать, в числе прочих условий, только будучи должным образом опубликованными.
Ну так сейчас уже не CPM-овские времена с расстановкой 0x1A в неиспользуемом месте последнего сектора файла. Так что нет там никакого стирания EOF, просто к концу дописывают. Правда, если последняя строка не заканчивается переводом строки — то может сконкатенировать последнюю старую строку с первой новой.
Так если VCS используется, то виноват не тот, кто к правилу раслабленно относится, а тот, кто коммитит содержательные изменения вместе со стилевыми. Ну просто несопоставимо. И если претензии к тому, кто пробелы не так ставит, лично я сочту придиркой (ну, если это не совсем уж кровь из глаз с отягчающими обстоятельствами), то коммит со стилевыми правками вперемешку с содержательными — это уже реально очень крутой продолб.
Я где-то выше уже писал, что если не нравится чей-то не соответствующий общепроектному стиль — то возьми и поправь, и закоммить отдельным коммитом, причем по возможности убедившись, что ни в чьих ветках не будет проблем слияния.
Вот именно поэтому я и не люблю энфорсинг чего угодно на уровне коммит-хуков, и поэтому же не люблю непрошенные или слишком легко делаемые "reformat code". Если это небольшая локальная правка в легаси-файле — то надо просто поправить, придерживаясь стиля, принятого в этом конкретном файле. Даже если это неудобно и нужно руками в нужных местах пробелы добавлять. А не выдавать коммит, в котором мешанина.