## 24 Replies - 3962 Views - Last Post: 02 June 2012 - 06:25 PM

### #16

## Re: What is more efficient

Posted 02 June 2012 - 12:15 AM

Apparently your teacher's question was specifically about insertion sort, or at least the situation were you continuously insert into a list and have to keep it sorted at all time. (This is one of the possible interpretations of your question that I mentioned in my initial post, but you never replied to make clear that this is in fact what you meant.) Note that the way to go for this scenario in real life would be a balanced BST - not a linked list, but that just as an aside. When some people said that vectors were faster to sort, they were almost certainly talking about the case were you add all elements first and then just sort it once (using algorithms like e.g. quick sort, not insertion sort). That or they were just objecting to your general statement that lists are better for sorting than vectors and not to the specific question.

### #17

## Re: What is more efficient

Posted 02 June 2012 - 12:29 PM

#include <iostream> #include <algorithm> #include <ctime> #include <cstdlib> #include <vector> #include <list> void test(int n) { std::vector<int> v; std::list<int> l; std::vector<int> random_vals; //just so that we can use the same random values for each test for(int i=0; i < n; ++i) { random_vals.push_back(rand()); } clock_t begin = clock(); for(int i=0; i < n; ++i) { int r = random_vals[i]; //uses exact algorthim for inserting element into vector that prof said v.insert(std::lower_bound(v.begin(), v.end(), r), r); } clock_t end = clock(); std::cout<<"vector time: "<<double(end - begin)/CLOCKS_PER_SEC<<'\n'; begin = clock(); for(int i=0; i < n; ++i) { int r = random_vals[i]; //uses near exact algorthim for inserting element into list that prof said //this is like a binary search but it has to advance the iterator step by step //this has the same linear time complexity but uses fewer comparisons l.insert(std::lower_bound(l.begin(), l.end(), r), r); } end = clock(); std::cout<<"list time: "<<double(end - begin)/CLOCKS_PER_SEC<<'\n'; } int main() { srand(time(NULL)); test(20000); return 0; }

I get these times:

vector time: 0.049

list time: 2.492

**that's 50 times slower!!**

and I'm not saying that std::list doesn't have its place, it does, but it's only in some really strange cases.

edit:

and as it turns out the simplest algorithm is also better.

#include <iostream> #include <algorithm> #include <ctime> #include <cstdlib> #include <vector> #include <list> template<class FwdIter, class T> FwdIter find_insertion_point(FwdIter begin, FwdIter end, const T& val) { while(begin != end) { if(*begin > val) { break; } ++begin; } return begin; } void test(int n) { std::vector<int> v; std::list<int> l; std::vector<int> random_vals; //just so that we can use the same random values for each test for(int i=0; i < n; ++i) { random_vals.push_back(rand()); } clock_t begin = clock(); for(int i=0; i < n; ++i) { int r = random_vals[i]; //uses exact algorthim for inserting element into vector that prof said v.insert(std::lower_bound(v.begin(), v.end(), r), r); } clock_t end = clock(); std::cout<<"vector time: "<<double(end - begin)/CLOCKS_PER_SEC<<'\n'; begin = clock(); for(int i=0; i < n; ++i) { int r = random_vals[i]; //uses near exact algorthim for inserting element into list that prof said //this is like a binary search but it has to advance the iterator step by step //this has the same liniar time complexity but uses fewer comparisions l.insert(find_insertion_point(l.begin(), l.end(), r), r); } end = clock(); std::cout<<"list time: "<<double(end - begin)/CLOCKS_PER_SEC<<'\n'; } int main() { srand(time(NULL)); test(20000); return 0; }

this gives me:

vector time: 0.049

list time: 0.834

that's still 17 times slower!

This post has been edited by **ishkabible**: 02 June 2012 - 12:39 PM

### #18

## Re: What is more efficient

Posted 02 June 2012 - 01:37 PM

My gut feel though is that his numbers will look very different and the linked lists will win if:

struct HugeRecord { int Key; char BigBlockRepresentingRestOfRecord[8192 - sizeof(int)]; };

and you start to compare vector<HugeRecord> vs list<HugeRecord> where the random numbers generated were in the Key fields.

This post has been edited by **Skydiver**: 02 June 2012 - 01:41 PM

### #19

## Re: What is more efficient

Posted 02 June 2012 - 01:41 PM

ishkabible, on 02 June 2012 - 09:29 PM, said:

It should be pointed out that both cases are O(n) (and the prof didn't say anything contrary to that), so neither is better just going by the Big-Oh. Though I have to say that phrasing it in terms of O(n) + O(n log n) vs. O(n) + O(1) certainly makes it sound

*as if*one was asymptotically better than the other, which is extremely misleading. That's the fault of the teacher though, not Big-Oh notation.

### #20

## Re: What is more efficient

Posted 02 June 2012 - 01:57 PM

Skydiver: yes; with something sufficiently sized I would expect a vector would be worse(I'll test it to see how far). in this instance however you can get better performance by using move semantics and dynamically allocate that array(C++11 only). if you have a bunch of small static arrays that have different types or purposes or the class has a ton of members(and I mean a TON) then a linked list would be better but that is exceedingly rare(epically considering the set of algorithms this would be applicable for). also, at that point you would probably dynamically allocate the instances anyway and a vector would be faster.

edit:

pretty surprising, it only took an array of 8 integers to overthrow an std::vector with 5000 items but with 20000 items it takes arrays of 150 elements for std::list to overthrow std::vector. I'm not exactly sure why this is. it's consistent on my system from 1000-40000 items that as the number of items goes up you need larger and larger elements for std::list to beat std::vector. I would *expect* that the behavior would continue. in the case of small <10000 elements it would be worth testing to see if std::list will beat std::vector with larger elements(say like 16 bytes or more) for certain algorithms. anything too much bigger(>32-64 bytes) dynamic memory allocation probably should've been used in the first place.

#include <iostream> #include <algorithm> #include <ctime> #include <cstdlib> #include <vector> #include <list> template<int size> struct big { int k; int data[size]; big(int x) : k(x) {} bool operator>(const big& B)/> { return k > b.k; } bool operator<(const big& B)/> { return k < b.k; } bool operator>=(const big& B)/> { return k >= b.k; } bool operator<=(const big& B)/> { return k <= b.k; } bool operator==(const big& B)/> { return k >= b.k; } bool operator!=(const big& B)/> { return k != b.k; } }; template<class FwdIter, class T> FwdIter find_insertion_point(FwdIter begin, FwdIter end, const T& val) { while(begin != end) { if(*begin > val) { break; } ++begin; } return begin; } template<int size> void test(int n) { std::vector<big<size>> v; std::list<big<size>> l; std::vector<int> random_vals; //just so that we can use the same random values for each test for(int i=0; i < n; ++i) { random_vals.push_back(rand()); } clock_t begin = clock(); for(int i=0; i < n; ++i) { int r = random_vals[i]; //uses exact algorthim for inserting element into vector that prof said v.insert(std::lower_bound(v.begin(), v.end(), r), r); } clock_t end = clock(); std::cout<<"vector time: "<<double(end - begin)/CLOCKS_PER_SEC<<'\n'; begin = clock(); for(int i=0; i < n; ++i) { int r = random_vals[i]; //uses near exact algorthim for inserting element into list that prof said //this is like a binary search but it has to advance the iterator step by step //this has the same liniar time complexity but uses fewer comparisions l.insert(find_insertion_point(l.begin(), l.end(), r), r); } end = clock(); std::cout<<"list time: "<<double(end - begin)/CLOCKS_PER_SEC<<'\n'; } int main() { srand(time(NULL)); test<8>(5000); return 0; }

This post has been edited by **ishkabible**: 02 June 2012 - 02:31 PM

### #21

## Re: What is more efficient

Posted 02 June 2012 - 02:27 PM

// ListVsVector.cpp : Defines the entry point for the console application. // #include "stdafx.h" template<int size> struct HugeRecord { int Key; char Dummy[size - sizeof(int)]; HugeRecord(int key) : Key(key) { } bool operator <(const HugeRecord & rhs) const { return Key < rhs.Key; } }; template<class T> void test(const std::vector<int> & random_vals) { std::vector<T> v; std::list<T> l; std::cout << "Record size: " << sizeof(T) << " bytes.\n"; clock_t begin = clock(); for(auto it = random_vals.begin(); it < random_vals.end(); ++it) { //uses exact algorthim for inserting element into vector that prof said T * r = new T(*it); v.insert(std::lower_bound(v.begin(), v.end(), *r), *r); } clock_t end = clock(); std::cout<<"vector time: "<<double(end - begin)/CLOCKS_PER_SEC<<'\n'; begin = clock(); for(auto it = random_vals.begin(); it < random_vals.end(); ++it) { //uses near exact algorthim for inserting element into list that prof said //this is like a binary search but it has to advance the iterator step by step //this has the same linear time complexity but uses fewer comparisons T * r = new T(*it); l.insert(std::lower_bound(l.begin(), l.end(), *r), *r); } end = clock(); std::cout<<"list time: "<<double(end - begin)/CLOCKS_PER_SEC<<'\n'; } int main() { srand(time(NULL)); //just so that we can use the same random values for each test std::vector<int> random_vals; for(int i=0; i < 5000; ++i) { random_vals.push_back(rand()); } test<int>(random_vals); test<HugeRecord<8>>(random_vals); test<HugeRecord<16>>(random_vals); test<HugeRecord<32>>(random_vals); test<HugeRecord<64>>(random_vals); test<HugeRecord<128>>(random_vals); test<HugeRecord<256>>(random_vals); test<HugeRecord<512>>(random_vals); test<HugeRecord<1024>>(random_vals); test<HugeRecord<2048>>(random_vals); test<HugeRecord<4096>>(random_vals); test<HugeRecord<8192>>(random_vals); std::cout << "Done.\n"; std::cin.get(); return 0; }

I must say you have a pretty beefy machine to do the 20000 ints in 0.049. I had to cut back to about 5000. Feel free to change the code above back to 20000 and put in the simpler search.

This post has been edited by **Skydiver**: 02 June 2012 - 02:31 PM

### #22

## Re: What is more efficient

Posted 02 June 2012 - 02:35 PM

if you turn on optimization and use the release/build version of your program you should get less of a gap.

This post has been edited by **ishkabible**: 02 June 2012 - 02:38 PM

### #23

## Re: What is more efficient

Posted 02 June 2012 - 03:01 PM

ishkabible, on 02 June 2012 - 02:35 PM, said:

if you turn on optimization and use the release/build version of your program you should get less of a gap.

I swapped from debug to release mode very early on. Or at least I thought I did... :-) Switching it back to Release again. ($!@# VS2010. No wonder I prefer to hand write my make files and build on the command line when not doing things quick and dirty.) Looks like the break even point is even lower now that I'm really building in release mode: somewhere between 128-256 bytes the list starts to win.

Yup, as I was reading elsewhere VC++ STL uses 1.5 growth factor for its vectors, while GCC uses 2 as the growth factor. And there is the issue of different memory managers. So testing different libs and array sizes should be there for completeness.

Anyway, I don't recall the source anymore, but I heard that for a typical LOB application, a "record" size is about 2-4K of data while game objects would be more in the 1-2K range. But when I heard this, this was in the days when the "style" was to keep everything in single structs because "allocating memory is slow so allocate as big a chunk as possible" was the philosophy. With people's now calling new left and right and confidence is safe pointers, I think "record" sizes are now smaller.

This post has been edited by **Skydiver**: 02 June 2012 - 03:12 PM

### #24

## Re: What is more efficient

Posted 02 June 2012 - 06:08 PM

### #25

## Re: What is more efficient

Posted 02 June 2012 - 06:25 PM

I pointed out that in implementation, std::vector is faster, just like I said it often is earlier. I showed a test to prove it.

sepp2k pointed O(n) + O(log n) == O(n) becuase you only keep the largest term with Big-O becuase these 2 items will scale similarly. Big-O isn't made to settle small differences in algorithms, just how well the algorithms scale.

Skydiver pointed out that if the elements are big enough that a linked list will preform the operation you described better than a vector. we then tested this to see how much bigger the items need to be and have no conclusive result(and the answer will probably differ from machine to machine, compiler to compiler, standard library to standard library, etc...). all we have shown is that linked lists will indeed preform this operation more efficiently for larger elements but how large "larger" is is very dependent on many factors.

This post has been edited by **ishkabible**: 02 June 2012 - 06:32 PM