Тег ‘программирование’

Очередное унижение программистов

https://felixit.blog/2018/08/16/elita/

Все так.

PS Что делать, если не хочется получить по морде? Don’t call yourself a programmer.

Ненавижу хохлов

Селюковское самомнение в сочетании с ахромными (по меркам нищей, в целом, Украины) доходами тамошних “айтишников” – термоядерная смесь.

Хуже индусов, честное слово.

fossil

А кто-нибудь в здравом уме (за исключением [info]vitus_wagner) пользовался системой контроля версий fossil?

https://www.fossil-scm.org/

Мне очень нравится тамошняя идея объединить в одно “хранилище” код, документацию в викиобразном формате и тикеты – но можно ли это все использовать в реальной жизни?

А. В. Столяров, “Программирование: введение в профессию”

Посмотрел на свежие “краудфандинговые” книги А. В. Столярова:

http://stolyarov.info/books/programming_intro

Лишний раз убедился, что фанатизм несовместим с преподавательской деятельностью – пусть заведомо ложные утверждения частично убраны, использовать эти книги в качестве учебника (и, стоит полагать, слушать лекции автора) категорически нельзя.

Можно ли с чисто педагогической точки зрения яростно обличать “стандартизаторов” языков C и C++? Возможно, не все, что они делают – правильно, но стоит ли осуждать в учебнике (!) современные стандарты? Сам автор книги давно ушел из большого секса, но те, кто по этой книге учится сейчас – будут профессионально заниматься программированием через 4-5 лет. Местами есть относительно разумные объяснения, какими возможностями из новых стандартов пользоваться не стоит – но в целом “вместе с водой выплеснули и ребенка”, и, скажем, о существовании того же stdint.h вообще не упоминается. Можно ли сейчас считать компетентным программиста на C, не знающего о существовании этого заголовочного файла – вопрос риторический.

В общем, местами книги можно считать хорошими, местами – приемлемыми, а кое-что вообще следовало бы вычеркнуть. Явно не подходит для “введения в профессию” – а вот как элементарный справочник по программированию в Unix-подобной среде использовать можно, если грамотно отделять тараканов автора от фактического материала.

2018 год

…а люди все еще с удивлением обнаруживают, что внутри ардуины стоит атмега, и что эту атмегу можно программировать на ассемблере:

https://movaxbx.ru/2018/06/05/как-программировать-arduino-на-ассемблере/

Чтобы не забыть

Столкнулся с интересным поведением Linux при попытке изобразить TCP-соединение с помощью “сырых” сокетов (raw sockets), точнее, чего-то на них похожего. Как только на не открытый “явно” (с помощью bind() и listen()) TCP-порт прилетал какой-либо пакет, что-то в составе операционной системы кидало в ответ пакет с флагом RST. Лечится такое поведение двумя способами – можно либо “недосоздать” сокет (вызвать bind(), listen() и не вызывать accept()), либо добавить правило в iptables, не позволяющее отправлять пакеты с RST – что-нибудь в таком роде:

iptables -I OUTPUT -p tcp --tcp-flags RST RST -j DROP

Про беспилотные автомобили

[info]vitus_wagner подкинул ссылку на MIT-овскую статью по модной теме беспилотных автомобилей. Анонс – “В MIT разработали систему, которая позволяет беспилотным автомобилям ездить по сельским дорогам без точной карты” – не очень точно отражает суть работы. Системы типа nVidia DAVE2, довольно простые в реализации (у меня есть даже подборочка материалов по теме) точно так же могут вертеть рулем в нужном направлении, и для своей работы требуют только видеокамеру, смотрящую вперед – данные от GPS и карта там необязательны.

Что отличает эту систему от “нейросетевого” подхода – даже не детерминированность, пусть даже она и приятна (есть несколько публикаций, показывающих, что нейросеть по образцу сделанной в nVidia “сходит с ума” при некоторых манипуляциях с картинкой – вплоть до того, что пытается повернуть совсем в другую сторону, если изменить в картинке на входе всего один пиксель). Внимательно попробуйте осознать описание DAVE2 – эта система определяет угол поворота руля, исходя из картинки, которую видит перед собой “водитель”. Но… Посмотрите на эту схему, в том или ином виде присутствующую в любом вводном материале про спортивное или “экстремальное” вождение:

apeks

Три траектории, изображенные здесь – это три разных способа прохождения одного и того же поворота, в той или иной степени “хорошие” (в зависимости, конечно, от прочих факторов). Для наглядности изображена “шпилька” – поворот на 180°, но вся та же теория остается верной и в том случае, если угол будет другим. “Осознанное” управление автомобилем предполагает, что водитель, подъезжая к повороту (из левого нижнего угла картинки), определит точку поворота руля и точку апекса – и, соответственно, траекторию в повороте. Но обратите внимание, что видимая картинка при приближении к повороту во всех трех случаях одинакова – так что система, полагающаяся в своем принятии решений только на текущий видеокадр, очевидно будет неспособна “выбирать” траекторию. Обратите внимание на то, как в ролике nVidia нейросеть “крутит” руль, дергая его туда-сюда (примерно на 7:32):

А представьте, если это будет происходить не на сухой дороге и не на смешной скорости, а в гололед? На небольшой скорости, имея отличный “запас” сцепления шин с дорогой, можно позволить себе игнорировать “физику” движения автомобиля – что и делают сейчас последователи nVidia. Если же дорожные условия становятся чуть более сложными – то так можно оказаться и в кювете.

Так вот, важнейшее, на мой взгляд, новшество в подходе MIT – это определение траектории, исходя из конфигурации дороги. Границы дорожного полотна их система определяет с помощью лидара, сканирующего пространство вокруг автомобиля с частотой 5 раз в секунду. Затем строится “локальная” траектория (довольно примитивным, правда, образом – ровно посередине между левой и правой обочинами “вписывается” сплайн, то есть достаточно гладкая кривая), и до очередного обновления автомобиль движется по этой траектории. Никто, в общем, не мешает “вписывать” траекторию и более “правильным” образом – скажем, между правой обочиной и серединой дороги, как предписывают ПДД.

Заметьте, насколько это отличается от подхода “авось нейросеть научится” :)

База данных за один вечер и три бутылки пива

Для начала – о том, как делать не надо. Вот представьте, что вам надо сохранять в какой-нибудь базе данных показания каких-нибудь датчиков, чтобы потом показывать их в модном веб-приложении. Вы уже хотите написать что-то в таком духе?

CREATE TABLE measurements (
    measurementID int NOT NULL AUTO_INCREMENT,
    sensorID int NOT NULL,
    time datetime NOT NULL,
    value double NOT NULL,
    PRIMARY KEY (measurementID)
)

Это очевидно неправильно – имел удовольствие несколько лет подряд наблюдать за эволюцией небольшой SCADA-системы, где хранение данных организовали примерно так. Пока датчиков было немного – оно работало, но примерно на сотне-другой обновляющихся примерно раз в 5-10 секунд датчиков потребовало для работы некоторых костылей. Для начала – в БД перестали записывать “небольшие” изменения данных – скажем, меньше 5% (величина была выбрана довольно произвольно – не надо спрашивать, соответствует ли такой подход требованиям технического задания :) ) от предыдущего сохраненного значения. Затем – по мере накопления данных соорудили чудовищную систему из триггеров и хранимых процедур, которая автоматически создавала “архивные” таблицы сравнительно небольшого размера. Впоследствии, конечно же, выяснилось, что эта система временами глючит и иногда новую таблицу для архива надо создавать вручную.

Наконец, на одном из объектов в дополнение к привычным “медленным” газоанализаторам поставили два десятка акселерометров – и тут все повалилось уже серьезно. Во-первых… нет, для начала в нулевых. Не надо говорить мне, что datetime в SQL неспособен хранить данные с “разрешением” меньше секунды, а опрашиваемый раз в секунду акселерометр бесполезен – тут речь шла уже о том, чтобы записать в базу хоть что-то. А теперь во-первых – показания акселерометров меняются сравнительно быстро и под фильтр “небольших” изменений данных не подпадают, и во-вторых – отказы БД стали чуть ли не ежесуточными. Считайте сами – в сутках 86400 секунд, и при двух десятках пишущих что-то датчиков мы влегкую получаем 1,7 миллиона записей в сутки. Да, часть из них отфильтруется – но и миллиона строк хватит, чтобы популярные СУБД с SQL хорошо и надежно “легли”.

Признаться, я списывал многое из этих проблем на невысокую квалификацию разработчиков этой системы, но после доклада Сергея Аксенова “Антипаттерны разработки программных комплексов для интернета вещей” на Inothings++ понял, насколько героические люди используют SQL для хранения такого рода данных. Про выбор СУБД в видео – с 4:28:

Идея понятна – реляционные СУБД расчитаны на количество строк порядка миллионов (десятков миллионов – если у вас поблизости есть грамотный администратор баз данных), а как легко посчитать – это всего лишь суточный архив сравнительно небольшой системы. Впрочем, случай “Стрижа” еще более-менее прост – частота опроса каких-нибудь ЖКХшных счетчиков относительно небольшая, всего несколько раз в сутки. А что делать, если хочется хранить, скажем, данные по 16 каналам АЦП с небольшой в общем-то частотой дискретизации в 16 тысяч выборок в секунду? Нет, я прекрасно представляю, как это сделать “на файлах”, и это совсем не сложно – простенький формат хранения данных можно полностью реализовать за неделю неспешной работы (собственно, что-то наподобие edflib, но работающее на микроконтролере с сотней килобайт памяти я написал в прошлом году где-то за несколько дней):

Implementing EDF takes a week. EDF+ takes a few weeks but is better and more powerfull. If you still decide to start with EDF, it is wise to adopt the 12 simple additional EDF+ specs.

Не смотрите, что он предназначен для записи всяких физиологических данных – я в таком виде пробовал всякие обороты двигателя, расход воздуха и прочее время впрыска записывать, они в этот формат прекрасно вписываются :)

Еще из полезного чтения – статья Luca Deri о системе, названной им tsdb – построенной поверх Berkeley DB системе, обеспечивающей хранение миллионов (!) временнЫх рядов (time series – собственно, это общее название для такого рода данных). Решение не совсем подходящее для моего случая – но опять же содержащее несколько полезных идей.

Для начала – система, многократно превосходящая по производительности решения на основе SQL, реализована всего лишь в 1000 или около того строк кода на Си. Именно это и вдохновило меня на написание собственного решения – 1000 строк это совсем немного, а следовательно, должно быть довольно просто. Второе – данные желательно каким-либо образом объединять – если в tsdb это сделано довольно произвольным образом (в базе много редко обновляемых временных рядов), то в моем случае я просто решил писать “секундные” (или соответствующие какой-то доле секунды) записи, как в EDF.

В общем, осознав эти “три источника и три составные части”, я взял пивка и засел за Visual Studio – и примерно за вечер написал прототип базы данных, оптимизированной под мои требования – десятки-сотни одновременно записываемых временных рядов с частотой дискретизации от единиц до тысяч Гц. Собственно, по факту получился тот же EDF, только записанный в Berkeley DB. Выбор довольно произвольный (прежде всего – ее используют в tsdb) – но эта, так сказать, “встраиваемая СУБД” поразила меня своей простотой. Немного не радует лицензия – хотя при желании могу выложить код на какой-нибудь гитхаб для очистки совести.

Что могу сказать? Не прилагая никаких усилий в части оптимизации, на собственном ноутбуке я “из коробки” получил скорость записи в базу данных около 40-50 Мбит/с (похоже, упираясь в производительность жесткого диска) – причем, судя по всему, падения производительности с ростом числа записей в БД не происходит. Например, в БД размером около 11,5 Гб – это чуть меньше 1,5 миллионов записей по 8 килобайт (в каждой из записей – по 4000 “точек”, каждая из которых – двухбайтовое целое) никакого снижения скорости записи или чтения я не наблюдал (дальше просто стало жалко жесткий диск). Что забавно – тесты “на чтение” демонстрируют полезность кеширования – сначала 10 000 записей читаются за долгие 8 секунд, а затем, если повторить тот же тест “не отходя от кассы” – за 0,22 секунды. Не видел бы – не поверил.

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

PS А если вам все же нравится SQL – почитайте, как правильно организовывать хранение time series в реляционной БД:

https://blog.timescale.com/time-series-data-why-and-how-to-use-a-relational-database-instead-of-nosql-d0cd6975e87c

И все-таки хочу напомнить, что решение “на коленке” практически не уступает приведенному в статье по ссылке в плане производительности (и да, надо бы проверить его с четырехгигабайтным кешем :) ).

Операционная система из говна и палок

На “Гиктаймсе” опубликовали конспект первой лекции курса Олега Артамонова по программированию микроконтролеров. Курс, конечно, немного экзотический в сравнении с любым интернетовским руководством по тем же STM32 – в нем рассматривается программирование с использованием операционной системы RIOT. Никакого вам CubeMX, никакой FreeRTOS – но в целом материал не особо привязан к конкретной ОС и “железу” и ориентирован скорее на то, чтобы продемонстрировать подходы к программированию для микроконтролеров “вообще”.

Для тех, кому проще воспринимать видео – на Youtube выкладываются и видеозаписи лекций:

https://www.youtube.com/playlist?list=PLJEYfuHbcEIApuZR4L5tRiBCwTZCYeTNY

Но при всех заявленных и видимых достоинствах этих лекций, хвалить их целиком пока рано – поэтому перейду к всякой ерунде. Как водится, половина удовольствия от чтения “околоэлектронных” материалов на “Хабре” и “Гиктаймсе” – это комментарии, где обычно ссаными тряпками гоняют ардуинщиков. В этот раз к “гонимым” добавились также те, кто не осилил ничего, кроме всевозможных HAL и StdPeriphLib от производителя, и те, кто почему-то считает микроконтролером Raspberry Pi. Но все это не заслуживало бы упоминания – если бы не один комментарий:

…например, в Contiki — там многозадачность с инвалидностью третьей группы, там надо в треде либо без switch-case, либо без сообщений жить. Этому в университете всех учить не надо, кому в жизни не посчастливится — сами научатся.

https://geektimes.ru/company/samsung/blog/299187/#comment_10699171

Полез смотреть, что же за альтернативный подход к многозадачности исповедуют авторы операционной системы Contiki – и обнаружил там совершенно замечательную штуку. Оказывается, тамошнее подобие “потоков” обычной RTOS реализовано довольно необычно, исключительно средствами языка C.

Для начала – вот такой хитрый пример кода, который обычно называется Duff’s device – “Прием Даффа”, в честь Тома Даффа, обратившего внимание на то, что метки в конструкции switch языка C позволяют нарушать “блочную” структуру программы – например, перейти сразу внутрь цикла:

switch (count % 8) {
    case 0:    do { *to = *from++;
    case 7:         *to = *from++;
    case 6:         *to = *from++;
    case 5:         *to = *from++;
    case 4:         *to = *from++;
    case 3:         *to = *from++;
    case 2:         *to = *from++;
    case 1:         *to = *from++;
               } while ((count -= 8) > 0);
}

Кстати говоря, Duff’s Device упомянут [info]sharpc в известном “Теоретическом минимуме для программиста“. Конструкция довольно дикая, мало чем отличающаяся от GOTO – и хочу заметить, что особых преимуществ по скорости (в оригинале она использовалась для того, чтобы развернуть цикл в memcpy) на современных процессорах она не дает. Знать о ней, наверное, надо, а вот применять – только по необходимости.

А теперь сделаем еще один шаг вперед – обратите внимание, что такой переход позволяет “сохранить” текущее положение “внутри” выполняемой функции. Сначала пример без макросов (взятый со странички Адама Дункельса про protothreads и немного измененный):

volatile int counter;

int example( int *lc ) {
    switch ( *lc ) { case 0:

    printf( "First run!\n" );
    while ( 1 ) {
        *lc = 9; case 9: if ( !(counter > 10) ) return 0;
        printf( "Threshold reached\n" );
        counter = 0;
    }

    } *lc = 0; return 2;
}

Будем вызывать эту функцию примерно таким образом:

int main( void ) {
    int lc = 0;

    while ( 1 ) {
        example( &lc );
        printf( "Back in main, counter = %d\n", counter );
        counter++;
    }

    return 0;
}

Обратите внимание, что строчка First run! напечатается только один раз, несмотря на то, что функция вызывается многократно. Фактически, таким нехитрым приемом реализован механизм ожидания событий – нетрудно догадаться, что в промежутках между вызовами нашей функции counter может изменяться как угодно (на это я намекаю, объявив его volatile). А теперь определим несколько макросов:

struct pt {
    int lc;
};
#define PT_BEGIN(pt)          switch((pt)->lc) { case 0:
#define PT_WAIT_UNTIL(pt, c)  pt->lc = __LINE__; case __LINE__: if(!(c)) return 0
#define PT_END(pt)            } (pt)->lc = 0; return 2
#define PT_INIT(pt)           (pt)->lc = 0

И перепишем пример, используя их:

volatile int counter;

int example( struct pt *pt ) {
    PT_BEGIN( pt );

    printf( "First run!\n" );
    while ( 1 ) {
        PT_WAIT_UNTIL( pt, counter > 10 );
        printf( "Threshold reached\n" );
        counter = 0;
    }

    PT_END( pt );
}

int main( void ) {
    struct pt example_pt;
    PT_INIT( &example_pt );

    while ( 1 ) {
        example( &example_pt );
        printf( "Back in main, counter = %d\n", counter );
        counter++;
    }

    return 0;
}

Хочу добавить, что в компиляторе из Microsoft Visual Studio этот пример не работает, если при компиляции указан параметр /ZI (он по умолчанию установлен для конфигурации Debug) – можно заменить его на /Zi.

Оцените, что получилось – исключительно средствами языка C реализован простенький, из говна и палок, механизм кооперативной многозадачности. Если добавить к нему планировщик и, скажем, какой-нибудь таймер, то получится та самая операционная система Contiki – названная в честь построенной из тех же говна и палок лодки Тура Хейердала. Теоретически, в Contiki есть и механизм вытесняющей многозадачности – но реализован он не для всех архитектур, в отличие от кооперативной, для которой достаточно лишь компилятора C. Это позволяет “портировать” ядро Contiki куда угодно.

Какие же у этого подхода недостатки? Начну с очевидного – использовать одновременно и protothreads, и конструкцию switch нельзя. Другая нехорошая штука – при переходе потока в состояние ожидания и выходе в планировщик теряются значения всех локальных переменных внутри функции этого потока. Это довольно неприятно, так как требует постоянно держать в голове “нестандартное” поведение программы. Бороться с этим можно либо объявляя локальные переменные потока, как static, либо используя глобальные переменные. Наконец, ждать событий можно только в основной функции потока, что резко ограничивает “полет фантазии” в реализации какой-то нетривиальной логики.

Впрочем, все это позволяет реализовать некоторое количество не очень сложных примеров – которые и составляют большую часть “дистрибутива” Contiki.

Глазами ученого на Хабре

Почитайте (сам исходный пост не айс, а вот комменты осилить очень рекомендую), очень здорово видна разница в образе мышления программистов и “ученых”:

https://habrahabr.ru/post/349624/

В комментах, правда, выясняется, что “ученый” тоже в говне моченый, но и “оппоненты” отжигают не по-детски.

PS И даже не знаю, какой из этих двух вариантов омерзительнее:

C и С++ изучают только программисты. Естественнонаучники (за очень редким исключением) учат программирование на Делфи, а потом всякие спецпакеты. Максимум пролог будет. Там не учат С98. Там не учат что памятью в принципе можно управлять. Тем более — что нужно. Учат так: вы придумываете правильный алгоритм, компьютер его выполняет. Учат как переписать алгоритм из головы на паскаль.

https://habrahabr.ru/post/349624/#comment_10682588

или

Я не знаю где вас учили, но на моём естественно-научном факультете сначала был курс C# (2 года). А теперь вообще идёт курс Java EE c Хадупами и всем фаршем.

https://habrahabr.ru/post/349624/#comment_10682700

Open Source как религия

Осознал между делом, что за фразой “Мы используем X, потому что это open source” могут быть две совершенно разные мотивации. Первая, “религиозная”, встречается, например, у малолетних читателей журнала “Ксакеп”. Вторая, “практическая”, выражается словами – “можно сделать форк, если когда припрет“.

Особенно забавно, что когда “практики” все-таки задалбываются от кривых понятий “руководителей” опенсорсного проекта и наконец-то делают пресловутый форк, то “верующие” их всячески за это осуждают.

Продолжим поиски

По рекомендации Sergey из комментариев к недавней записи про Trac и Subversion посмотрел на систему контроля версий Mercurial. В принципе, понравилось – хотя TortoiseHg выглядит намного запутаннее TortoiseSVN; с другой стороны, принцип работы с DVCS немного закрывает некоторые из моих проблем – с частью проектов приходится работать без доступа к интернету.

Если рассмотреть переход на Mercurial – то список сервисов из той записи сожмется до двух вариантов (напомню, что цены приведены за 5 Гб места):

Xp-Dev 96$ = 5800 рублей/год Есть также git и Mercurial
repositoryhosting.com 108$ = 6500 рублей/год Есть также git и Mercurial; новости на сайте заканчиваются 2014 годом

Если продолжить в том же направлении – то зачем упираться в Trac? Может, появилось что-то еще? Предлагают использовать Jira – но по-моему, она предназначена для “управления проектами” в стиле Agile и прочего Scrum. Мне надо кое-что попроще – в “моих” проектах присутствует один (редко два) разработчика, он же в большинстве случаев сам себе и начальник, и тестер. Соответственно, надо:

- простой багтрекер;
- вики для документирования и записи всяких умных мыслей;
- желательно интегрированный со всем этим делом просмотр исходного кода.

Trac в принципе всем этим требованиям удовлетворяет – но на что еще стоит посмотреть? Ах да, еще одно требование – не хочется попадать, так сказать, на vendor lock-in – в Trac мне нравится то, что я могу забрать все содержимое “проекта” и развернуть его заново где угодно, хоть на собственной персоналке.

А где сейчас модно размещать хранилище Subversion?

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

Первый вариант: взять дешевый VDS; например, минимальный тарифный план у FirstVDS.ru – 199 рублей в месяц, или около 2400/год. За эти деньги предлагается виртуальный сервер с 1 Гб оперативной памяти и 30 Гб диска. Навскидку, такая конфигурация “потянет” Apache со всеми необходимыми причиндалами. Основной минус – надо самостоятельно все это администрировать, а мне это ох как не хочется. Не то, чтобы я сомневался в своих способностях делать все по мануалам – в конце концов, я ставил Trac и SVN на сервер с Windows – но просто не хочется лезть в администрирование.

Второй вариант – посмотреть в сторону специализированного хостинга Trac+Subversion. Нашел несколько разных сервисов, для сравнения возьму стоимость тарифного плана “на 5 Гб” (где-то он идет как минимальный, где-то, наоборот – почти самый крутой):

MySvn 1200 рублей/год Выглядит полумертвым
Xp-Dev 96$ = 5800 рублей/год Есть также git и Mercurial
ProjectLocker 228$ = 13700 рублей/год Не более 5 проектов; есть также git
demobereich 79 Евро = 5500 рублей/год Немцы со всем отсюда вытекающим; последние новости на сайте – за 2012 год
DevZing 144$ = 8600 рублей/год
ProjectHut 228$ = 13700 рублей/год Не более 20 проектов; есть также git
repositoryhosting.com 108$ = 6500 рублей/год Есть также git и Mercurial; новости на сайте заканчиваются 2014 годом

Тут, конечно, стоит обратить внимание на разброс по цене – в 10 раз, на порядок! “Средний” же хостинг с Trac и SVN стоит около 5-6 тысяч рублей. Очень привлекательно на общем фоне выглядит MySvn – но он производит впечатление полумертвого.

А кто что посоветует?

PS Гитхаб не предлагать.

Про музыку

Лучшее музыкальное сопровождение процесса установки Visual Studio – какой-нибудь убойный NSBM.

Вы делаете это неправильно

По-моему, почти в каждый курс программирования входит задачка вроде “напишите программу, решающую квадратные уравнения”. Обычно это второе или третье задание после “Hello, world!” – считается, что это хороший способ продемонстрировать нетривиальные инструкции ветвления. “Хорошее” решение сводится к вычислению дискриминанта и в случае, если он неотрицательный – вычислению корней квадратного трехчлена ax2+bx+c по формуле, известной из курса алгебры за седьмой, что ли, класс:

square1

Вот такой вариант решения обычно считается более-менее приемлемым (хотя его можно/нужно обвешать еще несколькими проверками – например, не равен ли коэффициент a нулю?):

int solve(double a, double b, double c, double *x1, double *x2){
	double d = b*b - 4.*a*c;
	if( d >= 0 ){
		d = sqrt(d);
		*x1 = (-b + d)/(2.*a);
		*x2 = (-b - d)/(2.*a);
		return 0;
	}
	return -1;
}

В чем проблема? На первый взгляд все более-менее хорошо, но… Давайте для тестирования будем подсовывать уравнения с известными корнями – используя для этого теорему Виета. А именно, зафиксируем коэффициент a=1, тогда уравнение с корнями x1 и x2 будет иметь коээффициенты b=-(x1+x2) и c=x1x2. Сравнивая корни, полученные при решении уравнения, с известными нам, оценим “качество” решения.

Если корни “нормальные” – те, с которыми справится шестиклассник – то все хорошо. Но что будет, если взять два “нехороших” корня – к примеру, x1=1, x2=10-14 (это для double; если вы пользуетесь float – то возьмите второй корень, равный 10-5)? Проверьте – не забыв включить вывод максимально возможного количества значащих цифр (в printf лучше всего использовать форматный спецификатор %g, при использовании вывода в стиле C++, через iostream, такой вывод включен по умолчанию). Ошибка при вычислении второго корня возникнет уже в четвертой значащей цифре, это, на самом деле, уже довольно неприлично.

В чем дело? Если обратить внимание на “обычную” формулу для вычисления корней квадратного уравнения, то мы увидим, что при вычислении меньшего корня корень из дискриминанта вычитается из b – а так как они в этом случае очень близки, то возникающая при этом вычислительная ошибка оказывается слишком большой.

Метод, разумеется, можно улучшить. Для начала – можно вспомнить о существовании еще одной формулы для корней квадратного уравнения:

square2

Выводится она абсолютно аналогичным образом, от “классической” отличается тем, что “не работает” при c=0.

Если переписать программу, чтобы она использовала эту формулу – то меньший корень “нехорошего” уравнения будет вычисляться точно, а проблемы возникнут с большим корнем. Причина та же самая – вычитание двух близких по величине чисел. Но ведь если вычислять больший корень по первой формуле, а меньший – по второй, то эта проблема исчезнет! Поэтому более правильный метод решения квадратного уравнения должен выглядеть так:

- вычисляем дискриминант D=b2-4ac
- если дискриминант неотрицателен, то вычисляем

q

- корни уравнения равны q/a и c/q.

Как реализовать это в программе – довольно очевидно, это особо ее не усложнит.

Какая здесь мораль? Численные методы и программирование – это две совершенно разных области человеческого знания. Математические задачки – вроде решения квадратного уравнения – могут показаться интересными с точки зрения обучения программированию, но это “чужая территория”, и можно столкнуться с совершенно непредсказуемыми вещами. Признайтесь, многие ли слышали о сложностях, возникающих при решении на компьютере квадратных уравнений – хотя казалось бы, что может быть проще?

Скажите, а с ARM все действительно так плохо?

В одном прожекте возникла необходимость беспроводной передачи неприличного количества данных с АЦП. Даже в самых оптимистичных сценариях получалось, что придется гнать без проводов поток данных порядка 150 кбит/с. Немного? Но при таком потоке “затыкаются” все легкодоступные радиоудлинители UART – неважно, какой там у них радиоинтерфейс – WiFi, Bluetooth, или что-то еще. Более того, большинству из них недоступна скорость выше 115200 бод, что “отсекает” их еще на этапе ознакомления с ТТХ.

В поисках какого-то более подходящего решения набрел на микроконтролер CC3200 производства Texas Instruments. Что мне понравилось? По пунктам:

- ядро Cortex-M4 (хотелось бы, конечно, Cortex-M4F, но и это сойдет);
- встроенный WiFi, по отзывам – действительно быстрый;
- встроенные раздельные модули SPI и SD-host (я сначала думал, изучая примеры, что обмен с SD-картой будет идти с использованием модуля SPI, судя по назначению выводов – но нет, они там никак не связаны);
- возможность переназначать выводы утилитой Pinmux – хочешь, заводи SD-карту на эту сторону микрухи, хочешь – на другую, в общем, все офигенно.

Ну, где у нас АЦП – там хорошо бы и обработать сигнал? Благо в ядре Cortex-M4, в отличие от распространенного Cortex-M3, присутствуют команды, упрощающие цифровую обработку сигналов – например, реализацию всевозможных цифровых фильтров. Но на этом этапе начались какие-то дикие танцы с бубнами :)

Для начала – есть библиотека CMSIS, унифицированная для всех ARM реализация некоторых часто используемых функций. Особенно мне была интересна CMSIS-DSP, часть библиотеки с реализацией функций для цифровой обработки сигнала. Да, я могу написать реализацию какого-нибудь там фильтра Баттерворта или быстрого преобразования Фурье – но оптимизировать его для ARM я вряд ли буду, да и зачем это делать, когда есть готовое общепринятое решение?

Но для использования этого готового решения требуется некоторая поддержка от производителя микроконтролера – и здесь все становится просто ужасно. У Texas Instruments используется своя среда разработки (на основе Eclipse) и свой же компилятор. Может, имей я больше опыта программирования под ARM, я бы настроил что-то более распространенное, но для начала я просто следовал пунктам из Quick Start Guide.

Так вот, основное преимущество Cortex-M4 над Cortex-M3 – поддержка “DSP instruction set” – вообще никак не афишируется производителем в случае CC3200. Да, есть “патч” для одной из относительно старых версий CMSIS, выпущенный Texas Instruments несколько лет назад – но применимость его в случае CC3200 не озвучивается (и действительно, если “втупую” применить этот “патч”, ничего не выйдет). На просторах ютуба нашлось вот такое видео:

Через 15 секунд просмотра уже хочется восславить Кришну, а через минуту так и ждешь, что все начнут петь и плясать. Если серьезно – пахнет индусятиной в худшем смысле этого слова. Из озвученных в видео шагов один – фундаментально неправильный, а еще нескольким я не смог найти внятного объяснения.

В конечном итоге CMSIS-DSP я собрал (откомпилированная библиотека из дистрибутива с компилятором TI не очень дружит) – хотя, конечно, некоторые вопросы остались. И главный из них – в заголовке. Неужели любой шаг в сторону от любовно подобранных примеров из SDK превращается в вот такой забег по граблям под руководством индусов?

Гугл, мать его

А что такое замечательное сделали в Android Studio, что она еле ворочается на относительно современном ноутбуке? Eclipse, например, в разы быстрее.

Math Toolkit for Real-Time Development

Прочитал совершенно замечательную книжку Jack Crenshaw “Math Toolkit for Real-Time Development”. Хоть она и предназначена в первую очередь для программистов “встраиваемых систем” – читал с большим удовольствием. А почему? А просто потому, что она в первую очередь – про математику, а не про программирование.

Любой относительно нормальный программист почти не задумывается над тем, как реализованы функции из “стандартной” математической библиотеки. Крайне нечасто возникают и задачи, где надо как-то учитывать, скажем, ограниченную точность чисел с плавающей запятой. Во вводных курсах программирования такие вещи практически никогда не рассматривают, а если и рассматривают – то неправильно. Например, я был в свое время очень удивлен, когда узнал, что некоторые вполне себе профессиональные программисты не имеют никакого представления об IEEE 754, и искренне считают, что вещественные числа в Delphi ведут себя так же, как вещественные числа в школьной математике.

Почему речь идет именно про “встраиваемые системы”? Книжка написана в 2000 году, задолго до того, как появилось представление об Internet of Things – и встраиваемые системы оставались последним местом, где жила всякая экзотика типа восьми- и шестнадцатибитных процессоров. Сейчас это уже немного не так, всякие PIC и AVR в более-менее серьезных местах найти уже трудно, а даже самой простенькой техникой рулят микроконтроллеры, которые по своим характеристикам уже вплотную подбираются к моему первому компьютеру (и заметьте – начинал я отнюдь не со “Спектрума”, я еще не настолько стар!). В общем, о практическом применении этой книжки можно и поспорить.

В общем, будем считать, что эта книга со временем все больше и больше приближается к “чистой”, то есть совершенно бесполезной, математике. Глобально в ней рассматриваются две темы – реализация некоторых “математических” функций, обычно входящих в стандартную библиотеку, и некоторые численные методы – дифференцирование, интегрирование и решение задачи Коши для дифференциальных уравнений. Первая из них возникала в мехматовском “Программировании и работе на ЭВМ”, вторая – в том или ином виде присутствовала в течение всех четырех лет, что на мехмате читается курс околокомпьютерных наук (речь о 2005-2010 годах, сейчас что-то немного поменялось) – но в целом я бы отнес это к второму семестру.

Что можно сказать про первую тему? Да, писать собственные синусы с косинусами приходится немногим. Но очень и очень немногие при необходимости смогут сделать это правильно. Из “остаточных знаний” второго семестра я смог бы навскидку назвать лишь пару-тройку из тех “подводных камней”, что упоминаются в книге. О некоторых вещах речь вообще не заходила ни разу и они оказались для меня сюрпризом. Более того, даже для сравнительно простой задачи – вычисления квадратного корня – приводится несколько алгоритмов, отличающихся требованиями по точности, скорости, наличию или отсутствию математического сопроцессора. Если вам вдруг захочется реализовать вычисление квадратного корня на каком-нибудь AVR – есть и “целочисленный” алгоритм.

Один из шедевров, не побоюсь этого слова, приведенных в книге – функция bitlog(), приближенно вычисляющая логарифм. Вместе с ее кодом – который можно смело использовать для любых Obfuscated C Contest – приводится подробнейшее описание, как и почему она работает.

/* Bitlog function
*
* Invented by Tom Lehman at Invivo Research, Inc.,
* ca. 1990
*
* Gives an integer analog of the log function
* For large x,
*
* B(x) = 8*(log(base 2)(x) – 1)
*/
short bitlog(unsigned long n)
{
    short b;
    // shorten computation for small numbers
    if(n <= 8)
        return (short)(2 * n);
    // find the highest non-zero bit
    b=31;
    while((b > 2) && ((long)n > 0))
    {
        --b;
        n <<= 1;
    }
    n &= 0x70000000;
    n >>= 28;
    cout << b << ' ' << n << endl;
    return (short)n + 8 * (b - 1);
}

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

Вторая группа вопросов, разобранных в этой книге - численные методы. Уровень математической строгости, конечно, уступает "кирпичу" Бахвалова, да и первой части этой же книги - но дело в том, что для понимания численного дифференцирования и интегрирования надо хотя бы немного знать о дифференцировании и интегрировании обычном - на что американский автор книги для программистов рассчитывать никак не может. Тем не менее, приводятся несколько формул численного дифференцирования и интегрирования с оценками их точности и читатель даже подводится к одному из способов построения таких формул - представить, что функция приближена многочленом, и добиться того, чтобы для многочленов рассматриваемая функция была бы точной.

Для дифференциальных уравнений довольно подробно рассматриваются методы Адамса (многошаговый) и Рунге-Кутты. Опять же, так как с точки зрения программирования они тривиальны, много внимания уделяется получению формул для расчетов. Это все вполне доступно второкурснику мехмата (или любому, кто осилил формулу Тейлора и азы программирования), так что вполне можно обозвать книжку "Кратким введением в численные методы".

Что очень важно - такого рода "элементарного" учебника на русском языке я припомнить не могу. Учебники по численным методам рассчитаны на студентов где-то 4 курса и обычно требуют неплохой математической подготовки вместе с серьезным "погружением" в предмет. Книги "для программистов" обходят численные методы стороной - тема эта все-таки довольно специфическая. Ценность же этой книги - в том, что в ней рассматриваются некоторые неочевидные приемы, о которых, как я помню, действительно упоминалось на семинарах - но они сохранились у меня в лучшем случае в виде "остаточных знаний", а в худшем - "вроде это было вот в той книжке" (а по численным методам пришлось почитать довольно много чего интересного, спасибо И. С. Григорьеву и его отношению к прогульщикам-халявщикам).

В общем, мне понравилось.

Хочется напомнить

Московский районный суд г. Калининграда подкинул повод перечитать Falsehoods Programmers Believe About Names. Кто не читал – рекомендую.

Нужно ли программисту высшее образование

Нашел весьма забавные “десять мнений”:

http://eax.me/education/

Половина авторов не знает, что такое “высшее образование”, примерно такое же количество не может толком сформулировать, кто же такой “программист”. Весьма показательно.