Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Groups keyboard shortcuts have been updated
Dismiss
See shortcuts

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