Введение

Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:

• Расстояние Левенштейна
• Расстояние Дамерау-Левенштейна
• Алгоритм Bitap с модификациями от Wu и Manber
• Алгоритм расширения выборки
• Метод N-грамм
• Хеширование по сигнатуре
• BK-деревья

А также проведу сравнительное тестирование качества и производительности алгоритмов.

В этой статье я расскажу, как отлаживать многопоточные приложения в Visual Studio 2010, используя окна Parallel Tasks и Parallel Stacks. Эти окна помогут понять структуру выполнения многопоточных приложений и проверить правильность работы кода, который использует Task Parallel Library.

Мы научимся:

• Как смотреть call stacks выполняемых потоков
• Как посмотреть список заданий созданных в нашем приложении (System.Threading.Tasks.Task)
• Как перемещаться в окнах отладки Parallel Tasks и Parallel Stacks
• Узнаем интересные и полезные мелочи в отладки с vs2010

Осторожно, много картинок

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

И снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».

В этой короткой заметке хочу рассказать о прекрасной программе для поиска утечек памяти под Visual Studio--Visual Leak Detector.
Она удивительно проста в использовании и выдает подробную информацию о найденных утечках, а на хабре пока не упоминалась.

Знаете ли вы что такое рейтрейсер? Это программа которая рисует трёхмерную сцену на экране так, как её бы увидели вы. Конечно, не совсем так, но некоторые рейтрейсеры умеют рисовать очень правдоподобные картинки, например как в "Аватаре".

Идея рейтрейсера очень простая и в этой статье я раcскажу как устроен этот алгоритм и даже напишу его на JavaScript. Картинки и пример прилагаются.

Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

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

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

На написание данной статьи меня подтолкнул топик HTML в PDF, правда по причине того, что он посвящен языку php, лично мне он был мало полезен, т.к. весь опыт работы с php у меня сводился в переводе нескольких скриптов на C#, поэтому я решил сделать небольшой обзор того, что доступно для работы с pdf по средствам языка C#.

Ко мне в список попало 7 библиотек, о которых я скажу несколько слов, а для самой популярной (судя по ответам на stackoverflow), я напишу, как с помощью неё сделать простейший документ. Сразу скажу, что это iTextSharp и работа с ней будет описана в конце статьи.

Существует великое множество файловых систем. Это и файловые системы для носителей информации (FAT*, NTFS, ext* и т.д.), и сетевые файловые системы (NFS, CIFS и т.д.), и виртуальные файловые системы, и великое множество других. А появлялась ли у тебя, %habrauser%, потребность в своей, еще несуществующей файловой системе? О том, как ее сделать для ОС Windows на managed-коде (.net), и пойдет речь.

Введение
Как-то стояла задача отсортировать уникальный массив строк с использованием GPU с минимум кода и максимально возможной скоростью…
В данном посте опишу основную идею ее решения. В качестве элементов массива сортировки в данном посте выступают числа.
Случай с уникальными элементами небольшого массива
В качестве платформы была выбрана CUDA по причинам, которые можно считать брэндовыми или индвидуальными. По факту, здесь много примеров именно на CUDA, и она на данный момент получила большее развитие в GPU-вычислениях, чем аналогичные платформы от ATI и OpenCL.
Поиск в сети по алгоритмам сортировки на CUDA дал разные результаты. Вот наиболее интересный. Там есть рисунок

, из которого видно, что наилучший результат дал алгоритм QSORT, который дает сложность порядка от O(NlogN) до O(N^2). И хотя распараллеливание на GPU дало лучший в статье результат, закралось сомнение, что QSORT — не лучший способ использовать ресурсы видеокарты для данной задачи (особенно испугал размер приведенного кода). Далее описывается решение задачи, по сути «в одну строчку» с сложностью временной сложностью O(N) в худшем случае.

Создание QML файлов — невероятно веселая задача, но довольно часто проблематично разбить замечательные Photoshop шаблоны, которые прислал вам дизайнер, в полностью готовый интерфейс Qt Quick. Было бы замечательно, если бы мы смогли автоматизировать этот процесс? Я тоже так подумал, и написал пару полезных скриптов. Первый — скрипт для Photoshop. Просто положите его совместно с другими скриптам, и у Вас появится новый пункт в меню «Export QML», с помощью которого можно перебросить сцену в один QML-файл с элементами Text или Image из каждого слоя. Скрипт также можно использовать и для векторной графики, поскольку в Adobe Illustrator есть удобная опция экспорта в Photoshop.

Я сделал небольшое демонстрационное видео, чтобы лучшее продемонстрировать, как это работает на практике:

Чтобы было понятно, на чём следует концентрироваться при оптимизации, слайд из доклада «Создание программных систем в Google и его уроки»:

Будучи на конференции Qt Developer Days 2010 я узнал, что одним из самых популярных вопросов на собеседовании в разные зарубежные компании, работающие с Qt библиотекой, является вопрос о различиях в способах приведения типов в C++. Поэтому здесь я рассмотрю основные различия между static_cast, dynamic_cast, const_cast, reinterpret_cast, C-style cast, qobject_cast и qvariant_cast

Feed Converter представляет собой сервис по конвертации RSS и Atom лент в различные форматы для последующего их чтения в оффлайне с различных девайсов, таких как коммуникаторы, электронные книги etc.

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

Предлагаю вниманию читателей перевод статьи "Programming Sucks! Or At Least, It Ought To", опубликованной в «The Daily WTF». Публикация рассказывает о том, как избыток профессионализма на практике мешает эффективности и предназначена скорее для опытных разработчиков, нежели для новичков.

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

Замечательный сайт www.sorting-algorithms.com позволяет увидеть, как сортируются данные разными алгоритмами. Вы сможете посмотреть анимацию в зависимости от алгоритма, исходных данных.



Все это бегает и сортируется прямо на ваших глазах!

Работает на Google App Engine, видимо, поэтому и лежит от посетителей с «Хабра».

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



Давайте разберемся, что к чему. Допустим, у нас есть абстрактный IT-работник, очень сильно смахивающий на программиста, который будет создавать не менее абстрактный продукт в некой компании таких же абстрактных работников. Первое, что сделал бы оценщик середины 19 века, это вывел вполне четкие показатели труда. И были бы это время и количество кода. Чем больше кода создает работник, при минимальных временных затратах, тем более эффективный работник. Все это хорошо, но это не работает.

В вашей системе время играет важную роль? Ваши пользователи/компоненты распределены по территории всего земного шара, или хотя бы нашей необъятной родины? Значит, вам нужны часовые пояса. Что ж, это просто. Самое сложное, что вам придется сделать — не запутаться. Об этом мы с вами и поговорим. Для начала вам нужно научиться правильно думать. Думая правильно, все остальное будет для вас либо самоочевидным, либо достаточно простым.

Начнем с часов. Все мы привыкли определять время, глядя на часы на стене. При работе с часовыми поясами такое время называется Wall clock time. В принципе, ничего плохого в нем нет, только в разных местах земного шара в один и тот же момент времени часы показывают разное время. Если задаться целью, можно придумать алгоритм перевода wall clock time одного часового пояса в wall clock time другого. Обычно надо прибавить/отнять разницу в часах между часовыми поясами, кроме (внимание) моментов перехода на летнее/зимнее время. Вот когда начинается переход, вычисления становятся по-настоящему сложными.

Нам же нужно что-то простое и пуленепробиваемое, как… целое число.

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

Пользователи интернета тратят 80% времени, изучая информацию на «первом экране». Несмотря на то, что прокруткой они тоже пользуются, только 20% их внимания приходится на то, что расположено ниже «первого экрана».

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

Для написания ТЗ я задался вопросом поиска простого и удобного средства создания прототипов веб-страниц. Хотелось чего-то бесплатного и в онлайне, некой альтернативы Axure. Такой сервис удалось найти, его я и предлагаю вашему вниманию. Итак, встречайте www.gomockingbird.com – сервис, позволяющий создавать очень красивые прототипы легко и удобно.
Помимо представления самого сервиса, этим постом хотелось также привлечь внимание общественности к полезной практике прототипирования.