-
X-Received: by 10.31.9.212 with SMTP id 203mr10256vkj.28.1502875271440; Wed, 16 Aug
2017 02:21:11 -0700 (PDT)
X-Received: by 10.31.9.212 with SMTP id 203mr10256vkj.28.1502875271440; Wed, 16 Aug
2017 02:21:11 -0700 (PDT)
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!news.nask.pl!news.nask.org.pl!news.unit0.net!weretis.net!feeder6.news.
weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.
nntp.dca1.giganews.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!m34no23
8328iti.0!news-out.google.com!i9ni50qte.0!nntp.google.com!w51no153837qtc.0!post
news.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Wed, 16 Aug 2017 02:21:11 -0700 (PDT)
In-Reply-To: <f...@g...com>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=159.205.37.107;
posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
NNTP-Posting-Host: 159.205.37.107
References: <oms9l6$db4$1@node2.news.atman.pl>
<f...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <0...@g...com>
Subject: Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa
From: "M.M." <m...@g...com>
Injection-Date: Wed, 16 Aug 2017 09:21:11 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 83
Xref: news-archive.icm.edu.pl pl.comp.programming:211111
[ ukryj nagłówki ]On Wednesday, August 16, 2017 at 2:52:19 AM UTC+2, bartekltg wrote:
> Facet tu mówi o tym:
> https://www.youtube.com/watch?v=JfmTagWcqoE
> Ok 16 minuty zaczyna się właściwa cześć, wcześniej konstruuje
> drzewo na mądrych wskaźnikach.
> [...]
Ja mam pytanie, w jakich zastosowaniach naprawdę jest potrzebne
drzewo na wskaźnikach (jakichkolwiek)? Ja mam drzewka zazwyczaj
na QVectorze, ale mogę też, jako odpowiednik allocatora, szablon
drzewka sparametryzować std::vector, std::array, itd.
Gdy robię benczmark, i gdy sumaryczny czas zwalniania z takich
struktur jak std::set, czy QMap trwa np. 10sekund, to w moim
nadal wynosi 0.000 - tak, stoper nie zdąży się włączyć.
Drzewko na tablicy jest niby ciut wolniejsze, ale oszczędza
pamięć, bo jako indeksy można użyć int8, int16, int32, a
wskaźnik ma rozmiar 64 bity. W efekcie jest więcej trafień w
cache i drzewko jest w niektórych przypadkach 1.5 raza
szybsze.
> Dośc pobieżnie, i jestem niemal pewien, ze kod, który pokazuje
> jest n^2 a nie nlogn ;-) Jeśli mamy wskaźnik na parent to łatwo
> naprawić.
>
> Pomysł, by zwalniać w pętli jeśli jest jeden potomek,
> rekurencyjnie, gdy więcej, nie sprawdzi się:
> /\
> /\
> /\
> /\
> /\
> /\
> /\
> /\
>
> To drzewo też ma głębokość O(n), a zwalniasz je rekurencyjnie.
> (do naprawienia, jeśli masz głęgokość poddrzewa, ale to bardzo
> szczegolny przypadek).
Ale ostatni potomek też iteracyjnie.
> @pomysł M.M. by przerzucić wierzchołki do innego kontenera i tam je
> skasować (pomysł wspominany i w filmiku) nie wymaga tak dużego stosu.
To chyba najprostsza metoda. Dwa wektory są potrzebne. Jeden ma
węzły, drugi węzły których potomków jeszcze nie dodano do pierwszej -
tak można zamienić drzewko na wektor bez rekurencji. Gdy nie trzeba
zamieniać na tablicę, ale od razu zwalniać, to wystarczy wektor z
dziećmi których zwolniono rodziców.
> Przesuń usuwany wierzchołek do kontenera.
> Teraz całe drzewo tam siedzi, zaczepione pod ten element;-)
> Niech indeks pokazuje na ten (jedyny na razie) element. int i=0; :)
>
> Teraz w pętli:
> Wszystkie dzieci wierzchołka spod 'i' przerzuć do kontenera,
> i++
> Pętle konczysz, gdy i =size.
>
> Działająca przykąłdowa implementacja (wystarczy c++11, ale make_unique
> aż się prosi gdziniegdzie:) poniżej.
Tak, chyba o tym samym myślałem.
Pozdrawiam
Następne wpisy z tego wątku
- 16.08.17 11:40 bartekltg
- 16.08.17 12:08 M.M.
- 16.08.17 12:24 bartekltg
- 16.08.17 15:46 Borneq
- 16.08.17 16:05 Borneq
- 16.08.17 16:06 bartekltg
- 16.08.17 16:07 M.M.
- 16.08.17 16:11 bartekltg
- 16.08.17 16:22 Borneq
- 16.08.17 16:42 M.M.
- 17.08.17 00:31 bartekltg
- 17.08.17 01:12 M.M.
- 17.08.17 02:46 Borneq
- 17.08.17 08:11 Tomasz Kaczanowski
- 17.08.17 12:26 M.M.
Najnowsze wątki z tej grupy
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
- C++. Podróż Po Języku - komentarz
Najnowsze wątki
- 2025-07-12 Warszawa => PC Hardware Expert / Specjalista PC <=
- 2025-07-12 Warszawa => Account Manager - Usługi rekrutacyjne <=
- 2025-07-12 Warszawa => Administrator IT <=
- 2025-07-12 Warszawa => IT Administrator <=
- 2025-07-12 Warszawa => Asystent/tka ds. Administracji <=
- 2025-07-12 Warszawa => Specjalista/stka ds. Organizacji <=
- 2025-07-12 Warszawa => MENA New Business Manager <=
- 2025-07-12 Gdynia => Controlling systems Consultant <=
- 2025-07-12 Warszawa => Developer Microsoft Dynamics 365 Finance & Operations (D36
- 2025-07-12 Warszawa => Programista Microsoft Dynamics 365 Finance & Operations (D
- 2025-07-12 Warszawa => Dyrektor IT <=
- 2025-07-12 Warszawa => IT Director <=
- 2025-07-12 Czy wypowiedź Kaczyńskiego o Braunie jest skarżalna? ["działa z OBCEJ inspiracji"]
- 2025-07-11 Rejestrator temperatur - termopara, siec
- 2025-07-11 DPD, przeniesienie numerów z a2mobile i z Orange