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

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

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

Наверное многие слышали или сталкивались с таким параметром JVM как -javaagent, увидеть этот параметр вы могли используя Jrebel или Plumbr это могло выглядеть например так JAVA_OPTS=-javaagent:[path/to/]jrebel.jar или так -javaagent:/path-to/plumbr.jar
Хотя javaagent появился еще в версии java 1.5, многие разработчики так никогда и не использовали возможности агентов и имеют смутное представление что это такое.
Что же это за агент? Зачем он может нам понадобиться и как написать свой?

Здравствуйте, уважаемые хабравчане!

Данным постом хочу представить сообществу проект, который время от времени писался мной последний год: SASM (SimpleASM) — IDE для разработки программ на языке ассемблера x86 и x86-64.



SASM — простая кроссплатформенная (доступна на Windows и Linux) среда разработки для языков ассемблера NASM, MASM, GAS, FASM с подсветкой синтаксиса и отладчиком. Программа работает «из коробки» и хорошо подойдет для начинающих изучение языка ассемблера. Основана на Qt. Распространяется по свободной лицензии GNU GPL v3.0.

Исходники лежат в репозитории на GitHub.
Бинарники можно скачать на сайте программы.

Под катом Вы найдете немножко истории и более подробное описание возможностей.

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

• Часть 1: zsh
• Часть 2: bash

Преамбула

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

Введение

Bash, в отличие от zsh, требует к себе некоторого велосипедостроения в отношении автодополнений. Бегло погуглив, я не нашел более-менее нормальных туториалов, потому за основу были взяты имеющиеся в системе файлы автодополнений для pacman (искренне надеюсь, что отцы-основатели Arch'а не придумывали много велосипедов).

Недавно я открыл для себя удобство отложенного чтения — когда заинтересовавшую статью в сети можно прочитать в любое время, комфортно расположившись c любимым девайсом на диване / пляже / под одиноким деревцем на тропе, ведущей к базовому лагерю у подножья Эвереста. И хотя проприетарных решений для этого хватает (Instapaper, Pocket, Readability), душа настойчиво требовала OpenSource. И вот к какому решению я пришёл после исследования возможных вариантов.

Что-то меня пробило на написание заметок последнее время, поэтому пока энтузиазм не спал раздаю долги.
Год назад я пришёл на хабр со статьёй "TCP(syn-flood)-netmap-generator производительностью 1,5 mpps", после которой многие писали и даже звонили с просьбой описать создание такой же «вилки» со спуффингом на максимуме возможностей 10GB сети. Я всем обещал, а руки всё не доходили.
Кто-то скажет, что это руководство для хакеров, но ведь свинья грязи найдёт, а те кому нужен этот инструмент в благонадёжных целях могу остаться ни с чем.

При разработке ПО часто возникают интересные задачи. Одна из таких: работа с гео-координатами пользователей. Если вашим сервисом пользуются миллионы пользователей и запросы к РСУБД происходят часто, то выбор алгоритма играет важную роль. О том как оптимально обрабатывать большое количество запросов и искать ближайшие гео-позиции рассказано под катом.

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

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

Помните эти задачи «при помощи циркуля и линейки постройте...»? Вот здесь можно поупражняться в таких построениях.

20 уровней построены по принципу «от простого к сложному». Предыдущие достижения (к примеру, умение строить равносторонний треугольник) на следующих уровнях доступны уже в виде инструментов.

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

В данной статье я бы не хотел заострять внимание на принципе работы сборщика мусора — об этом прекрасно и наглядно описано здесь: habrahabr.ru/post/112676. Хочется больше перейти к практическим основам и количественным характеристикам по настройке Garbage Collection в JVM — и попытаться понять насколько это может быть эффективным.

Количественные характеристики оценки эффективности GC

Рассмотрим следующие показатели:

• Пропускная способность Мера, определяющая способность приложения работать в пиковой нагрузке не зависимо от пауз во время сборки и размера необходимой памяти
• Время отклика Мера GC, определяющая способность приложения справляться с числом остановок и флуктуаций работы GC
• Размер используемой памяти Размер памяти, который необходим для эффективной работы GC

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

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

Как известно, в Java нет беззнаковых типов. Если в Си вы могли написать unsigned int (char, long), то в Java так не получится. Однако нередко возникает необходимость в выполнении арифметических операций именно с числами без знака. На первый взгляд кажется, что беззнаковые типы в принципе-то и не особо нужны (подумаешь, MaxInt для чисел со знаком меньше в два раза, если нужны числа больше, я просто возьму long и далее BigInteger). Но основное различие на самом деле не в том, сколько различных неотрицательных чисел можно положить в signed или unsigned int, а в том, как над ними производятся арифметические операции и сравнения. Если вы работаете с бинарными протоколами или с двоичной арифметикой, где важен каждый используемый бит, нужно уметь выполнять все основные операции в беззнаковом режиме. Рассмотрим эти операции по порядку:

Преобразование byte в short (int, long)

Обычный каст (int) myByte выполнит расширение до 32 бит со знаком — это означает, что если старший бит байта был установлен в 1, то результатом будет то же самое отрицательное число, но записанное в 32-битном формате:

0xff -> 0xffffffff (-1)

Часто это не то, чего бы мы хотели. Для того, чтобы выполнить расширение до 32 бит без знака и получить 0x000000ff, в Java можно записать:

int myInt = myByte & 0xff;
short myShort = myByte & 0xff;

Сравнение без учёта знака

Для беззнакового сравнения есть лаконичная формула:

int compareUnsigned(int a, int b) {
    return Integer.compare( a ^ 0x80000000, b ^ 0x80000000 );
}

Для byte, short и long, соответственно, константы будут 0x80, 0x8000 и 0x8000000000000000L.

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

Первым делом, мы начали смотреть маршруты Google и Яндекс. И к сожалению, пришлось от них отказаться, т.к. первые разрешали показывать их только на родных картах, вторые, не знали что есть велосипеды и даже пешеходы.

Немного изучив предметную область, мы нашли наконец что искали: Open Source Routing Machine. Проект, с открытым исходным кодом, который позволяет развернуть у себя на сервере, свой собственный сервис построения маршрутов.



Тайлы: MapBox, Яндекс-Карты
Картографические данные: участники OpenStreetMap

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

От переводчика:
спор сторонников написания final везде и всюду и их противников сродни спору остроконечников и тупоконечников. Как и в некоторых других сообществах, в нашей компании этот вялотекущий спор шел годами. И только эта статья Ричарда Вэрбёртона (Richard Warburton) позволила нашим остроконечникам взять верх.

О чём речь?

Начнем с небольшого рассказа. Несколько недель назад я отправил в список рассылки Java core libs своё предложение убрать модификатор final с некоторых методов. В результате возникло несколько тем для дискуссии. Одна из них, например, — выяснить, в какой степени ухудшится производительность вызова метода, который был final, если этот final с него убрать.

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

В новой версии Java 8 наконец-то появились долгожданные лямбда-выражения. Возможно, это самая важная новая возможность последней версии; они позволяют писать быстрее и делают код более ясным, а также открывают дверь в мир функционального программирования. В этой статье я расскажу, как это работает.

Java задумывалась как объектно-ориентированный язык в 90-е годы, когда объектно-ориентированное программирование было главной парадигмой в разработке приложений. Задолго до этого было объектно-ориентированное программирование, были функциональные языки программирования, такие, как Lisp и Scheme, но их преимущества не были оценены за пределами академической среды. В последнее время функциональное программирование сильно выросло в значимости, потому что оно хорошо подходит для параллельного программирования и программирования, основанного на событиях («reactive»). Это не значит, что объектная ориентированность – плохо. Наоборот, вместо этого, выигрышная стратегия – смешивать объектно-ориентированное программирование и функциональное. Это имеет смысл, даже если вам не нужна параллельность. Например, библиотеки коллекций могут получить мощное API, если язык имеет удобный синтаксис для функциональных выражений.

Главным улучшением в Java 8 является добавление поддержки функциональных программных конструкций к его объектно-ориентированной основе.

Почему это нужно для вашего автомобиля?

Задумывались ли вы над тем чтоб отобразить параметры работы вашего автомобиля в собственном Android приложении? Если да, тогда добро пожаловать под кат. Мы как раз будем обсуждать вопрос разработки подобного приложения.

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

Активные-пассивные

Если метки не используют собственную батарею питания, а получают его от поля считывателя – пассивные. Если используется батарейное питания, то активные.
Еще есть «полу-пассивные» метки (также называются «BAP» – Battery Assisted Passive), которые используют радиоинтерфейс и протокол обмена пассивной системы, но есть батарея питания. Постоянное питание чипа таких меток может несколько улучшать ее характеристики по дальности регистрации, но чаще дополнительное питание используется для встроенных датчиков (температуры, ускорения, влажности и т. п.). Батарея используется для питания датчиков и накопления данных при нахождении метки вне поля считывателя, с последующим их считыванием при входе в зону регистрации.
Активные метки, достаточно дорогие, большие по размерам, но зато дистанция их регистрации может достигать километра. Также есть специальный класс активных меток RTLS – Real Time Locating Systems – системы определения положения в реальном времени.
Важным отличием пассивных меток от активных является то, что пассивные метки НЕ ИЗЛУЧАЮТ радиосигнал. Пассивные метки, отвечая на сигнал считывателя, только модулируют нагрузку своей антенной системы в момент ее нахождения в поле несущей частоты считывателя. Считыватель обнаруживает и детектирует эти слабые отраженные модуляции на фоне непрерывного излучения несущей частоты через свою приемопередающую антенну.
Системы EPC Gen2 относятся к пассивным, но бывают и полу-пассивные специальные метки.

Частотный диапазон

LF – Low Frequency, 125-135 кГц. «Обычные» метки-карточки или домофонные брелки для систем контроля доступа, метки-капсулы для «чипирования» животных (но и среди высших мыслящих существ также есть любители встроенных уникальных идентификаторов).

HF – High Frequency, 13,553-13,567 МГц. Все транспортные проездные карты, банковские беспроводные карты, устройства и метки NFC. Также есть более «простые» метки без криптографических функций, содержащие только идентификатор.

UHF – Ultra High Frequency. Диапазоны 433,075-434,790 МГц и 2400-2483,5 МГц используются активными метками и RTLS, а также брелками сигнализаций, беспроводными клавиатурами, мышками и т. п.

Для EPC Gen2 в мировом масштабе используется UHF диапазон 860-960 МГц, но локально в странах и регионах используются более узкие полосы.
В РФ используются частоты европейского диапазона 865,6-867,6 МГц в соответствии со стандартом ETSI EN302-208-1 V1.2.1, хотя формально выделенная в РФ полоса уже — 866,6-867,4 МГц.
Стандарт EPC Gen2 (полностью Electronic Product Code Class 1 Generation 2) разработан международной организацией GS1 EPC Global. Ему также соответствует стандарт ISO/IEC 18000-63(С). Соответствующая национальная версия ГОСТ разрабатывается.

Какие же существенные преимущества и отличия имеют RFID-системы EPC Gen2 по сравнению с другими?:

• Рекордная дистанция регистрации меток для пассивных систем до 10 и более метров, что объясняется использованием «полного» электромагнитного поля, а не магнитной связи петлевых антенн считывателя и метки, как в LF и HF;
• Эффективный «антиколлизионный» механизм, позволяющий считывать одновременно до 300 уникальных меток в зоне регистрации;
• Высокая скорость считывания метки – до сотен раз в секунду. Экспериментально подтверждена возможность регистрации одиночных меток при их перемещении через зону регистрации на скорости до 250 км/час;
• Наименьшая цена простой метки-наклейки (на 2013 год около 5 рублей при больших объемах поставки).

Тестирование — один из самых важных этапов при разработке приложения. И приложения на Android не есть исключением. При написании кода обычно нужно его просматривать и задуматься над тем, как же его протестировать потом. Представим ситуацию, когда вам нужно покрыть тестами ваш проект, который полностью написан. Чаще всего, это не так-то просто. Скорее всего, ваш код просто-напросто не был реализован так, чтобы его было легко тестировать. Это означает, что вам придётся делать изменения в нём, чтобы сделать его поддающимся тестированию… не разрушив никакой функциональности (собственно это в наше время и называется рефакторингом (refactoring)).

Компании ЗАО «МЦСТ» и КБ «Панорама» провели испытания разрабатываемого целью которых, являлась проверка функционирования отечественной ГИС Оператор на программно-аппаратной платформе «Эльбрус».

Данная ГИС принята на снабжение ВС РФ приказом министра обороны РФ № 598 от 15 августа 2013г., что делает ее стратегически важным ресурсом. Предназначена она для управления картами местности, снимками и матрицами на основе атласа карт, создания карт оперативной обстановки, отображения 3D моделей местности и оперативной обстановки.

Пост содержит перевод статьи «Error Handling in Node.js», которую подготовили сотрудники компании Joyent. Статья была опубликована 28 марта 2014 года на сайте компании. Dave Pacheco поясняет, что статья призвана устранить неурядицу среди разработчиков, касаемо лучших практик работы с ошибками в Node.js, а так же ответить на вопросы, которые часто возникают у начинающих разработчиков.