Hejka,

Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
sortowania.
Jak to zrobić wydajnie? Jakiś algorytm sprytny?

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

W dniu poniedziałek, 14 września 2015 21:56:08 UTC+2 użytkownik szemrany napisał:
> Hejka,
>
> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
> sortowania.
> Jak to zrobić wydajnie? Jakiś algorytm sprytny?

Trochę mało informacji. Jeżeli dziedzina wartości intów jest ograniczona, można
zliczać występowanie każdej wartości. Jeśli nie, to bez czegoś co przypomina
sortowanie sie nie obędzie.

AdamK

do góry

szemrany wrote:
> Hejka,
>
> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
> sortowania.
> Jak to zrobić wydajnie? Jakiś algorytm sprytny?
>

collection zamiast tablicy?

do góry

On 14.09.2015 21:56, szemrany wrote:
> Hejka,
>
> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
> sortowania.
> Jak to zrobić wydajnie? Jakiś algorytm sprytny?

Wpakuj do tablicy hashującej, takiej bez powtórzeń
(unordered_set<> w cpp). [To, jak się zastanowić,
bardzo podobne rozwiązanie do proponowanego przez Adama]

Może być nawet szybsze niż sortowanie (oczekiwaną złożoność
ma liniową), ale za to pamięci zeżre trochę.

Czemu nie chcesz sortowania?

pzdr
bartekltg

do góry

On 15.09.2015 03:23, witek wrote:
> szemrany wrote:
>> Hejka,
>>
>> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
>> sortowania.
>> Jak to zrobić wydajnie? Jakiś algorytm sprytny?
>>
>
> collection zamiast tablicy?

A co to?

pzdr
bartekltg

do góry

On Tue, 15 Sep 2015 04:10:29 +0200, bartekltg wrote:

>> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
>> sortowania.
>> Jak to zrobić wydajnie? Jakiś algorytm sprytny?
>
> Wpakuj do tablicy hashującej, takiej bez powtórzeń
> (unordered_set<> w cpp). [To, jak się zastanowić,
> bardzo podobne rozwiązanie do proponowanego przez Adama]
>
> Może być nawet szybsze niż sortowanie (oczekiwaną złożoność
> ma liniową), ale za to pamięci zeżre trochę.

I naprawdę algorytmika niczego lepszego nie wymyśliła?

> Czemu nie chcesz sortowania?

W zasadzie w przypadku jaki tu i teraz potrzebuję sortowanie jest
dopuszczalne, ale chciałem to zrobić generycznie i mieć do wykorzystania w
innych przypadkach, a nie zawsze zmiana kolejności elementów będzie
dopuszczalna.

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

Użytkownik "szemrany" <s...@o...off> napisał:

> I naprawdę algorytmika niczego lepszego nie wymyśliła?

Ano wymyslila, ale "to zalezy" (a nawet bardzo zalezy).

Jesli roznica max - min nie jest za duza to "funkcja hashujaca"
sprowadzi sie do "indeksowania wartoscią" w rodzaju
uniques[x - min] = x

Jesli np wartosci mogace wystapic w tablicy sa z gory znane
i niezbyt liczne to np. "perfect hash" nie jest najgorszym wyborem.

Ogolnie to podpowiedz: specjalizowany _pod inty_ kontener typu set
(zwykle "hashujacy" lub b-drzewiasty).
powinna wystarczyc.

AK


---
Ta wiadomość została sprawdzona na obecność wirusów przez oprogramowanie antywirusowe
Avast.
https://www.avast.com/antivirus

do góry

On Tue, 15 Sep 2015 10:50:15 +0200, AK wrote:

>> I naprawdę algorytmika niczego lepszego nie wymyśliła?
>
> Ano wymyslila, ale "to zalezy" (a nawet bardzo zalezy).
>
> Jesli roznica max - min nie jest za duza to "funkcja hashujaca"
> sprowadzi sie do "indeksowania wartoscią" w rodzaju
> uniques[x - min] = x
>
> Jesli np wartosci mogace wystapic w tablicy sa z gory znane
> i niezbyt liczne to np. "perfect hash" nie jest najgorszym wyborem.
>
> Ogolnie to podpowiedz: specjalizowany _pod inty_ kontener typu set
> (zwykle "hashujacy" lub b-drzewiasty).
> powinna wystarczyc.

To nie jest algorytmika, to brute force :-)
Ale chyba rzeczywiście nie ma sprytniejszej metody lub jeszcze jej nie
wymyślono.

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

On 15.09.2015 09:32, szemrany wrote:
> On Tue, 15 Sep 2015 04:10:29 +0200, bartekltg wrote:
>
>>> Mam tablicę intów i potrzebuję usunąć duplikaty. Chciałbym uniknąć
>>> sortowania.
>>> Jak to zrobić wydajnie? Jakiś algorytm sprytny?
>>
>> Wpakuj do tablicy hashującej, takiej bez powtórzeń
>> (unordered_set<> w cpp). [To, jak się zastanowić,
>> bardzo podobne rozwiązanie do proponowanego przez Adama]
>>
>> Może być nawet szybsze niż sortowanie (oczekiwaną złożoność
>> ma liniową), ale za to pamięci zeżre trochę.
>
> I naprawdę algorytmika niczego lepszego nie wymyśliła?

A co byś chciał lepszego?

>
>> Czemu nie chcesz sortowania?
>
> W zasadzie w przypadku jaki tu i teraz potrzebuję sortowanie jest
> dopuszczalne, ale chciałem to zrobić generycznie i mieć do wykorzystania w

Sortowanie jest bardzo generyczne.

> innych przypadkach, a nie zawsze zmiana kolejności elementów będzie
> dopuszczalna.

Tak podejrzewałem, że nie chcesz zamieniać kolejności,
ale tego NIE NAPISAŁEŚ ;p

Przechodząc tablicę trzymaj kontener (drzewo zrównoważone - set,
lub tablice hashującą - unordered set) z elementami już
przetworzonymi, obrabiasz element z tablicy jeśli nie ma go
w pomocniczym kontenerze. Po obrobieniu wsadzasz go tam.

pzdr
bartekltg

do góry

Użytkownik "szemrany" <s...@o...off> napisał:

> To nie jest algorytmika, to brute force :-)

Jakie brute force ? Zastanow sie.
Perfect hash (powszechnie stosowany np w kompilatorach,
roznych dispatcherach i nie tylko),

https://en.wikipedia.org/wiki/Perfect_hash_function
http://homepages.dcc.ufmg.br/~nivio/papers/cikm07.pd
f
https://en.wikipedia.org/wiki/Dynamic_perfect_hashin
g

czy mapowania wartosc-index/indeksowanie wartoscią
(patrz chocby Bentley "Perelki programowania") to brute force ?

To przeciez _najwydajniejsze_ z mozliwych sposobow
znaljdowania/separacji (w tym wartosci unikalnych).

AK


---
Ta wiadomość została sprawdzona na obecność wirusów przez oprogramowanie antywirusowe
Avast.
https://www.avast.com/antivirus

do góry