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

Тема в разделе "Общие вопросы по С и С++", создана пользователем AlexVI, 10 фев 2012.

Статус темы:
Закрыта.
  1. AlexVI

    AlexVI Гость

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

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    используй рекурсию чтобы не считать "for"

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

    Код (Text):
    void f( int n ) {
    if( 0 >= n )
    return;
    for( int i = 0; i < 2; i ++ )
    f( n - 1 );
    }
    не проверял, могут быть опечатки. Но тут вроде видно, что при n = 2 "будет 2 фор", при n = 32, соответственно, 32 )
     
  3. AlexVI

    AlexVI Гость

    подскажите может еще есть варианты как ускорить вычисление, может ассемблеровские вставки или еще что ??? может есть стандартные функции какието ... как быстро перебирать эти комбинации...
     
  4. qqwertty

    qqwertty Гость

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

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

    AlexVI Гость

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

    qqwertty Гость

    киньте ваш код, не весь, а только алгоритм, я не оч понимаю что именно вам нужно, тогда подумаем, что сделать можно

    Хотя если можете, то лучше всю прогу, так проще будет
     
  7. AlexVI

    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
    }
    }
    }
     
  8. AlexVI

    AlexVI Гость

    в данном примере
    есть вектор длиной 5 бит
    затем формирую все возможные комбинации длиной 3 бита это используется 3 for как видно из кода. Но при входном векторе длиной 2000 бит и формировать все возможные комбинации длиной допустим 12 (это количество комбинаций длиной 12 которые можно получит на входном векторе длиной 2000)это уже использую 12 for' ов

    Добавлено:
    в данном примере
    есть вектор длиной 5 бит
    затем формирую все возможные комбинации длиной 3 бита это используется 3 for как видно из кода. Но при входном векторе длиной 2000 бит и формировать все возможные комбинации длиной допустим 12 (это количество комбинаций длиной 12 которые можно получит на входном векторе длиной 2000)это уже использую 12 for' ов
     
  9. qqwertty

    qqwertty Гость

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

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

    AlexVI Гость

    да все правильно алгоритм реализуется по формуле
    n!/((n-k)!k!) и при моих условиях это n=2000 и k=12 число сотни тысяч триллионов комбинаций. Да спасибо за наппавление

    Добавлено:
    да все правильно алгоритм реализуется по формуле
    n!/((n-k)!k!) и при моих условиях это n=2000 и k=12 число сотни тысяч триллионов комбинаций. Да спасибо за направление
     
  11. AlexVI

    AlexVI Гость

    подскажите может ли помочь в этом вопросе генерирование исключений если да то как им воспользоваться в моем случае
     
  12. qqwertty

    qqwertty Гость

    Вы имеете ввиду throw? И в каком вопросе? Если что-то ускорить, то вряд ли.
     
  13. AlexVI

    AlexVI Гость

    Да, имел ввиду ускорения вычисления.
    Вот нашел код, довольно неплохо работает но только на четыре порядка т.е 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);
    }
     
  14. qqwertty

    qqwertty Гость

    Развернуть рекурсию в цикл,

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

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

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

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

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

    AlexVI Гость

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

    Добавлено:
    да мне надо перебрать все комбинации, если бы конкретную. А с развернутой рекурсией у меня есть вариант работает медленнее чем этот.
     
  16. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    как это? - я знаю лишь как заменить правосторонюю рекурсию циклом, а все остальные виды...возможно ли?
    МБ я ошибаюсь, но писать в файл большими блоками быстрее чем маленькими(меньше число обращений). А значит, можно сохранять результаты в ОЗУ(дефицита щас нет) и потом разом все писать в файл, время работы должно снизиться.
     
  17. qqwertty

    qqwertty Гость

    Загуглите: Любую ли рекурсию можно заменить циклом? Или в таком духе, если ответам гугла не верите. ;)
     
  18. Trs

    Trs Гость

    Ваша задача не оптимизируема в принципе. В такой ситуации надо думать о том, зачем вам, собственно, все размещения? Обычно перебором пытаются найти конкретные комбинации, удовлетворяющие какому-нибудь условию. И тут уже можно думать о таких вещах как отсекание заведомо неподходящих множеств комбинаций, жадные алгоритмы, эволюционные и генетические алгоритмы, всякие эвристические методы и т. д.
     
  19. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    qqwertty
    Ага, но к снижению времени работы программы это не приведет(если вызов рекурсивной функции заменить помещением в стек текущего состояния, безусловным переходом,...,...), но qqwertty писал именно в этом контексте:
    А вотЪ замена правосторонней рекурсии таки приведет к повышению скорости работы программы(как раз за счет того, что программа перестанет тиранить нерезиновый стек).
    Но вцелом, тут ключи оптимизации не помогут, надо менять алгоритм.
     
  20. qqwertty

    qqwertty Гость

    r04, не понимаю к чему вы клоните....
    Я лишь ответил на ваш вопрос:

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

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

Поделиться этой страницей