Сотрудник Mozilla Николас Нетеркот опубликовал заметку с очень чётким объяснением, почему размер буфера памяти для программы нужно увеличивать экспоненциально, а не линейно.

Предположим, что у нас есть структура данных, для которой нужно всё больше памяти, например, строка или вектор. Если новые элементы не помещаются в буфере, то создаётся новый буфер, туда копируются всё содержимое из старого, а затем старый буфер освобождается. Обычное этим занимается realloc().

Так вот. Представим, что наш изначальный 1-байтный буфер растёт по 1 байту до тех пор, пока не достигнет размера 1 МиБ. Сколько памяти мы задействовали для него кумулятивно?

1 + 2 + 3 + … + 1,048,575 + 1,048,576 = 549,756,338,176 байт

Неслабо, да?

Введение

Этот текст можно рассматривать как обзор библиотеки Strutext, задуманной автором как набор эффективных алгоритмов лингвистической обработки текста на языке C++. Код библиотеки находится в репозитории на Github. Библиотека имеет открытый исходный код и поставляется под лицензией Apache License 2.0, т.е. может быть использована совершенно бесплатно без каких-либо существенных ограничений.

В примерах использованы Qt Creator 3.0.0 (MinGW) и Qwt-6.1.0.

Для понимания этой статьи читатель должен иметь начальный опыт разработки windows-приложений в среде Qt Creator, понимать концепцию «сигнал-слот». Также рекомендуется познакомиться с частью №1 и №2 цикла моих статей про Qwt:

habrahabr.ru/post/211204
habrahabr.ru/post/211867

Qwt – графическая библиотека, позволяющая значительно упростить процесс визуализации данных в программе. Упрощение заключается в следующем: нет необходимости вручную прописывать элементы отображения, такие как шкалы координат, сетки, кривые данных и проч. Следует лишь задавать параметры этих элементов.

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

В части №3 мы сделаем следующее:

• добавим виджет для отображения графика в Designer Form, что позволит использовать элементы управления Qt Creator;
• построим демонстрационную кривую, реализуем базовые удобства работы с графиком: возможность перемещения по полю графика, его приближение/удаление, отобразим координаты курсора при его перемещении;
• отобразим координат клика в строке состояния Designer Form;
• переместим кривую вдоль оси х, используя стандартные элементы управления из Qt Creator.

В примерах использованы Qt Creator 3.0.0 (MinGW) и Qwt-6.1.0.
Для понимания этой статьи читателю желательно:

• иметь начальный опыт разработки windows-приложений в среде Qt Creator;
• понимать концепцию «сигнал-слот»;
• познакомиться с частью №1 цикла моих статей про Qwt: habrahabr.ru/post/211204

Qwt – графическая библиотека, позволяющая значительно упростить процесс визуализации данных в программе. Упрощение заключается в следующем: нет необходимости вручную прописывать элементы отображения, такие как шкалы координат, сетки, кривые данных и проч. Следует лишь задавать параметры этих элементов.

В части №1 (постепенно разрастающегося) цикла статей мы:
• подключили Qwt к Qt Creator;
• построили график;
• настроили оси координат;
• изменяли масштаб графика (приближали/удаляли его);
• перемещались по полю графика;
• отображали координаты рядом с курсором по щелчку мышкой.

В части №2 мы расширим функциональность нашего визуализатора:
• добавим строку состояния;
• сохраним координаты клика в переменных и отобразим их в строке состояния;
• добавим кнопку на панель управления;
• добавим на панель управления QwtCounter (поле для номера, значение которого можно изменять стрелками, см. картинку).
• зададим с помощью QwtCounter смещение графика x;
• нажатием на кнопку сместим график на ранее заданную величину х.

Примечание: В рамках этой статьи при добавлении элементов управления GUI не используется.

Для понимания этой статьи читатель должен иметь начальный опыт разработки windows-приложений в среде Qt Creator.
В примерах используются Qt Creator 3.0.0 (MinGW) и Qwt-6.1.0.

Qwt – графическая библиотека, позволяющая значительно упростить процесс визуализации данных в программе. Упрощение заключается в следующем: нет необходимости вручную прописывать элементы отображения, такие как шкалы координат, сетки, кривые данных и проч. Следует лишь задавать параметры этих элементов.
Аналогия: для того, чтобы построить график в Excel Вы выбираете данные и настраиваете параметры их отображения: минимум и максимум шкал, цвет кривых, подписи данных и др. За визуализацию отвечает Excel – сами элементы Вы не программируете.
Особо отмечу, что Qwt позволяет работать с достаточно большими объемами данных (я работал с 200 000 точек) без возникновения раздражающих «тормозов».
В данной статье мы будем отображать кривую на графике, масштабировать ее, перемещаться по графику, смотреть координаты курсора. Таким образом, мы реализуем минимальный функционал, необходимый для вывода и просмотра графиков. В последующих статьях наш графический редактор будет оснащен дополнительными возможностями.

Красота растений привлекала внимание математиков веками. Активнее всего изучались интересные геометрические свойства растений, такие как симметрия листьев относительно центральной оси, радиальная симметрия цветов, и спиральное расположение семечек в шишках. «Красота связана с симметрией» (H. Weyl. Symmetry). Во время роста живых организмов, особенно растений, можно четко видеть регулярно повторяющиеся многоклеточные структуры. В случае составных листьев, например, маленькие листочки, которые являются частью большого взрослого листа, имеют ту же форму, что весь лист имел на раннем этапе формирования.

В 1968г. Венгерский биолог и ботаник Аристид Линденмайер (Aristid Lindenmayer) предложил математическую модель для изучения развития простых многоклеточных организмов, которая позже была расширена и используется для моделирования сложных ветвящихся структур — разнообразных деревьев и цветов. Эта модель получила название Lindenmayer System, или просто L-System.

Для тех, кто в теме и не хочет все читать целиком, проскрольте вниз, есть вопрос.

На этой фотографии автомобиль, использующий в качестве топлива алюминий.



Этот автомобиль был одним из самых интересных экспонатов выставки энергосберегающих технологий ENES-2013.

Рассказываю забавную идею, которая была сформулирована у нас сегодня на работе.

Представим себе бота, который занимается майнингом биткоинов, предоставляет какие-то простенькие услуги через WWW (например, генерирует псевдоосмысленный текст за очень малые деньги на бирже копирайтеров).

И пусть этот бот имеет простую программу:
1) Часть выручки переводить на свой лицевой счёт (аккаунт, с которого этот бот запущен в облаке)
2) Как только наберётся достаточно средств, посредством антиге*а и списка известных облачных провайдеров регистрировать новый аккаунт и запускать там свою копию.

Большая часть «копий» должна приходиться на тот же самый сервис, где запущен бот, меньшая — на произвольные другие.

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

В рамках концепции «on demand self-service», которая более-менее общепринята для облаков, это всё, что нужно для саморазмножающейся конструкции.

Полное оригинальное название статьи: «Why your first FizzBuzz implementation may not work: an exploration into some initially surprising but great parts of Rust (though you still might not like them)»

tl;dr;-версия: На первый взгляд некоторые аспекты Rust могут показаться странными и даже неудобными, однако, они оказываются весьма удачными для языка, который позиционируется как системный. Концепции владения (ownership) и времени жизни (lifetime) позволяют привнести в язык сильные статические гарантии и сделать программы на нём эффективными и безопасными, как по памяти, так и по времени.

Лицензия: CC-BY, автор Chris Morgan.

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

FizzBuzz предполагается как простое задание для новичка, но в Rust присутствуют несколько подводных камней, о которых лучше знать. Эти подводные камни не являются проблемами Rust, а, скорее, отличиями от того, с чем знакомо большиство программистов, ограничениями, которые на первый взгляд могут показаться очень жёсткими, но в действительности дают громадные преимущества за малой ценой.

Rust это «подвижная мишень», тем не менее, язык становится стабильней. Код из статьи работает с версией 0.12. Если что-то сломается, пожалуйста, свяжитесь со мной. Касательно кода на Python, он будет работать как в двойке, так и в тройке.

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

Работая над статьей о роли требований в процессе разработки программного обеспечения я обнаружил шкалу уровней зрелости процесса управления требованиями (requirements management maturity), предложенную в 2003 году одним из специалистов по работе с требованиями Rational Software Джимом Хьюманном (Jim Heumann).

Хочу поделиться с читателями habrahabr данной классификацией.

Введение

Термин «зрелость» – определяется как полное, состоявшееся развитие той или иной системы. Так как любое развитие требует затрат, в контексте бизнеса это означает, что организация принимает решение об объемах инвестиций в собственное развитие, четко понимая какие выгоды она при этом получает.

Ниже приведена шкала уровней зрелости процесса управления требованиями, построенная по аналогии с моделью CMMI. Эти модели никак не связаны между собой, но имеют некоторое пересечение. Так, достижение уровня 5 (Интеграция требований) зрелости процесса управления требованиями позволит получить как минимум уровень 3 (Процессы определены на уровне всей организации) по модели CMMI. Однако это не является прямым следствием, так как достижение высокого уровня зрелости в одном процессе не гарантирует общего повышения зрелости организации в целом.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2
Часть 3

Оптимальная сортировка

Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n² ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

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

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2

Логарифмы

Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1

Сложность

Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Введение

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

Тем не менее, знание теории тоже имеет свои преимущества и может оказаться весьма полезным. В этой статье, предназначенной для программистов, которые являются хорошими практиками, но имеют слабое представление о теории, я представлю один из наиболее прагматичных программистских инструментов: нотацию «большое О» и анализ сложности алгоритмов. Как человек, который работал как в области академической науки, так и над созданием коммерческого ПО, я считаю эти инструменты по-настоящему полезными на практике. Надеюсь, что после прочтения этой статьи вы сможете применить их к собственному коду, чтобы сделать его ещё лучше. Также этот пост принесёт с собой понимание таких общих терминов, используемых теоретиками информатики, как «большое О», «асимптотическое поведение», «анализ наиболее неблагоприятного случая» и т.п.

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

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

Я постараюсь покрыть все, что мне известно по теме — несмотря на то, что известно мне сравнительно не так уж много, материала вполне хватит поста на два, а то и на три. Все алгоритмы иллюстрируются исходниками на C# (а так как я любитель функционального программирования, то где-нибудь в послесловии речь зайдет и о F# — но это читать не обязательно :). Итак, приступим.

Введение

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

Следующий пункт нашей обязательной программы — куча (heap). Думаю, также многим известная структура данных, однако краткий обзор я все же приведу.
Представьте себе двоичное дерево с какими-то данными (ключами) в вершинах. И для каждой вершины мы в обязательном порядке требуем следующее: ее ключ строго больше, чем ключи ее непосредственных сыновей. Вот небольшой пример корректной кучи:

На заметку сразу скажу, что совершенно не обязательно думать про кучу исключительно как структуру, у которой родитель больше, чем его потомки. Никто не запрещает взять противоположный вариант и считать, что родитель меньше потомков — главное, выберите что-то одно для всего дерева. Для нужд этой статьи гораздо удобнее будет использовать вариант со знаком «больше».

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

Электронный набор с говорящим — для русского уха — названием SAM позволит создать практически все, о чем вы мечтали: для этого понадобятся Bluetooth-модули и софт, работающий по принципу drag-and-drop. Естественно, фраза «все, о чем вы мечтали» не должна вводить вас в заблуждение. Все в пределах разумного…

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

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

Добрый день, уважаемые хабровчане.

Этот пост будет про недокументированные функции микроволновой печи. Я покажу, сколько полезных вещей можно сделать, если использовать слегка доработанную микроволновку нестандартным образом.

В микроволновке находится генератор СВЧ волн огромной мощности

Мощность волн, которые используются в микроволновке, уже давно будоражит моё сознание. Её магнетрон (генератор СВЧ) выдаёт электромагнитные волны мощностью около 800 Вт и частотой 2450 МГц. Только представьте, одна микроволновка вырабатывает столько излучения, как 10 000 wi-fi роутеров, 5 000 мобильных телефонов или 30 базовых вышек мобильной связи! Для того, что бы эта мощь не вырвалась наружу в микроволновке используется двойной защитный экран из стали.

Описываемый проект внедрён и используется уже лет пять. Пришло время рассказать, как всё было и поделиться опытом.

Давным-давно работал я техником (что-то вроде лаборанта, но более узкоспециализировано) в одном из учебных заведений среднего профессионального образования нашей необъятной родины. Смотрел, как проходят занятия, видел, как неаккуратно обращаются с хрупким программным обеспечением студенты и преподаватели, участвовал в массовых рутинных операциях, таких как: «переустановить некую самую популярную ОС на 30 и более разных компьютеров», «ой, нам для нужд учебного процесса срочно нужно поставить вот этот программный пакет, но аудиторию ещё не знаем» и далее в таком же духе.

Был я не совсем доволен положением вещей. Казалось мне, что всё должно быть проще, легче, изящней и вообще работать чуть ли не само (знакомое чувство?). В итоге взрывоопасная смесь из юношеского максимализма, студенческой неопытности и желания изменить мир сотворили в моей голове «идеальную» картину, как оно всё-таки должно быть.

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