Excessive long time on quicksorting

This is a discussion on Excessive long time on quicksorting within the C++ Programming forums, part of the General Programming Boards category; I'm using Kruskal's algorithm for minimal cost tree to solve a high school c++ problem. The graph is represented in ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    48

    Excessive long time on quicksorting

    I'm using Kruskal's algorithm for minimal cost tree to solve a high school c++ problem.
    The graph is represented in an array of arcs. My problem is rather odd: quicksort takes an awful lot of time (17 sec on an AMD Athlon LE-1640 2.59Ghz) sorting the array by its .c member value. What's wrong with my code?
    The values i'm testing for are: N(number of nods in the graph) = 500, M(number of arcs in the graph) = 10000.
    LE: Solved - The quicksort algorithm's implementation was wrong - the recursive calls should be made outside the while loop.

    Code:
     
    #include <fstream>
    
    using namespace std;
    ifstream i_file("retea.in");
    ofstream o_file("retea.out");
    
    #define Nmax 1001
    #define Mmax 20001
    #define Kmax 50001
    struct Conexiune
    {
    	int x;
    	int y;
    	double c;
    };
    void Quicksort(int left, int right, Conexiune Vector[])    //<--takes 17 sec to sort the array
    {
    	int i = left;
    	int j = right;
    	Conexiune temp;
    	Conexiune pivot = Vector[(i+j)/2];
    	while(i<=j)
    	{ 
    		while(Vector[i].c<pivot.c) i++;
    		while(Vector[j].c>pivot.c) j--;
    		
    		if(i<=j)
    		{
    			temp = Vector[i];
    			Vector[i] = Vector[j];
    			Vector[j] = temp;
    			i++;
    			j--;
    		}
             }  //<---Fixed bracket :)
    		if(left < j)
    		{
    			Quicksort(left,j, Vector);
    		}
     		if(i<right)
    		{
    			Quicksort(i, right, Vector);
    		}
    		
    	
    
    
    	
    }
    
    
    Conexiune Muchie[Mmax];
    int N, M, K;
    int Familie[Nmax];
    int Selectat[Mmax];
    
    int main()
    {
    	
    	int i, j;	
    	i_file>>N>>M>>K;
    	for(i=0; i<M; i++)
    	{
    		i_file>>Muchie[i].x>>Muchie[i].y>>Muchie[i].c;
    		if(i<N)
    		{
    			Familie[i+1] = i+1;
    		}
    		Selectat[i]= 0;
    	}
    	
    
    	Quicksort(0, M-1,(Conexiune*) Muchie);
    	
    	i=N-1;
    	while(i>0)
    	{
    		for(j=0; j<M; j++)
    		{	
    
    			if(Familie[Muchie[j].x]!=Familie[Muchie[j].y])
    			{								
    				int min, max;
    				
    				Selectat[j] = 1;
    				if(Familie[Muchie[j].x] < Familie[Muchie[j].y])
    				{				
    					min = Familie[Muchie[j].x];
    					max = Familie[Muchie[j].y];
    				}
    				else
    				{
    					max = Familie[Muchie[j].x];
    					min = Familie[Muchie[j].y];
    				}
    				for(int z = 1; z<=N; z++)
    				{
    					if(Familie[z] == max)
    					{
    						Familie[z]= min;
    					}
    
    				}
    				i--;
    				if(i<0) break;
    			}
    		}
    	}
    
    	double suma=0;
    	double Vector[Kmax];
    	int counter = 1;
    	int localcounter = 0;
    	Vector[0] = 0;
    	double max =0;
    	for(i=0; i<M; i++)
    	{
    		if(Selectat[i] == 1)
    		suma = suma + Muchie[i].c;
    		if(Selectat[i] == 1 && max < K)
    		{
    			
    			localcounter =0;
    			for(j=0; j<counter; j++)
    			{
    				if(Muchie[i].c + Vector[j] > max )
    				{
    
    					max = Muchie[i].c + Vector[j];
    					Vector[localcounter+counter] = Muchie[i].c + Vector[j];
    					localcounter++;
    					
    				}
    			}
    			counter = counter + localcounter;
    		}
    
    	}
    	o_file<<suma<<"\n"<<counter;
    	
    
    
    	return 0;
    }
    Last edited by like_no_other; 03-24-2010 at 01:07 AM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,544
    > temp = Vector[i];
    > Vector[i] = Vector[j];
    > Vector[j] = temp;
    The size of your struct (approx 16 bytes) probably means the compiler is generating calls to memcpy() to perform your struct assignments.

    Calls to memcpy() for small amounts of memory are expensive in relation to the amount of useful work done.

    Profile how many times you actually hit these 3 lines.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    48
    It steps 341125075 times (for a 10000 long array) through those 3 lines - this is way past O(n log n) complexity.
    Last edited by like_no_other; 03-23-2010 at 03:34 PM.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Times that large for such a small struct to me make it jump out right away that it cannot simply be inefficiency of individual operations.
    Plugging this code directly into my sorting algorithm demo program indicated that it is far worse than O(n*n) running time, and in fact looks somewhat similar in operation to Stooge Sort!
    There was clearly some serious algorithmic flaw here in this implementation.

    It turns out that the problem is that the recursive calls are being made from inside the loop. These calls need tobe made after the while loop. Fixing that makes it run as expected. So you only had one bracket in the wrong place.
    Last edited by iMalc; 03-24-2010 at 12:35 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    48
    Thanks, that solved the problem.
    As to what Salem wrote about memcpy() calls being inefficient for small chunks of data, would it make any noticeable difference to define a custom assignment operator for manually copying each member - my execution time limit is 0.6 sec?

  6. #6
    Registered User
    Join Date
    Mar 2010
    Posts
    18
    A self-defined operator most likely won't improve efficiency, on the contrary: unnecessary assignments can be optimized away with compiler-generated operator=, but since the compiler doesn't know what your operator= does, it can't optimize it away (who knows, perhaps you increment some global variable, or write a letter to the pope every time operator= is called). Low-level efficiency you can worry about after profiling, anyways. But you might see an essential improvement in your algorithm if you don't blindly take the value in the middle of your array, but take, say, 5 random values and use the median of this sample, and don't recurse if your array has a length of some fixed size, say 10. Or even better, use std::sort(), which is so highly optimized that you won't come near it with home-brew code, most likely. Finally, if you did what you algorithmically could, play around with compiler optimizations before doing dirty work like low-level optimization yourself. It (a) saves your time and (b) preserves readability/maintainability of your code.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    No, there is no need to define a custom assignment operator.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Sep 2008
    Posts
    48
    Problem solved, the code performs beautifully with a worst execution time of 0.21 sec.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to time how long a program takes to run?
    By advancedk in forum C Programming
    Replies: 2
    Last Post: 08-18-2008, 07:50 PM
  2. Time to seconds program
    By Sure in forum C Programming
    Replies: 1
    Last Post: 06-13-2005, 08:08 PM
  3. Quick, Partiotion, and Insertion Sort
    By silicon in forum C++ Programming
    Replies: 0
    Last Post: 05-18-2005, 08:47 PM
  4. The space time continueimnms mm... (rant)
    By Jeremy G in forum A Brief History of Cprogramming.com
    Replies: 32
    Last Post: 06-27-2004, 01:21 PM
  5. convert unix long time to get hour
    By huskers in forum C Programming
    Replies: 11
    Last Post: 05-09-2002, 07:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21