CODEWITHSUNDEEP
arraysalgorithmdata-structuresmergetheory
cpp_noname
cpp_noname

Reputation: 2071

Efficiently Merging Adjacent Blocks

This is what I am trying to do: I have a routine called merge() that regularly gets called. Its task is to merge data structures called "Block" whose content is a range of integers represented by "s_idx" and "e_idx", denoting the starting index and the end index, respectively. Adjacent blocks are blocks whose ranges can be combined into a new contiguous range. For example, block 3 with range (25,32) and block 4 with range (33,40) are adjacent and their ranges can therefore be combined to produce a new contiguous range (25,40). So at the end, there will be only one block left, having combined all the individual blocks to produce the range (0,N-1), where N is the total number of blocks.

My question is : is there any efficient algorithm to perform such an operation?

The current implementation uses an O(N^2) algorithm, which slows down dramatically as the number of blocks grows.

for( int i=0 ; i<_merge_list.max()-1 ; i++ )
    {
        for( int j=i+1 ; j<_merge_list.max() ; j++ )
        {
            if( _merge_list.exist(i) && _merge_list.exist(j) )
            {
                if( _merge_list[i]->get_end_idx() + 1 ==    _merge_list[j]->get_start_idx() )
                {
                    _merge_list[i]->set_end_idx( _merge_list[j]->get_end_idx() );
                    _merge_list[i]->set_link( _merge_list[j]->get_block_idx() );


                                    perform(_merge_list[i]);

                    _merge_list.remove(j);          
                }
            }
        }

    }

Upvotes: 1

Views: 391

Answers (1)

NominSim
NominSim

Reputation: 8511

Are all your blocks guranteed to be contiguous? If that's the case it should be trivial to find min,max indices in O(N) time then create one final block, otherwise you could sort the blocks first then merge O(NlogN) + O(N) = O(NlogN)

If you maintain the blocks in a sorted manner, it only takes O(N) time to merge a block. If you have them all at once then you sort the array of blocks first, then merge. If you get them piecemeal you merge into the array of blocks in a way that maintains the sorted ordering.

Upvotes: 1

Related Questions