Jump to content
  • Advertisement
Sign in to follow this  
JonConley

Heap (Looking for crits)

This topic is 2776 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been programming awhile and am in a Computer Science program. Gone to several competitions (won CCSC at Franklin college this year).

Basically looking for crits / potential speed ups in my heap. Got bored, never implemented one so decided to do it today.

main (test case with time)

#include <iostream>
#include <ctime>
#include <Windows.h>
#include "Heap.h"

using namespace std;

int main()
{
Heap<int> mine;
srand(time(NULL));
time_t begin, end;
begin = GetTickCount();
for(unsigned int i = 0; i < 100000; i++)
{
mine.push(rand());
}
end = GetTickCount();
cout << end - begin << endl;
for(unsigned int i = 0; i < 100000; i++)
{
mine.pop();
}
end = GetTickCount();
cout << end - begin << endl;
return 0;
}



Heap.h

#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

template<typename H>
class Heap
{
static bool comp(const H& a, const H& b)
{
return a > b;
}
inline void filterUp()
{
//a nodes parent is (n-1)/2 and since n is SIZE -1, substitute
//and get (SIZE-2)/2
unsigned int n(SIZE -1), nPar( (SIZE-2)/2);
H temp;
while(n > 0 && Heap<H>::comp(nodes[n], nodes[nPar]) )
{
temp = nodes[nPar];
nodes[nPar] = nodes[n];
nodes[n] = temp;
n = nPar;
nPar = (n - 1) /2;
}
}//filter

inline void filterDown()
{
if(SIZE <= 1)
return;
//initialize when created (saves a copy)
unsigned int n(0), nChi1(1), nChi2(2), toSwap;
H temp;

while(nChi1 < SIZE)
{
if(nChi2 < SIZE)
{
//if compare function returns true than use nChi1 as index
toSwap = comp(nodes[nChi1], nodes[nChi2]) ? nChi1 : nChi2;
if(comp(nodes[toSwap], nodes[n]))
{
//temp variable
temp = nodes[toSwap];
nodes[toSwap] = nodes[n];
nodes[n] = temp;
n = toSwap;
//New child index
nChi1 = n*2+1;
nChi2 = n*2+2;
}//if statement
else
break;
}//if child 2 is big enough
else
{
//now if there is no 2nd child to current parent
//check compare, if true swap
if(comp(nodes[nChi1], nodes[n]))
{
temp = nodes[nChi1];
nodes[toSwap] = nodes[n];
nodes[n] = temp;
break;
}//if statement
break;
}
}
}
unsigned int SIZE;
vector<H> nodes;
public:
Heap(unsigned int Reserve = 30);
Heap(const H& Data, unsigned int Reserve = 30);
Heap(H Data, unsigned int Reserve = 30);
Heap(const vector<H>& Data);
void push(H& Data);
void push(H Data);
void pop();
const H& front()
{
if(SIZE > 0)
return nodes[0];
}
~Heap(void);
};

#include "Heap.inl"



Heap.inl (because vs 2008 doesn't have export working it seems so just tossed it in another file without .cpp)

#pragma once
#include "Heap.h"

template<typename H>
inline Heap<H>::Heap(unsigned int Reserve) : SIZE(0)
{
nodes.reserve(Reserve);
}
template<typename H>
inline Heap<H>::Heap(const H& Data, unsigned int Reserve) : SIZE(1)
{
nodes.reserve(Reserve);
nodes.push_back(Data);
}
template<typename H>
inline Heap<H>::Heap(H Data, unsigned int Reserve) : SIZE(1)
{
nodes.reserve(Reserve);
nodes.push_back(Data);
}
template<typename H>
inline Heap<H>::Heap(const vector<H>& Data)
{
//Copy the vector in and sort it (sorted high to low will give a heap)
SIZE = Data.size();
nodes.reserve(SIZE*2);
//copy Data into nodes
copy(Data.begin(), Data.end(), nodes.begin());
//Sort to create a heap
sort(nodes.begin(), nodes.end, heap::comp);
}
template<typename H>
inline Heap<H>::~Heap(void)
{
}
template<typename H>
void inline Heap<H>::push(H& Data)
{
SIZE++;
nodes.push_back(Data);
filterUp();
}
template<typename H>
void inline Heap<H>::push(H Data)
{
SIZE++;
nodes.push_back(Data);
filterUp();
}

template<typename H>
void inline Heap<H>::pop()
{
//swap the front with the back
swap((*nodes.begin()), (*(nodes.end()-1)));
nodes.pop_back();
SIZE --;
filterDown();
}





Also I understand sorting isn't the best way to create a heap from a vector, but that wasn't my main priority. Main priority was to get push and pop working quickly.

From AMD's Profiler
CS:EIP Symbol + Offset 64-bit Timer samples
0x11414c0 Heap<int>::filterDown 85.71
0x11413d0 Heap<int>::filterUp 7.14
0x1141110 main 3.57
0x11412b0 Heap<int>::pop 3.57

4 functions, 20 instructions, Total: 28 samples, 100.00% of shown samples, 2.79% of total session samples
16 ms for all the pushes to happen
47 for everything to happen.

Share this post


Link to post
Share on other sites
Advertisement
Interesting, but off hand I see a few critical flaws. They are flaws in what you are doing, not flaws in the code itself, which I'll let others point out.

Premature optimization. The chunk of code is simply not going to be a bottleneck in the real world. Granted, you wouldn't want to introduce pessimizations to it, but even a simple implementation should have excellent real-world performance. It is an optimization of the wrong thing. The correct optimization would be at other levels of the program.

Invalid profile results. This goes along closely with the previous one. Your normal use case is going to be a tight loop that fits in the CPU cache and the compiler can trivially optimize. To get a realistic view of performance you need to do some serious work with it.

Duplicated functionality. This is re-inventing the wheel. Instead of offering an improvement, the code will have TWO versions instead of just one. Given the choice between the standard library and a hacked-together template, I'd pick the standard library. Look at the C++ language's push_heap(), pop_heap(), make_heap(), and sort_heap() functions. It also looks like you may have a few more comparisons than the maximums guaranteed by the standard.

Other less-critical flaws are that your code has more exceptional behavior (="more likely to generate exceptions") than the built in versions, such as creating and assigning to temporaries rather than std::swap(). It is generally a flaw to combine two jobs of memory/container management and data structure management; if you wanted a sorted container then pick an associative container that does the right thing by default.

Share this post


Link to post
Share on other sites
Don't use inline, templates are inline expanded anyway.

std::vector is used, yet unsigned int is used for iteration. Elements in vector are indexed by vector<T>::size_type, which may be larger than int.

Quote:
temp = nodes[nPar];
nodes[nPar] = nodes[n];
nodes[n] = temp;
See std::swap.

Quote:
static bool comp(const H& a, const H& b)
Make this a free function.

Quote:
inline void filterUp()
{
//a nodes parent is (n-1)/2 and since n is SIZE -1, substitute
//and get (SIZE-2)/2
unsigned int n(SIZE -1), nPar( (SIZE-2)/2);
Considering SIZE is unsigned, what happens if SIZE is 1? Also, ALLCAPSNAMES are usually reserved for macros or constants.

Quote:
const H& front()
{
if(SIZE > 0)
return nodes[0];
}
This shouldn't even compile since it doesn't always return.

Quote:
using namespace std;
Don't put this into global scope, definitely not into headers, maybe into cpp. Inside function body it's ok.

Quote:
nChi1 = n*2+1;
nChi2 = n*2+2;
I didn't go through code, but indexing is usually zero-based, so children are 2n and 2n+1. Maybe this is something else though.


Put these to on top of main cpp file:
Quote:
#define _HAS_ITERATOR_DEBUGGING 0
#define _SECURE_SCL 0
Then run the benchmarks again.

Share this post


Link to post
Share on other sites
About the front yeah I was thinking that before, then got side tracked and never went back to it. The premature optimization isn't for anything. It is more of to get insight on what I am doing one way, and should be done a different way. Will fix those items and rerun benchmarks when I can.

Frob, I am not using this for anything, just doing it as an exercise since I've never programmed a heap (I like to implement things to understand them better, although a heap is relatively easy it was just for a quick exercise).

Thanks for the replies.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!