Мы с другом решаем пойти в поход от Сан Франциско до Лос Аджелеса, чтобы заскочить в гости к нашим друзьям на Ньюпорт Бич. Посмотрим на карту и примерно прикинем путь по берегу:



Путь займёт около 400 миль, в день мы можем пройти 4 мили в час по десять часов, так что придём мы туда примерно через 10 дней. Мы звоним друзьям и бронируем столик на 6 вечера в воскресенье.

Рассмотрим ситуацию, когда необходимо обрабатывать столкновения между объектами. Как вы в этом случае поступите? Вероятно, самым простым решением будет проверить каждый объект с каждым другим объектом. И это правильное решение, и все будет замечательно до тех пор пока объектов не много. Как только их станет порядка нескольких тысяч, вы заметите, что все стало как-то медленно работать. А если частиц несколько десятков тысяч или сотен? Тогда все замрет. Вот здесь уже интересно, на какие хитрости и оптимизации вы пойдете, чтобы решить такую проблему.

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

Содержание

1. Обзор алгоритмов
1.1. Полный перебор
1.2. Sweep & Prune
1.3. Регулярная сеть
2. Некоторые оптимизации
2.1. Sweep & Prune
2.2. Регулярная сеть
3. Сравнение скорости выполнения
4. Приложение (программа и исходный код)
5. Заключение

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

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

• Грамотно обрабатывайте запросы на изменение требований
• Урезайте лишний функционал
• Управляйте рисками
• Используйте гибкие методологии
• Научитесь управлять Death March проектами

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

• есть некоторое количество (можно считать, что не более 16 миллионов) измерений набора параметров. Число параметров в наборе – от 2 до 5.
• измерение параметров может быть относительно успешным – тогда их результат будет неподалеку от истинного (параметры и тип распределения неизвестны), либо не успешным – тогда результат будет случайным (опять-таки с неизвестными параметрами распределения). Определить по одиночному измерению, было ли оно успешным, нельзя.
• Можно считать, что точка сгущения существует. Если их несколько с близким качеством (которое формально так и не определяется), можно выдать любую.
• ответ нужно дать за один проход по исходным данным: перевычислять их или сохранять целиком – дорого.
• И, как обычно, хочется, чтобы алгоритм выглядел попроще, а работал побыстрее.

Задача

Требуется обеспечить работоспособность определённого IP-адреса (шлюза, важного сервера и т.д.) при пропадании связи с устройством, которому этот адрес первоначально принадлежит, с помощью резервных устройств.

В статье для этой цели будут использованы Debian Linux, протокол CARP и утилита ucarp.

Вместо введения

Добрый день, Хабралюди.
Хотел бы поделиться со всеми моим скромным опытом выбора языка программирования для своих проектов. Сразу хочу подчеркнуть – я выбирал язык исходя из собственных нужд, и, вполне вероятно, что ваш выбор в аналогичных условиях может быть другим. Все же я искренне надеюсь, что эта статья будет полезной, так как в ней достаточно подробно и аргументировано проводится сравнение D с C++ и C#, а так же упоминаются свыше десяти различных языков, принадлежащих к различным классам и реализующих различные парадигмы. Сам D разрабатывается как высокоуровневый язык для системного и прикладного программирования.

Вдохновившись статьёй Привет из свободного от libc мира, я так же решил проделать нечто подобное. Чтобы не заниматься этим бесцельно, я решил поставить перед собой следующую задачу. Сделать программу, выводящую какую-нибудь простую строку, вроде «ELF, hello!». Разобраться с тем, как именно она будет представлена в исполняемом файле. Ну и попутно, постараться уложиться в 100 байт.

В первой части статьи, переведенной уважаемым skb7, было рассмотрено идиому Pimpl (pointer to implementation, указатель на реализацию), ее назначение и преимущества. Во второй части будет рассмотрено проблемы, возникающие при использовании этой идиомы, а также предложены некоторые варианты их решения.

Алгоритм метода Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.

Недавно задался вопросом ведения документации по исходному коду и сборки её используя Doxygen и CMake. Столкнулся сразу с неприятной проблемой. Дело в том, что в своих проектах я использую следующую структуру:

  build/
  src/
  CMakeLists.txt
  Doxyfile

Сборка, в моём случае, происходит в каталоге build. Но сборка может быть выполнена из любого места. Так вот, если изменить каталог сборки, документация не будет собрана, т.к. Doxygen не найдет исходников по которым нужно собрать эту самую документацию. Тогда то я и задумался, как же управлять процессом сборки документации в связке CMake и Doxygen? Что если мне нужно получить несколько видов документации: пользователя и разработчика? Держать два файла конфигурации для Doxygen? Мне такой вариант не нравится, т.к. файлы будут отличаться значением только одной переменной ENABLED_SECTIONS. Ниже я расскажу о там как можно управлять сборкой документации.

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

Эта картина сгенерирована программой Context Free по следующему описанию:

startshape T
// FLIGIZ
background{b -1}
tile {s 2.5}
rule T {3*{r 120 hue 30}S{x .3}}
rule S 3{CIRCLE{hue 30}4*{r 20 b.007 sat .1}S[s.3.7y.9]}
rule S {CIRCLE{hue 15}9*{r 20 b.05 hue -3}S[s.3.7y.9]}
rule S {S{flip 90}}

Как часто можно наблюдать ситуацию, когда списки дел сделаны менее чем на 10%. Потому что мы все пытаемся впихнуть в один день, неделю и т.д.

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


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

На самом деле, осознать иллюзорность важности дел в нашем мире — это только первый шаг. Самое трудное — делать правильный выбор.

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

Параллельная компиляция Qt-проектов под Windows с использованием QtCreator — зверь загадочный и очень привередливый. В этой небольшой статье я расскажу, как же все-таки его приручить. Параллельная компиляция может быть выполнена достаточно просто в теории, на практике дела обстоят не совсем гладко, чему в подтверждение бесконечное число тем на форумах, где предлагаются всевозможные решения. Ни одно из них, к сожалению, нам не помогло.

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

UPD: Более новая статья: Метапрограммирование с примерами на JavaScript. И лекция по статье на Youtube (лекция записана в Киевском политехническом институте 18 апреля 2019 года в рамках курса «100 видео-лекций по программированию»):

The Little Redis Book — это бесплатная книга про Redis.

Книга была написана Karl Seguin, при поддержке Perry Neal. Karl Seguin является также автором книги The Little MongoDB Book, которую часто рекомендуют для быстрого старта с MongoDB. Первая версия повилась около недели назад.

Сегодня я сделал первую версию перевода этой книги. Исходные тексты доступны в репозитории на GitHub. Там же можно найти и готовый PDF.

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

Я благодарен следующим людям за помощь в переводе оригинального текста и вычитке результата:

• Dmitry Scriptin
• Денис Веселов
• polinom

Я прошу все неточности и опечатки отправлять для коррекции перевода.

Меня просто бесит, когда менеджер проекта отправляет макет дизайна — письмом, с припиской «Вот, нарисовали. Смотрите. Ждем ваших замечаний». Убил бы.

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

— Это возмутительно! И вот почему:

Компания id Software выложила все свои проекты Open Source на github. Вот полный список, пользуйтесь на здоровье!

Doom 3 GPL
Wolfenstein 3D для iOS
DOOM Classic для iOS
Quake GPL
DOOM
Quake-Tools, инструменты и утилиты для Quake
idsetup, setup от DOOM, Final DOOM, Strife и др.
Quake-2-Tools GPL
GtkRadiant GPL
Wolfenstein: Enemy Territory GPL
Return to Castle Wolfenstein Multiplayer GPL
Return to Castle Wolfenstein Single-player GPL
Quake 2 GPL
Quake III Arena GPL