Re: [Boost-users] complexity problem using multi_index insert()

Subject: Re: [Boost-users] complexity problem using multi_index insert()
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2010-02-28 06:46:00

Andrew Kokkalis <andrewkokkalis <at> gmail.com> writes:
> 
> Joaquín M López writes:
> 
> > I think I'm misunderstanding this: do you mean your container
> >  is holding 9500! elements? As 9500! ~ 9*10^33664 this can't possibly
> > be the case.
> 
> Obviously it is not factorial! Once again i was wrong and fool
> The elements in my container are 46,238,536Â  (n^2 - n ) / 2Â  so complexity
> for storage is O(n^2)And the problem is that inserting those few elements
> into the multi_index container takes almost 9 minutes.
> As I said before I'm using "std::pair<iterator,bool>
> insert(const value_type& x);".Is there  a faster way to insert?

I take it you're inserting the elements in some sort
of double loop like this, right?

for(int i=0;i<cluster1_elements;++i){
  for(int j=0;j<cluster2_elements;++j){
    container.insert(cluster_d(i,j,distance(i,j)));
  }
}

If so, note that the elements are inserted in the same
order as maintained by your first index, so you can take
advantage of hinted insertion:

    container.insert(cluster_d(i,j,distance(i,j)),container.end());

If the double loop is set up the other way around, i.e. first
cluster2 then cluster1, please reverse it. This should reduce
insertion times by a noticeable amount (I dare say 25% or so,
but you'll be able to report back when you try it).

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo