Перебор вариантов

объясни, пожалуйста, что эти каракули обозначают.

большое количество вариантов
выполнение занимает слишком много времени

а с чем ты сравниваешь? может быть затрачиваемое время адекватно. лучше бы ты привёл цифры и конкретизировал задачу вместо этого куска говнокода.

объясни, пожалуйста, что эти каракули обозначают.

Что, кроме того, что написано в ОП, тебе непонятно? parfor? Параллельный for.

а с чем ты сравниваешь?

Непозволительно много для меня времени. Я задал вопрос про оптимизацию.

лучше бы ты привёл цифры и конкретизировал задачу вместо этого куска говнокода.

Стандартный ответ человека, который не читает дальше первой строки. Из кода достаточно ясно, что я хочу сгенерировать все такие матрицы box со всеми возможными комбинациями 0-1 на нечётных местах. box_size=10, например.

Что я потом делаю с этой box значения не имеет.

Ты же понимаешь, что ты перебираешь все последовательности.

Да.

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

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

Дальше у меня идут простые арифметические операции, их количество порядка box_size^2.

А вот для больших i у меня возникают сомнения в эффективности использования de2bi.

box_size=10
2^(box_size^2/2)-1

1125899906842623

а, ну ок, успехов

А, нет, de2bi отрабатывает быстро. На цикл уходит «Elapsed time is 0.000055 seconds», из которых 0.000014 - de2bi, что уже для box_size=10, даже в 4 потока, займет 500 лет.

В любом случае, спасибо за советы, буду придумывать другие методы.

http://mathworld.wolfram.com/Self-AvoidingWalkConnectiveConstant.html

Надо почитать, как они «have enumerated walks of up to length 51», что простым перебором, как у меня, будет ~3^51 вариантов.

500 лет

теоретически, если оптимизировать, то на современном 8-ядерном пк можно перебрать все варианты для box_size=10 меньше чем за двое суток (1.3 по моим подсчётам). но это только перебрать.

Это-то отлично, но я хотел это потом расширить для 3х измерений, т.е. 10х10х10. Или хотя бы 8х8х8.

Но ты всё равно расскажи, как? Интересно же.

с распараллеливанием и использованием инструкций avx, лучше писать на си или асме, чтобы было минимум оверхеда. я делал на асме простую программу, складывающую числа от 1 до миллиарда. на моём процессоре она выполнялась за 75 миллисекунд.

Ты предыдущие итерации в памяти хранишь?

Так ты привёл пример совсем простой задачи.

Кста, https://habrahabr.ru/post/330690/

Надо почитать, как они «have enumerated walks of up to length 51»

почитай кнута, «искусство программирования», том 4 «комбинаторные алгоримы»

Я ничего из написанного тут не понимаю, но надо использовать мемоизацию

Я почитал их новую статью 2016 года. Скорее всего, кнут имеет к этому отношение весьма посредственное.

Но почитать стоит, да.

написал на С, с флагом -О3 занимает порядка 20.

скорее всего компилятор сокращает цикл до одной инструкции. код покажешь?

Так тут и показывать-то нечего:

#include <stdio.h>
#include <stdint.h>
int main()
{
	unsigned long long int j, i = 0;
	for ( j = 1; j <= 1000000000; j++)
	{
		i +=j;
	}
	printf("sum = %llu \n", i);
}

Пока писал этот пост - нашёл ошибку. Странно, что -Wall не ругался на переполнение int. И, да, надо будет весь свой код теперь проверять, боюсь, что может быть такой же косяк.

Есть мысль, что всё после оптимизации сводится к трюку Гаусса: sum = n*(n+1)/2

вот что на это генерирует компилятор с -O2:

main:
    sub	rsp, 8
    mov	edi, OFFSET FLAT:.LC0
    xor	eax, eax
    movabs	rsi, 500000000500000000
    call	printf
    xor	eax, eax
    add	rsp, 8
    ret

Ну я не удивлён, Гаусс, храни его господь.