Re: Problem with a list of times

Posted by Luigi Ballabio-2 on Oct 02, 2002; 1:22am
URL: http://quantlib.414.s1.nabble.com/Problem-with-a-list-of-times-tp2221p2228.html

At 04:46 PM 10/1/02 +0200, Perissin Francesco wrote:

>I am playing around with QL in order to get the pricing of a range accrual
>on interest rates, using the tree pricing on one factor models. I am stuck
>because of the following problem: when preparing the list of times to be
>given to the model, it seems that the std::list<Time> is not able to sort
>them efficiently!!!?!! (after waiting 1 minute, I realized that this much
>more cpu consuming that the pricing itself!!)
>
>The list contains no more than 2500 times, i.e. the starting and ending
>times of a 5 years daily range accrual. Obviously, many of them are equal,
>and should be removed using the unique() method.
>
>The questions are:
>+ is it necessary that the tree is built using all of these dates? (they are
>relevant in order to calculate the digital options...)
>+ is there a way to sort them more efficiently? Maybe I should insert them
>in the correct place of the list, one by one?

Ciao Francesco,
         hmm, this is strange---it shouldn't take that long. And you
shouldn't be forced to insert them at the right place---which is a sorting
algorithm in its own right, but not the most efficient, and besides, I
suspect you would implement it somewhat less efficiently than your
compiler's implementor :)

Are you using something like

std::list<Time> l;
for (... 2500 times ...)
     l.push_back(time);
l.sort()

? If so, does it get better if you instead use

std::deque<Time> q;
for (... 2500 times ...)
     q.push_back(time);
std::sort(q.begin(),q.end());

Later,
         Luigi