Случайный поиск или на удивление быстрый поиск

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

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

Собственно алгоритм простой:

1. Вычисляем требуемое количество точек, чтобы с указанной вероятностью P найти минимум с указанной точностью;
2. Генерируем с равномерным распределением нужное количество точек и находим в какой из целевая функция принимает минимальное значение.

Алгоритм очень простой, теперь поговорим про две реализации, первая - которая приходит первой на ум, вторая - немного оптимизированный вариант. На счёт генерации - стандартный генератор C/С++ примерно воспроизводит равномерное распределение, поэтому использовать можно его.

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

Вторая реализация
Поскольку точки могут генерироваться независимости друг от друга, а так же вычисляться значение функции, то первое что пришло на ум - распараллелить. Осталось это сделать так, чтобы прога не занимала слишком много памяти(3 миллиарда double - это всё-таки уже много, если я не ошибся 22.4 Гб, если размер типа 8 байт). Поэтому реализовывалось всё так:
У нас есть n потоков, каждый поток должен посчитать по m точек, за раз он считает N точек(тоже параллельно), выбирает из них минимум и сравнивает с текущим приближением, далее, если надо меняет текущее приближение и генерирует ещё N точек и так пока не сгенериует их m штук. В конце у нас остаётся n чисел - минимум из каждого потока, их них выбирается уже глобальный минимум.
Число N можно высчитывать как-нибудь из сходя из общего числа точек на поток, но я просто бал фиксированно N = 10000 (были и другие варианты). Потому что меньших N (при N = 100) затраты на создание потоков были больше чем выгода.
Так что если нам надо хранить три числа(координаты точки и значение функции), то уйдёт всего 3*(n + n*N) ячеек памяти, что намного меньше чем 3*n*m (учитываем, что число потоков n на персональном компьютере невелико - от 2 до 16, примерно, а число m может быть несколько сотен миллионов, то выигрыш в памяти, по сравнению в всеобщим распараллеливанием виден).
Теперь зачем нужно делать это порциями по N штук, а не посчитать по m на потоке - по тем же самым причинам время и память, в рассматриваемом случае минимум из N ищется очень быстро(если ещё упорядочивать при добавлении то ещё быстрее) и памяти надо дополнительной, под 3*N, а не 3*m.
Плюсы: скорость - вот тут и было моё удивление, меньше за минуту на 4-х потоках обрабатывает до миллиарда точек.
Минусы: в реализации конечно не сильно труден, но значительно труднее чем первый метод.

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

Оценка времени работы алгоритмов. Виды роста затрат.

В последнее время было лень что-то писать. Очень лень. Но я собрался и решил написать о довольно лёгкой и в тоже время нужной теме - временные оценки для алгоритмов. Их цель - примерно оценить алгоритм по времени работы, в зависимости от входных данных и дать возможность сравнить алгоритмы, не имея их реализации. В прицепе, у всех алгоритмов есть особенности и если они[алгоритмы] легко и быстро реализуемы, то в конкретном случае сравнение на "практике" будет намного информативнее.
Об обозначениях: обычно используется O-натация, то есть обозначается как О(f(x)) или o(f(x)). Первое можно интерпретировать, как c*f(x), c>1, во втором случае 0<c<=1. Сама функция f(x) может быть, как непрерывной. так и дискретной, под x здесь понимается размер входных данных. Например x=n - длина массива, то функция будет дискретной, x=l - длина отрезка, функция будет непрерывной.
И теперь к самой теме: характеры роста, то есть вид функции f(x). Перечислять их буду в порядке возрастания временных затрат: сначала самые быстрые, затем все более медленные.

1. Полиномиальный рост
• f(x) = log(x) - логарифмический рост, считается одной из лучших оценок. Поскольку log(x) ~ x^a, 0<a<1 при больших x, то этот рост можно назвать минимальным из полиномиальных. Поскольку оценка определяется с точностью умножения на константу, то основание логарифма не важно.
• f(x) = x^a, a >1 - общий вид полиномиального роста, является приемлемой оценкой. Чем меньше показатель степени a, тем оценка лучше - времени меньше. Как было указанно выше  рост вида x*log(x) можно привести к этому типу роста
2. Экспоненциальный рост
Здесь небольшая путаница в терминологии,  при оценки алгоритмов часто любой не полиномиальный рост называют экспоненциальным.

• f(x) = e^x - экспоненциальный рост, рост в геометрической прогрессии. Является не очень хорошей оценкой для работы, однако обычно не критической. Если есть полиномиальный алгоритм, решающий эту задачу - лучше выбирать его.
• f(n) = n!, f(x) = Г(x) - факториальный рост, его спокойно можно включать в следующую группу, однако такие оценки тоже часто встречаются. Поясняю, почему здесь две функции - факториал достаточно известная оценка, но она определенна только для дискретных величин, для непрерывных общение факториала - гамма-функция.
3. Алгоритмы, от которых лучше бежать подальше
Врятле такие оценки вы когда-нибудь встретите, они здесь больше для сравнения - может быть и хуже.

• f(n) = sf(n) - суперфакториальный рост. sf(n) = 1! * 2! * .. * n! - произведение факториалов.  Растёт очень быстро.
• f(n) = (n!)^(n!) - я не думаю, что у такой зависимости есть название вообще. При увеличении n на единицу порядок порядка n увеличивается на единицу. Убунтовский калькулятор (9!)^(9!) на нетбуке уже считает оооочень долго(за 10 минут не посчитал), а виндосовский уже (7!)^(7!) не считает - переполнение.

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

Добавил (n!)^(n!) на график, только при n=1,2,3,4. Для сравнения: с (4!)^(4!) смогло сравняться только 32!. Ну а что дальше - понятно.

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

Аппаратная мощность - не всё для скорости работы программы

Люди, далёкие от программирования и вычислительной техники, часто считают, что скорость работы программы полностью определяется аппаратной мощностью вычислительной системы. Не так давно я пытался доказывать, что некоторые задачи нельзя быстро решить просто по тому, что не придумали хорошего алгоритма решения этих задач (я сейчас про класс NP). Однако мне кажется, что я не был убедителен. В искупление этого записал видео, где сравниваются две разных структуры и соответствующие им алгоритмы разработки. Так что если кому-то придётся объяснять нечто подобное можете сослаться на это видео.
Исходный код используемой в видео программы.
Само видео:

Сравнение сортировок

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

1. Берётся два случных элемента, выбирать надо до тех пор, пока эта пара не начнёт нарушать отношение порядка.
2. Выбранные элементы меняются местами.
3. Массив проверяется на упорядоченность.

Первый явный недостаток - алгоритм никогда не завершится, если массив уже отсортирован. Но это легко преодолеть, если проверить заранее. Меня такие ситуации не интересуют.
Другие сортировки, "конкурирующие" со случайной: это пузырьковая, вставки и выбор.
Признаюсь честно, сам, больше всего люблю сортировку вставками, т.к. оно учитывает уже имеющийся порядок и не меняет его. Полезное свойство, особенно  если надо делать сортировку по нескольким критериями.
Весь процесс вы можете посмотреть на видео, а если в крадце, то  на 10000 элементов:
1. Вставка 0.46 с
2. Выбор 0.53 с.
3. Пузырьковая 1.23 с.
4. Случайная 139.13 с.
Исходники можете скачать по этой ссылке.

Проект по физике: ряды Фурье, метод Эйлера и параллельное программирование

В третьем семестре мы разработали проект по физики - физический маятник. Я занимался вычислениями. Если в общих чертах, то там решалось дифференциальное уравнение методом Эйлера. И функция заданная эти уравнением раскладывалась в ряд Фурье.
Подсчёт коэффициентов Фурье занимал достаточно много времени (на компах в терминалках на это уходило до двух минут), поэтому решил попробовать ускорить это всё, используя OpenMP.
Сама задача не хитрая - распараллелить цикл подсчёта интегральных сумм(метод трапеций). Однако, в силу неявного задания функции очень неудобно считать её значения в точках, т.к. высчитываются они отдельно от предыдущих. Сказано - сделано.
Теперь просто - запускаем параллельный цикл с помощью #pragma parallel for и использованием reduction и получаем уже расспареллеленую версию интегрирования.
Что меня поразило, так это ускорение: если последовательный вариант считался 26.6 с, то параллельный 3.3 с.
Приведу схематичный пример кода (на С), который был и который стал(пояснения после)

double Ssin = 0, Scos = 0;
double fp = f(x1,fimax,vl,x1,&penenq,vl,w);
double fp1,fc,fc1,fs,fs1;

while(absol(x1-l)>=h){

 fp1 = f(x1, fp, vl, x1+h,&penenq,vl,w);
 fc = fp * cos(2*n*(x1)*pi/l)*h;
 fc1 = fp1 * cos(2*n*(x1+h)*pi/l)*h;
 fs = fp * sin(2*n*(x1)*pi/l)*h;
 fs1 = fp1 * sin(2*n*(x1+h)*pi/l)*h;
 Scos += (fc+fc1)/2;
 Ssin += (fs+fs1)/2;
 x1 += h1;
 fp = fp1;

};
Scos = 2*Scos/l;
Ssin = 2*Ssin/l;

Параллельный вариант:

double Ssin = 0, Scos = 0;
double fp1,fc,fc1,fs,fs1;
int it_numb = l/h;
double *fp = new double [it_numb];
fp[0] = f(x1,fimax,vl,x1,&penenq,vl,w);
for(int i = 1; i < it_numb; i++)
 fp[i] = f(x1+i*h);
int i;

#pragma omp parallel for reduction (+:Scos) reduction (+:Ssin) private (fc,fc1,fs,fs1,i) schedule(dynamic,4)

for(i = 1; i < it_numb; i++){
 fc = fp[i-1] * cos(2*n*(x1+i*h)*pi/l)*h;
 fc1 = fp[i] * cos(2*n*(x1+(i+1)*h)*pi/l)*h;
 fs = fp[i-1] * sin(2*n*(x1+i*h)*pi/l)*h;
 fs1 = fp[i] * sin(2*n*(x1+(i+1)*h)*pi/l)*h;
 Scos += (fc+fc1)/2;
 Ssin1 += (fs+fs1)/2;
}

Scos = 2*Scos/l;
Ssin = 2*Ssin/l; 
delete fp[];

x1 - текущая точка(в последовательном варианте) или начальная точка(в параллельном), l - промежуток интегрирования (если быть более точным [0,l]), h - шаг разбиения.

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