Ogromne obliczenia

Witam serdecznie!
Mam do wykonania w pracy zadanie polegające na przeszukaniu ponad stu miliardów zestawów sześciu liczb, które mają spełniać pewne warunki (tych warunków jest ok. 40), a następnie z tych, które te warunki spełnią wybrać rozwiązanie najlepsze (minimalne powiedzmy). Excel (czy raczej tamtejszy VBA) wysiada przy kilku milionach danych, próbowałem policzyć kilkadziesiąt razy mniejszy przykład w Sage'u, ale obliczenia trwały i trwały, Sage znaku życia nie dawał i koniec końców nic z niego nie wydusiłem.
Wpadłem więc na pomysł wzięcia się za jakiś "poważny" język programowania. Pomyślałem, że skoro w C++ pisze się gry, a to przecież gigantyczne obliczenia, to i z moimi sobie poradzi. Poczytałem trochę i spłodziłem pewien program w C++. Nie wiem, czy go tu umieszczać (bo to ponad 400 linii kodu), ale opiszę mój sposób podejścia do problemu. Kłopot w tym, że schodzi to straszliwie długo, z grubsza policzyłem, że mojemu komputerowi zeszłoby to ponad 100 dni... Dlatego proszę Was o jakieś rady, jak można by to było zrobić efektywniej.

1. Na początek definiuję te 40 funkcji (w każdej zabezpieczam instrukcją "if" ewentualne dzielenie przez zero itp., w przypadku błędu funkcja zwraca mi zero). Większość funkcji jest zależna od mniejszej ilości parametrów, niekoniecznie od wszystkich sześciu.
2. Potem zagnieżdżam 6 pętli for (moje parametry to głównie kąty, mają przebiec liczby od 1 do 180). Na każdym "piętrze" sprawdzam, czy funkcje zależne od wywołanych już parametrów nie zwracają zer (jako błędów) - robię to instrukcją "if". Oprócz tego sprawdzam kilka dodatkowych warunków, które muszą zajść. Jeśli coś zwraca błąd, przeskakuję do kolejnej wartości bieżącego parametru poleceniem continue.
3. Jeśli jakiś zestaw parametrów pomyślnie przejdzie próby, zapisuję go w pliku tekstowym. Plik otwieram przed pętlą, zamykam po pętli. Zabieg ten ma na celu zebranie dobrych danych w jednym miejscu.

W momencie, w którym uruchomiłem na próbę potrójną tylko pętlę, obliczenia trwały ok. pół minuty. Oznacza to, że włączając wszystkie 6 pętli, będę musiał liczyć 10*180^2 razy dłużej (dwa kąty i jeden parametr zmieniający się od 1 do 10), czyli jakieś 112 dni...

Przeprojektuj algorytm tak, aby liczba jego iteracji nie szła w miliardy. No chyba, że dotknąłeś problemu NP-Trudnego, to wówczas nie przeskoczysz problemu złożoności obliczeniowej.

Muszę sprawdzić wszystkie przypadki, każdy jest równie prawdopodobny. Czyli nie ma nadziei?

Jeżeli istnieje jedno rozwiązanie to raczej będziesz musiał przeszukać wszystkie kombinacje. Jeżeli istnieją rozwiązania 'satysfakcjonujące', tj. rozwiązań w puli jest więcej, ale niekoniecznie optymalnych to wówczas można zastosować algorytmy heurystyczne.

Jak to coś ważnego to poczytaj to obliczeniach w chmurze.

Nie wiem, ile tych rozwiązań istnieje, być może wiele, być może żadnego nie ma. Póki co dzięki za rady, będę czytał o tej chmurze.

stu miliardów zestawów sześciu liczb

Czyli masz ponad 2200 GB danych (zakładam, że liczba = int)? Rozumiem, że nie są to dane w pliku, bo nie pisaleś nic o czytaniu danych z dysku. A ponieważ raczej nie trzymasz 2200 GB w pamięci to nie są to dane wejściowe do programu czyli program je generuje, tak?

Wygląda na to, że starasz odnaleźć coś w zbiorze "wszystkich kombinacji czegoś" próbująć sprawdzić wszystkie kombinacje... co nigdy nie jest optymalne. Poza tym, przetworzenie 2200 GB danych musi trwać. Mówisz, że masz 6 pętli, czyli zakładamy złożoność O(x^6) czyli mamy 600000000000 iteracji.

Robisz coś metodą bruteforce, tutaj nie da się żadnym językiem zejść znacząco z czasem. Jedyna szansa dla Ciebie to wymyślenie innego algorytmu, albo zapytanie jakiegoś kolegi matematyka o opracowanie optymalniejszego algorytmu.

Zakladajac ze naprawde musisz przejsc te 100mld rekordow to mozesz zoptymalizowac swoj kod. Np.:
- powyciagac sprawdzenia na sam poczatek.
- moze kolejnosc warunkow ma znaczenia. Mozesz wybrac jakis reprezentatywny zbior danych (np 10k), przepuscic je przez wszystkie 40 warunkow i policzyc na jakim warunku najwiecej rekordow odpada, ustawiasz ten warunek w kodzie jako 1szy (tak by odrzucal niepoprawne rozwiazanie) i powtarzasz test z pozostalymi 39 warunkami.
- sprawdz czy uzywane funkcje nie da rady zastapic przez szybsze (piszesz ze pracujesz na katach, jesli uzywasz funkcji tryg. to moze lepiej to przerzucic na GPU)
- jesli masz dostep do kilku komputerow (np. jesli masz jakiegos znajomego na uczelni) to mozesz podzilic zbior na mniejsze i przetwarzac rownolegle.