Thread View: pl.comp.lang.c
4 messages
4 total messages
Started by Maciek
Thu, 11 May 2023 00:38
Złożoność obliczeniowa
Author: Maciek
Date: Thu, 11 May 2023 00:38
Date: Thu, 11 May 2023 00:38
1 lines
1705 bytes
1705 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 09:33
Date: Thu, 11 May 2023 09:33
9 lines
1646 bytes
1646 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: Wojciech Muła
Date: Thu, 25 May 2023 20:05
Date: Thu, 25 May 2023 20:05
8 lines
2176 bytes
2176 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 18:57
Date: Thu, 15 Jun 2023 18:57
10 lines
2461 bytes
2461 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