Thread View: pl.comp.lang.c
4 messages
4 total messages
Started by Maciek
Wed, 10 May 2023 17:38
Złożoność obliczeniowa
Author: Maciek
Date: Wed, 10 May 2023 17:38
Date: Wed, 10 May 2023 17:38
6 lines
499 bytes
499 bytes
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ć.
Re: Złożoność obliczeniowa
Author: heby
Date: Thu, 11 May 2023 11:33
Date: Thu, 11 May 2023 11:33
8 lines
503 bytes
503 bytes
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.
Re: Złożoność obliczeniowa
Author: =?UTF-8?Q?Wojcie
Date: Thu, 25 May 2023 13:05
Date: Thu, 25 May 2023 13:05
16 lines
833 bytes
833 bytes
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.
Re: Złożoność obliczeniowa
Author: Maciek
Date: Thu, 15 Jun 2023 11:57
Date: Thu, 15 Jun 2023 11:57
21 lines
1148 bytes
1148 bytes
czwartek, 25 maja 2023 o 22:05:46 UTC+2 Wojciech Muła napisał(a): > 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. 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.
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads