STL list.sort() is really slow!?

[Kanoisa]

Hi guys.

Been coding away today decided that i would update an old program i did a while ago which was the base of an organisor application.

So today i converted it to use STL instead of my hardcoded double linked class. I used list<> as my original implimentation was a double linked list, and vector<>. using the generic sort algorithm. The sort time using a vector for a few hundred objects wasn't too bad. However with the list implimentation it took nearly a second to sort.

Is this normal? considering by comparison my hard coded sort routine did the work in 0.002 seconds (its a big change i know)

So what i would like is can anyone offer some knowledge of what they would expect or if it suggests my hand coded routine is possibly flawed?

I have attached my project files to this if anyone wants a look at what i have done to see if its me and not STL who is to blame. (im using VS2008 but not using any VS specific code)

My next step is considering the speed of my algorithm to see if i make it flexable and then see if it is still faster. All i can reasonably assume right now is that due to the fact that the STL is so felxable they can't do things as convienantly as i can as i have exact knoweladge of the class im sorting.

Any and all comments welcome.

Thanks.

[arkoenig]

Using the standard list.sort algorithm should not take several seconds to sort a few hundred elements, so something must be wrong.

Unfortunately, I can't read the file you attached. When I try, I get "invalid or corrupted"

So perhaps you could post the relevant portions of the code, particularly your comparison function.

[Kanoisa]

Ok

It was done with winrar and my computer downloads and reads that fine but i dont know maybe it done something silly.

The comparison function is as follows.

//comparison function of cTasks for use in the vector or list sort algorithm
bool compareTaskTime(const cTask &one, const cTask &two)
{
	return ( (one.GetTimeT() ) < (two.GetTimeT() ) );
}

//which calls from inside the class definition .h file
u16 GetTimeT(void) const { return m_timeT; }; //u16 is typedef for unsigned short int

//the sort is called in each implimentation as follows 
//my hand written version
istream & C_Day::AddTask(std::istream &in)
{
	m_pTemp = new C_Task;//create new item
	m_pTemp->Load(in);//load members of m_pTemp from file

	if(m_pTaskList==null)//if list is empty
	{
		m_pTaskList = m_pTemp; //item is the base of the list
	}
	else
	{
		AddTaskToList(); //function to sort the item into the appropriate slot in the list
	}
	return in;
}

//in the STL list implimentation
//definition of m_taskList -> std::list<cTask> m_taskList;
std::istream& cDayL::AddTask(std::istream &in)
{
	cTask temp;
	temp.Load(in);
	m_taskList.push_back(temp);
	m_taskList.sort(compareTaskTime);
	return in;
}


//in the STL vector implimentation
//definition of m_taskList -> std::vector<cTask> m_taskList;
std::istream& cDayV::AddTask(std::istream &in)
{
	cTask temp;
	temp.Load(in);
	m_taskList.push_back(temp);
	sort(m_taskList.begin(),m_taskList.end(), compareTaskTime);
	return in;
}

I hope that is enough code to show what you need to see. If you require anything further let me know and ill post additional information.

Thanks for taking time to help so far .

[arkoenig]

My first observation is that you are sorting the entire list (or vector) every time you put a new element there. So if you have 1,000 elements, you're sorting it 1,000 times. It's hard to see how that can be particularly fast.

If you need to put new elements into the data structure while keeping it sorted, why not use a set or multiset?

[Kanoisa]

The reason for sorting it every time is that in actual use. i would add an element (type its details) and then sort it into place. Im thinking that when i know im reading from file i will refrain from sorting untill im done loading. Just need to see how i will do that.

I Think that will remove the inefficiency in the STL list implimentation ill post back in a bit when i get some numbers.

Thanks for the advice.

Finally about the set i dont want to get involved with types i dont know very well and from my background reading, its not worth it in this context and many more reads than inserts done. The vector is the implimentation i will use as upon revisng how the data is used, it is usually read sequentially, insertion to the end of the list followed by a sort which isnt ideal but not bad for vector and i dont forsee very many deletions from the structure so vector should do my job.

Thanks again for the input.

[Kanoisa]

A few optomisations and a vastly larger dataset and the tables turn dramatically.

code changes to STL load routine.

std::istream& cDay::AddTask(std::istream &in, size_t numItems)
{
	cTask temp;
	for(size_t n = 0; n<numItems; n++)
	{
		temp.Load(in);
		m_taskList.push_back(temp);
	}
	sort(m_taskList.begin(),m_taskList.end(), compareTaskTime);
	return in;
}

Results from using a 10000 element data set 20 times gives the following averages
STL
Average time for 20 passes = 0.0725451 seconds
Handcoded
Average time for 20 passes = 1.44453 seconds

Of course i could now rewrite my hand coded version to only sort at the end too but i would just be competing against myself which with a nice fast response from the vector implimentation that works i have no desire to sit for hours making a fast once use algorithm

All hail STL :)

(when they said STL makes life easier and code production faster they really meant it :) )

[mrnutty]

Do you really need to have the data sorted every time when you add in data?

[Kanoisa]

@first person.

I realised that i didnt. So i only sort it when an element is added manually by hand this wont occour very frequently so the overhead of the sort here should not be significant. With the load function it loads as many elements as i want now then after loading all of them does a single sort.

Would you agree that this new policy for sorting is acceptable or what would you suggest?

Edit: I used this new policy with both the linked list and the vector containers. the vector dramatically outperformed the list. I think its due to the vector iterators being random access and in light of such i have decided to use vector in place of list.