Post by Wojciech MuÅaNatomiast ja się rąbnąłem. Ta ładna złożoność liniowa byłby, gdyby std::set
potrafił się zbudować z posortowanej listy w czasie log(n) - ale nie potrafi.
To jest np. powód, dla którego czasem trzeba grzecznie podziękować std
i zrobić lepiej. :)
Jeśli masz poprawnego 'hita' wstawienie elementu jest w czasie
(zamortyzowanym) stałym, a ładując go posortowanymi danymi, wiadomo,
co jest dobrym "hintem'. Skoro sam mogę napisać liniowe wstawianie
do zbioru, dziwne by było, jakby domyslnie to nie działało. I wygląda
na to, że działa.
http://en.cppreference.com/w/cpp/container/set/set
i dla konstruktora z istniejącego kontenera:
2) N log(N) where N = std::distance(first, last) in general, linear in N
if the range is already sorted by value_comp().
I w testach to wychodzi.
https://www.dropbox.com/sh/gh35ths4ozwtbco/AAD8SSpJQEku_Z7EPzBiLR9ra?dl=0
Czas w funkcji rozmiaru danych dla nieposortowanych
i posotrowanych danych, oraz wykres proporcji.
Przypomina nieco logarytm;-)
double glob=0;
void test_set(int N)
{
vector<float> data(N);
random_device rd;
mt19937 gen(rd());
uniform_real_distribution<float> dist(1.0f,10.0f);
for (auto &it :data)
{
it=dist(gen);
}
stoper st;
st.start();
set<float> s1(data.begin(),data.end());
st.stop();
cout<<N<<" "<<st.val()<<" ";
sort(data.begin(),data.end());
//shuffle(data.begin(),data.end(),gen);
st.start();
set<float> s2(data.begin(),data.end());
st.stop();
cout<<st.val()<<endl;
glob+=*(s1.begin());
glob+=*(s2.begin());
}
void main_test_set()
{
for (int n=100000;n<100000000;n=(n*5)/4)
test_set(n);
cout<<endl<<glob<<endl;
}
pzdr
bartekltg