Как Убрать Цикл For Или Ускорить Вычисление

  • Автор темы Автор темы AlexVI
  • Дата начала Дата начала
Статус
Закрыто для дальнейших ответов.
A

AlexVI

подскажите по следующему вопросу
есть вектор длиной 5 бит из него формирую расчитываю все возможные комбинации(вектора) длиной 2 бита затем с длиной 3, 4. При поиске всех возможных комбинаций длиной 2 бита использую в программе два for, когда 3 бита соотв 3 for и т д. Проблема возникает когда исходный вектор имеет длину 32 000 бит и из него я ищу все возможные комбинации длиной 23 бита т.е. в проге имею 23 for что в итоге очень долго. В матлабе есть аналогичная функция nchoosek но она с такими длинами не работает. Можно ли как то ускорить расчет заменой for или еще чем... Заранее спасибо...
 
используй рекурсию чтобы не считать "for"

Добавлено: как то так:

Код: 
void f( int n ) {
if( 0 >= n )
return;
for( int i = 0; i < 2; i ++ )
f( n - 1 );
}

не проверял, могут быть опечатки. Но тут вроде видно, что при n = 2 "будет 2 фор", при n = 32, соответственно, 32 )
 
подскажите может еще есть варианты как ускорить вычисление, может ассемблеровские вставки или еще что ??? может есть стандартные функции какието ... как быстро перебирать эти комбинации...
 
Сколько секунд/минут идут вычисления? Если больше 20 секунд на мощном компе, совершенствуйте алгоритм, хитрости и вставки вам не помогут. БТВ, я не вникал, но не всякое вычисление можно выполнить за секунду.

Точнее не так: Хитрости вам помогут, но не сильно, все зависит во сколько раз вы хотите сократить время выполнения, если в 2 раза и больше, то меняйте/совершенствуйте алгоритм.
 
qqwertty сказал(а):
Сколько секунд/минут идут вычисления? Если больше 20 секунд на мощном компе, совершенствуйте алгоритм, хитрости и вставки вам не помогут. БТВ, я не вникал, но не всякое вычисление можно выполнить за секунду.

Точнее не так: Хитрости вам помогут, но не сильно, все зависит во сколько раз вы хотите сократить время выполнения, если в 2 раза и больше, то меняйте/совершенствуйте алгоритм.
Нажмите, чтобы раскрыть...

при длине входного вектора 2000 бит перебор всех комбинаций длиной 4 бита идет уже дней 8 днем и ночью и достигло только индексов
1_2_3_4 (это начало)
прошло 8 дней, стало
5_457_659_1890 (вот что в конце до 1997_1998_1999_2000)
 
киньте ваш код, не весь, а только алгоритм, я не оч понимаю что именно вам нужно, тогда подумаем, что сделать можно

Хотя если можете, то лучше всю прогу, так проще будет
 
вот код
char *inMat;
inMat=new char [5]; создаем вектор длиной 5
inMat[0]=0x00; все заполнено битовыми нулями
inMat[1]=0x00;
inMat[2]=0x00;
inMat[3]=0xff; тут одна битовая единица
inMat[4]=0x00; битовый ноль
формир все возможные комбинации длиной 3 на входном векторе длиной 5

for(int i1=0; i1<dlina-(3-1); i1++)
{ for (int i2=i1+1; i2<dlina-1; i2++)
{ for(int i3=i2+1; i3<dlina; i3++)
{
char R;
R=inMat[i1]^inMat[i2]^inMat[i3]; суммирую по мод2
}
}
}
 
AlexVI сказал(а):
вот код
char *inMat;
inMat=new char [5]; создаем вектор длиной 5
inMat[0]=0x00; все заполнено битовыми нулями
inMat[1]=0x00;
inMat[2]=0x00;
inMat[3]=0xff; тут одна битовая единица
inMat[4]=0x00; битовый ноль
формир все возможные комбинации длиной 3 на входном векторе длиной 5

for(int i1=0; i1<dlina-(3-1); i1++)
{ for (int i2=i1+1; i2<dlina-1; i2++)
{ for(int i3=i2+1; i3<dlina; i3++)
{
char R;
R=inMat[i1]^inMat[i2]^inMat[i3]; суммирую по мод2
}
}
}
Нажмите, чтобы раскрыть...
в данном примере
есть вектор длиной 5 бит
затем формирую все возможные комбинации длиной 3 бита это используется 3 for как видно из кода. Но при входном векторе длиной 2000 бит и формировать все возможные комбинации длиной допустим 12 (это количество комбинаций длиной 12 которые можно получит на входном векторе длиной 2000)это уже использую 12 for' ов

Добавлено:
AlexVI сказал(а):
вот код
char *inMat;
inMat=new char [5]; создаем вектор длиной 5
inMat[0]=0x00; все заполнено битовыми нулями
inMat[1]=0x00;
inMat[2]=0x00;
inMat[3]=0xff; тут одна битовая единица
inMat[4]=0x00; битовый ноль
формир все возможные комбинации длиной 3 на входном векторе длиной 5

for(int i1=0; i1<dlina-(3-1); i1++)
{ for (int i2=i1+1; i2<dlina-1; i2++)
{ for(int i3=i2+1; i3<dlina; i3++)
{
char R;
R=inMat[i1]^inMat[i2]^inMat[i3]; суммирую по мод2
}
}
}
Нажмите, чтобы раскрыть...
в данном примере
есть вектор длиной 5 бит
затем формирую все возможные комбинации длиной 3 бита это используется 3 for как видно из кода. Но при входном векторе длиной 2000 бит и формировать все возможные комбинации длиной допустим 12 (это количество комбинаций длиной 12 которые можно получит на входном векторе длиной 2000)это уже использую 12 for' ов
 
Я так понял, что вы реализовываете "Размещения без повторений", ну так там ф-ла A(k,n) = n!/(n-k)!
k - сколько вы выбираете n - сколько всего.

2000!/(2000-12)! довольно внушительное число перестановок и долго будет считаться в любом случае. Эти все алгоритмы есть, погуглите: "Размещения без повторений", может кто скоросной вариант написал уже.
 
qqwertty сказал(а):
Я так понял, что вы реализовываете "Размещения без повторений", ну так там ф-ла A(k,n) = n!/(n-k)!
k - сколько вы выбираете n - сколько всего.

2000!/(2000-12)! довольно внушительное число перестановок и долго будет считаться в любом случае. Эти все алгоритмы есть, погуглите: "Размещения без повторений", может кто скоросной вариант написал уже.
Нажмите, чтобы раскрыть...
да все правильно алгоритм реализуется по формуле
n!/((n-k)!k!) и при моих условиях это n=2000 и k=12 число сотни тысяч триллионов комбинаций. Да спасибо за наппавление

Добавлено:
qqwertty сказал(а):
Я так понял, что вы реализовываете "Размещения без повторений", ну так там ф-ла A(k,n) = n!/(n-k)!
k - сколько вы выбираете n - сколько всего.

2000!/(2000-12)! довольно внушительное число перестановок и долго будет считаться в любом случае. Эти все алгоритмы есть, погуглите: "Размещения без повторений", может кто скоросной вариант написал уже.
Нажмите, чтобы раскрыть...
да все правильно алгоритм реализуется по формуле
n!/((n-k)!k!) и при моих условиях это n=2000 и k=12 число сотни тысяч триллионов комбинаций. Да спасибо за направление
 
подскажите может ли помочь в этом вопросе генерирование исключений если да то как им воспользоваться в моем случае
 
Да, имел ввиду ускорения вычисления.
Вот нашел код, довольно неплохо работает но только на четыре порядка т.е n=2000 k=4
дальше требуется много времени. Может как тто оптимизировать можно этот код:

C++: 
#include <stdio.h>

int a[2000];
int na;

int n, m; // total, to-take

void step(int pos)
{
if(na==m) // one more completed
{
for(int i=0;i<na;i++) 
printf("%d ", a[i]+1); // тут записываю результат

puts("");

return;  
}

if(pos+m-na > n) // won't be able to complete
return;

na++;

for(int i = pos ? a[pos-1]+1 : 0; i<n; i++)
a[na-1] = i, step(pos+1);

na--;
}

int main()
{
scanf("%d %d", &n, &m);

for(int i=0;i<n;i++)
a[i] = i;

step(0); 
}
 
Развернуть рекурсию в цикл,

pos ? a[pos-1]+1 : 0; Это условие выполняется постоянно, хотя реальная необходимость в нем только 1 раз.

пост-инкременты заменить на пред- (но это сомнительно, компиляторы уже научились это делать сами)

заюзать ключи оптимизации (я не шарю в этой теме, но может поможет)

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

P.S. Вам именно ВСЕ эти сочетания нужны? Или только одно, потому что должны быть алгоритмы по нахождению конкретной перестановки (и может быть сочетания).
А если все, то смиритесь, все-равно, запись в файл долгая штука.
 
да мне надо перебрать все комбинации, если бы конкретную. А с развернутой рекурсией у меня есть вариант работает медленнее чем этот.

Добавлено:
да мне надо перебрать все комбинации, если бы конкретную. А с развернутой рекурсией у меня есть вариант работает медленнее чем этот.
 
Развернуть рекурсию в цикл,
Нажмите, чтобы раскрыть...
как это? - я знаю лишь как заменить правосторонюю рекурсию циклом, а все остальные виды...возможно ли?
А если все, то смиритесь, все-равно, запись в файл долгая штука.
Нажмите, чтобы раскрыть...
МБ я ошибаюсь, но писать в файл большими блоками быстрее чем маленькими(меньше число обращений). А значит, можно сохранять результаты в ОЗУ(дефицита щас нет) и потом разом все писать в файл, время работы должно снизиться.
 
r04 сказал(а):
как это? - я знаю лишь как заменить правосторонюю рекурсию циклом, а все остальные виды...возможно ли?
Нажмите, чтобы раскрыть...
Загуглите: Любую ли рекурсию можно заменить циклом? Или в таком духе, если ответам гугла не верите. ;)
 
Ваша задача не оптимизируема в принципе. В такой ситуации надо думать о том, зачем вам, собственно, все размещения? Обычно перебором пытаются найти конкретные комбинации, удовлетворяющие какому-нибудь условию. И тут уже можно думать о таких вещах как отсекание заведомо неподходящих множеств комбинаций, жадные алгоритмы, эволюционные и генетические алгоритмы, всякие эвристические методы и т. д.
 
qqwertty
Ага, но к снижению времени работы программы это не приведет(если вызов рекурсивной функции заменить помещением в стек текущего состояния, безусловным переходом,...,...), но qqwertty писал именно в этом контексте:
Не думаю, что программа может ускориться заметно.
Нажмите, чтобы раскрыть...
А вотЪ замена правосторонней рекурсии таки приведет к повышению скорости работы программы(как раз за счет того, что программа перестанет тиранить нерезиновый стек).
Но вцелом, тут ключи оптимизации не помогут, надо менять алгоритм.
 
r04, не понимаю к чему вы клоните....
Я лишь ответил на ваш вопрос:

r04 сказал(а):
как это? - я знаю лишь как заменить правосторонюю рекурсию циклом, а все остальные виды...возможно ли?
Нажмите, чтобы раскрыть...
Будет там слабый выйгрыш или даже офигенный пройгрыш, зависит только от ваших познаний.

r04 сказал(а):
А вотЪ замена правосторонней рекурсии таки приведет к повышению скорости работы программы(как раз за счет того, что программа перестанет тиранить нерезиновый стек).
Нажмите, чтобы раскрыть...

Современные компиляторы давно научились оптимизировать хвостовую рекурсию.
 
Статус
Закрыто для дальнейших ответов.
Мы в соцсетях:

Обучение наступательной кибербезопасности в игровой форме. Начать игру!

Верх Низ