Problem with a list of times

[Perissin Francesco]

Hi,

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?

Thanks

Francesco
--
############################### DISCLAIMER #################################

This  message  (including  any  attachments)  is  confidential  and  may be
privileged.  If you have received it by mistake please notify the sender by
return  e-mail  and  delete this message from your system. Any unauthorised
use  or  dissemination  of  this  message  in  whole or in part is strictly
prohibited.  Please  note  that e-mails are susceptible to change. Banca del
Gottardo (including  its  group  companies)  shall not be liable for the
improper  or  incomplete  transmission of the information contained in this
communication  nor  for  any delay in its receipt or damage to your system.
Banca del Gottardo  (or its group companies) does not guarantee that the
integrity   of  this  communication  has  been  maintained  nor  that  this
communication is free of viruses, interceptions or interference.

############################################################################

[Luigi Ballabio-2]

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

[Luigi Ballabio-2]

At 10:03 AM 10/2/02 +0200, Perissin Francesco wrote:
>Regarding the sorting issue, I was using the sort method of the list object,
>as in your first example. The deque class works much better, the sorting is
>practically instantaneous (I am not a programmer and this sounds quite
>strange to me, I'd be tempted to say that the sort algorithm of the list has
>been implemented very badly!!).

Ciao,
         it's not that strange if you think that a std::deque has random
access to its elements, while a std::list only has sequential access. In
principle, one could implement a N log N sorting for both (which is what
the Standard suggests). In practice, I guess Microsoft developers didn't
bother...

>The issue concerning the tree pricing of the daily digitals is still open.

Good luck,
                 Luigi

[Perissin Francesco]

Regarding the sorting issue, I was using the sort method of the list object,
as in your first example. The deque class works much better, the sorting is
practically instantaneous (I am not a programmer and this sounds quite
strange to me, I'd be tempted to say that the sort algorithm of the list has
been implemented very badly!!).

The issue concerning the tree pricing of the daily digitals is still open.

Thanks
Francesco
--
############################### DISCLAIMER #################################

This  message  (including  any  attachments)  is  confidential  and  may be
privileged.  If you have received it by mistake please notify the sender by
return  e-mail  and  delete this message from your system. Any unauthorised
use  or  dissemination  of  this  message  in  whole or in part is strictly
prohibited.  Please  note  that e-mails are susceptible to change. Banca del
Gottardo (including  its  group  companies)  shall not be liable for the
improper  or  incomplete  transmission of the information contained in this
communication  nor  for  any delay in its receipt or damage to your system.
Banca del Gottardo  (or its group companies) does not guarantee that the
integrity   of  this  communication  has  been  maintained  nor  that  this
communication is free of viruses, interceptions or interference.

############################################################################

[Jens Thiel]

Hi,

it's not a bad implementation in the STL, but a bad choice of the programmer
;-)   list, deque, vector, ... have all different strengths and weaknesses.

A list is optimal if your applications needs to insert objects in the middle
of the list and processing is usually done sequentially. Elements in the
list are "chained" with each other. Finding the n-th element (also called
random access) means to walk the whole chain - a rather expensive
operation - and to re-link the chain with the new element (cheap op). Adding
at the end is usually cheap because the container stores pointers to the
first and last element.

A vector on the other hand has instant random access because all elements
are stored sequentially in the memory. Adding at the end _could_ be very
expensive if you did not reserve enough room: the container needs to
allocate new space, copy ALL the existing elements, and then add the new
element with a single operation. Inserting somewhere inbetween is always
expensive, because all elements have to be moved up one place.

So if you just need to store times, and you know the required element count
or have a good guess (add some extra space here), reserve and use a vector
for your data.

Regards,

Jens.


> Regarding the sorting issue, I was using the sort method of the
> list object,
> as in your first example. The deque class works much better, the
> sorting is
> practically instantaneous (I am not a programmer and this sounds quite
> strange to me, I'd be tempted to say that the sort algorithm of
> the list has
> been implemented very badly!!).

[Luigi Ballabio-2]

At 01:44 PM 10/2/02 +0200, Jens Thiel wrote:
>it's not a bad implementation in the STL, but a bad choice of the programmer
>;-)   list, deque, vector, ... have all different strengths and weaknesses.

Just to complete the review: a deque has random access like vector, but
differs in the fact that deque is optimized for adding and removing items
at either end (adding and removing in the middle is expensive, like for
vector.)

Also as a partial excuse for Francesco, the C++ standard says in clause
25.3.1.1 that sort() has complexity N log N, which is the same as std::sort
(clause 25.3.1.1). Were this satisfied by his STL implementation, list
would have been a good choice for sequential insertion + sorting...

Bye,
         Luigi

[Jens Thiel]

> Were this satisfied by his STL implementation, list
> would have been a good choice for sequential insertion + sorting...

Why not encourage people to use STLport, especially with MSVC!?

  http://www.stlport.org/product.html


Jens.

[Luigi Ballabio-2]

At 02:14 PM 10/2/02 +0200, Jens Thiel wrote:
>Why not encourage people to use STLport, especially with MSVC!?
>
>   http://www.stlport.org/product.html

Good point. I'll try that when (if?) I have a little time (which might not
happen for a few weeks...)

Bye,
         Luigi