Algorytm rekurencyjny i stos oraz szybkość wykonywania.
Ostatnio zmodyfikowano 2013-07-18 20:56
johny Temat założony przez niniejszego użytkownika |
Algorytm rekurencyjny i stos oraz szybkość wykonywania. » 2013-07-17 18:35:20 Witam. Mam pewien program wykorzystujący algorytm rekurencyjny, który kompilowany pod ubuntu działa jak marzenie, a pod windowsem wysypuje stack overflow. Z czego to wynika? Kompilator przydziela inną wielkość stosu pod windowsem?
1. Jeśli tak to jak mogę zwiększyć pojemność stosu?
Napisałem to samo iteracyjnie. W tym celu symuluje stos używając mojej klasy Stack opartej na kolejce std::deque. Algorytm działa jak ślimak (niezależnie od tego czy kolejka jest tworzona normalnie czy dynamicznie).
2. Czy to, że dane będą umieszczone na stercie (czyli dynamicznie tworzone) zamiast w normalnej pamięci (która nawet nie wiem jak się nazywa) przyspiesza coś wykonywanie algorytmu? W sensie czy sterta różni się szybkością działania od normalnej pamięci? |
|
m4tx |
» 2013-07-17 18:44:30 | W sensie czy sterta różni się szybkością działania od normalnej pamięci? |
Stos jest z reguły szybszy. | Algorytm działa jak ślimak |
Spróbowałbym na początek określić rozmiar std::deque podczas tworzenia go. Być może podczas dodawania obiektów do niego jest on bardzo często rozszerzany i stąd niska wydajność. |
|
DejaVu |
» 2013-07-17 19:46:58 Kompilator przydziela inną wielkość stosu pod windowsem?
|
Każdy kompilator jak i każda jego wersja może przydzielać inny rozmiar stosu. Rozmiar stosu zmienia się za pomocą opcji kompilatora, więc sposób ustawienia jest bezpośrednio zależny od używanego kompilatora. Dodam jeszcze, że jeżeli algorytm potrzebuje tak dużej ilości pamięci stosu to należy poważnie rozważać jego implementację na stercie, a nie rozwiązywać problem poprzez zwiększenie rozmiaru stosu. |
|
johny Temat założony przez niniejszego użytkownika |
» 2013-07-17 20:07:04 W jaki sposób mogę określić początkowy rozmiar kolejki? Jeśli wpisuję tak: std::deque < T > kol( 100 );
to Qt Creator mi podkreśla linijkę na czerwono;d Kod klasy Stack: #ifndef STACK_H
#define STACK_H
#include <deque>
template < class T >
class Stack {
std::deque < T > kol;
public:
Stack() {
}
void clear() {
kol.clear();
}
bool isEmpty() const {
return kol.empty();
}
T & top() {
return kol.back();
}
void pop() {
kol.pop_back();
}
void push( const T & el ) {
kol.push_back( el );
}
void push( const T * el ) {
kol.push_back( * el );
}
};
#endif
// EDIT: W jaki sposób dodaje się na tym forum cytat?;d Chciałem zacytować fragment odpowiedzi DejaVu;d Podjąłem pewne kroki i zaimplementowałem to na stercie, ale działa strasznie wolno, toteż teraz staram się przyspieszyć :) |
|
DejaVu |
» 2013-07-17 20:19:00 |
|
johny Temat założony przez niniejszego użytkownika |
» 2013-07-17 21:35:12 kol.reserve( 100 ); nie kompiluje się. Nie wiem o co konkretnie chodziło użytkownikowi m4tx (jeśli chodzi o "określenie rozmiaru std::deque podczas tworzenia"), ale faktycznie kolejka ma dużo elementów (1.3~1.5 miliona). Jeszcze pytanie dotyczące stosu. Czy da się w jakiś sposób odczytać adres wskaźnika stosu w funkcji globalnej? |
|
pekfos |
» 2013-07-17 21:47:38 | Czy da się w jakiś sposób odczytać adres wskaźnika stosu w funkcji globalnej? |
Wstawką asma. Ale po co? |
|
Elaine |
» 2013-07-17 22:14:03 | Każdy kompilator jak i każda jego wersja może przydzielać inny rozmiar stosu. Rozmiar stosu zmienia się za pomocą opcji kompilatora, więc sposób ustawienia jest bezpośrednio zależny od używanego kompilatora. |
Pod Windowsem rozmiar stosu ustawia się podczas linkowania (później można go prosto zmienić, to tylko pole w nagłówku PE), a pod większością systemów *niksowych decydują o tym kernel systemu i administrator (poprzez ulimit). Kompilator nie ma wiele do powiedzenia, co najwyżej można go ostrzec, że stos może być nieciągły. |
|
| « 1 » 2 |