LINUX.ORG.RU

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

 


0

2

Есть программа (сейчас на матлабе), в которой я перебираю большое количество вариантов, точнее, все последовательности 0 и 1 размером n, т.е. 2^n. Соответственно, начало следующее:

parfor i = 1:2^(box_size^2/2)-1

 c_points = de2bi(i,box_size^2/2);
 
 box = zeros(box_size+2,box_size+2);

 for j = 1:box_size
     box(j+1,2+rem(j,2):2:box_size+1) = c_points(1 + (j-1)*box_size/2:j*box_size/2);
 end

de2bi - преобразует неотрицательное целое число i в вектор-строку двоичных цифр.

Есть ли простые способы это оптимизировать? Например, есть ли способ генерировать эти 0-1 строки оптимальнее? Сейчас выполнение занимает слишком много времени. Далее происходят не слишком сложные операции с матрицей box и, скорее всего, я даже готов переписать это на каком-нибудь другом языке, если это принесет ощутимый прирост к скорости выполнения.

★★★

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

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

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

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

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

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

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

tyakos ★★★ ()

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

ZERG ★★★★★ ()
Ответ на: комментарий от tyakos

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

ZERG ★★★★★ ()
Ответ на: комментарий от ZERG

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

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

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

tyakos ★★★ ()
Ответ на: комментарий от tyakos

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

1125899906842623

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

anonymous ()
Ответ на: комментарий от ZERG

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

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

tyakos ★★★ ()
Ответ на: комментарий от tyakos

500 лет

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

tyakos ★★★ ()
Ответ на: комментарий от tyakos

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

anonymous ()
Ответ на: комментарий от anonymous

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

ZERG ★★★★★ ()
Ответ на: комментарий от anonymous

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

ZERG ★★★★★ ()
Ответ на: комментарий от tyakos

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

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

dsxl ()

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

zolden ★★★★★ ()
Ответ на: комментарий от dsxl

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

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

tyakos ★★★ ()
Ответ на: комментарий от anonymous

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

ZERG ★★★★★ ()
Ответ на: комментарий от ZERG

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

anonymous ()
Ответ на: комментарий от anonymous

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

#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

ZERG ★★★★★ ()
Ответ на: комментарий от ZERG

вот что на это генерирует компилятор с -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

anonymous ()
Ответ на: комментарий от anonymous

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

ZERG ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.