Re: Tablica int i usuwanie duplikatów

From	bartekltg <bartekltg@gmail.com>
Newsgroups	pl.comp.programming
Subject	Re: Tablica int i usuwanie duplikatów
Date	2015-09-16 17:58 +0200
Organization	ATMAN - ATM S.A.
Message-ID	<mtc3ip$vok$1@node2.news.atman.pl> (permalink)
References	(5 earlier) <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>

Show all headers | View raw

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

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-14 21:56 +0200
  Re: Tablica int i usuwanie duplikatów Adam Klobukowski <adamklobukowski@gmail.com> - 2015-09-14 13:50 -0700
  Re: Tablica int i usuwanie duplikatów witek <witek7205@gazeta.pl.invalid> - 2015-09-14 20:23 -0500
    Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 04:10 +0200
  Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 04:10 +0200
    Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-15 09:32 +0200
      Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-15 10:50 +0200
        Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-15 12:01 +0200
          Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-15 14:53 +0200
      Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 14:16 +0200
      Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-16 07:21 +0200
        Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 07:38 +0200
          Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-16 10:57 +0200
            Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 11:34 +0200
              Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 03:31 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 12:52 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 05:03 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 16:49 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 17:31 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 17:58 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 18:25 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 18:28 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 10:41 -0700
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 19:57 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 22:46 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 23:27 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-17 00:23 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-17 05:37 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 00:18 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-18 09:07 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 18:20 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 20:22 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 20:47 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 21:01 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 21:36 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 22:50 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 03:08 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 11:34 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 20:52 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 04:35 -0700
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 04:57 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 14:43 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 05:50 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 15:08 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 06:23 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 15:44 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:20 +0200
                Re: Tablica int i usuwanie duplikatów Tomasz Kaczanowski <kaczus@dowyciecia_poczta.onet.pl> - 2015-09-21 08:09 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:13 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:10 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 09:58 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 20:44 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-22 04:43 -0700
              Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-17 08:12 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-17 15:14 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-17 16:37 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-18 07:22 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 15:15 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-19 20:45 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 21:01 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-20 16:27 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-20 17:14 +0200
          Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 11:05 +0200
            Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 11:40 +0200
              Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 12:05 +0200
  Re: Tablica int i usuwanie duplikatów Sebastian Biały <heby@poczta.onet.pl> - 2015-09-16 19:11 +0200
    Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 10:46 -0700
      Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 19:55 +0200

csiph-web