Шаблон vector библиотеки STL выигрывает почти по всем параметрам у обычного С++ массива. Он позволяет добавлять и удалять элементы, освобождает выделенную память при уничтожении, позволяет контролировать выход за пределы массива и т.д. Тем не менее, у него есть один недостаток – для его работы требуется дополнительная память, небольшая, но в ряде случаев существенная. Ниже рассмотрена реализация контейнера, позволяющая немного снизить затраты памяти и повысить производительность.

Дорогие друзья, доброго времени суток!

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

Я понимаю, почему генетические алгоритмы пользуются такой большой популярностью: они очень образны и, следовательно, доступны для понимания. В самом деле, несложно и крайне интересно представить решение некой задачи, как реальный биологический процесс развития популяции живых существ с определёнными свойствами. Между тем, алгоритм отжига также имеет свой прототип в реальном мире (это понятно и из самого названия). Правда, пришёл он не из биологии, а из физики. Процесс, имитируемый данным алгоритмом, похож на образование веществом кристаллической структуры с минимальной энергией во время охлаждения и затвердевания, когда при высоких температурах частицы хаотично движутся, постепенно замедляясь и застывая в местах с наименьшей энергией. Только в случае математической задачи роль частиц вещества выполняют параметры, а роль энергии — функция, характеризующая оптимальность набора этих параметров.

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

Для дальнейшего чтения необходимо иметь представление о деревьях, а также желательно знать об оценке сложности алгоритмов. Алгоритмы в этой статье будут сопровождаться кодом на C#.

Введение

Двоичная куча представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков. В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-heap, поскольку корень поддерева является максимумом из значений элементов поддерева. В этой статье для простоты используется именно такое представление. Напомню также, что дерево называется полным бинарным, если у каждой вершины есть не более двух потомков, а заполнение уровней вершин идет сверху вниз (в пределах одного уровня – слева направо).

В этом топике — обещанный обзор разных настольных игр.

— Первая часть — это «портированные» версии известных компьютерных (по сюжету Starcraft, Warcraft, Civilization, Age of Empires, Master of Orion, Doom)
— Вторая часть — игры, которые интересны многим хабражителям, судя по комментариям к прошлым топикам.
— В комментариях предлагаю делиться информацией об интересных играх: думаю, многие смогут подсказать нечто необычное в плане поиграть или же предупредить от напрасной покупки.
— Топик будет интересен тем, кто хочет понять, что популярно на рынке, вкратце посмотреть товар для магазина и тем, кому просто интересно, что же там вообще есть из настольных игр для себя, компании или в подарок.
— В конце есть приятный бонус хабрачитателям.

Сайт rospil.info «лежит».
Update: ruleaks.net тоже «лежит» со страницей «500+»
Update: Люди, ассоциированные с проектами, подтверждают, что это DDOS-атаки.

Напомню, что сегодня у Навального увели почту на GMail. По запросу в техподдержку он её себе вернул.

Буду дополнять топик по мере поступления информации.

Поучительная история о техниках оптимизации наглядно.

Техзадание

Объявим в рамках топика небольшой конкурс по архитектурно-ориентированной оптимизации программного обеспечения.
Вкратце, код состоит из пачки функций, производящих невнятные на первый взгляд манипуляции с исходными данными, и примочки-драйвера, который n раз запускает неоптимизированную версию, затем оптимизированную, сравнивает насчитанные циферки, и, в случае их совпадения, выдает отношение времени выполнения. Вот так:

Executing original code… done
Executing optimized code… done
Checking results… PASSED
Number of runs: 3
Original code average time: 11.954537 sec.
Optimized code average time: 1.052994 sec.
Speedup: 11.35

Разрешено использовать любые техники оптимизации, компилятор GCC с любыми опциями, и, скажем, сервер с двумя четырехъядерными процессорами Intel Xeon E5420 2.5 GHz.
Вот, кстати, код:

Здравствуйте, уважаемые хабраюзеры!
Интересовались ли Вы когда-нибудь как работает снифер и что он из себя представляет? Или как Ваш любимый фаервол защищает Вас от троянов и прочей гадости на сетевом уровне? Да и вообще, как он работает? Я уверен, что Вы задавали себе такого рода вопросы, но все же, если нет, то я от части Вам про это расскажу. Начиная с этой статьи мы будем постепенно осваивать написание своего сниферо-подобного драйвера. Сегодня мы рассмотрим некоторые общие положения, которые нам будут необходимы для понимая всего того, что будет происходить в последующих статьях. Перед прочтением этой статьи, дабы у Вас началась складываться более или менее ясная картина, я рекомендую Вам прочтение прошлого топика Краткий обзор драйверов спецификации NDIS

Всем кому это интересно прошу под кат.

… Пару лет назад здесь уже был топик на сходную тему, хочу поделиться своими соображениями…

Одной из проблем, возникающих при написании игры, пространство действия которой содержит больше трех пространственных измерений, является визуализация сцены действия, в достаточной мере понятная пользователю, и пригодная для управления как персонажем (или объектом) игры, так и виртуальной камерой, создающей изображение.
Большинство многомерных игр, которые попадались мне в последнее время, были головоломками — аналогами кубика Рубика. Но для разных размерностей головоломки авторам приходилось использовать различные способы визуализации.

Введение

В 1965 г. в журнале «Information and Control» была опубликована работа Л.Заде под названием «Fuzzy sets». Это название переведено на русский язык как нечеткие множества. Побудительным мотивом стала необходимость описания таких явлений и понятий, которые имеют многозначным и неточный характер. Известные до этого математические методы, использовавшие классическую теорию множеств и двузначную логику, не позволяли решать проблемы этого типа.

Неугомонный Карстен Нол, который уже много лет исследует криптоустойчивость GSM сетей, на конгрессе Chaos Computer Club в Берлине представил новый способ перехвата и расшифровки GSM сигнала, который не требует дорогостоящего оборудования и значительного количества времени.

Хакер под ником Zoz выступил на конференции Defcon 18 с 20-минутным рассказом, как ему удалось обнаружить десктоп, украденный год назад. История действительно необычная (слайды презентации, видео (см. с 3:15)).

Zoz месяцами выслеживал, когда где-нибудь на аукционах появятся комплектующие с его серийными номерами, но безуспешно. Аккаунт в сервисе DynDNS (привязка домена к динамическому IP-адресу) тоже не подавал признаков жизни. Через 30 дней они прислали письмо, что если желаете сохранить аккаунт в режиме отсутствия активности, то нужно купить апгрейд до версии Pro. В октябре 2009 года Zoz сделал это — и удача повернулась у нему лицом.

7 мая 2010 года в аккаунте DynDNS появилась странная запись.

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

Рок-музыка – музыка жизни для очень и очень многих, это музыка, которая несет в себе сильнейшую энергетику: от мрачной и темной, до пафосно возвышенной и каждый может найти в ней что-то для себя. Утонченная красота рок-баллад и невероятный драйв «боевиков» сносит мозг огромному количеству людей вот уже около 50ти лет. Но мы не будем углубляться в историю, не будем пытаться доказать, кто же все-таки был первым рокером: битлз или блек саббат – оставим это музыковедам. Также мы не будем пытаться разграничить её на стили, говоря «это фиговая попса, а это – труъ», ведь, на мой взгляд, МУЗЫКА не может быть заключена в какие-либо рамки. Задача этой статьи несколько иная – я хочу попытаться пролить свет на то, чем является рок-музыка изнутри. На то, что для большинства глаз скрыто, и то, что волнует многих: «а как он это сделал?», «а что это такое торчит?» — то, что разграничивает слушателя и музыканта. Я хочу попытаться пролить свет на те вещи, на которых в большинстве своем базируется рок-музыка: инструменты, техники игры, технологическая сторона вопроса, однако хочется сделать это как можно проще и понятнее. Это как раз то, чего не хватало мне в свое время и, надеюсь, станет для вас интересным и занимательным. Так же я попытаюсь провести небольшой экскурс в искусство звукозаписи и то, как можно сделать РОК у себя дома:).
Заранее попрошу простить меня за некоторую заангажированность, необъективность и необразованность по некоторым вопросам – я лишь любитель, а не профессионал, кроме этого – музыка является искусством, на которое всегда найдется как минимум 2 разные точки зрения.

Инженер Apple Эндрю Кэрол (Andrew Carol) с помощью конструктора Lego создал аналог антикитерского механизма (датирован 150-100 гг до н.э.). Это уникальная система шестерён с передаточным соотношением 254:19, которая моделирует движение Солнца и Луны относительно неподвижных звёзд.



Как и древнегреческий механический компьютер, копия из Lego способна с высокой точностью предсказывать лунные и солнечные затмения.

Здравствуй, хабрачитатель.

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

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

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

Задачи я буду брать с сайта http://uva.onlinejudge.org/, где располагается достаточно большая коллекция задач на любой вкус, и там же можно проверить свое решение. Выбирать буду случайным образом и всегда доводить начатое до финального решения, которое ознаменуется оценкой «Accepted» (Принято). Для решения этих задач нам потребуется знание одного из языков программирования: c, c++, java, pascal, а также терпение, логика и базовое знание английского языка, т.к. условия задач мы получаем на английском языке.

Итак, начнем мы с простой задачки из набора «Для новичков» для разминки, чтобы проверить свои способности.

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



Ден Мейер из Стэнфордского университета в течение месяцев замерял скорость касс, занёс все данные в таблицу и вывел следующую формулу:

y = 2,9572x + 41,174

Это формула зависимости скорости обслуживания в секундах (y) от количества товаров (x).

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

То, что мы сегодня создадим, корректнее будет назвать LKM (Linux Kernel Module или загрузочный модуль ядра). Стоит сказать, что драйвер – это одна из разновидностей LKM.

Писать модуль мы будем под ядра линейки 2.6. LKM для 2.6 отличается от 2.4. Я не буду останавливаться на различиях, ибо это не входит в рамки поста.

Мы создадим символьное устройство /dev/test, которое будет обрабатываться нашим модулем. Хочу сразу оговориться, что размещать символьное устройство не обязательно в каталоге /dev, просто это является частью «древнего магического ритуала».

Есть хорошая статья Питера Норвига, в которой он рассказывает как написать спеллчекер в 20 строк кода. В этой статье он показывает как поисковые системы могут исправлять ошибки в запросах. И делает это довольно элегантно. Однако, у его подхода есть два серьезных недостатка. Во-первых, исправление более трех ошибок требует больших ресурсов. А гугл, кстати, неплохо справляется и с четырьмя ошибками. Во-вторых, нет возможности проверки связного текста.



Итак, хочется исправить эти проблемы. А именно, написать корректор коротких фраз или запросов, который:

• умел бы выявлять три (и более) ошибки в запросе;
• умел бы проверять «разорванные» или «слипшиеся» фразы, например expertsexchange — experts_exchange, ma na ger — manager
• не требовал много кода для реализации
• мог бы достраиваться до исправления ошибок на других языках и других типов" ошибок

Остальное — под катом.

Еще давно очень многих интересовал один вопрос: «Эта программа занимает всего 100 кб, что за музыку она воспроизводит? Как это работает?»

Так вот, называется это чудо – Трекерная музыка. И что самое главное – она занимает очень мало места, в отличие от .mp3 или .wav. В современных популярных ОС трекерные файлы (MOD, XM, S3M, IT и пр.) проигрываются большинством медиаплееров, например, Winamp, VLC, Amarok, Audacious и другими.

Скачать такую музыку можно, например отсюда — keygenmusic.net, или отсюда www.modarchive.org. Это отнюдь не единственные ресурсы, стоит только обратиться к поиску.

Для того, чтобы воспроизвести такую музыку в своей программе, нам потребуется минимальное знание C++, а также minifmod, доступный в исходниках. Как заявляют разработчики, minifmod добавит всего 50 кб к вашему exe-файлу (без учета сжатия).

Иногда, даже у вполне состоявшегося программиста, появляется желание написать что-то, что было бы интересно не только работодателю. Такой человек бреется по утрам и думает, а почему бы не подарить счастье всему человечеству.