Comments / Profile of Sdima1357 / Habr

Дмитрий Самсонов @Sdima1357

image processing

ProfileArticles9PostsNewsComments2K

Интуитивная разработка алгоритмов

Sdima1357 Nov 3 2017 at 14:37

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

0

Интуитивная разработка алгоритмов

Sdima1357 Nov 3 2017 at 14:22

А что Вам не понравилось?
Универсальный метод решения задач:
1 сформулируй условия задачи
2 поищи, возможна она уже решена, если да то используй готовое решение
3 если нет готового решения включи мозг напиши минимальное решение
4 если нет решения заплати тому кто может решить
5 если нет решения брось эту задачу, попробуй вернуться к первому пункту попозже или возьми другую задачу.
Чем не универсальный метод? Первые три пункта описаны в статье

0

Интуитивная разработка алгоритмов

Sdima1357 Nov 3 2017 at 14:04

Вы возможно не поверите, но 99 % реальных задач у программистов именно такие, а для одного процента можно заплатить и позвать Вас ( а потом и меня :)

0

Интуитивная разработка алгоритмов

Sdima1357 Nov 3 2017 at 13:57

Критика должна быть конструктивной, а не по принципу все плохо, «автор убей себя об стену»

0

Интуитивная разработка алгоритмов

Sdima1357 Nov 3 2017 at 13:48

4 «мне пора учить людей как писать статьи»
Напишите лучше.
Вполне себе рабочий алгоритм. Правда задачу быстрее решить по другому. Сначала построить конвекс ( это О(n) на плоскости ) для всех вершин каждого объекта и проверить пересекаются ли с конвексами других объектов а потом проверять по треугольникам

0

Ядра атомов: в самом сердце материи

Sdima1357 Nov 3 2017 at 08:11

Для того чтобы протон мог показать что нибудь интересное, нужно сообщить ему что нибудь интересное

+3

О стеке простыми словами — для студентов и просто начинающих

Sdima1357 Nov 2 2017 at 17:26

Ваше объяснение уже ближе:
стек — это патроны в магазине автомата. Последний вставленный выходит первым.

0

О стеке простыми словами — для студентов и просто начинающих

Sdima1357 Nov 2 2017 at 17:18

Тут вообще много пропущено. Что такое функции new и delete и как они работают. Объяснять простые понятия основываясь на более сложных наверное не самый оптимальный подход.

0

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 2 2017 at 17:06

DaylightIsBurning
1.1 ns (rnd32) бит на том же тесте и моей платформе: habrahabr.ru/post/323158/#comment_10503460

0

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 2 2017 at 15:47

лучший Mersenne Twister генератор который я видел :). А вообще спасибо, посмотрю обязательно. Мне скорость и качество очень критичны(RANSAC like code).

0

Инопланетяне по Дарвину

Sdima1357 Nov 2 2017 at 14:25

Извините, обознался они так похожи :(

+3

Инопланетяне по Дарвину

Sdima1357 Nov 2 2017 at 14:17

«Коммунизм нельзя построить на отдельно взятой планете. Даешь победу коммунизма в нашей галактике!» ( Карл с последней картинки)

+1

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 2 2017 at 13:22

Больше 2 в одном потоке выигрыша по скорости скорее всего не дадут.
А зачем Вам 10? Первый рандом инит из time остальные из первого:
FRand fr(time_count());
FRand fr1(fr.rand());
FRand fr2(fr.rand());

0

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 2 2017 at 12:58

Они сдвинуты.:) На Cycles*2.
Инициализируйте разными seed из того же time

0

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 2 2017 at 12:46

Вот именно для отсутствия коллизий и нужно Ваши статические переменные переложить в members, как в моем примере. Компилятор использует больше регистров и уменьшает latency. посмотрите разницу между 2 и 3 примером по скорости

0

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 2 2017 at 12:10

Вот Вам пример на базе этой библиотеки(Обратите внимание на два последних случая):

	const int Cycles = 100000000;
        FRand  fr;
	FRand  fr1;
	{
		HiCl cl("gen");
		summ=0;
		for (int k=0;k<Cycles;k++)
		{
			summ+=fr.urand();
		}
	}
	cout<<summ/Cycles<<"\n";;
	{
		HiCl cl("gen");
		summ = 0;
		summ1 = 0;
		for (int k=0;k<Cycles/2;k++)
		{
			summ+=fr.urand();
			summ1+=fr.urand();
		}
	}
	cout<<(summ+summ1)/Cycles<<"\n";
	
	{
		HiCl cl("gen");
		summ=0;
		summ1 = 0;
		for (int k=0;k<Cycles/2;k++)
		{
			summ+=fr.urand();
			summ1+=fr1.urand();
		}
	}
	cout<<(summ+summ1)/Cycles<<"\n";

//log
gen 351.955 ms
0.499969
gen 347.921 ms
0.500026
gen 272.77 ms
0.499971

Собственно оболочка:

#ifndef FRand_H
#define FRand_H
extern "C"
{
#include <tinymt32.h>
}
class FRand
{
	tinymt32_t tinymt;
public:	
	FRand()
	{
                tinymt.mat1 = 0x8f7011ee;
	        tinymt.mat2 = 0xfc78ff1f;
	        tinymt.tmat = 0x3793fdff;
		int seed = 1;
		tinymt32_init(&tinymt, seed);
	}
	FRand(int seed)
	{
                tinymt.mat1 = 0x8f7011ee;
	        tinymt.mat2 = 0xfc78ff1f;
	        tinymt.tmat = 0x3793fdff;
		tinymt32_init(&tinymt, seed);
	}
	inline double urand()
	{
		return tinymt32_generate_32double(&tinymt);	
	}
	uint32_t 	rand()
	{
		return tinymt32_generate_uint32(&tinymt);
	}
};
#endif

0

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 2 2017 at 11:00

Возьмите код отсюда
* brief Tiny Mersenne Twister only 127 bit internal state
*
* author Mutsuo Saito (Hiroshima University)
* author Makoto Matsumoto (University of Tokyo)

github.com/MersenneTwister-Lab/TinyMT
На моей машине дает (3.2 GHz ) 2.7 ns per uniform number и это лучший генератор который я видел

+1

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 2 2017 at 10:42

rand() — отвратная и древняя функция,static thread_local — не нужно, нужны именно переменные члены класса или структуры. Еще раз, статические переменные затрудняют работу оптимизатора если Вы используете более одного экземпляра класса даже в одном потоке.

+2

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 1 2017 at 20:37

Автору
Вообще — типичный код для математика: отличная алгоритмическая работа и значительно более слабая (хотя и неплохая) реализация. Фунцию Variate поправьте обязательно, однозначно будет проблема со скоростью (конфликт read-modify-write на общей памяти)
Кроме того, статические переменные затрудняют работу оптимизатора если Вы используете более одного экземпляра класса

+3

RandLib. Библиотека вероятностных распределений на C++17

Sdima1357 Nov 1 2017 at 18:42

1
«RandLib избавляет пользователя от двух вещей: выбора базового генератора (функции, возвращающей целое число от 0 до некого RAND_MAX) и выбора стартовой позиции для случайной последовательности (функция srand()). Сделано это во имя удобства, так как многим пользователям этот выбор скорее всего ни к чему.»

— Не согласен.Для отладки очень часто нужна именно повторяемость.

2
Могут быть проблемы со статическими переменными в функциях BasicRandGenerator<..>::Variate() в многопоточной среде, лучше сделать их членами класса.

+4

1 2 ...

91

92 93 ...