CODEWITHSUNDEEP
c++calgorithm
czar x
czar x

Reputation: 448

best alternative algo for sort/manipulate/sort

I need a better algo for following situation: Log file containing data from two sensors i.e. number of entries are available for given time and are appended one below other e.g.

time < no. entries 1> < no. entries 2>

2

3

3

time < no. entries 1> < no. entries 2>

..

..

Currently i can read the file and after dynamically allocating the memory i built an list, which is sorted. Certain manipulation at the top 3 entries which may result in decrease the values currently it posses. After this i need to sort again and manipulate until one of the array is completely empty.

Please suggest a better algorithm for this situation since the continuous sorting is taking long time after every manipulation. Can i use b-trees or any other method to reduce the time? Also the file can go beyond 100MB so please suggest optimization for reading and building a list of array.

Upvotes: 1

Views: 266

Answers (3)

vvnraman
vvnraman

Reputation: 1343

You would need to implement a custom priority queue for your needs. You can implement a binary-heap which would act as your priority queue. Read more about on this Wikipedia Page.

The cost of forming the heap is O(n) from a list of n elements.

In general, binary-heaps only expose the methods push(), pop(), front() or peek() to the programmer which have O(log n) complexity for insertion and deletion. They have the methods heap-up() or heap-down() as private, which are called internally by push() and pop() respectively, and thus they cause the heap property to be maintained.

I'm asking you to implement a custom priority queue as you need to manipulate the entries of the queue, which may cause the order of elements to change. You can use an std::vector as your container for the Priority Queue. You would need the following extra stuff:

  • Provide an overloaded operator [] which returns a const reference to the indexed element.
  • If you decide to alter the key or the rank of an element which would alter the order of elements, you can do so by providing a replace(int iIndex, const Type &item) method which replaces the element at iIndex with the element item but preserves the ordering of elements.

Here is what it may look like:

template <class Type>
bool PriorityQueue<Type>::Replace(int iIndex, const Type &item ){
    if ( iIndex < m_itemList.size() ) {        
        if ( item < m_itemList[ iIndex ] ) {
            m_itemList[ iIndex ] = item;
            HeapUp( iIndex );
        }
        else {
            m_itemList[ iIndex ] = item;
            HeapDown( iIndex );
        }
    }
    else {
        return false;
    }
}

So the replace() method automatically calls the heapUp() or the heapDown() internally to preserve the heap property. The complexity of this would again be O(log n) at worse.

The operator [] should return a const reference to the program so that you don't abuse it accidentally and corrupt your heap ordering. The only change in the heap should be done by the replace() method.

Upvotes: 1

StilesCrisis
StilesCrisis

Reputation: 16300

Have you looked at std::set, std::map, and their multi cousins? These containers always stay sorted no matter what order you insert or remove elements, and they are easy to use.

Upvotes: 0

caf
caf

Reputation: 239251

It's a little hard to tell exactly what you're doing, but it sounds like you want a data structure where is is efficient to:

  • Find & remove the top N entries sorted by some key;
  • Insert an entry.

The name for this is a Priority Queue. There are many ways to implement an efficient priority queue.

Upvotes: 0

Related Questions