Блог пользователя mkagenius

Автор mkagenius, 13 лет назад, По-английски
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.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
+1 for your profile name :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
test next way: set<int> st;  for (int i = 0; i < a.size(); i++) st.insert(st.end(), a[i]);
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Just checked, Still sorting+inserting is faster.
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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. :)
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Double post.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Have you ever try the case that input is very large; i.e. list which have million elements? Still faster?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Yes , I have also tested it for million integers. :)