---

Hej gruppe,

Hvis jeg skriver følgende kode:

LazyPointer.h
----------------------------------------------------
#ifndef _METIS_LAZYPOINTER_H_
#define _METIS_LAZYPOINTER_H_

#include <vector>
#include <ostream>
#include <math.h>


namespace metis {
class Conf {
public:
Conf () {};
Conf (const Conf& c) {};
};

class LazyPointer {
public:
LazyPointer (Conf& source, Conf& goal);
~LazyPointer() {};

// You shouldn't be able to set another goal
Conf* getGoal() { return _goal; };
Conf* getSource() { return _source; };

void findPath();

protected:


private:
Conf* _goal;
Conf* _source;
std::vector<Conf> _roadmap; // Original configurations
};
}


#endif // _METIS_LAZYPOINTER_H_
----------------------------------------------------




LazyPointer.cpp
----------------------------------------------------
#include "LazyPointer.h"
#include <iostream>


int main (int argc, char **argv) {
metis::Conf goal;
metis::Conf source;
metis::LazyPointer lp(source,goal);
lp.findPath();

}

namespace metis {
LazyPointer::LazyPointer (Conf& source, Conf& goal) {
_roadmap.push_back(source);
_source = &_roadmap.back();

if (_source == &_roadmap[_roadmap.size()-1])
std::cout << "Source added correctly" << std::endl;

_roadmap.push_back(goal);
_goal = &_roadmap.back();

if (_goal == &_roadmap[_roadmap.size()-1])
std::cout << "Goal added correctly" << std::endl;
}


void LazyPointer::findPath() {
std::cout << "Roadmap size: " << _roadmap.size() << std::endl;
for (unsigned int i = 0; i < _roadmap.size(); ++i) {
if (_source == &_roadmap[i]) {
std::cout << "Source found" << std::endl;
}
if (_goal == &_roadmap[i]) {
std::cout << "Goal found" << std::endl;
}
}
}
}
----------------------------------------------------



så fås et output som følger:
------------------------------
Source added correctly
Goal added correctly
Roadmap size: 2
Goal found
------------------------------

en debugging af problemet viste sig at std::vector flytter rundt på
objekterne i hukommelsen efter sidste push_back....
Hvorfor i hele hulen flyttes objekterne? Det kan da ikke være særlig
optimalt, når vi snakker om at flytte dem fysisk?

En god forklaring ønskes. Det har kostet en hel dags arbejde og lidt til.


Mvh / Preben Holm

---

Preben wrote:
> en debugging af problemet viste sig at std::vector flytter rundt på
> objekterne i hukommelsen efter sidste push_back....
> Hvorfor i hele hulen flyttes objekterne? Det kan da ikke være særlig
> optimalt, når vi snakker om at flytte dem fysisk?
>
> En god forklaring ønskes. Det har kostet en hel dags arbejde og lidt til.

Jeg ved ikke om jeg kan tilbyde en god forklaring, men,

Hver gang du kalder push_back kan du resikere at den flytter rundt på
objekterne i din vector, dvs. alle referencer du måtte have til objekter
i vectoren vil være invalide. (Som en sidebemærkning kan det noteres at
det ikke vil ske hvis du kalder pop_back.)

I praksis er en vector arrangeret som ét stort hukommelses område, hvis
den får brug for mere plads vil den allokere mere plads og flytte de
eksisterende elementer over i den nye plads.
Det sker for at få en vector til at opføre sig som et array.
I nogle tilfælde vil den reservere plads til et antal elementer
af gangen for at undgå at skulle flytte alle elementer på én gang,
men det kan man ikke stole på, og man ved ikke hvornår den har
flyttet, kun hvornår det måske er sket.

Hvis det er et problem kan du reservere plads til alle elementer inden
du starter, bruge en vector af pointere, eller du kan bruge en
std::list. I stedet for at gemme pointere til elementer i din
vector (_goal og _source) kunne du bruge index'er.

--
Absolutely not the best homepage on the net:
http://home20.inet.tele.dk/midgaard
But it's mine - Bertel

---

Bertel Brander wrote:
> Preben wrote:
>
>> en debugging af problemet viste sig at std::vector flytter rundt på
>> objekterne i hukommelsen efter sidste push_back....
>> Hvorfor i hele hulen flyttes objekterne? Det kan da ikke være særlig
>> optimalt, når vi snakker om at flytte dem fysisk?
>>
>> En god forklaring ønskes. Det har kostet en hel dags arbejde og lidt til.
>
>
> Jeg ved ikke om jeg kan tilbyde en god forklaring, men,
>
> Hver gang du kalder push_back kan du resikere at den flytter rundt på
> objekterne i din vector, dvs. alle referencer du måtte have til objekter
> i vectoren vil være invalide. (Som en sidebemærkning kan det noteres at
> det ikke vil ske hvis du kalder pop_back.)
>
> I praksis er en vector arrangeret som ét stort hukommelses område, hvis
> den får brug for mere plads vil den allokere mere plads og flytte de
> eksisterende elementer over i den nye plads.
> Det sker for at få en vector til at opføre sig som et array.
> I nogle tilfælde vil den reservere plads til et antal elementer
> af gangen for at undgå at skulle flytte alle elementer på én gang,
> men det kan man ikke stole på, og man ved ikke hvornår den har
> flyttet, kun hvornår det måske er sket.
>
> Hvis det er et problem kan du reservere plads til alle elementer inden
> du starter, bruge en vector af pointere, eller du kan bruge en
> std::list. I stedet for at gemme pointere til elementer i din
> vector (_goal og _source) kunne du bruge index'er.
>

Ja, det var en udmærket forklaring, men hold da helt fast hvor giver det
en dårlig performance i det lange løb - men så kan man selvfølgelig
altid allokere det man ved man får brug for.

Du må da meget gerne løse mit prioritetskø problem --- det driller endnu
mere! Har erstattet med en vector af pointere.

Mvh / Preben

---

Preben wrote:
> Ja, det var en udmærket forklaring, men hold da helt fast hvor giver det
> en dårlig performance i det lange løb - men så kan man selvfølgelig
> altid allokere det man ved man får brug for.

Hvis performance er det vigtigste er det nok ikke vectorer
man skal bruge.

--
Absolutely not the best homepage on the net:
http://home20.inet.tele.dk/midgaard
But it's mine - Bertel

---

"Bertel Brander" <bertel@post4.tele.dk> wrote in message
news:447df5f3$0$210$edfadb0f@dread16.news.tele.dk...
> Preben wrote:
>> Ja, det var en udmærket forklaring, men hold da helt fast hvor giver det
>> en dårlig performance i det lange løb - men så kan man selvfølgelig altid
>> allokere det man ved man får brug for.
>
> Hvis performance er det vigtigste er det nok ikke vectorer
> man skal bruge.

Det kommer jo an på hvilken form for performance man har brug for.
Til random access findes der ikke noget hurtigere en vector.


Venlig hilsen

Mogens Hansen

---

"Preben" <64bitNoNoNoSPAM@mailme.dk> wrote in message
news:447dead9$0$15789$14726298@news.sunsite.dk...

[8<8<8<]
> Ja, det var en udmærket forklaring, men hold da helt fast hvor giver det
> en dårlig performance i det lange løb

Nej - ikke hvis man har valgt den rigtige container type til opgaven.

> - men så kan man selvfølgelig altid allokere det man ved man får brug for.

Ja, det er en mulighed.
Hvis man ikke indsætter tit er det heller ikke et problem.

Hvis man har et performance problem med at indsætte i en vector, hvor man
ikke kan afgøre den endelige størrelse, så skal man bruge en deque i stedet
for vector.
Den har konstant tids indsætning i begyndelsen og slutningen af containeren,
men lineær tid i midten.
Den har konstant tid tilgang til et vilkårigt element.

Men i modsætning til vector ligger alle elementer ikke i sekventiel
hukommelse, og tilgangen er ikke helt lige så hurtig så hurtig som vector.

Venlig hilsen

Mogens Hansen

---

Preben wrote:
> Bertel Brander wrote:

>> Hvis det er et problem kan du reservere plads til alle elementer inden
>> du starter, bruge en vector af pointere, eller du kan bruge en
>> std::list. I stedet for at gemme pointere til elementer i din
>> vector (_goal og _source) kunne du bruge index'er.
>>
>
> Ja, det var en udmærket forklaring, men hold da helt fast hvor giver det
> en dårlig performance i det lange løb - men så kan man selvfølgelig
> altid allokere det man ved man får brug for.

Det var selvfølgelig rart, hvis vectorer var lidt smartere:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html

> Du må da meget gerne løse mit prioritetskø problem --- det driller endnu
> mere! Har erstattet med en vector af pointere.

Jeg kender ikke dit specifikke problem, men en jeg har skrevet
en high-performance queue for et par år siden:

http://www.cs.aau.dk/~nesotto/pie/pie.tgz

Kig efter filen pie/pm/nearest_queue.hpp for at få et indblik
i teknikken.

-Thorsten