Тема «магических квадратов» достаточно интересна, т.к. с одной стороны, они известны еще с древности, с другой стороны, вычисление «магического квадрата» даже сегодня представляет собой весьма непростую вычислительную задачу. Напомним, чтобы построить «магический квадрат» NxN, нужно вписать числа 1..N*N так, чтобы сумма его горизонталей, вертикалей и диагоналей была равна одному и тому же числу. Если просто перебрать число всех вариантов расстановки цифр для квадрата 4х4, то получим 16! = 20 922 789 888 000 вариантов.

Подумаем, как это можно сделать более эффективно.


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

Легко доказать, что эта сумма всегда одинакова, и вычисляется по формуле для любого n:

Мы будем рассматривать квадраты 4х4, так что сумма = 34.
Обозначим все переменные черех X, наш квадрат будет иметь такой вид:

Первое, и очевидное, свойство: т.к. сумма квадрата известна, крайние стоблцы можно выразить через остальные 3:
X14 = S - X11 - X12 - X13
X24 = S - X21 - X22 - X23
...
X41 = S - X11 - X21 - X31

Таким образом, квадрат 4х4 фактически превращается в квадрат 3х3, что уменьшает число вариантов перебора с 16! до 9!, т.е. в 57млн раз. Зная это, приступаем к написанию кода, посмотрим насколько сложен такой перебор для современных компьютеров.

С++ — однопоточный вариант

Принцип программы весьма прост. Берем множество чисел 1..16 и цикл for по этому множеству, это будет х11. Затем берем второе множество, состоящее из первого за исключением числа x11, и так далее.

Примерный вид программы выглядит так:

int squares = 0; int digits[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 }; Set mset(digits, digits + N*N); for (int x11 = 1; x11 <= MAX; x11++) {   Set set12(mset); set12.erase(x11);   for (SetIterator it12 = set12.begin(); it12 != set12.end(); it12++) {     int x12 = *it12;     Set set13(set12); set13.erase(x12);     for (SetIterator it13 = set13.begin(); it13 != set13.end(); it13++) {        int x13 = *it13;        int x14 = S - x11 - x12 - x13;        if (x14 < 1 || x14 > MAX) continue;        if (x14 == x11 || x14 == x12 || x14 == x13) continue;        ...        int sh1 = x11 + x12 + x13 + x14, sh2 = x21 + x22 + x23 + x24, sh3 = x31 + x32 + x33 + x34, sh4 = x41 + x42 + x43 + x44;        int sv1 = x11 + x21 + x31 + x41, sv2 = x12 + x22 + x32 + x42, sv3 = x13 + x23 + x33 + x43, sv4 = x14 + x24 + x34 + x44;        int sd1 = x11 + x22 + x33 + x44, sd2 = x14 + x23 + x32 + x41;        if (sh1 != S || sh2 != S || sh3 != S || sh4 != S || sv1 != S || sv2 != S || sv3 != S || sv4 != S || sd1 != S || sd2 != S)          continue;        // Если числа прошли все проверки на пересечения, то квадрат найден        printf("%d %d %d %d  %d %d %d %d  %d %d %d %d  %d %d %d %d\n", x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44);        squares++;    } } printf("CNT: %d\n", squares); 

Полный текст программы можно найти под спойлером.

#include <set> #include <stdio.h> #include <ctime> #include "stdafx.h"  typedef std::set<int> Set; typedef Set::iterator SetIterator;  #define N 4 #define MAX (N*N) #define S 34  int main(int argc, char *argv[]) { 	// x11 x12 x13 x14  	// x21 x22 x23 x24  	// x31 x32 x33 x34  	// x41 x42 x43 x44   	const clock_t begin_time = clock();  	int squares = 0; 	int digits[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 }; 	Set mset(digits, digits + N*N); 	for (int x11 = 1; x11 <= MAX; x11++) { 		Set set12(mset); set12.erase(x11); 		for (SetIterator it12 = set12.begin(); it12 != set12.end(); it12++) { 			int x12 = *it12; 			Set set13(set12); set13.erase(x12); 			for (SetIterator it13 = set13.begin(); it13 != set13.end(); it13++) { 				int x13 = *it13; 				int x14 = S - x11 - x12 - x13; 				if (x14 < 1 || x14 > MAX) continue; 				if (x14 == x11 || x14 == x12 || x14 == x13) continue;  				Set set21(set13); set21.erase(x13); set21.erase(x14); 				for (SetIterator it21 = set21.begin(); it21 != set21.end(); it21++) { 					int x21 = *it21; 					Set set22(set21); set22.erase(x21); 					for (SetIterator it22 = set22.begin(); it22 != set22.end(); it22++) { 						int x22 = *it22; 						Set set23(set22); set23.erase(x22); 						for (SetIterator it23 = set23.begin(); it23 != set23.end(); it23++) { 							int x23 = *it23, x24 = S - x21 - x22 - x23; 							if (x24 < 1 || x24 > MAX) continue; 							if (x24 == x11 || x24 == x12 || x24 == x13 || x24 == x14 || x24 == x21 || x24 == x22 || x24 == x23) continue;  							Set set31(set23); 							set31.erase(x23); set31.erase(x24); 							for (SetIterator it31 = set31.begin(); it31 != set31.end(); it31++) { 								int x31 = *it31; 								Set set32(set31); set32.erase(x31); 								for (SetIterator it32 = set32.begin(); it32 != set32.end(); it32++) { 									int x32 = *it32; 									Set set33(set32); set33.erase(x32); 									for (SetIterator it33 = set33.begin(); it33 != set33.end(); it33++) { 										int x33 = *it33, x34 = S - x31 - x32 - x33; 										if (x34 < 1 || x34 > MAX) continue; 										if (x34 == x11 || x34 == x12 || x34 == x13 || x34 == x14 || x34 == x21 || x34 == x22 || x34 == x23 || x34 == x24 || x34 == x31 || x34 == x32 || x34 == x33) continue;  										int x41 = S - x11 - x21 - x31, x42 = S - x12 - x22 - x32, x43 = S - x13 - x23 - x33, x44 = S - x14 - x24 - x34; 										if (x41 < 1 || x41 > MAX || x42 < 1 || x42 > MAX || x43 < 1 || x43 > MAX || x44 < 1 || x41 > MAX) continue;  										if (x41 == x11 || x41 == x12 || x41 == x13 || x41 == x14 || x41 == x21 || x41 == x22 || x41 == x23 || x41 == x24 || 											x41 == x31 || x41 == x32 || x41 == x33 || x41 == x34) 											continue; 										if (x42 == x11 || x42 == x12 || x42 == x13 || x42 == x14 || x42 == x21 || x42 == x22 || x42 == x23 || x42 == x24 || 											x42 == x31 || x42 == x32 || x42 == x33 || x42 == x34 || x42 == x41) 											continue; 										if (x43 == x11 || x43 == x12 || x43 == x13 || x43 == x14 || x43 == x21 || x43 == x22 || x43 == x23 || x43 == x24 || 											x43 == x31 || x43 == x32 || x43 == x33 || x43 == x34 || x43 == x41 || x43 == x42) 											continue; 										if (x44 == x11 || x44 == x12 || x44 == x13 || x44 == x14 || x44 == x21 || x44 == x22 || x44 == x23 || x44 == x24 || 											x44 == x31 || x44 == x32 || x44 == x33 || x44 == x34 || x44 == x41 || x44 == x42 || x44 == x43) 											continue;  										int sh1 = x11 + x12 + x13 + x14, sh2 = x21 + x22 + x23 + x24, sh3 = x31 + x32 + x33 + x34, sh4 = x41 + x42 + x43 + x44; 										int sv1 = x11 + x21 + x31 + x41, sv2 = x12 + x22 + x32 + x42, sv3 = x13 + x23 + x33 + x43, sv4 = x14 + x24 + x34 + x44; 										int sd1 = x11 + x22 + x33 + x44, sd2 = x14 + x23 + x32 + x41; 										if (sh1 != S || sh2 != S || sh3 != S || sh4 != S || sv1 != S || sv2 != S || sv3 != S || sv4 != S || sd1 != S || sd2 != S) 											continue;  										printf("%d %d %d %d  %d %d %d %d  %d %d %d %d  %d %d %d %d\n", x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44); 										squares++; 									} 								} 							} 						} 					} 				} 			} 		} 	} 	 	printf("CNT: %d\n", squares);  	float diff_t = float(clock() - begin_time)/CLOCKS_PER_SEC; 	printf("T = %.2fs\n", diff_t);  	return 0; }

Результат: всего было найдено 7040 вариантов «магических квадратов» 4х4, а время поиска составило 102с.

Кстати интересно проверить, есть ли в списке квадратов тот самый, который изображен на гравюре Дюрера. Разумеется есть, т.к. программа выводит все квадраты размерности 4х4:

Нельзя не отметить, что Дюрер вставил квадрат в изображение не просто так, цифры 1514 также обозначают год создания гравюры.

Как можно видеть, программа работает (отмечаем задачу как verified at 1514 by Albrecht Dürer;), однако время выполнения не так и мало для компьютера с процессором Core i7. Очевидно, что программа выполняется в один поток, и целесообразно задействовать все остальные ядра.

С++ — многопоточный вариант

Переписать программу с использованием потоков в принципе несложно, хотя и немного громоздко. К счастью, есть почти забытый сегодня вариант — использование поддержки OpenMP (Open Multi-Processing). Эта технология существует аж с 1998г, и позволяет директивами процессора указать компилятору, какие части программы выполнять параллельно. Поддержка OpenMP есть и в Visual Studio, так что для превращения программы в многопоточную, достаточно добавить в код лишь одну строку:

int squares = 0; #pragma omp parallel for reduction(+: squares) for (int x11 = 1; x11 <= MAX; x11++) {   ... } printf("CNT: %d\n", squares); 

Директива #pragma omp parallel for указывает, что следующий цикл for можно выполнять параллельно, а дополнительный параметр squares задает имя переменной, которая будет общей для параллельных потоков (без этого инкремент работает некорректно).

Результат налицо: время выполнения сократилось со 102с до 18с.

#include <set> #include <stdio.h> #include <ctime> #include "stdafx.h"  typedef std::set<int> Set; typedef Set::iterator SetIterator;  #define N 4 #define MAX (N*N) #define S 34  int main(int argc, char *argv[]) { 	// x11 x12 x13 x14  	// x21 x22 x23 x24  	// x31 x32 x33 x34  	// x41 x42 x43 x44   	const clock_t begin_time = clock();  	int squares = 0; 	#pragma omp parallel for reduction(+: squares) 	for (int x11 = 1; x11 <= MAX; x11++) { 		int digits[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 }; 		Set mset(digits, digits + N*N); 		Set set12(mset); set12.erase(x11); 		for (SetIterator it12 = set12.begin(); it12 != set12.end(); it12++) { 			int x12 = *it12; 			Set set13(set12); set13.erase(x12); 			for (SetIterator it13 = set13.begin(); it13 != set13.end(); it13++) { 				int x13 = *it13; 				int x14 = S - x11 - x12 - x13; 				if (x14 < 1 || x14 > MAX) continue; 				if (x14 == x11 || x14 == x12 || x14 == x13) continue;  				Set set21(set13); set21.erase(x13); set21.erase(x14); 				for (SetIterator it21 = set21.begin(); it21 != set21.end(); it21++) { 					int x21 = *it21; 					Set set22(set21); set22.erase(x21); 					for (SetIterator it22 = set22.begin(); it22 != set22.end(); it22++) { 						int x22 = *it22; 						Set set23(set22); set23.erase(x22); 						for (SetIterator it23 = set23.begin(); it23 != set23.end(); it23++) { 							int x23 = *it23, x24 = S - x21 - x22 - x23; 							if (x24 < 1 || x24 > MAX) continue; 							if (x24 == x11 || x24 == x12 || x24 == x13 || x24 == x14 || x24 == x21 || x24 == x22 || x24 == x23) continue;  							Set set31(set23); 							set31.erase(x23); set31.erase(x24); 							for (SetIterator it31 = set31.begin(); it31 != set31.end(); it31++) { 								int x31 = *it31; 								Set set32(set31); set32.erase(x31); 								for (SetIterator it32 = set32.begin(); it32 != set32.end(); it32++) { 									int x32 = *it32; 									Set set33(set32); set33.erase(x32); 									for (SetIterator it33 = set33.begin(); it33 != set33.end(); it33++) { 										int x33 = *it33, x34 = S - x31 - x32 - x33; 										if (x34 < 1 || x34 > MAX) continue; 										if (x34 == x11 || x34 == x12 || x34 == x13 || x34 == x14 || x34 == x21 || x34 == x22 || x34 == x23 || x34 == x24 || x34 == x31 || x34 == x32 || x34 == x33) continue;  										int x41 = S - x11 - x21 - x31, x42 = S - x12 - x22 - x32, x43 = S - x13 - x23 - x33, x44 = S - x14 - x24 - x34; 										if (x41 < 1 || x41 > MAX || x42 < 1 || x42 > MAX || x43 < 1 || x43 > MAX || x44 < 1 || x41 > MAX) continue;  										if (x41 == x11 || x41 == x12 || x41 == x13 || x41 == x14 || x41 == x21 || x41 == x22 || x41 == x23 || x41 == x24 || 											x41 == x31 || x41 == x32 || x41 == x33 || x41 == x34) 											continue; 										if (x42 == x11 || x42 == x12 || x42 == x13 || x42 == x14 || x42 == x21 || x42 == x22 || x42 == x23 || x42 == x24 || 											x42 == x31 || x42 == x32 || x42 == x33 || x42 == x34 || x42 == x41) 											continue; 										if (x43 == x11 || x43 == x12 || x43 == x13 || x43 == x14 || x43 == x21 || x43 == x22 || x43 == x23 || x43 == x24 || 											x43 == x31 || x43 == x32 || x43 == x33 || x43 == x34 || x43 == x41 || x43 == x42) 											continue; 										if (x44 == x11 || x44 == x12 || x44 == x13 || x44 == x14 || x44 == x21 || x44 == x22 || x44 == x23 || x44 == x24 || 											x44 == x31 || x44 == x32 || x44 == x33 || x44 == x34 || x44 == x41 || x44 == x42 || x44 == x43) 											continue;  										int sh1 = x11 + x12 + x13 + x14, sh2 = x21 + x22 + x23 + x24, sh3 = x31 + x32 + x33 + x34, sh4 = x41 + x42 + x43 + x44; 										int sv1 = x11 + x21 + x31 + x41, sv2 = x12 + x22 + x32 + x42, sv3 = x13 + x23 + x33 + x43, sv4 = x14 + x24 + x34 + x44; 										int sd1 = x11 + x22 + x33 + x44, sd2 = x14 + x23 + x32 + x41; 										if (sh1 != S || sh2 != S || sh3 != S || sh4 != S || sv1 != S || sv2 != S || sv3 != S || sv4 != S || sd1 != S || sd2 != S) 											continue;  										printf("%d %d %d %d  %d %d %d %d  %d %d %d %d  %d %d %d %d\n", x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44); 										squares++; 									} 								} 							} 						} 					} 				} 			} 		} 	} 	 	printf("CNT: %d\n", squares);  	float diff_t = float(clock() - begin_time)/CLOCKS_PER_SEC; 	printf("T = %.2fs\n", diff_t);  	return 0; } 

Это гораздо лучше — т.к. задача практически идеально распараллеливается (расчеты в каждой ветви не зависят друг от друга), время меньше примерно в число раз, равное количеству ядер процессора. Но увы, принципиально большего из этого кода не получить, хотя какими-то оптимизациями может и можно выиграть несколько процентов. Переходим к более тяжелой артиллерии, расчетам на GPU.

Вычисления с помощью NVIDIA CUDA

Если не вдаваться в подробности, то процесс вычислений, выполняющийся на видеокарте, можно представить как несколько параллельных аппаратных блоков (blocks), каждый из которых выполняет несколько процессов (threads).

Для примера можно привести пример функции сложения 2х векторов из документации CUDA:

__global__ void add(int n, float *x, float *y) {   int index = threadIdx.x;   int stride = blockDim.x;   for (int i = index; i < n; i += stride)       y[i] = x[i] + y[i]; }

Массивы x и y — общие для всех блоков, а сама функция таким образом выполняется одновременно сразу на нескольких процессорах. Ключ тут в параллелизме — процессоры видеокарты гораздо проще чем обычный CPU, зато их много и они ориентированы именно на обработку числовых данных.

Это то, что нам нужно. Мы имеем матрицу чисел X11, X12,..,X44. Запустим процесс из 16 блоков, каждый из которых будет выполнять 16 процессов. Номеру блока будет соответствовать число X11, номеру процесса число X12, а сам код будет вычислять все возможные квадраты с для выбранных X11 и X12. Все просто, но здесь есть одна тонкость — данные нужно не только вычислить, но и передать с видеокарты обратно, для этого в нулевом элементе массива будем хранить число найденных квадратов.

Основной код получается весьма простым:

#define N 4 #define SQ_MAX 8*1024 #define BLOCK_SIZE (SQ_MAX*N*N + 1)  int main(int argc,char *argv[]) {     const clock_t begin_time = clock();        int *results = (int*)malloc(BLOCK_SIZE*sizeof(int));     results[0] = 0;      int *gpu_out = NULL;     cudaMalloc(&gpu_out, BLOCK_SIZE*sizeof(int));     cudaMemcpy(gpu_out, results, BLOCK_SIZE*sizeof(int), cudaMemcpyHostToDevice);     squares<<<MAX, MAX>>>(gpu_out);     cudaMemcpy(results, gpu_out, BLOCK_SIZE*sizeof(int), cudaMemcpyDeviceToHost);      // Print results     int squares = results[0];     for(int p=0; p<SQ_MAX && p<squares; p++) {         int i = MAX*p + 1;         printf("[%d %d %d %d  %d %d %d %d  %d %d %d %d  %d %d %d %d]\n",                  results[i], results[i+1], results[i+2], results[i+3],                  results[i+4], results[i+5], results[i+6], results[i+7],                 results[i+8], results[i+9], results[i+10], results[i+11],                 results[i+12], results[i+13], results[i+14], results[i+15]);     }     printf ("CNT: %d\n", squares);        float diff_t = float(clock() - begin_time)/CLOCKS_PER_SEC;     printf("T = %.2fs\n", diff_t);        cudaFree(gpu_out);     free(results);        return 0; }

Мы выделяем блок памяти на видеокарте с помощью cudaMalloc, запускаем функцию squares, указав ей 2 параметра 16,16 (число блоков и число потоков), соответствующие перебираемым числам 1..16, ждем выполнения с помощью функции cudaDeviceSynchronize, затем копируем данные обратно через cudaMemcpy.

Сама функция squares по сути повторяет код из предыдущей части, с той разницей, что приращение количества найденных квадратов делается с помощью atomicAdd — это гарантирует что переменная будет корректно изменяться при одновременных обращениях.

// Compile: // nvcc -o magic4_gpu.exe magic4_gpu.cu  #include <stdio.h> #include <ctime>  #define N 4 #define MAX (N*N) #define SQ_MAX 8*1024 #define BLOCK_SIZE (SQ_MAX*N*N + 1) #define S 34  // Magic square: // x11 x12 x13 x14  // x21 x22 x23 x24  // x31 x32 x33 x34  // x41 x42 x43 x44    __global__ void squares(int *res_array) { 	int index1 = blockIdx.x, index2 = threadIdx.x; 	if (index1 + 1 > MAX || index2 + 1 > MAX) return;  	const int x11 = index1+1, x12 = index2+1; 	for(int x13=1; x13<=MAX; x13++) {  		if (x13 == x11 || x13 == x12) 			continue; 		int x14 = S - x11 - x12 - x13; 		if (x14 < 1 || x14 > MAX) continue; 		if (x14 == x11 || x14 == x12 || x14 == x13) 			continue; 		for(int x21=1; x21<=MAX; x21++) {  			if (x21 == x11 || x21 == x12 || x21 == x13 || x21 == x14) 				continue; 			for(int x22=1; x22<=MAX; x22++) { 				if (x22 == x11 || x22 == x12 || x22 == x13 || x22 == x14 || x22 == x21) 					continue; 				for(int x23=1; x23<=MAX; x23++) { 					int x24 = S - x21 - x22 - x23; 					if (x24 < 1 || x24 > MAX) continue; 					if (x23 == x11 || x23 == x12 || x23 == x13 || x23 == x14 || x23 == x21 || x23 == x22) 						continue; 					if (x24 == x11 || x24 == x12 || x24 == x13 || x24 == x14 || x24 == x21 || x24 == x22 || x24 == x23) 						continue; 					for(int x31=1; x31<=MAX; x31++) {  						if (x31 == x11 || x31 == x12 || x31 == x13 || x31 == x14 ||  x31 == x21 || x31 == x22 || x31 == x23 || x31 == x24) 							continue; 						for(int x32=1; x32<=MAX; x32++) { 							if (x32 == x11 || x32 == x12 || x32 == x13 || x32 == x14 || x32 == x21 || x32 == x22 || x32 == x23 || x32 == x24 || x32 == x31) 								continue; 							for(int x33=1; x33<=MAX; x33++) { 								int x34 = S - x31 - x32 - x33; 								if (x34 < 1 || x34 > MAX) continue; 								if (x33 == x11 || x33 == x12 || x33 == x13 || x33 == x14 || x33 == x21 || x33 == x22 || x33 == x23 || x33 == x24 || x33 == x31 || x33 == x32) 									continue; 								if (x34 == x11 || x34 == x12 || x34 == x13 || x34 == x14 || x34 == x21 || x34 == x22 || x34 == x23 || x34 == x24 || x34 == x31 || x34 == x32 || x34 == x33) 									continue;  								const int x41 = S - x11 - x21 - x31, x42 = S - x12 - x22 - x32, x43 = S - x13 - x23 - x33, x44 = S - x14 - x24 - x34; 								if (x41 < 1 || x41 > MAX || x42 < 1 || x42 > MAX || x43 < 1 || x43 > MAX || x44 < 1 || x44 > MAX)  									continue; 								if (x41 == x11 || x41 == x12 || x41 == x13 || x41 == x14 || x41 == x21 || x41 == x22 || x41 == x23 || x41 == x24 || 									x41 == x31 || x41 == x32 || x41 == x33 || x41 == x34) 									continue; 								if (x42 == x11 || x42 == x12 || x42 == x13 || x42 == x14 || x42 == x21 || x42 == x22 || x42 == x23 || x42 == x24 || 									x42 == x31 || x42 == x32 || x42 == x33 || x42 == x34 || x42 == x41) 									continue; 								if (x43 == x11 || x43 == x12 || x43 == x13 || x43 == x14 || x43 == x21 || x43 == x22 || x43 == x23 || x43 == x24 ||  									x43 == x31 || x43 == x32 || x43 == x33 || x43 == x34 || x43 == x41 || x43 == x42) 									continue; 								if (x44 == x11 || x44 == x12 || x44 == x13 || x44 == x14 || x44 == x21 || x44 == x22 || x44 == x23 || x44 == x24 ||  									x44 == x31 || x44 == x32 || x44 == x33 || x44 == x34 || x44 == x41 || x44 == x42 || x44 == x43) 									continue;    								int sh1 = x11 + x12 + x13 + x14, sh2 = x21 + x22 + x23 + x24, sh3 = x31 + x32 + x33 + x34, sh4 = x41 + x42 + x43 + x44; 								int sv1 = x11 + x21 + x31 + x41, sv2 = x12 + x22 + x32 + x42, sv3 = x13 + x23 + x33 + x43, sv4 = x14 + x24 + x34 + x44; 								int sd1 = x11 + x22 + x33 + x44, sd2 = x14 + x23 + x32 + x41; 								if (sh1 != S || sh2 != S || sh3 != S || sh4 != S || sv1 != S || sv2 != S || sv3 != S || sv4 != S || sd1 != S || sd2 != S) 									continue;  								// Square found: save in array (MAX numbers for each square) 								int p = atomicAdd(res_array, 1); 								if (p >= SQ_MAX) continue;  								int i = MAX*p + 1; 								res_array[i]   = x11; res_array[i+1] = x12; res_array[i+2]  = x13; res_array[i+3]  = x14;  								res_array[i+4] = x21; res_array[i+5] = x22; res_array[i+6]  = x23; res_array[i+7]  = x24;  								res_array[i+8] = x31; res_array[i+9] = x32; res_array[i+10] = x33; res_array[i+11] = x34;  								res_array[i+12]= x41; res_array[i+13]= x42; res_array[i+14] = x43; res_array[i+15] = x44;   								// Warning: printf from kernel makes calculation 2-3x slower 								// printf("%d %d %d %d  %d %d %d %d  %d %d %d %d  %d %d %d %d\n", x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34, x41, x42, x43, x44); 							} 						} 					} 				} 			} 		} 	} }  int main(int argc,char *argv[]) { 	int *gpu_out = NULL;     cudaMalloc(&gpu_out, BLOCK_SIZE*sizeof(int));  	const clock_t begin_time = clock();  	int *results = (int*)malloc(BLOCK_SIZE*sizeof(int)); 	results[0] = 0; 	cudaMemcpy(gpu_out, results, BLOCK_SIZE*sizeof(int), cudaMemcpyHostToDevice);        squares<<<MAX, MAX>>>(gpu_out);      cudaMemcpy(results, gpu_out, BLOCK_SIZE*sizeof(int), cudaMemcpyDeviceToHost);  	// Print results 	int squares = results[0]; 	for(int p=0; p<SQ_MAX && p<squares; p++) { 		int i = MAX*p + 1; 		printf("[%d %d %d %d  %d %d %d %d  %d %d %d %d  %d %d %d %d]\n", results[i], results[i+1], results[i+2], results[i+3], 																		 results[i+4], results[i+5], results[i+6], results[i+7], 																		 results[i+8], results[i+9], results[i+10], results[i+11], 																		 results[i+12], results[i+13], results[i+14], results[i+15]); 	} 	printf ("CNT: %d\n", squares);    	float diff_t = float(clock() - begin_time)/CLOCKS_PER_SEC; 	printf("T = %.2fs\n", diff_t);    	cudaFree(gpu_out); 	free(results);    	return 0; } 

Результат не требует комментариев — время выполнения составило 2.7с, что примерно в 30 раз лучше изначального однопоточного варианта:

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

Заключение

Задача нахождения «магических квадратов» оказалась технически весьма интересной, и в то же время непростой. Даже с вычислениями на GPU поиск всех квадратов 5х5 может занять несколько часов, а оптимизацию для поиска магических квадратов размерности 7х7 и выше, еще предстоит сделать.

Математически и алгоритмически, тоже есть несколько нерешенных моментов:
— Зависимость количества «магических квадратов» от N. Известно что квадрата 2х2 не существует, квадрат 3х3 существует всего 8, квадратов 4х4 как мы выяснили, 7040, но исключение поворотов или отражений в алгоритм пока не добавлено. Для больших размерностей вопрос пока открыт.
— Исключение квадратов, являющимися поворотами или отражениями уже найденного.
— Скорость и оптимизация алгоритма. К сожалению, потестировать код на суперкомпьютере или хотя бы на NVIDIA Tesla возможности нет, если кто-то может запустить, было бы интересно. Если у кого есть идеи по самому алгоритму, их тоже можно попробовать реализовать. При желании можно даже запустить распределенный проект по поиску квадратов, если конечно наберется достаточно число читаталей 😉

Об анализе и свойствах самих магических квадратов можно написать отдельную статью, если будет интерес.

PS: К вопросу, который наверняка последует, «а зачем это надо». С точки зрения расхода электроэнергии вычисление магических квадратов ничем не лучше или хуже вычисления биткоинов, так что почему бы и нет? К тому же, это интересная разминка для ума и интересная задача в области прикладного программирования.

Вдохновившись картинками и видео решил опробовать свои силы. Разработка корпуса, электроники и программы будет вестись с 0.

Итак, часть 1 — разработка 3D модели корпуса

Исходные материалы и комплектующие для будущего робота:

0. Arduno Due (писать будем в Atmel Studio на чистом C без Arduino IDE, заодно расскажу как подключить отладчик к этой плате) — 1шт;

1. HLK-RM04 (UART to WIFI converter) — прозрачный мост с UART в WIFI — 2шт;

2. Сервоприводы MG996R (из китая, как же без него) — 18шт;

3. LM317D2T-TR для питания сервоприводов + мелкая рассыпуха в виде резисторов и конденсаторов;

4. САПР «КОМПАС 3D»;

5. Фанера 3мм в качестве материала для корпуса (дёшево и пахнет вкусно);

6. Возможность заказать лазерную резку;

7. Время. Много времени.

В самом начале пути встал вопрос «А какой же корпус я хочу?». В процессе поиска ответа на данный вопрос набрел на несколько готовых решений. Больше всего понравились PhantomX и A-Pod. Посмотрев на корпуса, решил уже было начать разработку, но нет. Появилась следующая проблема: так как этих роботов в глаза я не видел и в руках не держал, то я имел плохое представление об их габаритах. В поиске решения этой проблемы я наткнулся на одну из статей на хабре. Автор статьи tomnewmann любезно поделился со мной чертежами своего проекта, за что ему большое спасибо.

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

Coxa

Спустя несколько часов размышлений появилась первая модель «Coxa» (так принято обозначать узел, соединяющий ногу с корпусом). Узел попытался сделать максимально компактным. Сервопривод будет полностью находится внутри, соответственно нужно не забыть (что я первый раз и сделал) про отверстие для вывода проводов.

Деталь 1 — Ось, на которую будет крепиться Femur (вторая часть ноги). Собрана из винта М3×15, шайбы и гайки М3
Деталь 2 — Винт М3×20
Деталь 3 — Стойка для печатных плат M3x20
Деталь 4 — Являются своего рода фиксаторами сервопривода, для предотвращения его перемещения по вертикали.

Высоту (А) данного узла необходимо делать такой, чтобы в внутрь смог уместиться сервопривод, который будет стоять на раме.

Femur

Далее нужно сделать «Femur». Деталь оказалась самой простой из всех и думаю не нуждается в комментариях.

Деталь 1 — Винт М3×20
Деталь 2 — Пластиковая втулка 3×10 (длинную стойку я не нашел, пришлось искать другие пути решения)
Деталь 3 — Стойка для печатных плат M3x30

Tibia

Следующая деталь — «Tibia», последняя часть ноги. С ней проблем быть не должно и её длина зависит от высоты, на которую планируется понимать робота. У меня она составляет 130мм от оси сервопривода, больше делать не стал, так как с увеличением длины увеличивается и нагрузка на сервоприводы, особенно на сервопривод в «Coxa». На второй стороне сделал на второе отверстие под ось, чтобы можно было перевернуть сервопривод и уменьшить длину рычага, если вдруг сервоприводам будет тяжело.

Рама

Далее на очереди идет рама — самая большая часть. Именно она определяет конфигурацию ног будущего робота. Существует несколько вариантов расположения ног, но я остановился на варианте буквой Ж (при взгляде сверху похож).

На первых этапах проектирования возник вопрос: «А на каком расстоянии должны находится ноги друг от друга?». В поисках ответа на этой вопрос я понял, что каких-либо рекомендаций по этому поводу нет. Изучая чужие проекты и варианты походок сделал вывод о том, что расстояние подбирается исходя из желаемого максимального угла поворота конечности. Чем больше расстояние между ногами тем больший угол могут достичь конечности во время ходьбы.

В решении данного вопроса помогли чертежи tomnewmann, из которых я и взял расстояние между ног, так как габариты роботов были довольно похожи (мой немного меньше). Спустя несколько часов родились верхняя и нижняя части рамы:

В нижней части рамы сделан вырез под АКБ и его крепления. Кстати крепиться он будет на липучку, которые используются на квадриках при креплении АКБ к ним. Рама получилось довольно большой. Посидев еще 1 вечер и сделав промежуточные детали в виде опор между частями, я решил, что пора сделать сборку рамы с установленными сервоприводами. Результат не заставил себя долго ждать:

Так как все необходимые компоненты у нас уже есть, то можно сделать полную сборку корпуса:

В центре корпуса между пластинами планировался располагаться блок питания для сервоприводов, снизу 3S Li-po аккумулятор, а сверху плата управления (Arduino Due). В соответствии с этим я изменил сборку рамы:

Плата сверху это модель Arduino Mega c каким-то шилдом. Используется просто для вида и имеет аналогичные размеры, как и Due.

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

Решением первой задачей являлись крышки сверху и снизу, закрывающие АКБ и управляющую электронику. Это единственные детали, которые будут собраны при помощи клея. Спустя вечер родилась модель нижней крышки.

Если с первой задачей проблем не было, то со второй задачей возникли трудности на 2 дня. Да, именно столько времени у меня заняло, чтобы просто придумать ему имя. Случайно вспомнив фильм «Терминатор» решил назвать его «Skynet» и вырезать имя на верхней крышке. Так же добавил вырезы для HC-SR04.

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

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

P.S.

1. Чертежи не скрываю и готов поделиться ими с любым желающим.
2. Буду рад любой критике и готов ответить на любые вопросы в рамках данного материала.

Честно говоря, мне самому слегка конфузно в очередной раз говорить об Атомарном дизайне. Про концепции дизайн-систем сказано практически все и, казалось бы, добавить уже нечего. Но постойте! Ведь атомы в реальном мире из чего-то состоят: протоны, нейтроны, электроны… Можно ли сопоставить со структурой атома дизайн-функционал, в котором мы работаем? Я уверен, что ответ положительный и вот почему…

Глобальные стили

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

Если рассмотреть, например, кнопку как молекулу, состоящую из двух атомов: фона и надписи, то на фон можно влиять следующим образом:

1. Добавить цвет (Fill). Любой фон можно закрасить или заполнить текстурой.
2. Добавить обводку (Stroke). Затем регулировать ее толщину, сделать пунктирной, изменить цвет.
3. Скруглить углы (Corner radius). Кнопки с максимально скругленными углами, кажется, снова станут популярными в обозримом будущем.
4. Добавить тень (Shadow). В основном наружную, но иногда и внутреннюю. Современные инструменты позволяют наслаивать несколько теней.

Я не включил сюда поворот объекта и изменение размеров, т.к. это больше про изменения в пространстве

Элементарные частицы дизайн-атома

Посмотрите на схему состава атома, прежде чем я продолжу:

Теперь самое интересное. Кто-нибудь уже догадался, какие свойства дизайн-объекта можно сопоставить с частицами атома?

Нейтроны — это заливка. На визуализации структуры атома нейтроны в самом центре. Метафора подходит безукоризненно.

Протоны — скругление углов. Их расположенные по углам атома сразу ассоциируется с этим свойством в дизайне.

Нуклоны очень хочется сопоставить с обводкой. Увы, нуклон не является частицей, а лишь является названием объединяющим протоны и нейтроны, но это и неважно! Итак нуколы — это тень. Потому как обводка собирает воедино то, что находится внутри неё. Это полностью совпадает с картинкой выше.

Электрон — это тень. Википедия показывает мне эту картинку, напоминающую тень. Идеальное совпадение по всем параметрам.

Назад к дизайн-системам

Это лишь дополнение к общей теории Атомарного дизайна при проектировании дизайн систем. Концепция глобальных стилей однозначно вызывает привыкание к Figma (кажется Sketch недавно пошёл аналогичным путем). И благодаря такой подаче, мы — дизайнеры и разработчики получили еще больше гибкости для кастомизации если эффективно планируем архитектуру будущей системы:

ПС: Дизайн требует практики, а не теории. Но иногда стоит отвлечься от практики ненадолго, чтобы структурировать накопленный опыт в новые теории.

О чем это все?

Я расскажу о том, как построить модель акторов с помощью MailboxProcessor из стандартной библиотеки, на какие моменты обратить внимание и о том, какие подводные камни вас могут ожидать.

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

Если вы про мейлбоксы все знаете и без меня — вам тут может быть скучно.

Почему акторы?

Ради практики. Про модель акторов я читал, смотрел видео, мне все понравилось, но сам не пробовал. Теперь попробовал.

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

Почему MailboxProcessor, а не, например, Akka.net?

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

О мейлбокс процессорах и сопутсвующем бойлерплейте

Суть проста. Мейлбокс внутри имеет message loop и некое состояние. Ваш message loop будет это состояние обновлять в соответствии с новым пришедшим сообщением.

let actor = MailboxProcessor.Start(fun inbox ->           // the message processing function         let rec messageLoop oldState = async{              // read a message             let! msg = inbox.Receive()              // do the core logic             let newState = updateState oldState msg              // loop to top             return! messageLoop newState              }          // start the loop         messageLoop (0,0)         )

Обратите внимание, messageLoop рекурсивен, и в конце он должен быть вызван снова, иначе будет обработано только одно сообщение, после чего этот актор "умрет". Также messageLoop асинхронен, и каждая следующая итерация выполняется при получении нового сообщения: let! msg = inbox.Receive().

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

let buildActor applyMessage zeroState =         MailboxProcessor.Start(fun inbox ->         let rec loop state = async{             let! msg = inbox.Receive()             let newState = applyMessage state msg             return! loop newState         }         loop zeroState         ) 

Круто! Теперь нам не нужно постоянно следить за тем, чтоб не забыть return! loop newState. Как известно, актор хранит состояние, однако сейчас совершенно не очевидно, как это состояние получить извне. У мейлбокс процессора есть метод PostAndReply, который принимает на вход функцию AsyncReplyChannel<'Reply> -> 'Msg. Сначала меня это ввело в ступор — совершенно непонятно, откуда эту функцию взять. Но на деле все оказалось проще: все сообщения надо завернуть в DU-обертку, поскольку у нас теперь получается 2 операции над нашим актором: послать само сообщение и попросить текущее состояние. Вот как это выглядит:

type Mail<'msg, 'state> =     | Post of 'msg     | Get of AsyncReplyChannel<'state>

Наша функция-конструктор теперь выглядит вот так:

let buildActor applyMessage zeroState =         MailboxProcessor.Start(fun inbox ->         let rec loop state = async{             let! msg = inbox.Receive()             match msg with             | Post msg ->                 let newState = applyMessage state msg                 return! loop newState             | Get channel ->                 channel.Reply state                 return! loop state         }         loop zeroState         ) 

Теперь для работы с мейлбоксом нам нужно все наши сообщения заворачивать в этот Mail.Post. Чтобы не писать это каждый раз, лучше это завернуть в небольшую апишку:

module Mailbox =      let buildAgent applyMessage zeroState =         MailboxProcessor.Start(fun inbox ->         let rec loop state = async{             let! msg = inbox.Receive()             match msg with             | Post msg ->                 let newState = applyMessage state msg                 return! loop newState             | Get channel ->                 channel.Reply state                 return! loop state         }         loop zeroState         )      let post (agent: MailboxProcessor<_>) msg = Post msg |> agent.Post      let getState (agent: MailboxProcessor<_>) = agent.PostAndReply Get      let getStateAsync (agent: MailboxProcessor<_>) = agent.PostAndAsyncReply Get  type MailAgent<'msg, 'state> = MailAgent of address:string * mailbox:MailboxProcessor<Mail<'msg, 'state>>     with member this.Post msg =             let (MailAgent (address,this)) = this             Mailbox.post this msg          member this.GetState() =             let (MailAgent (address,this)) = this             Mailbox.getState this          member this.GetStateAsync() =             let (MailAgent (address,this)) = this             Mailbox.getStateAsync this          member this.Address =             let (MailAgent (address, _)) = this             address          member this.Dispose() =             let (MailAgent (_, this)) = this             (this:>IDisposable).Dispose()          interface IDisposable with           member this.Dispose() = this.Dispose()

О том, что это за address:string я расскажу чуть позже, а пока наш бойлерплейт готов.

Собственно, змейка

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

Вот все вот это вместе и нужно размазать по нашим акторам.

Изначальная раскладка у меня была такая:

• Актор с таймером. Принимает сообщения старт/стоп/пауза. Раз в n милисекунд отправляет сообщение Flush актору комманд. В качестве состояния хранит System.Timers.Timer
• Актор комманд. Принимает сообщения от юзера Move Up/Down/Left/Right, AddPerk Speed/Attack (да, моя змейка умеет быстро ползать и атаковать негодяев) и Flush от таймера. В качестве состояния хранит список команд, а при флаше этот список обнуляет.
• Актор змейки. Хранит состояние змейки — перки, длину, направление, изгибы и координаты.
  Принимает список сообщений от актора комманд, сообщение Tick (чтобы сдвинуть змейку на 1 ячейку вперед), и сообщение GrowUp от актора поля, когда она находит еду.
• Актор поля. Хранит карту ячеек, принимает состояние змейки в сообщении и натягивает координаты на существующую картину. А также отправляет GrowUp актору змейки и команду Stop таймеру, если игра окончена.

Как видите, даже при таком небольшом количестве сущностей карта сообщений уже получается нетривиальная. И уже на этом этапе возникли трудности: дело в том, что по умолчанию F# не позволяет циклические зависимости. В текущей строке кода вы можете использовать только код, написанный выше, и то же самое применимо к файлам в проекте. Это не баг, а фича, и я ее очень люблю, поскольку она помогает держать код в чистоте, но что делать, когда циклические ссылки нужны по дизайну? Конечно же, можно использовать rec namespace — и тогда внутри одного файла можно будет ссылаться на все подряд, что есть в этом файле, чем я и воспользовался.
Код ожидаемо испортился, но тогда это казалось единственным вариантом. И все заработало.

Проблема внешнего мира

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

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

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

type Agent<'message,'state> =     | Box of MailAgent<'message,'state>     | DeadBox of string * MailAgent<string * obj, Map<string,obj list>>     with member this.Post msg =             match this with             | Box box -> box.Post msg             | DeadBox (address, deadbox) -> (address, box msg) |> deadbox.Post          interface IDisposable with             member this.Dispose() =                 match this with                 | Box agent -> agent.Dispose()                 | DeadBox (_,agent) -> agent.Dispose()

А сама система выглядит так:

type MailboxNetwork() as this =      [<DefaultValue>]     val mutable agentRegister: ConcurrentDictionary<string, obj>     do this.agentRegister <- ConcurrentDictionary<string, obj>()      let deadLettersFn deadLetters (address:string, msg:obj) =         printfn "Deadletter: %s-%A" address msg         match Map.tryFind address deadLetters with         | None -> Map.add address [msg] deadLetters         | Some letters ->              Map.remove address deadLetters             |> Map.add address (msg::letters)      let deadLettersAgent() = ("deadLetters", Map.empty |> Mailbox.buildAgent deadLettersFn) |> MailAgent      member this.DeadLetters = deadLettersAgent()     member this.Box<'message,'state>(address) =         match this.agentRegister.TryGetValue address with         | (true, agent) when (agent :? MailAgent<'message,'state>) ->             let agent = agent :?> MailAgent<'message, 'state>             Box agent         | _ -> DeadBox (address, this.DeadLetters)      member this.KillBox address =         this.agentRegister.TryRemove(address) |> ignore      member this.RespawnBox (agent: MailAgent<'a,'b>) =         this.KillBox agent.Address         this.agentRegister.TryAdd (agent.Address, agent) |> ignore      interface IDisposable with         member this.Dispose() =                 for agent in this.agentRegister.Values do                     match agent with                     | :? IDisposable as agent -> agent.Dispose()                     | _ -> ()

Вот тут нам и пригодился тот самый address:string, о котором я писал выше. И снова все заработало, внешнюю зависимость теперь было легко прокинуть куда надо. Функции-конструкторы акторов теперь принимали аргументом систему акторов и доставали оттуда необходимых адресатов:

   let gameAgent (mailboxNetwork: MailboxNetwork) = mailboxNetwork.Box<Command list, GameState>(gameAddress)      let commandAgentFn (mailboxNetwork: MailboxNetwork) commands msg =         let gameAgent = gameAgent mailboxNetwork         match msg with         | Cmd cmd -> cmd::commands         | Flush ->             commands |> gameAgent.Post             [] 

Медленно

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

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

1. Пользователь отправляет произвольное количество команд напрямую в актор команд.
2. Таймер отправляет тик актору команд и в ранней реализации еще и актору змеи, чтобы тот передвинул змейку на следующую клетку
3. Актор команд отправляет список команд для змеи, когда соответствующее сообщение приходит от таймера.
4. Актор змеи, обновив свое состояние согласно 2 верхним сообщениям, отправляет состояние актору поля.
5. Актор поля все перерисовывает. Если змея нашла еду, то он отправляет актору змеи сообщение GrowUp, после чего тот отправляет новое состояние обратно актору поля.

И на все это есть 1 такт, которого не хватает, с учетом синхронизации в недрах MailboxProcessor. Более того, в текущей реализации таймер посылает следующее сообщение каждые n милисекунд независимо ни от чего, так что если мы 1 раз не влезли в такт, сообщения начинают скапливаться, и ситуация усугубляется. Гораздо лучше было бы "растянуть" этот конкретный такт, обработать все, что накопилось, и пойти дальше.

Финальная версия

Очевидно, что схему сообщений надо упрощать, при этом очень желательно оставить код максимально простым и доступным — условно говоря, не хочется все пихать в 1 god actor, да и смысла в акторах тогда не очень много получается.

Поэтому взглянув на свой список акторов я понял, что первым лучше всего пожертвовать актором-змеей. Таймер нужен, буфер команд пользователя тоже нужен, чтобы в реальном времени их накапливать, но выливать только раз в такт, а змею держать в отдельном акторе объективной необходимости нет, это было сделано просто для удобства. К тому же, смержив его с актором поля можно будет без задержки обработать GrowUp сценарий. Tick сообщение для змеи тоже большого смысла не имеет, поскольку когда мы получаем сообщение от актора команд, это уже означает, что новый такт случился. Добавив к этому растягивание такта в случае задержки, имеем следующие изменения:

1. Убираем Tick & GrowUp сообщения.
2. Мержим актор змеи в актор поля — он теперь будет хранить "тапл" этих состояний.
3. Убираем System.Timers.Timer из актора таймера. Вместо этого схема работы будет следующая: получив команду Start, он отправляет Flush актору команд. Тот отправляет список команд актору поля+змейки, последний актор все это обрабатывает и отправляет таймеру сообщение Next, тем самыс запрашивая у него новый тик. Таймер же, получив Next ждет Thread.Sleep(delay) и начинает весь круг сначала. Все просто.

Подведем итог.

• В предыдущей реализации 500 мс были минимально допустимым дилеем. В текущей дилей можно вообще убрать — актор поля затребует новый такт, когда будет готов. Скапливание необработанных сообщений с предыдущих тактов теперь невозможно.
• Карта обмена сообщениями сильно упрощена — вместо сложного графа имеем самый простой цикл.
• Это упрощение решило тот баг, когда таймер несколько раз получал Stop в случае проигрыша.
• Список сообщений уменьшился. Меньше кода — меньше зла!

Выглядит это так:

    let [<Literal>] commandAddress = "command"     let [<Literal>] timerAddress = "timer"     let [<Literal>] gameAddress = "game"      let commandAgent (mailboxNetwork: MailboxNetwork) = mailboxNetwork.Box<CommandMessage, Command list>(commandAddress)     let timerAgent (mailboxNetwork: MailboxNetwork) = mailboxNetwork.Box<TimerCommand, TimerState>(timerAddress)     let gameAgent (mailboxNetwork: MailboxNetwork) = mailboxNetwork.Box<Command list, GameState>(gameAddress)      let gameAgentFn (mailboxNetwork: MailboxNetwork) updateUi gameState cmd =         let timerAgent = timerAgent mailboxNetwork         match gameState.gameFrame with         | Frame field ->             let gameState = Game.updateGameState gameState cmd             timerAgent.Post Next             updateUi gameState             gameState         | End (Win _) ->             timerAgent.Post PauseOrResume             Game.updateGameState gameState cmd         | _ ->              timerAgent.Post Stop             gameState      let commandAgentFn (mailboxNetwork: MailboxNetwork) commands msg =         let gameAgent = gameAgent mailboxNetwork         match msg with         | Cmd cmd -> cmd::commands         | Flush ->             commands |> gameAgent.Post             []      let timerAgentFn (mailboxNetwork: MailboxNetwork) (state: TimerState) cmd =         let commandAgent = commandAgent mailboxNetwork         match cmd with         | Start -> commandAgent.Post Flush; {state with active = true}         | Next ->              if state.active then                 Threading.Thread.Sleep(state.delay)                 commandAgent.Post Flush;              state         | Stop -> printfn "Stop received"; { state with active = false }         | PauseOrResume ->              if not state.active then                 commandAgent.Post Flush             { state with active = not state.active }         | SetDelay delay ->              Threading.Thread.Sleep(delay)             if state.active then                 commandAgent.Post Flush             {state with delay = delay}

Ссылки

• Введение в мейлбоксы
• Исходники мейлбокса для самых любознательных

Вы наверняка использовали Storyboard или XIB для верстки интерфейсов? Верстать из кода это прекрасно, но иногда намного проще понять как устроен какой-то из компонентов интерфейса, увидев его, а не прочитав. В этой записи я хочу обсудить необходимость использования для IBOutlet модификатора private.

Так вот представим, что вы привычно собираетесь создать IBOutlet (ссылку на View с StoryBoard) для какого-нибудь из ваших UILabel.

При перетаскивании мышкой Xcode заботливо создаст нам что-то вроде

@IBOutlet weak var myLabel: UILabel!

Я долгое время считал эту конструкцию оптимальной, до того момента как мой коллега не спросил — а почему твои IBOutlet не private?

В самом деле, зачем мне оставлять все IBOutlet-ы доступными извне?
Представим себе классическую задачу — у нас есть ячейка, в которой отображается, к примеру, чей-то контакт

import UIKit  class ContactCell: UITableViewCell {      @IBOutlet private weak var nameLabel: UILabel!     @IBOutlet private weak var positionLabel: UILabel!      override func awakeFromNib() {         super.awakeFromNib()     }      func setupCell(withContact contact: Contact) {         nameLabel.text = contact.name         positionLabel.text = contact.position     }  }

С помощью добавления private к привычным нам IBOutlet можно гарантировать, что указанные поля ячейки не будет заданы из другого класса. Особенно это может быть полезно при командной работе, когда кто-то по неосторожности / нехватке времени / глупости (нужное подчеркнуть) попробует задать цвета, текст или какие-то другие свойства у Label-ов ячейки прямо в методе tableView(_:cellForRowAt:).

А представьте, что ячейка или целый ViewController содержит множество IBOutlet-ов, что настроек отображения масса. Не проще ли обезопасить себя добавлением private, чем потом искать почему внешний вид элемента вдруг изменился или откуда-то появился Gesture Recognizer, который задает неожиданное поведение?

p.s.
Если после прочтения вам захочется использовать private для IBOutlet-ов, то для простоты можно завести для этого снипет в Xcode