Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву.

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

Monodroid и Monotouch это фреймворки от xamarin, которые дают возможность разрабатывать приложение на языке C# для Android и iOS соответственно. Так как это относительно новая технология информации в интернете не слишком много (за исключением офф сайта и большого количества тем на stackoverflow.com), на русском языке же я не нашел никаких туториалов и информации вообще.

Что бы устранить это недоразумение решил написать небольшой туториал о том как начать разрабатывать приложения под мобильные платформы при помощи этих фреймворков. В этой статье я рассмотрю только Monodroid.

Оценка количества выученных и запомненных слов иностранного языка прежде всего интересна для понимания того, насколько далеко человек продвинулся в «пассивном» восприятии информации: тексты, речь, фильмы, и т.д. Предлагаю ознакомиться с несколькими способами, которые я применял, найденные в сети и «самопальные». Внизу — парочка тестов для оценки vocabulary, методика для поиска важных слов, которые пока не зацепились в мозгу, несколько рассуждений и немного ссылок.

Крошечный open-source дрон разработанный Bitcraze «прожжуживает» свой путь на рынок этой весной, нацеленный на хакеров и моддеров, экспериментирующих, как в помещениях так и на открытом воздухе.

Должен признаться, что я плохой программист. Я не люблю настраивать Maven и писать конфигурации для Spring Framework. Я не знаю в деталях, как работает JVM (да и в общих чертах представляю это себе довольно смутно). Я плохо понимаю паттерны проектирования, а любая новая технология вводит меня в уныние. И тем не менее, я люблю программировать.

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

Минуточку внимания.

Я не стану говорить о Robot Battle и тому подобных вещах. Вот не стану и всё. Возможно, я странный человек, но мне не нравится иметь дело с чем-то, хоть отдалённо напоминающим реальную физику. Интересующиеся могут почитать об этой игре здесь, а статья немного о другом.

Игра Oil Rush

В данной статье, состоящей из двух частей, речь пойдёт об использовании возможностей процедурных генераторов при создании контента для компьютерной игры Oil Rush и бенчмарка Valley (выйдет в феврале), разработанных на нашем собственном движке Unigine.

С каждым днем слово java все больше и больше воспринимается уже не как язык, а как платформа благодаря небезызвестному invokeDynamic. Именно поэтому сегодня я бы хотел поговорить про виртуальную java машину, а именно — об так называемых Performance опциях в Oracle HotSpot JVM версии 1.6 и выше (server). Потому что сегодня почти не встретить людей, которые знают что-то больше чем -Xmx, -Xms и -Xss. В свое время, когда я начал углубляться в тему, то обнаружил огромное количество интересной информации, которой и хочу поделится. Отправной точкой, понятное дело, послужила официальная документация от Oracle. А дальше — гугл, эксперименты и общение:

-XX:+DoEscapeAnalysis

Начну, пожалуй, с самой интересной опции — DoEscapeAnalysis. Как многие из Вас знают, примитивы и ссылки на объекты создаются не в куче, а выделяются на стеке потока (256КБ по умолчанию для Hotspot). Вполне очевидно, что язык java не позволяет создавать объекты на стеке на прямую. Но это вполне себе может проделывать Ваша JVM 1.6 начиная с 14 апдейта.

Про то, как работает сам алгоритм можно прочитать тут (PDF). Если коротко, то:

• Если область видимости объекта не выходит за область метода, в котором он создается, то такой объект может быть создан на фрейме стека вместо кучи (на самом деле не сам объект, а его поля, на совокупность которых заменяется объект);
• Если объект не покидает область видимости потока, то к такому объекту другие потоки не имеют доступа и следовательно все операции синхронизации над объектом могут быть удалены.

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

• GlobalEscape — объект доступен из других потоков и из других методов, например статическое поле.
• ArgEscape — объект был передан как аргумент или на него есть ссылка из объекта аргумента, но сам он не выходит из области видимости потока в котором был создан.
• NoEscape — объект не покидает область видимости метода и его создание может быть вынесено на стек.

После этапа анализа, уже сама JVM проводит возможную оптимизацию: в случае если объект NoEscape, то он может быть создан на стеке; если объект NoEscape или ArgEscape, то операции синхронизации над ним могут быть удалены.

Следует уточнить, что на стеке создается не сам объект а его поля. Так как JVM заменяет цельный объект на совокупность его полей (спасибо Walrus за уточнение).

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

    for (int i = 0; i < 1000*1000*1000; i++) {
        Foo foo = new Foo();
    }

скорость выполнения может увеличится в 8-15 раз. Хотя, на казалось бы, очевидных случаях из практики о которых недавно писалось (тут и тут) EscapeAnalys не работает. Подозреваю, что это связано с размером стека.

Кстати, EscapeAnalysis как раз частично ответственен за известный спор про StringBuilder и StringBuffer. То есть, если Вы вдруг в методе использовали StringBuffer вместо StringBuilder, то EscapeAnalysis (в случае срабатывания) устранит блокировки для StringBuffer'а, после чего StringBuffer вполне превращается в StringBuilder.

Все чаще приходится слышать: "Работай на результат!"

"Работай на результат!" — кричит начальник подчиненному, чтобы заставить этого тупого неповоротливого кретина, принятого в команду по протекции, приносить хоть какую-то пользу общему делу.

"Мы работаем на результат!" — бахвалится бригада голодных гастарбайтеров, надеясь, что, если они будут кричать именно это, их предложение хотя бы немного выделится среди гула голосов тысяч голодных и безработных.

"Обязательна ориентированность на результат!" — напишет пожилая кадровичка «ГорАвиаВагонМорСтроя» в требования к кандидату на должность помощника бухгалтера, будучи уверенной в том, что раз все так пишут, то и ей надо.

"Наш девиз — Работа на Результат!" — именно так, с двумя Большими Буквами для большего пафоса пишет на корпоративном сайте очередной говноконторы-однодневки молоденькая девочка-всё-в-одном, гордо именующая себя помощником руководителя по связям с общественностью. И этот самый руководитель, даже не знающий, что секретутка это, оказывается, ни больше ни меньше, целый его помощник, тоже употребит эту фразу на фуршете в городской администрации с целью создать себе рекламу в среде местных бюрократов.

Культ карго. Мало кто из произносящих эту фразу может внятно объяснить, какой смысл в неё вкладывается. Люди верят в неё, как в волшебную формулу, заклинание, они пихают её куда ни попадя, надеясь, что она придаст им уникальность, выделит их из толпы таких же неудачников. Организации, Компании, конторы да и откровенные «шараги» не мыслят себя без этого лозунга. Как же это, «Рога и копыта» работают на результат, а мы, что, хуже?



А хуже ли?

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

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

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

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

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

Об экспериментах с компьютерной голографией писалось неоднократно. [1, 2, 3] Мне эта тема просто любопытна. Я как-то экспериментировал с бит-реверсивной перестановкой (bit-reversal permutation) изображений и случайно обнаружил голографические свойства. Но обо всем по порядку.

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

Для начала – что такое европейские языки. Предлагаю ограничиться государственными языками стран Европы. Так как границы Европы – вещь спорная, то отдельно оговоримся про соседние страны. Духовно близкий Израиль, а также Грузию и Армению можно отличить по письменности из той же блок-схемы, Азербайджан и Казахстан я включу по доброте душевной, а Абхазию и Южную Осетию – в качестве прогиба перед российской властью. Так что абхазский в наш классификатор попадёт, а баскский и гэльский – ну уж нет, перебьются.

Языков больше, чем типов письменности. Поэтому диаграмка получилась большая. Отличать языки друг от друга будем в основном по особенным буквам, в частности, по буквам с диакритическими значками (диакритикой). Диакритика бывает над гласной (в букве й), над согласной (буква č) или может как-то сопровождать букву (как в букве ç; строго говоря это не дикритика вовсе, но мы здесь будем придерживаться такого жаргона). Наиболее известные (с моей точки зрения) значки в Европе — это умляут (он же диаерезис: ü), гачек (č) и акут (é).

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

Backup Box умеет синхронизировать разные облачные сервисы, а также делать бэкапы сайтов (FTP и MySQL).

Говоря «хаос», мы, обычно, подразумеваем полное отсутствие порядка, абсолютную неупорядоченность и случайность. С математической точки зрения, хаос и порядок – понятия не взаимоисключающие. Теория хаоса (есть что-то завораживающие в названиях математических теорий) – достаточно молодая математическая область, создание которой приравнивают по значимости открытий ХХ века к созданию квантовой механики. Хаос случается в нелинейных динамических системах. Иначе говоря, любой процесс, который протекает со временем, может быть хаотичным (например, высота дерева, температура тела или популяция мадагаскарских тараканов).

Есть люди, которым нравится писать .NET приложения. Есть люди, которые любят системы компьютерной алгебры. В этой статье круги Эйлера пересекутся!

На одной улице в Бердичеве жили трое портных. У первого была вывеска: “Лучший портной в городе”, у второго — “Лучший портной в мире”, а третий написал: “Лучший портной на этой улице”.

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

Вы никогда, НИКОГДА не станете богатым от экономии на покупках в супермаркете!

Сотни миллионов людей в мире экономят как на покупках, так и на самих супермаркетах, не говоря уже о миллионах голодных, “экономящих” на еде вообще. Можно предположить, что достаточно большая часть экономящих людей попадается на удочку относительно больших чисел, получаемых умножением грошей на 20-30-40 лет… без какого-либо положительного финансового эффекта. Причина элементарна: экономический план на десятки лет — это оксюморон. Такой план не учитывает множество факторов, влияние которых весьма значительно и на более короткие сроки, поэтому он может называться мечтой, фантазией, как угодно еще, только не финансовым планом. Кризисы, биржевые скачки, инфляция, изменения в жизни, в работе, в уровне доходов, политической обстановке… да одна только кратковременная флюктуация в курсе валют может мгновенно уничтожить нажитое непосильным трудом (как и наоборот, кстати). Вы не разбогатеете за 20 лет, отказывая себе в шоколадках, или не тратя деньги на сигареты, или “собирая бутылки”. Вернее, не так. Ваш шанс разбогатеть за NN лет совершенно не зависит от ваших сегодняшних действий и еще меньше зависит от мелочей. А все потому, что

Вопрос о столах поднимался несколько раз (раз, два).

Однако, на чем же мы сидим перед столом?

Стул — не менее важная часть рабочего места любого человека, много времени работающего за компьютером в течение дня.

Все мы работаем с компьютером и порой не замечаем, на чем же мы сидим.

Оказывается наши санитарные правила и нормы (СанПиН 2.2.2/2.4.1340-03) достаточно хорошо описывают удобный эргономичный стул для работы взрослых за компьютером!

А какой стул правильный?

Предыстория

Не так давно, а именно 5 июня хабрачеловек по имени alan008 задал вопрос. Чтобы не заставлять ходить за подробностями, приведу его здесь:

Нужна помощь!

За несколько лет с разных трекеров (преимущественно c rutracker'а) разными клиентами (преимущественно uTorrent'ом) скачано много гигабайт разного полезного контента. Скачанные файлы впоследствии вручную перемещались с одного диска на другой, uTorrent их соответственно не видит. Многие .torrent файлы устарели сами по себе (например, велась раздача сериала путем добавления новых серий заменой .torrent файла).

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

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

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

Потратив в общей сложности неделю на разбор формата .torrent-файла, поиск нормально работающей библиотеки для его парсинга, я приступил к написанию программы, которая позволит решить проблему затронутую в упомянутом вопросе.

Прежде чем начать, стоит отметить несколько моментов:

1. Получилось много, но не все.
2. По формату файла .torrent будут даны лишь необходимые пояснения.
3. Людей, чувствительных к временами некачественному коду, прошу меня заранее простить — я знаю, что многое можно было написать лучше, оптимальнее и безглючнее.

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