[C++]Tablica dwuwymiarowa, najwieksza suma kilku elementów.

[kicha93]

Witam, mam z algorytmów i struktur danych takie oto zadanie: Zadanie nr 1, jakies bledy przy kopiowaniu.

Mam zrobic 2 wersje kody, optymalna i "siłową",

kod wyszukiwania:

Kod: Zaznacz cały

    for (int i=0; i<=x-px; i++)
    {
        for (int j=0; j<=y-py; j++)
        {
            sum2=0;
            for(int a=i;a<i+px;a++) for(int b=j;b<j+py;b++) { sum2+=tablica[a][b]; ops++; }
            if(sum1 < sum2) {
                    sum1 = sum2; cx = i; cy = j;
            }
        }
    }

A wiec poki co napisalem kod ktory idzie przez wszystkie elementy prócz najbardziej na prawo i na dole(aby nie bylo powtorzen), no i wykonuje sie ladnie, ale np dla tablicy 100x8000 jest to okolo juz 506mln obliczen (ta zmienna ops) i 3s kodu kompilacji, i tu teraz do was pytanie, czy moge to uznac juz za metodę optymalna czy jest to siłowa.
Nie widze innej metody szybszej/o mniejszej ilosci operacji, moze pomozecie, cos podpowiecie. Brak mi pomyslu na inną metodę.

[Gouranga]

Musi być w C++ czy może być w C?
Chcesz wskazówek czy gotowy kod z tłumaczeniami?
Możesz optymalizować kod przez programowanie współbieżne czy tylko przez zmianę algorytmu?

[kicha93]

Zaczalem w C++ wiec raczej oba algorytmy maja byc w tym jezyku, aczkolwiek pewnie nic zlego by sie nie stalo jesli C, prowadzący pozwala C/C++/Java/C#.
Cokolwiek co mi pomoze zobaczyc ze jest sposob na inne wykonanie przeszukania niz przejscie przez cala tablice, nazwy algorytmow, podpowiedzi, gotowe przykladowe rozwiazania, itp:P
Chodzi o wykonanie algorytmu ktory tylko wykona sie nawet byle jak, i o drugi ktory wykona to jak najszybciej i z najmniejsza iloscia operacji. Przedmiot to Algorytmy wiec chodzi o znalezienie dogodnego algorytmu.

[Gouranga]

nie wiem jak możnaby to zoptymalizować bez programowania współbieżnego
można ew. się pokusić o znalezienie największej wartości w tablicy i zbadanie wszystkich prostokątów do których należy, po czym stwierdzenie czy jakikolwiek inny prostokąt może dać większą wartość ale to i tak się sprowadza do sprawdzenia wszystkich

[kicha93]

To moze masz pomysl na gorszą wersję?:D
Ogolnie chodzi o zlozonosc obliczen i tutaj wg mnie mniej sie nie da, bo co bym nie wymyslil to i tak nie spadna obliczenia.

[Gouranga]

właśnie gorszej też nie ma, tu po prostu musisz policzyć te wartość dla każdego prostokąta, nic mniej, nic więcej

[Chromosom]

Niech wymiary całego pola wynoszą \(\displaystyle{ a,b}\), natomiast wymiary mniejszego prostokąta \(\displaystyle{ n,k}\). Gdyby obliczać sumę każdego prostokąta oddzielnie, musielibyśmy wykonać \(\displaystyle{ nk(a-n+1)(b-k+1)}\) dodawań. Zamiast tego, wykonajmy algorytm w następujących krokach:

1. Obliczenie sumy elementów znajdujących się wewnątrz prostokąta rozpoczynającego się w lewym górnym rogu oraz zapisanie wyniku jako maksimum. Uzyskana wartość powinna pozostać w pamięci w celu wykorzystania w przyszłości. Jednocześnie, podczas przeprowadzania obliczeń, zapisujemy w pamięci sumy elementów tworzących wiersze oraz kolumny tego prostokąta - będą one potrzebne później. W tym celu możemy utworzyć 2 tablice: kolumny[a] oraz wiersze.

2. Obliczenie sumy elementów składających się na wszystkie kolumny o wymiarach \(\displaystyle{ 1\times k}\), których najwyższa komórka jest jednocześnie fragmentem górnej krawędzi całego pola, oraz sumy elementów składających się na wszystkie wiersze o wymiarach \(\displaystyle{ 1\times n}\), których lewa komórka jest jednocześnie fragmentem lewej krawędzi całego pola.

3. Zapisanie sumy pierwszego prostokąta jako maksimum, następnie odjęcie od tego prostokąta pierwszej kolumny, oraz dodanie \(\displaystyle{ n+1}\) kolumny, licząc od lewej strony. W ten sposób uzyskujemy sumę kolejnego prostokąta za pomocą \(\displaystyle{ n+1}\) dodawań, zamiast wcześniejszych \(\displaystyle{ nk}\).

4. Gdy powyższa procedura dobiegnie końca (zostanie osiągnięta prawa krawędź tablicy), należy odnieść się do sumy pierwszego rozważanego prostokąta (znajdującego się najbardziej na lewo oraz najwyżej) - od sumy tej należy odjąć pierwszy wiersz i dodać ostatni. W ten sposób uzyskamy sumę prostokąta znajdującego się poniżej.

5. Teraz należy odjąć od każdej z kolumn rozważanych w punkcie 2. ich najwyższy element, oraz dodać do nich element znajdujący się na pozycji \(\displaystyle{ n+1}\) licząc od góry.

6. Od prostokąta rozważanego w punkcie 4. odejmujemy kolumnę o numerze 1 i dodajemy kolumnę o numerze \(\displaystyle{ n+1}\).

W ten sposób wykonamy znacznie mniej działań dodawania. Będzie to miało szczególnie duże znaczenie w przypadku wielkich tablic. Jeśli zależy nam na pamięci, możemy zrezygnować z zapisywania sum kolumn i wierszy, zamiast tego odejmując od pierwszego prostokąta skrajną lewą kolumnę (\(\displaystyle{ k}\) działań) oraz dodając \(\displaystyle{ n+1}\) kolumnę licząc od lewej strony (również \(\displaystyle{ k}\) działań) - jednakże tutaj złożoność będzie nieco większa. Pozostawiam do samodzielnego dokończenia.

[Gouranga]

Chromosom, zysk czasu kosztem pamięci. Bez angażowania dodatkowej pamięci nie skrócisz tego algorytmu.

[Chromosom]

Jeśli zależy nam na pamięci, możemy zrezygnować z zapisywania sum kolumn i wierszy, zamiast tego odejmując od pierwszego prostokąta skrajną lewą kolumnę (\(\displaystyle{ k}\) działań) oraz dodając \(\displaystyle{ n+1}\) kolumnę licząc od lewej strony (również \(\displaystyle{ k}\) działań)

Przechowywanie w pamięci sumy liczb znajdujących się w obrębie jednego prostokąta raczej nie jest wymagające.