Search
Write a publication
Pull to refresh
-29
@svr_91read⁠-⁠only

Пользователь

Send message

SSD SATA против SSD PCI-E | Часть первая: теоретическая

Reading time4 min
Views210K
В любом устройстве всегда найдется слабое звено – bottle neck (бутылочное горлышко), самый слабый компонент, который будет лимитировать производительность остальных частей. Долгое время в настольных компьютерах главными “тормозами перестройки” были жёсткие диски, и ни 7200, ни 10000, ни даже 15000 оборотов в минуту, не меняли ситуацию кардинально. С появлением твердотельных накопителей дело сдвинулось с мёртвой точки. Но прогресс не щадит и это быстрое решение. Интерфейс SATA не способен удовлетворить запросы пользователей, поэтому стали появляться новые стандарты и интерфейсы.


Читать дальше →

Приключения Тыж-программиста. Предновогоднего поднятия настроения пост

Reading time11 min
Views173K

Обычная ситуация на заказе. Кадр из К/Ф «Четыре комнаты»

Каждый из нас знаком с клеймом «тыж-программиста», даже если ты веб-дизайнер. Сидишь у компьютера — программист! Собирательный образ супергероя на ниве починки вычислительной и не очень техники, романтика. Но в реальности с этой ролью справляется более-менее смышленый эникейщик с банкой дисков, отверткой и смекалкой, кем и являлся ваш покорный слуга в период с 2008 по 2011 год. И так, пока Владивосток готовится ко сну, чтобы раньше всех начать чистить мандарины и строгать оливьешку, а западная часть России только предвкушает завтрашние приготовления ко встрече Нового Года, я предлагаю тебе, читатель, устроиться поудобнее и познакомиться с теми случаями из моей практики, которые я уже не смогу забыть. Это была отличная школа, которая позволила научиться находить выходы казалось бы из тупиковых ситуаций имея при себе минимум инструмента и максимум нервного заказчика за плечом. Приобретенные в работе навыки общения и прокачанная смекалка не раз спасали меня в моей дальнейшей трудовой деятельности уже в роли саппорта на различных проектах. Я побывал на нескольких сотнях заказов, встретил несколько сот людей, ситуаций и проблем. Кто-то был изначально зол, кто-то был тихим котиком и не мешал работать, а о ком-то я расскажу сегодня.

И да обойдет меня стороной банхаммер НЛО! Поехали!
Стать на 15 минут тыж-программистом

Пишите компараторы правильно

Reading time5 min
Views151K
В Java для введения порядка среди определённых объектов можно написать компаратор — класс, содержащий функцию compare, которая сравнивает два объекта. Альтернативой компаратору является естественный порядок объектов: объект реализует интерфейс Comparable, который содержит метод compareTo, позволяющий сравнить этот объект с другим. Сравнивающая функция должна вернуть 0, если объекты равны, отрицательное число (обычно -1), если первый объект меньше второго, и положительное число (обычно 1), если первый больше. Обычно реализация такой функции не представляет сложностей, но имеется один случай, о котором многие забывают.

Сравнение используется различными алгоритмами от сортировки и двоичного поиска до поддержания порядка в сортированных коллекциях вроде TreeMap. Эти алгоритмы завязаны на три важных свойства сравнивающей функции: рефлексивность (сравнение элемента с самим собой всегда даёт 0), антисимметричность (сравнение A с B и B с A должны дать разный знак) и транзитивность (если сравнение A с B и B с C выдаёт одинаковый знак, то и сравнение A с C должно выдать такой же). Если сравнивающая функция не удовлетворяет этим свойствам, алгоритм может выдать совершенно непредсказуемый результат. Причём скорее всего вы не получите никакого исключения, просто результат будет неверный.

Как обнаружилось, несоблюдение этих свойств — не такая уж редкая ситуация. Проблема возникает при сравнении вещественных чисел — float или double.
Читать дальше →

Это правильно, но неверно

Reading time3 min
Views53K
Специалисты заслуженно не любят задачи и головоломки на собеседованиях. Но мы просто любим порешать такие задачи в свое удовольствие. Вот что мне лично не нравится, так это когда ты получаешь правильный ответ, но при этом твое решение кажется автору неверным. Хочу просто показать решение нескольких популярных подобных задач, которые можно получить в уме и без сложных расчетов и сопоставить их с авторскими верными.
Читать дальше →

Грязные трюки с макросами C++

Reading time10 min
Views149K
В этой статье я хочу сделать две вещи: рассказать, почему макросы — зло и как с этим бороться, а так же продемонстрировать пару используемых мной макросов C++, которые упрощают работу с кодом и улучшают его читаемость. Трюки, на самом деле, не такие уж и грязные:
  • Безопасный вызов метода
  • Неиспользуемые переменные
  • Превращение в строку
  • Запятая в аргументе макроса
  • Бесконечный цикл

Заранее предупреждаю: если Вы думаете увидеть под катом что-то крутое, головоломное и сногсшибательное, то ничего такого в статье нет. Статья про светлую сторону макросов.
Читать дальше →

Откуда есть пошло комплексное число

Reading time3 min
Views154K
В современной математике комплексное число является одним из фундаментальнейших понятий, находящее применение и в «чистой науке», и в прикладных областях. Понятно, что так было далеко не всегда. В далекие времена, когда даже обычные отрицательные числа казались странным и сомнительным нововведением, необходимость расширения на них операции извлечения квадратного корня была вовсе неочевидной. Тем не менее, в середине XVI века математик Рафаэль Бомбелли вводит комплексные (в данном случае точнее сказать, мнимые) числа в оборот. Собственно, предлагаю посмотреть, в чем была суть затруднений, доведших в итоге солидного итальянца до подобных крайностей.
Читать дальше →

Насколько медленны iostreams?

Reading time7 min
Views81K
Потоки ввода-вывода в стандартной библиотеке C++ просты в использовании, типобезопасны, устойчивы к утечке ресурсов, и позволяют простую обработку ошибок. Однако, за ними закрепилась репутация «медленных». Этому есть несколько причин, таких как широкое использование динамической аллокации и виртуальных функций. Вообще, потоки — одна из самых древних частей стандартной библиотеки (они начали использоваться примерно в 1988 году), и многие решения в них сейчас воспринимаются как «спорные». Тем не менее, они широко используются, особенно когда надо написать какую-то простую программу, работающую с текстовыми данными.

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

Сегодня в комментариях у посту возникло обсуждение о медленности iostreams. В частности, freopen пишет
Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)

а aesamson даёт такую рекомендацию
Можно заменить на getchar_unlocked() для *nix или getchar() для всех остальных.
getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.


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

Гипотеза Бёрча — Свиннертон-Дайера

Reading time11 min
Views19K
Эта примечательная гипотеза связывает поведение функции L там, где в настоящее время неизвестно, определена ли она, и порядок группы Ш, про которую неизвестно, конечна ли она!
J.T.Tate, The arithmetic of elliptic curves, Inventiones mathematicae 23 (1974)
Оригинал
This remarkable conjecture relates the behaviour of a function L at a point where it is not at present known to be defined to the order of a group Ш which is not known to be finite!
(Краткая справка насчёт актуальности цитаты 40-летней давности: после Уайлса и Ко таки стало известно, что функцию L можно определить на всей комплексной плоскости. Конечность группы Ш в общем случае остаётся неизвестной.)
Остаётся обсудить возможность ошибки. В качестве предосторожности против внутренних ошибок компьютера можно прогнать все вычисления дважды или делать проверки внутри программы. Более того, компьютеры — в отличие от людей — устроены так, что их ошибки обычно чересчур велики, чтобы их не заметить. Мы уверены, что в наших результатах нет подобных ошибок. С другой стороны, при кодировании замысловатой схемы вычислений в компьютерную программу неизбежны программистские ошибки. Большинство из них обнаруживаются ещё до основных запусков, из-за того, что программа виснет или выдаёт нелепые результаты. Но программа, которую считается работающей, всё ещё может содержать логические ошибки, проявляющиеся при редких стечениях обстоятельств: и действительно, большинство компьютеров подвержено аномалиям, из-за которых те иногда ведут себя не так, как должны по спецификациям. В сущности, наша программа для этапа (ii) оказалась неточной и пропустила очень небольшое количество эквивалентностей, которые должна была найти.

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

B.J.Birch and H.P.F.Swinnerton-Dyer, Notes on elliptic curves. I, Journal für die reine und angewandte Mathematik 212 (1963)
Оригинал
It remains to discuss the question of error. One can take precautions against machine errors either by running all the calculations twice or by checks included in the program. Moreover, machines — unlike human beings — are so designed that the errors they make are usually too gross to be overlooked. We are satisfied that there are in our results no undetected errors of this sort. On the other hand, in translating an elaborate scheme of calculation into a machine program one is bound to make mistakes. Most of these are found before the program is used for production runs; they show up because the program grinds to a halt or produces ridiculous results. But a program which is believed to work may still contain logical errors which only have an effect in rare circumstances: and indeed most computers have anomalies which cause them occasionally not to behave in the way that their specifications suggest. In fact, our program for stage (ii) was imperfect in that a very few equivalences were missed by the machine.

For these reasons we believe that results obtained from a computer should not be automatically trusted. In some cases they can be checked because they have properties which were not essentially used in the course of the calculation and which would be unlikely to survive if an error had been made. (For example, if a table of a smooth function has been calculated without the use of interpolation, it can be checked by differencing.) But if checks of this sort are not available, results should not be fully trusted until they have been independently reproduced by a different programmer using a different machine. We do not think this sets an unreasonable standard, now that computers are becoming so widely available; and we are satisfied that lower standards have already led to a number of untrue results being published and believed.


Под катом не будет формулировки гипотезы; знающие выражения вроде «Euler product» и «holomorphic continuation» (и в смысле языка, и в смысле обозначаемых понятий) могут прочитать пятистраничный pdf с сайта института Клэя. Под катом — некоторая попытка пояснить, на каком направлении развития математической мысли вообще находится гипотеза Бёрча — Свиннертон-Дайера. А также — как можно досчитать до больших чисел вроде тех, что показаны на КДПВ, менее чем за секунду.
Читать дальше →

Детекторы углов

Reading time18 min
Views114K
Мне интересна обработка изображений, в особенности работа с особыми точками. Ища информацию по детекторам углов, я не нашел достаточно большого обзора этих алгоритмов на русском языке. Поэтому я решил исправить ситуацию, написав эту статью. План статьи следующий:

  • Введение
  • Свойства особых точек
  • Детекторы углов
    • Moravec
    • Harris
    • Shi-Tomasi
    • Förstner
    • SUSAN
    • Trajkovic
    • FAST
    • CSS
    • Детектор, основанный на глобальных и локальных свойствах кривизны
    • CPDA
  • Выводы



Читать дальше →

Параллельное программирование с CUDA. Часть 2: Аппаратное обеспечение GPU и шаблоны параллельной коммуникации

Reading time14 min
Views34K

Содержание


Часть 1: Введение.
Часть 2: Аппаратное обеспечение GPU и шаблоны параллельной коммуникации.
Часть 3: Фундаментальные алгоритмы GPU: свертка (reduce), сканирование (scan) и гистограмма (histogram).
Часть 4: Фундаментальные алгоритмы GPU: уплотнение (compact), сегментированное сканирование (segmented scan), сортировка. Практическое применение некоторых алгоритмов.
Часть 5: Оптимизация GPU программ.
Часть 6: Примеры параллелизации последовательных алгоритмов.
Часть 7: Дополнительные темы параллельного программирования, динамический параллелизм.
Читать дальше →

Параллельное программирование с CUDA. Часть 1: Введение

Reading time11 min
Views140K

Еще одна статья о CUDA — зачем?


На Хабре было уже немало хороших статей по CUDA — раз, два и другие. Однако, поиск комбинации «CUDA scan» выдал всего 2 статьи никак не связанные с, собственно, алгоритмом scan на GPU — а это один из самых базовых алгоритмов. Поэтому, вдохновившись только что просмотренным курсом на Udacity — Intro to Parallel Programming, я и решился написать более полную серию статей о CUDA. Сразу скажу, что серия будет основываться именно на этом курсе, и если у вас есть время — намного полезнее будет пройти его.
Читать дальше →

10 возможностей быть продуктивнее с Eclipse для Java разработчиков

Reading time4 min
Views64K


Многие из вас знают, как эффективно повышает производительность использование горячих клавиш, шаблонов кода и очень клёвой строки поиска (Quick Access), но я бы хотел рассказать о десяти возможностях, которые знают не все.
Стать продуктивнее

«Математика – один из видов искусства»: пост к столетию со дня рождения Мартина Гарднера

Reading time3 min
Views59K

Перевод поста Эда Пегга Младшего (Ed Pegg Jr) "Martin Gardner’s 100th Birthday"

Я думаю, содержание этого поста будет интересно всем, кто любит математику и ее красоту, всем, кто знаком с замечательными книгами и задачами Мартина Гарднера, а также будет полезно учителям, школьникам и студентам. Все ссылки в данном посте ведут на сайты Wolfram Demonstrations Project (коллекция бесплатных интерактивных демонстраций, созданных пользователями системы Mathematica на языке Wolfram Language с помощью технологии Computable Document Format (CDF), при этом для вас доступны исходные коды всех демонстраций, а значит, вы можете каждую из них скачать, изучить и изменить под себя) и Wolfram MathWorld (крупнейшая и самая авторитетная онлайн-энциклопедия по математике).

Gardner100_1.gif

Читать далее...

Документ в перспективе, что с ним делать? Корректировка результатов бесконтактного сканирования и фотографий документов

Reading time7 min
Views18K
Идея данной статьи возникла у нас после прочтения статьи «Как работает автоматическое выделение документа на изображении в программе ABBYY FineScanner?», опубликованной на Хабре компанией ABBYY, в которой подробно описан алгоритм определения границ документа на образе, полученном камерой мобильного телефона.
Статья, безусловно, интересная и полезная. Мы, «с чувством глубокого удовлетворения» отметили, что ABBYY использует в работе те же математические алгоритмы, что и мы, и благоразумно опускает некоторые детали, без которых точность определения границ документа существенно снижается.
Думаю, что по прочтении статьи у некоторой части читателей возник резонный вопрос: «А что делать с обнаруженным на снимке документом дальше?» Отвечу словами Чеширского Кота Алисе: «А куда ты хочешь прийти?» Если конечная цель – «вытащить» из снимка текстовые данные, тогда нужно максимально облегчить задачу системе распознавания. Для этого в первую очередь нужно исправить перспективные искажения, бич всех фотоснимков документов «от руки». Если не решить эту проблему, попытка распознать данные может дать результат, сравнимый с попытками распознавания капчи. На фрилансерских сайтах с завидной регулярностью появляются «верующие» в победу машинного интеллекта над капчой за мелкий прайс. Блажен, кто верует, но мы сейчас не об этом.
Итак, в данной статье мы попытаемся подхватить эстафету у ABBYY и рассказать на своем опыте, как можно с минимальными затратами привести призмообразный, в лучшем случае, документ, который мы идентифицировали на снимке (спасибо ABBYY за науку), к прямоугольной форме, желательно с сохранением исходных пропорций. Экзотические случаи, вроде пятиугольных или овальных документов мы пока не рассматриваем, хотя, вопрос интересный.
Читать дальше →

Почему вы никогда не должны говорить «никогда»

Reading time7 min
Views56K
Эта моя публикация чуть более чем полностью является ответом на перевод статьи «Почему вы никогда не должны использовать MongoDB». Статья, которая, по сути, рекомендует держаться подальше от MongoDB, является самой заплюсованной в хабе. И это звучит как приговор. Поэтому логично либо хаб закрыть и больше никогда не читать, либо написать ещё более рейтинговое опровержение. Конечно же, я выбрал второй вариант, рискуя своим рейтингом и кармой (ввиду крайней холиварности в комментах).

image
Картинка самоиронии

Читать дальше →

За один проход

Reading time7 min
Views157K
Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.
Другие задачи

Ликбез: методы ресайза изображений

Reading time7 min
Views128K
Почему изображение, масштабированное с бикубической интерполяцией, выглядит не как в Фотошопе. Почему одна программа ресайзит быстро, а другая — нет, хотя результат одинаковый. Какой метод ресайза лучше для увеличения, а какой для уменьшения. Что делают фильтры и чем они отличаются.

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


Этот человек сидит среди ромашек, чтобы привлечь ваше внимание к статье.
Читать дальше →

Статистическая проверка случайности двоичных последовательностей методами NIST

Reading time16 min
Views62K


Любой, кто, так или иначе, сталкивался с криптографией, знает, что без генераторов случайных чисел в этом деле не обойтись. Одно из возможных применений таких генераторов, например, – генерация ключей. Но не каждый при этом задумывается, а насколько «хорош» тот или иной генератор. А если и задумывался, то сталкивался с тем фактом, что в мире не существует какого-либо единственного «официального» набора критериев, который бы оценивал, насколько данные случайные числа применимы именно для данной области криптографии. Если последовательность случайных чисел предсказуема, то даже самый стойкий алгоритм шифрования, в котором данная последовательность будет использоваться, оказывается, уязвим — например, резко уменьшается пространство возможных ключей, которые необходимо «перебрать» злоумышленнику для получения некоторой информации, с помощью которой он сможет «взломать» всю систему. К счастью, разные организации все же пытаются навести здесь порядок, в частности, американский институт по стандартам NIST разработал набор тестов для оценки случайности последовательности чисел. О них и пойдет речь в данной статье. Но сначала — немного теории (постараюсь изложить не нудно).

Читать дальше →

ZeroMQ: сокеты по-новому

Reading time7 min
Views81K
В любом среднем или крупном приложении, будь оно desktop или web, для бизнеса или для личного пользования, программисту необходимо решить важную архитектурную задачу — как будут общаться между собой потоки, процессы, модули, ноды, кластера, и прочие части эко-системы его приложения.

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

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

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

Однако, в этом мире бесплатный сыр только в мышеловке. Поэтому я постарался по мере сил и опыта выяснить, чем придется поплатиться за удобство, какие я нашел плюсы и минусы при применении данной библиотеки.
Читать дальше →

Корреляционный анализ или Почему существуют странные корреляции

Reading time3 min
Views22K
На данный опус меня навела публикация «Деньги, товар и немного статистики. Часть вторая», в которой автор исследовал зависимости между ценами на различные товары. Несколько смутило то, что несмотря на мастерское обращение с MatLab'ом, автор ни разу не упомянул об уровне значимости полученных корреляций. Ведь, связь между двумя величинами может и существовать, но если она статистически не значима, говорить о ней мы можем лишь в контексте рассуждений и домыслов.

Пощупать данные «руками» долго не получалось, но вот выдался свободный час, и я, вооружившись R, двинулся в путь.
Читать дальше →

Information

Rating
Does not participate
Registered
Activity