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

Subject: Re: [Boost-users] complexity problem using multi_index insert()
From: Andrew Kokkalis (andrewkokkalis_at_[hidden])
Date: 2010-02-28 05:52:05

2010/2/28 Andrew Kokkalis <andrewkokkalis_at_[hidden]>

> > I'm using them for the process of clustering a huge amount of data
>> > (posts from an aple blog from the last 4-5 years)I'm counting
>> > Euclidean distance between two clusters, which I store in a multi_index
>> > container like the above
>> > [...]
>> > My problem is that I have to count 9500! (! = factorial) distances,
>> > and store them in the multi_index container.
>>
>> 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.
>>
>
> Is it impossible for a container such as the above to hold that much
> elements?
> during insertion ram is over 2.4 gb (only for this program).
>
> I'm running now the program with different parameters and see the number of
> elements that are stored.
>

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?