-
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.P
OSTED!not-for-mail
From: "AK" <n...@n...com>
Newsgroups: pl.comp.programming
Subject: Re: Tablica int i usuwanie duplikatów
Date: Wed, 16 Sep 2015 17:31:55 +0200
Organization: ATMAN - ATM S.A.
Lines: 43
Message-ID: <mtc22e$4hh$1@node1.news.atman.pl>
References: <q1dqtorkbx55$.vtwhsmj03gkt$.dlg@40tude.net>
<mt7umm$ulv$1@node1.news.atman.pl>
<3aivb8qrco1q$.13cffg23pn4pg.dlg@40tude.net>
<a...@n...v.pl>
<mtav82$r76$1@node2.news.atman.pl>
<a...@n...v.pl>
<mtbd2l$9d5$1@node2.news.atman.pl>
<5...@g...com>
<mtbvi8$1ro$1@node1.news.atman.pl>
NNTP-Posting-Host: dynamic62-133-135-241.ostnet.pl
Mime-Version: 1.0
Content-Type: text/plain; format=flowed; charset="utf-8"; reply-type=response
Content-Transfer-Encoding: 8bit
X-Trace: node1.news.atman.pl 1442417550 4657 62.133.135.241 (16 Sep 2015 15:32:30
GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Wed, 16 Sep 2015 15:32:30 +0000 (UTC)
In-Reply-To: <mtbvi8$1ro$1@node1.news.atman.pl>
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Windows Mail 6.0.6002.18197
X-MimeOLE: Produced By Microsoft MimeOLE V6.0.6002.18463
X-Antivirus: avast! (VPS 150915-1, 2015-09-15), Outbound message
X-Antivirus-Status: Clean
Xref: news-archive.icm.edu.pl pl.comp.programming:208317
[ ukryj nagłówki ]Użytkownik "bartekltg" <b...@g...com> napisał:
> A, jeszcze jedno, tutaj nie musimy używać set<int>, bo to rzeczywiście
> nam nieźle zwolni.
> Weźmy trudniejszą wersję, czyli pytacz chce przetwarzać liczby
> w takiej kolejności w jakiej są w tablicy, tylko pominąć już raz
> przetworzone. Ale skoro liczby mamy dane z góry, możemy je sobie
> skopiować, posortować, (opcjonalnie machnąć std::unique aby pozbyć
> \się duplkatów z posortowanej wersji). Do tego trzymamy tablicę
> booli (vector<bool>) o tej samej długości.
>
> Dostając liczbę, wyszukujemy ją binarnie w pomoczniczej posortowanej
> tablicy, sprawdzamy czy bit w teblicy booli jest zapalony.
>
> Będzie szybsze niż operacja na drzewach, i prawdopodobnie zajmie
> mniej pamięci niż obie pozostałe wersje.
> Prawdopodobnie, bo dla złośliwego przypadku - bardzo dużo podobnych
> danych, ale niewiele różnych liczb, lepiej jest tworzyć
> pomocniczy zbiór na żywo.
Po co tak skomplikowanie ?
Mozna bardzo prosto.
1. Pytacz tworzy (pustego) seta (np.hash-seta)
2. Pytacz idzie/iteruje sobie po tablicy intow.
Dla kazdego inta sprawdza czy jest w secie
jesli tak to: vec[i] := wartosc markujaca "nic" (jakies MAX_UINT albo cus)
jesli nie to: dodaje wartosc vec[i] do seta
3. i += 1
Ma zarowno wektor zmodyfikowany "w miejscu" (rozumiem, ze tak chcial), a i kolejnosc
zachowana.
Wydajne, proste, niezalezne od postaci/implementacji seta.
PS: Oczywiscie mozna jeszcze inaczej: nie markujac "nic" tylko biezacy kompiujac
vec[i] za ostatni niepowtarzalny (pamietajac wczesniej jego indeks) ale po co/to
zalezy ?
Byc moze lepiej/prosciej pozniej odfiltrowac przy iteracji te elementy z "nic"
AK
---
Ta wiadomość została sprawdzona na obecność wirusów przez oprogramowanie antywirusowe
Avast.
https://www.avast.com/antivirus
Następne wpisy z tego wątku
- 16.09.15 17:58 bartekltg
- 16.09.15 18:25 AK
- 16.09.15 18:28 bartekltg
- 16.09.15 19:11 Sebastian Biały
- 16.09.15 19:41 M.M.
- 16.09.15 19:46 M.M.
- 16.09.15 19:55 bartekltg
- 16.09.15 19:57 AK
- 16.09.15 22:46 bartekltg
- 16.09.15 23:27 AK
- 17.09.15 00:23 bartekltg
- 17.09.15 08:12 slawek
- 17.09.15 14:37 M.M.
- 17.09.15 15:14 bartekltg
- 17.09.15 16:37 AK
Najnowsze wątki z tej grupy
- 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
- "Wuj dobra rada" z KDAB rozważa: Choosing the Right Programming Language for Your Embedded Linux Device
- Nowa ustawa o ochronie praw autorskich - opis problemu i szkic ustawy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
Najnowsze wątki
- 2025-05-02 Wrocław => Controlling systems Consultant <=
- 2025-05-02 Kraków => Programista MS Dynamics 365BC/NAV <=
- 2025-05-02 Kraków => Koordynator Produkcji / Przedstawiciel ds. rozwoju produktu
- 2025-05-02 Warszawa => Spedytor Międzynarodowy <=
- 2025-05-02 Białystok => NMS System Administrator <=
- 2025-05-02 Warszawa => Sales Director (Cloud solutions) <=
- 2025-05-02 Czy na URZĘDACH RP3 można bezkarnie LATAMI wywieszać flagę obcego państwa? [podstawa prawna]
- 2025-05-02 tona telefonów komórkowych kryje ok. 3,5 kilograma srebra, 360 gramów złota i 280 gramów palladu.
- 2025-05-01 Jak zbudować Perpetum Mobile
- 2025-05-01 Wybory ten wygra kto odzyska TEPS'ę od Kulczyka
- 2025-04-30 Czy wymieniacie fotel kierowcy, gdy kupujecie używanego gruchota po prostacie i nietrzymaniu moczu ?
- 2025-05-02 dewastują Tesle
- 2025-05-02 jadę do państwa polskiego
- 2025-05-01 zachowaj odstęp
- 2025-04-30 Czy wymieniacie fotel kierowcy, gdy kupujecie używanego gruchota po prostacie