Zrychleni behu programu – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
11. 4. 2012   #1
-
0
-

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;
}

Nahlásit jako SPAM
IP: 77.48.32.–
Reklama
Reklama
KIIV+42
God of flame
11. 4. 2012   #2
-
0
-

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

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
11. 4. 2012   #3
-
0
-

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....

Nahlásit jako SPAM
IP: 77.48.32.–
KIIV+42
God of flame
11. 4. 2012   #4
-
0
-

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

Nahlásit jako SPAM
IP: 94.112.32.–
Program vždy dělá to co naprogramujete, ne to co chcete...
11. 4. 2012   #5
-
0
-

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..... :-(

Nahlásit jako SPAM
IP: 77.48.32.–
ondra.holub+1
Stálý člen
11. 4. 2012   #6
-
0
-

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ů.

Nahlásit jako SPAM
IP: 212.96.189.–
11. 4. 2012   #7
-
0
-

Jak to predalokuji? Nikdy jsem to nedelala :(

Nahlásit jako SPAM
IP: 77.48.32.–
ondra.holub+1
Stálý člen
12. 4. 2012   #8
-
0
-

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.

Nahlásit jako SPAM
IP: 194.138.12.–
12. 4. 2012   #9
-
0
-

Chapu, to skoro urcite pomuze. Diky moc.

Nahlásit jako SPAM
IP: 77.48.32.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 140 hostů

Podobná vlákna

Zastaveni behu programu — založil Tom@sQo

Konec běhu programu — založil Polarski

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý