Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Złożoność obliczeniowa

27 views
Skip to first unread message

Maciek

unread,
May 10, 2023, 8:38:31 PM5/10/23
to
Jeśli chodzi o biblitekę standardową to algorytmy sortujące mają całkiem dobrą wydajność z tego co widzę. Natomiast przy bardzo dużej ilości danych rzędu 5 - 7 GB lepiej przechowywać dane posortowane w pojemniku std::set ? Właściwie nie jestem pewny jaka jest złożoność utrzymania danych w tym pojemniku ? Chodzi mi o to że dane w nim przechowywane mogą się zmieniać.

heby

unread,
May 11, 2023, 5:36:09 AM5/11/23
to
On 11/05/2023 02:38, Maciek wrote:
> Natomiast przy bardzo dużej ilości danych rzędu 5 - 7 GB lepiej przechowywać dane posortowane w pojemniku std::set ?

Lepiej opisz co to za są za dane. std::set ma ogromny narzut na
allokację, przy takiej ilości danych. Co oznacza, że złożonośc ma dużą
stałą zależną od innych czynników niż sam algorytm a sam proces liczenia
wiekszy/mniejszy może być też czasochłonny dla dziwacznych danych.

Nie zawsze generyczny algorytm jest najlepszy.


Wojciech Muła

unread,
May 25, 2023, 4:05:46 PM5/25/23
to
On Thursday, May 11, 2023 at 2:38:31 AM UTC+2, Maciek wrote:
> Jeśli chodzi o biblitekę standardową to algorytmy sortujące mają całkiem dobrą wydajność z tego co widzę. Natomiast przy bardzo dużej ilości danych rzędu 5 - 7 GB lepiej przechowywać dane posortowane w pojemniku std::set ? Właściwie nie jestem pewny jaka jest złożoność utrzymania danych w tym pojemniku ? Chodzi mi o to że dane w nim przechowywane mogą się zmieniać.

std::set ma złożoność logarytmiczną i to jest zdefiniowane w standardzie, patrz: https://en.cppreference.com/w/cpp/container/set

Jeśli potrzebujesz trzymać te dane w pamięci, to lepiej używać B-drzew.

w.

Maciek

unread,
Jun 15, 2023, 2:58:00 PM6/15/23
to
Hm no tak, to był głupi pomysł w sumie zaraz po poście wyciągnąłem wniosek ale już nie chciałem mieszać w poście. Oczywiście drzewa. Dzieki.
0 new messages