
平台论坛博客文库

› 论坛 › 程序设计 › C/C++ › 求解一个空间位置的算法

1 23 / 3 页

求解一个空间位置的算法 [复制链接]

windyrobin

稍有积蓄

论坛徽章:: 0

21楼 [报告]

发表于 2009-03-29 13:53 |只看该作者

考虑过把二维映射为一维，但如果不离散化，会占用太多空间，
如果离散化，就难以支持修改操作 ,最难的地方是如何保存window id,
rmq .树状数组貌似也不太合适...

抛砖引玉，大牛指点...

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

太平绅士

家境小康

论坛徽章:: 0

22楼 [报告]

发表于 2009-03-29 14:39 |只看该作者

原帖由 windyrobin 于 2009-3-29 13:42 发表
复习了下算法，搞到凌晨2点，写了个简陋的线段树
测试发现，在我提供的例子中，速度是普通版的1. 8倍左右，
我用vector存储 window id , 添加、删除修改操做比较低效，
换成set 应该能大幅提高修改操作效 ...

学习了..
这个实现看起来比我的有效率一点, 构造线段树比较快.

我用线段的端点, 作为线段树的节点, 利用std::map作为这些节点的容器,
这样构造了一个变种的动态线段树. 但是初始化的动作太慢了.
查找的效率有一点提高, 不足以弥补构造花费的时间.

贴代码, 仅实现了1维。
最开始使用set保存线段，实现了插入/删除，不过构造线段树的时间更加惨不忍睹。
后来改成vector保存线段，能构造的快一点，仅有插入。

#include <windows.h>
#include <vector>
#include <map>
#include <set>
#include <list>
struct u_line
{
inline u_line( int x, int y )
: m_x( x )
, m_y( y )
{
}
int m_x;
int m_y;
bool operator<( u_line const &right ) const
{
if( this->m_y < right.m_y )
return true;
else if( this->m_y > right.m_y )
return false;
else if( this->m_x < right.m_x )
return true;
else
return false;
}
};
struct u_point
{
int start_pos;
//std::set< u_line > lines;
std::vector< u_line > lines;
};
void dump_point( int index, std::map< int, u_point > const &points )
{
printf( "%d=====\n", index );
for( std::map< int, u_point >::const_iterator itr = points.begin( );
itr != points.end( );
++itr )
{
printf( "Point: %d\n", itr->second.start_pos );
for( std::vector< u_line >::const_iterator itr_line = itr->second.lines.begin( );
itr_line != itr->second.lines.end( );
++itr_line )
{
printf( "[%d,%d] ", (itr_line)->m_x, (itr_line)->m_y );
}
printf( "\n" );
}
}
#if 0
void del_line( std::map< int, u_point > &points, u_line const &line )
{
std::map< int, u_point >::iterator itr = points.upper_bound( line.m_x );
if( itr == points.end( ) || itr == points.begin( ) )
{
printf( "del_line: %d %d, Point: NOT FOUND0\n", line.m_x, line.m_y );
return;
}
--itr;
if( itr->second.start_pos != line.m_x )
{
printf( "del_line: %d %d, Point: NOT FOUND1\n", line.m_x, line.m_y );
return;
}
while( itr != points.end( ) && itr->second.start_pos <= line.m_y )
{
std::map< int, u_point >::iterator itr_this = itr;
++itr;
if( itr_this->second.start_pos < line.m_y )
itr_this->second.lines.erase( line );
if( itr_this->second.lines.size( ) == 0
&& itr_this != points.begin( ) )
{
std::map< int, u_point >::iterator prev = itr_this;
--prev;
if( prev->second.lines.size( ) == 0 )
points.erase( itr_this );
}
}
dump_point( __LINE__, points );
}
#endif
void add_line( std::map< int, u_point > &points, u_line const &line )
{
/* <0> Insert end point */
//printf( "Insert %d\n", line.m_y );
u_point point1;
point1.start_pos = line.m_y;
std::pair< std::map< int, u_point >::iterator, bool > insert1 =
points.insert( std::make_pair( line.m_y, point1 ) );
std::map< int, u_point >::iterator itr1 = insert1.first;
//dump_point( __LINE__, points );
if( insert1.second )
{/* A new point was inserted, any lines on previous point need to insert to the line array of new point */
std::map< int, u_point >::iterator prev = itr1;
if( prev != points.begin( ) )
{
--prev;
//itr1->second.lines.insert( prev->second.lines.begin( ), prev->second.lines.end( ) );
itr1->second.lines = prev->second.lines;
}
}
//dump_point( __LINE__, points );
/* <1> Insert start point. */
//printf( "Insert %d\n", line.m_x );
u_point point0;
point0.start_pos = line.m_x;
std::pair< std::map< int, u_point >::iterator, bool > insert0 =
points.insert( std::make_pair( line.m_x, point0 ) );
std::map< int, u_point >::iterator itr0 = insert0.first;
//dump_point( __LINE__, points );
if( insert0.second )
{/* A new point was inserted, any lines on previous point need to insert to the line array of new point */
std::map< int, u_point >::iterator prev = itr0;
if( prev != points.begin( ) )
{
--prev;
//itr0->second.lines.insert( prev->second.lines.begin( ), prev->second.lines.end( ) );
itr0->second.lines = prev->second.lines;
}
}
//dump_point( __LINE__, points );
/* <2> Append line to the new added point */
for( std::map< int, u_point >::iterator itr = itr0;
itr != itr1;
++itr )
//itr->second.lines.insert( line );
itr->second.lines.push_back( line );
//dump_point( __LINE__, points );
}
bool search_point( std::map< int, u_point > &points, int pos, int &found_num )
{
std::map< int, u_point >::iterator itr = points.upper_bound( pos );
if( itr == points.end( ) || itr == points.begin( ) )
{
//printf( "Search: %d, Point: NOT FOUND\n", pos );
return false;
}
--itr;
//printf( "Search: %d, Point: %d, size = %d\n", pos, itr->second.start_pos, itr->second.lines.size( ) );
for( std::vector< u_line >::const_iterator itr_line = itr->second.lines.begin( );
itr_line != itr->second.lines.end( );
++itr_line )
{
++found_num;
//printf( "[%d,%d] ", (itr_line)->m_x, (itr_line)->m_y );
}
//printf( "\n" );
return true;
}
int main( int argc, char **argv )
{
#define TEST_SIZE 10000
#define MAP_SIZE 65536
#define LOOP_NUM 10000
/* <0> 直接在vector中查找 */
std::vector< u_line > lines;
{
DWORD ticks = ::GetTickCount();
for( int i = 0; i < TEST_SIZE; ++i )
{
u_line line( rand( ) % MAP_SIZE, rand( ) % MAP_SIZE );
if( line.m_x > line.m_y )
std::swap( line.m_x, line.m_y );
if( line.m_x < line.m_y )
lines.push_back( line );
}
printf( "create time %d\n", (int)( ::GetTickCount( ) - ticks ) );
}
{
int found_num = 0;
DWORD ticks = ::GetTickCount();
for( int i = 0; i < LOOP_NUM; ++i )
{
int pos = rand( ) % MAP_SIZE;
for( std::vector< u_line >::iterator itr = lines.begin( );
itr != lines.end( );
++itr )
{
if( itr->m_x <= pos && itr->m_y > pos )
++found_num;
}
}
printf( "found_num = %d, search time = %d\n", found_num, (int)( ::GetTickCount( ) - ticks ) );
}
/* <1> 利用map构造的线段树中查找 */
std::map< int, u_point > points;
{
DWORD ticks = ::GetTickCount();
for( int i = 0; i < TEST_SIZE; ++i )
{
u_line line( rand( ) % MAP_SIZE, rand( ) % MAP_SIZE );
if( line.m_x > line.m_y )
std::swap( line.m_x, line.m_y );
if( line.m_x < line.m_y )
add_line( points, line );
}
printf( "create time %d\n", (int)( ::GetTickCount( ) - ticks ) );
}
{
int found_num = 0;
DWORD ticks = ::GetTickCount();
for( int i = 0; i < LOOP_NUM; ++i )
{
int pos = rand( ) % MAP_SIZE;
search_point( points, pos, found_num );
}
printf( "found_num = %d, search time = %d\n", found_num, (int)( ::GetTickCount( ) - ticks ) );
}
return 0;
}