Path: csiph.com!news.mixmin.net!newsreader4.netcologne.de!news.netcologne.de!newsfeed.freenet.ag!feeder2.ecngs.de!ecngs!feeder.ecngs.de!81.171.118.64.MISMATCH!peer04.fr7!news.highwinds-media.com!newsfeed.neostrada.pl!unt-exc-01.news.neostrada.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.POSTED!not-for-mail
From: bartekltg <bartekltg@gmail.com>
Newsgroups: pl.comp.programming
Subject: =?UTF-8?Q?Re:_Tablica_int_i_usuwanie_duplikat=c3=b3w?=
Date: Wed, 16 Sep 2015 17:58:17 +0200
Organization: ATMAN - ATM S.A.
Lines: 81
Message-ID: <mtc3ip$vok$1@node2.news.atman.pl>
References: <q1dqtorkbx55$.vtwhsmj03gkt$.dlg@40tude.net> <mt7umm$ulv$1@node1.news.atman.pl> <3aivb8qrco1q$.13cffg23pn4pg.dlg@40tude.net> <almarsoft.2913144209340693774@news.v.pl> <mtav82$r76$1@node2.news.atman.pl> <almarsoft.1833076260504397560@news.v.pl> <mtbd2l$9d5$1@node2.news.atman.pl> <50609ffa-fe60-473f-8adc-5be498ec3dc2@googlegroups.com> <mtbvi8$1ro$1@node1.news.atman.pl> <mtc22e$4hh$1@node1.news.atman.pl>
NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node2.news.atman.pl 1442419097 32532 89.73.81.145 (16 Sep 2015 15:58:17 GMT)
X-Complaints-To: usenet@atman.pl
NNTP-Posting-Date: Wed, 16 Sep 2015 15:58:17 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0
In-Reply-To: <mtc22e$4hh$1@node1.news.atman.pl>
X-Received-Bytes: 4258
X-Received-Body-CRC: 1792247794
Xref: csiph.com pl.comp.programming:27516

On 16.09.2015 17:31, AK wrote:
> Użytkownik "bartekltg" <bartekltg@gmail.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 ?

Przecież napisałem jakie są wady i zalety tamtej metody w stosunku
do tej najprostszej. ;-)
Jeśli unikalnych elementów jest praie n, to ta metoda jest szybsza od
set i mniej pamieciożerna od seta i unordered_set.

Pytacz narzekał na niedobór algorytmów, to dajmu mu do wyboru;-)

 > 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 nie to: dodaje wartosc vec[i] do seta

To co opisałeś to z grubsza dwie ostatnie linijki mojego postu.
Nie rozpisywałem się, bo już było w wątku.
Trzeba było te algorytmiki nazywać. I będzie
[1] szemrany 10:40
[2] A.K 11:34
[3] M.M 14:56

  ;-)



> Ma zarowno wektor zmodyfikowany "w miejscu" (rozumiem, ze tak chcial), a
> i kolejnosc zachowana.

To nie jest algorytm działający w miejscu. Średnio potrzebuje
on O(n) pamięci.



> 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"


Myślałem że autor chce tylko odpalić jakąś funkcję dla unikalnych
elementów. Jeśli chce zamienić zawartosć tablicy,
to jest to raczej standardowy sposób niż przekombinowanie, wszelkie
unique czy remove_if tak działają. Jedziemy dwoma iteratorami,
"zapisującym" i "odczytującym".
while (odczytujący!=end)
    jeśli ( odczytujący pokazuje na pierwsze wystąpienie),
        {wartość zapisujemy pod iterator "zapisyjący"
          i przesuwamy 'zap.' o oczko. }
    "Odczytujący" robi krok.
//zabawa z obsługą pomocniczego zbior jak poprzednio,

pzdr
bartekltg