Zrychleni behu programu – C / C++ – Fórum – Programujte.com

Dobry den,

potrebovala bych trosku pomoci. Potrebuju zrychlit tento program. Ocenim jakoukoliv radu. Predem Dekuju.

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

void prirad_index(vector<int>& kam, int ktery, int kolik)
{
vector<int>::iterator pom = kam.begin() + ktery - 1;
*pom = kolik;
};

int vrat_index(vector<int>& odkud, int ktery)
{
vector<int>::iterator pom = odkud.begin() + ktery - 1;
return(*pom);
};

void komponenty(int v,
    int& index,
    vector<bool>& je_ve_stacku,
    vector<int>& index_pole,
    vector<int>& nejnizsi_cesta,
    vector<int>& stack,
    vector<vector<int> >& graf )
{
prirad_index(index_pole, v, index);
prirad_index(nejnizsi_cesta, v, index);
++index;
stack.push_back(v);
je_ve_stacku[v - 1] = true;

//for each (v, w) in E do
vector<vector<int> >::iterator v_p = graf.begin() + v - 1;
vector<int>::iterator w = (*v_p).begin();
if ((*v_p).front() != 0)
{
while (w != (*v_p).end())
{
  if (vrat_index(index_pole, *w )== -1)
  {
    //if (w.index is undefined) then
    //strongconnect(w)
   komponenty(*w, index, je_ve_stacku, index_pole, nejnizsi_cesta, stack, graf);
    //v.lowlink := min(v.lowlink, w.lowlink)
   prirad_index(nejnizsi_cesta, v, min(vrat_index(nejnizsi_cesta, v), vrat_index(nejnizsi_cesta, *w)));

  }
    //else if (w is in S) then
  else
  {
   if (je_ve_stacku[ *w - 1] == true)
   {
    //v.lowlink := min(v.lowlink, w.index)
    prirad_index(nejnizsi_cesta, v, min(vrat_index(nejnizsi_cesta, v), vrat_index(index_pole, *w)));
   };
  };
  ++w;
};
};
  
   //if (v.lowlink = v.index) then
if (vrat_index(nejnizsi_cesta, v) == vrat_index(index_pole, v))
{
  int w_int = stack.back();
  stack.pop_back();
  je_ve_stacku[w_int - 1] = false;
  cout << w_int << " ";
   //until (w = v)
  while (w_int != v)
  {
  w_int = stack.back();
  stack.pop_back();
  je_ve_stacku[w_int - 1] = false;
  // add w to current strongly connected component
  cout << w_int << " ";
  };
  cout << endl;
};
};
void cti_vstup(int vrcholy, vector<vector<int> >& graf)
{
for (int i =0; i < vrcholy; ++i)
{
int pom;
cin >> pom;
vector<int> pompom;
if (pom==0)
  {
   pompom.push_back(0);
}
while (pom!=0)
   {
    pompom.push_back(pom);
    cin >> pom;
   };
graf.push_back(pompom);
};
};

int main()
{
int vrcholy;
cin >> vrcholy;
vector<vector<int> > graf;
cti_vstup(vrcholy, graf);
vector<int> index_pole, nejnizsi_cesta;
//inicializace indexu jednotlivych vrcholu
for (int i =0; i < vrcholy; ++i)
{index_pole.push_back (-1);};
for (int i =0; i < vrcholy; ++i)
{nejnizsi_cesta.push_back(-1);};
vector<int> stack;
vector<bool> je_ve_stacku(vrcholy, false);
int index = 0;
for (int i = 1; i <= vrcholy; ++i)
{
  if (vrat_index(index_pole, i) == -1)
  {
   komponenty(i, index, je_ve_stacku, index_pole, nejnizsi_cesta, stack, graf);
  };
};

return 0;
}

Co to ma delat? Mas nejaky vzorek dat, ktery se ti zda byt moc pomaly?

Je to Tarjanuv algoritmus. Hleda silne souvisle komponenty v grafu.

Vzorek pomalych dat bohuzel nemam :-(. Musim to odevzdavat do programku, kterej to sam vyhodnoti a potom mi hodi bud chybovou hlasku (spatna odpoved/program spadl apod.), nebo potvrdi spravnost. Vstupy nevidim. No a tohle funguje na 9 vstupech z 10. A ja potrebuju aby to fungovalo na 10 vstupech.  

Uplne by mi stacila nejaka obecna odpoved, jak treba pracovat s tema datovejma strukturama co tam mam. Nebo jestli je nemam nahradit necim, co bude rychlejsi. Nebo jestli by nejaka podminka nesla nekam presunout, aby se vyhodnocovala mene krat.... Nebo ja nevim, treba jestli by neslo nejak zrychlit to nacitani..... Proste jakoukoliv radu ocenim....

no asi takto (kdyz pominu mizerne formatovani):

na stack se hodi spise trida deque...

je_ve_stacku tezko rict... mozna i map (opet zalezi na zpusobu cislovani vrcholu)

pokud vrcholy nejsou cislovane pos sobe tak i pro ostatni veci map

prirad_index a vrat_index - co ti vadi na   vector[index] = hodnota ? a opacne + jeste volat funkci k tomu navic

Vrcholy jsou cislovane od jedne do n. Ke kazdemu vrcholu mam seznam vrcholu, do kterych se z nej muzu dostat (tyhle data jsou ve vector<vector<int> > graf). Vsechny vrcholy prochazim rekurzivne (prohledavanim do hloubky) a pripisuju si k nim nejake hodnoty typu int. Dale se koukam na ty hodnoty, ktere uz mam zapsane a podle toho se rozhoduji co dal delat. Tolik snad alespon trosku pochopitelny popis toho, co to zhruba dela. 

Nad map jsem taky premyslela ale nejsem si prave jista, jestli by to zrychlila nebo ne..... Kdyz jsou ty vrcholy cislovane poporade a ja vlastne jedine co delam je, ze se podivam/prepisu jedno konkretni misto. Mozna by to slo lip. V podstate bych ztratila jenom neco malo casu na tom, ze by se ta mapa tvorila. A pak bych ty hodnoty mozna hledala o neco rychleji. Ale zase nevim, jestli kdybych tam davala jako klice cisla od jedne do n, tak jestli by si to udelalo nejakej rozumnej strom, nebo jestli by to udelalo proste "caru" (a tim padem bych mela uplne to same co u vektoru.....). Nemam s tim az takovou zkusenost a nejsem si jista..... :-(

Degue urcite zkusim. 

Jeste me teda napadlo dat misto int short int (kterej by mi uplne stacil), ale tam bych asi jenom hybla s pameti a ne s vykonem..... :-(

Můžeš zkusit pro ty vectory předalokovat místo metodou reserve. Ale asi tím moc nezískáš. Když jsem si kdysi hrál s grafy, tak jsem dosáhl největšího zrychlení tak, že jsem celý graf po načtení překonvertoval z objektové hierarchie do pole intů. (Už jsem znal počet uzlů, takže to bylo i paměťově docela efektivní.) Zrychlení bylo pekelné, protože pak už všechny operace byly jenom posunování indexu. Ale nemusí to být vhodné řešení pro tento případ a není to zase triviální úprava na pár řádků.

Jak to predalokuji? Nikdy jsem to nedelala :(

Pokud víš, kolik v tom vektoru bude prvků, tak můžeš použít metodu reserve. Ale má to efekt jenom v případě, že tam strkáš velké množství prvků nebo máš naopak hodně vektorů s malým množstvím prvků.

Vektor má normálně "předalokovaný" prostor pro více prvků než kolik v něm je. Pokud to tak neměl, tak by přidávání nových prvků bylo velice nefektivní, protože by probíhalo (zjednodušeně) nějak takto:

• přealokuj novou velikost
• překopíruj všechna data do nového umístění
• uvolni původní data

Toto by se dělo při každém přidávání. Tím, že je nějaký prostor už předalokovaný, tak se to děje jenom občas a většinou to funguje tak, že není nutné se o nic starat. Nicméně pokud už předem budu vědět, kolik prvků v tom vektoru bude, můžu mu to říct tou zmiňovanou metodou reserve a on bude předalokovaný přesně na ten počet prvků - nebude tedy muset přealokovávat nový buffer a kopírovat stávající data.

Můžeš si to prozkoušet na následujícím příkladě:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vi;
    std::cout << "Vektor ma predalokovan prostor pro " << vi.capacity() << " prvku\n";

    const int LEN = 10;

    vi.reserve(LEN);
    std::cout << "Vektor ma predalokovan prostor pro " << vi.capacity() << " prvku\n";

    for (int i = 0; i < LEN; ++i)
    {
        vi.push_back(i);
    }
    std::cout << "Vektor ma predalokovan prostor pro " << vi.capacity() << " prvku - nic se neprealokovalo\n";

    std::cout << "Adresa prvniho prvku je " << &vi[0] << '\n';

    vi.push_back(1000);
    std::cout << "Vektor ma predalokovan prostor pro " << vi.capacity() << " prvku - doslo k realokaci\n";

    std::cout << "Adresa prvniho prvku je " << &vi[0] << " - muze by jina, nez pred realokaci";
}

A jinak ještě platí další pravidlo - pokud neznáš předem počet prvků a nepotřebuješ k nim náhodný přístup přes index (tedy, vždy je procházíš postupně), tak místo vektoru použij std::list a o nějaké realokace se nemusíš starat.

Chapu, to skoro urcite pomuze. Diky moc.