mkagenius's blog

An interesting fact regarding STL usage.
By mkagenius, 13 years ago, In English
Let there be a sequence of integers : 3,1,6,3,7,8,2,7 ;

If you insert this sequence in set<int> after sorting the, time taken as a whole ( i.e sorting + inserting) will be lesser than direct insertion into the set without sorting.
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
+1 for your profile name :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
test next way: set<int> st;  for (int i = 0; i < a.size(); i++) st.insert(st.end(), a[i]);
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Just checked, Still sorting+inserting is faster.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      look at this code

      MS VS 2008 Express release:

      The stupid way
      sort time: 1062
      insert time: 3735
      sort+insert time: 4797
      The smart way
      sort time: 969
      insert time: 1734
      sort+insert time: 2703

      MinGW g++.exe -o cc cc.cpp

      The stupid way
      sort time: 3375
      insert time: 9812
      sort+insert time: 13281
      The smart way
      sort time: 3579
      insert time: 3453
      sort+insert time: 7032

      So, i hope you can see, st.insert(st.end(), a[i]) works up to three times faster, if array is sorted.

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Oh sorry, I thought you asked to check the insertion time with your way 'without' sorting the array.

        So, sorting + inserting_your_way is faster than sorting+insert_the_normal_way is faster than inserting_the_normal_way .
        Thanks for sharing. :)
        → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Double post.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Have you ever try the case that input is very large; i.e. list which have million elements? Still faster?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think Alias's post above answers your question (they use 2^22 ~ 4 million elements for testing). If you didn't get it - yes, still faster.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes , I have also tested it for million integers. :)
    → Reply