回复 6楼 九转星河
经过测试，结果很意外，使用平衡树反而是最慢的
对于100086个数据：
无优化原始算法，耗时
30.496 秒
使用平衡树容器，耗时 284.290 秒
使用链表作容器，耗时 117.960 秒
用分段数组容器，耗时
3.049 秒
使用简单的数组，耗时
1.412 秒
记得以前听说过一句话“现代CPU上，数组插入数据其实比链表插入数据还快”，看起来真是这样，平衡树因为数据分散，内存页面切换会耗费掉大量时间。
以下是测试代码：
程序代码：
#include <iostream>
#include <random>
#include <functional>
#include <chrono>
#include <algorithm>
#include <set>
#include <deque>
#include <list>
#include <vector>
using namespace std;
size_t foo1( const unsigned a[], size_t size ) // 无任何优化
{
size_t num = 0;
for( size_t i=0; i!=size; ++i )
for( size_t j=i+1; j!=size; ++j )
if( a[j] > a[i] )
++num;
return num;
}
size_t foo2( const unsigned a[], size_t size ) // 平衡树
{
size_t num = 0;
std::multiset<unsigned> buf;
for( size_t i=0; i!=size; ++i )
{
num += distance( buf.begin(), std::lower_bound(buf.begin(),buf.end(),a[i]) );
buf.insert( a[i] );
}
return num;
}
size_t foo3( const unsigned a[], size_t size ) // 链表
{
size_t num = 0;
std::list<unsigned> buf;
for( size_t i=0; i!=size; ++i )
{
auto p = std::lower_bound(buf.begin(),buf.end(),a[i]);
num += distance( buf.begin(), p );
buf.insert( p, a[i] );
}
return num;
}
size_t foo4( const unsigned a[], size_t size ) // 分段数组
{
size_t num = 0;
std::deque<unsigned> buf;
for( size_t i=0; i!=size; ++i )
{
auto p = std::lower_bound(buf.begin(),buf.end(),a[i]);
num += distance( buf.begin(), p );
buf.insert( p, a[i] );
}
return num;
}
size_t foo5( const unsigned a[], size_t size ) // 数组
{
size_t num = 0;
std::vector<unsigned> buf;
buf.reserve( size );
for( size_t i=0; i!=size; ++i )
{
auto p = std::lower_bound(buf.begin(),buf.end(),a[i]);
num += distance( buf.begin(), p );
buf.insert( p, a[i] );
}
return num;
}
void test( unsigned foo(const unsigned [],size_t) )
{
std::array<unsigned,100086> a;
std::generate( begin(a), end(a), std::bind(std::uniform_int_distribution(0u,1000'000'000u),std::default_random_engine(0)) );
std::chrono::time_point<std::chrono::steady_clock> now = std::chrono::steady_clock::now();
unsigned n = foo( &a[0], a.size() );
std::chrono::time_point<std::chrono::steady_clock> cur = std::chrono::steady_clock::now();
std::cout << "result = " << n << ", Takes " << std::chrono::duration_cast<std::chrono::milliseconds>(cur-now).count() << " milliseconds.\n";
}
int main( void )
{
test( foo1 );
test( foo2 );
test( foo3 );
test( foo4 );
test( foo5 );
}
~
