From fda7e8a2c82b52119c548ba80f5e49bb655986be Mon Sep 17 00:00:00 2001 From: "jan.reininghaus" Date: Fri, 2 May 2014 12:27:08 +0000 Subject: enable pruning in vector_heap.h git-svn-id: https://phat.googlecode.com/svn/trunk@167 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d --- include/phat/representations/vector_heap.h | 41 +++++++++++++++++------------- 1 file changed, 24 insertions(+), 17 deletions(-) (limited to 'include') diff --git a/include/phat/representations/vector_heap.h b/include/phat/representations/vector_heap.h index 6706790..78501f0 100644 --- a/include/phat/representations/vector_heap.h +++ b/include/phat/representations/vector_heap.h @@ -27,16 +27,26 @@ namespace phat { std::vector< dimension > dims; std::vector< column > matrix; - mutable thread_local_storage< column > temp_column_buffer; + std::vector< index > inserts_since_last_prune; -// std::vector< index > steps_since_last_prune; + mutable thread_local_storage< column > temp_column_buffer; protected: - //void _prune( index idx ) - //{ - // temp_column_buffer( ).clear( ); - // _get_col( idx, temp_column_buffer( ) ); - //} + void _prune( index idx ) + { + column& col = matrix[ idx ]; + column& temp_col = temp_column_buffer(); + temp_col.clear(); + index max_index = _pop_max_index( col ); + while( max_index != -1 ) { + temp_col.push_back( max_index ); + max_index = _pop_max_index( col ); + } + col = temp_col; + std::reverse( col.begin( ), col.end( ) ); + std::make_heap( col.begin( ), col.end( ) ); + inserts_since_last_prune[ idx ] = 0; + } index _pop_max_index( index idx ) { @@ -76,7 +86,7 @@ namespace phat { { dims.resize( nr_of_columns ); matrix.resize( nr_of_columns ); - // steps_since_last_prune.assign( nr_of_columns, 0 ); + inserts_since_last_prune.assign( nr_of_columns, 0 ); } // dimension of given index @@ -140,18 +150,15 @@ namespace phat { // adds column 'source' to column 'target' void _add_to( index source, index target ) - { + { for( index idx = 0; idx < (index)matrix[ source ].size( ); idx++ ) { matrix[ target ].push_back( matrix[ source ][ idx ] ); - std::push_heap( matrix[ target ].begin( ), matrix[ target ].end( ) ); + std::push_heap( matrix[ target ].begin(), matrix[ target ].end() ); } - // steps_since_last_prune[ target ] += matrix[ source ].size(); - //if( 2 * steps_since_last_prune[ target ] > matrix[ target ].size() ) { - // // std::cout << "Prune" << std::endl; - // _prune( target ); - // steps_since_last_prune[ target ] = 0; - //} - + inserts_since_last_prune[ target ] += matrix[ source ].size(); + + if( 2 * inserts_since_last_prune[ target ] > ( index )matrix[ target ].size() ) + _prune( target ); } }; } -- cgit v1.2.3