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

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

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

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

Но неужто людям не найдётся полезного занятия?

Перевод статьи: 35 Lessons in 35 Years
http://ryanfreitas.tumblr.com/post/968361763/35-lessons-in-35-years (англ.)

Ваши вопросы Вы можете направить автору:
http://ryanfreitas.tumblr.com/ask

Я не профессиональный переводчик и не могу знать о статусе:
«white trash ballin», а поэтому буду благодарен любым корректировкам.

Современные высоконагруженные приложения изменили требования к СУБД — сегодня необходимы эффективные технологии создания cпециализированных решений с гарантированным временем реакции при обработке больших массивов данных. Вместе с тем, несмотря на появление таких относительно новых технологий как NoSQL, потенциал давно существующих подходов реализован еще не полностью.

Интернет проекты с высокой нагрузкой и приложения класса XTP (extreme transaction processing) изменили требования к технологиям СУБД. Приоритетными требованиями стали простота разработки, возможность cпециализации технологии хранимых данных для конкретного проекта, поддержка постоянного времени реакции системы при увеличении нагрузки, обеспечение низкой стоимости масштабирования и стоимости обработки больших объемов данных.

В качестве ответа на новые потребности возникло движение NoSQL — новый класс баз данных, который обещает разработчикам высокую скорость внесения изменений в приложения, низкие затраты на масштабирование и обработку/хранение больших объемов данных, высокую скорость работы на относительно недорогом железе — ценности, которые всегда были важны и для технологий компании InterSystems. Практически всегда NoSQL базы реализуют отличную от привычной парадигму работы приложений с базами данных — переход от концепции интегрирующей СУБД для нескольких приложений к концепции СУБД для одного приложения или одного проекта и больше — отдельной специфичной задачи в рамках проекта.

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

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

— Мы получаем больше миллиона твитов в день, и наш сервер просто не успевает их обрабатывать. Поэтому мы хотим установить на кластер Hadoop и распределить обработку.

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

— А что вы собираетесь делать с уже обработанными данными?
— Скорее всего, мы будем складывать их в MySQL, как делали это раньше, или даже удалять.
— Тогда вам определённо не нужен Hadoop.

Мой бывший коллега был далеко не первым, кто говорил про распределённые вычисления на Hadoop. И каждый раз я видел полное непонимание того, зачем была придумана и разработана эта платформа.

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

• действия выполняются вручную, что требует сосредоточенности и аккуратности;
• жёсткие временные рамки.

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

Вам кажется, что кто-то подключился к вашему Wi-Fi, перехватывает пакеты и следит за вами? А может, в свете последних новостей, вам захотелось уйти в подполье? Тогда встречайте проект Bunny.py — средство для незаметной передачи данных при беспроводных коммуникациях.

Американец Паркер Томпсон разработал приложение, с помощью которого можно эффективно скрывать трафик в пакетах 802.11. Приложение позволяет поднять собственную беспроводную сеть между устройствами, которая будет невидима для постороннего наблюдателя (darknet), — а все потому, что ее трафик будет замаскирован в посторонних Wi-Fi-пакетах.

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

Перевод статьи Аллана О’Доннелла Learning C with GDB.

Исходя из особенностей таких высокоуровневых языков, как Ruby, Scheme или Haskell, изучение C может быть сложной задачей. В придачу к преодолению таких низкоуровневых особенностей C, как ручное управление памятью и указатели, вы еще должны обходиться без REPL. Как только Вы привыкнете к исследовательскому программированию в REPL, иметь дело с циклом написал-скомпилировал-запустил будет для Вас небольшим разочарованием.

Недавно мне пришло в голову, что я мог бы использовать GDB как псевдо-REPL для C. Я поэкспериментировал, используя GDB как инструмент для изучения языка, а не просто для отладки, и оказалось, что это очень весело.

Представьте себе фреймворк общего назначения для распределенного исполнения приложений со следующими статистическими показателями*:


* Статистические данные за 2011 год.

А теперь представьте, что это не Hadoop.

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

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

Что происходит внутри процессора? Сколько времени уходит на исполнение одной инструкции? Что значит, когда новый процессор имеет 12, или 18, или даже 31-уровневый конвейер?

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

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

Эта статья рассказывает, как устроен вычислительный конвейер x86 процессора.

Эта статья — частичный перевод одной интересной статьи с sqlite.org, в которой подробно рассматривается реализация транзакций в SQLite. На самом деле я очень редко работаю с SQLite, но тем не менее мне очень понравилось это чтиво. Поэтому если хотите просто развить кругозор — будет интересно почитать. Первые две секции не включены в перевод, так как там нет ничего интересного, да и мне лень их набивать (пост и так огромный).

3.0 Однофайловый коммит

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

3.1 Начальное состояние

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

В рамках своей научной активности реализовал так называемый Федеративный Фильтр Калмана (Federated Kalman Filter). В этой статье рассказывается о том, что такое «Федеративный ФК», чем он отличается от обобщенного, а также описывается консольное приложение, реализующее данный фильтр и генетические алгоритмы для подбора параметров его математической модели. Приложение было реализовано с использованием TPL (Task Parallel Library), поэтому пост будет интересен не только специалистам по цифровой обработке сигналов.

UPD1: после прочтения двух недавних статей решил тоже присоединиться к эксперименту/исследованию/авантюре (называйте как хотите). В конце статьи добавил еще один опрос — "Стали бы Вы поощрать рублем такие узко специализированные статьи на Хабрахабре?".

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

Как же они этого добиваются?

Часто считают, что десятикратная производительность вытекает из десятикратных способностей или десятикратных знаний. Я так не думаю. Не хочу сказать, что способности или знания бесполезны. Но за много лет я заметил, что самое главное тут — десятикратная разборчивость. Фокус в том, чтобы постоянно уклоняться от паршивой работенки.

Примечание переводчика: Оригинал здесь. Все примеры в оригинале написаны на JavaScript, но я решил перевести их на Scheme. Уверен, менее понятно не стало, но зато видна вся красота этого языка.
UPD: добавил ко всем примерам справа еще и оригинальные примеры на JavaScript.


Если закрыть глаза на практическую сторону компьютеров — размер, вес, цену, тепло и т.п., что же на самом деле должен уметь язык программирования? Давайте исследуем этот вопрос.

Для понимания примеров в этой статье необходимы базовые понятия о функциях в LISP (Scheme). Если вы понимаете, что напечатает этот код, можно смело читать дальше:

(define x 10) (define (f y) (display x) (newline) (display y) (newline) ) (define g f) (f 1) (g 2)

var x = 10; var f = function(y) { console.log(x); console.log(y); } var g = f; f(1); g(2);

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

Сегодня мы завершаем серию публикаций о фреймворке FML, в которых рассказываем о том, как и для чего автоматизировали в Яндексе применение технологий машинного обучения. В сегодняшнем посте мы расскажем:

• почему нужно следить за качеством факторов и как мы это делаем;
• как FML помогает в задачах распределённых вычислений над поисковым индексом;
• каким образом и для чего наши технологии машинного обучения уже применяются и могут быть применены как в Яндексе, так и вне его;
• какую литературу можно посоветовать для более глубокого погружения в затронутую проблематику.

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


В последние несколько лет интенсивно развивается новое направлении в теории восстановления изображений — слепая обратная свертка (Blind Deconvolution). Появилось достаточно много работ по этой теме, и начинается активное коммерческое использование результатов.
Многие из вас помнят конференцию Adobe MAX 2011, на которой они как раз показали работу одного из алгоритмов Blind Deconvolution: Исправление смазанных фотографий в новой версии Photoshop
В этой статье я хочу подробнее рассказать — как же работает эта удивительная технология, а также показать практическую реализацию SmartDeblur, который теперь тоже имеет в своем распоряжении этот алгоритм.
Внимание, под катом много картинок!

На форуме Stackoverflow обсуждают, как сделать PNG, который будет по-разному выглядеть в разных браузерах. Например, картинка вверху выглядит как груша в Chrome/Firefox, но «превращается» в яблоко в браузере IE.

Пару лет назад я писал об использовании базы PAF (Postcode Address File) британской Королевской почты (Royal Mail) для приведения почтовых адресов, вводимых пользователями, к стандартному виду. Поскольку PAF — основная интеллектуальная собственность Royal Mail, то заполучить её не так-то просто: годовая подписка стоит от £400 в зависимости от полноты базы и от частоты апдейтов. Спустя неделю-другую после оформления подписки по почте приходит солидная красная коробочка с CD-диском:


На диске — EXE-файл, который запрашивает «серийный номер» и распаковывает базу (набор CSV-файлов) на диск. Серийный номер присылают отдельно, чтобы злоумышленник, перехвативший посылку, не смог бы воспользоваться базой. (Вот выдумают же — текстовый файл с серийным номером!) Номер у каждого клиента свой, чтобы в случае «утечки» было ясно, к кому предъявлять претензии. Впрочем, организовать «утечку» самих данных серийный номер никак не мешает, и на WikiLeaks в 2009 г. появилась база Postzon (одна из составляющих PAF). В комментариях к ней отмечено, что "данная база составлена на средства налогоплатильщиков, и активисты, в их числе газета The Guardian и сэр Тим Бернерс-Ли, уже давно пытаются убедить Royal Mail открыть свободный доступ к PAF; но до сих пор эти попытки не увенчались успехом". Впрочем, через год после появления Postzon на WikiLeaks аналогичная по содержанию база появилась в открытом доступе от имени британской картографической службы Ordnance Survey и под названием OS Code-Point Open — таким образом и Royal Mail сохранила лицо, не уступив требованиям активистов, и утёкшие данные официально получили статус общедоступных. Тем не менее, полностью PAF до сих пор необщедоступна. (Пока я готовил эту статью, Postzon и с WikiLeaks куда-то пропала; но гугл всё помнит.)

Спустя год после получения PAF мне понадобилось в неё снова заглянуть, но листочек с серийным номером, присланный отдельно от диска, за год успел куда-то затеряться. Тут мне и стало интересно — насколько сложно будет обойти проверку серийного номера в продукте таком солидном и так яростно защищаемом от «освободителей информации»? Через полчаса данные были у меня на винте, а сама программа-распаковщик мне показалась неплохим демонстрационным примером для начинающих реверс-инженеров. Никакая IDA не потребуется — только бесплатные и быстроустанавливаемые инструменты.

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