Path: csiph.com!au2pb.net!feeder.erje.net!1.eu.feeder.erje.net!feeder2.ecngs.de!ecngs!feeder.ecngs.de!81.171.118.61.MISMATCH!peer01.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: Fri, 18 Sep 2015 00:18:56 +0200
Organization: ATMAN - ATM S.A.
Lines: 46
Message-ID: <mtfe8g$7cu$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> <mtc3ip$vok$1@node2.news.atman.pl> <mtc56n$7m6$1@node1.news.atman.pl> <b2c86ec7-8415-40a7-988f-dd5ab18827f0@googlegroups.com> <mtcaik$d1l$1@node1.news.atman.pl> <mtckeb$nhk$1@node1.news.atman.pl> <mtcmsn$j1k$1@node2.news.atman.pl> <mtcq5e$tdl$1@node1.news.atman.pl> <1f8412e7-1873-4b19-9439-bcb269b9af3f@googlegroups.com>
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 1442528336 7582 89.73.81.145 (17 Sep 2015 22:18:56 GMT)
X-Complaints-To: usenet@atman.pl
NNTP-Posting-Date: Thu, 17 Sep 2015 22:18:56 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0
In-Reply-To: <1f8412e7-1873-4b19-9439-bcb269b9af3f@googlegroups.com>
X-Received-Bytes: 3208
X-Received-Body-CRC: 1188715242
Xref: csiph.com pl.comp.programming:27542

On 17.09.2015 14:37, M.M. wrote:
> On Thursday, September 17, 2015 at 12:23:43 AM UTC+2, bartekltg wrote:
>> On 16.09.2015 23:27, AK wrote:
>>> Użytkownik "bartekltg"  napisał:
>>>
>>>> No właśnie, niekiedy. A w standardowym przypadku jesteśąmy do tyłu.
>>>> Jeden przebieg zajmie zauważalną cześć czasu proponowanych tu
>>>> rozwiązań.
>>>> To wydaje się zbyt lekki problem na wstępną analizę danych.
>>>
>>> Zalezy. Zalkezy co sie rozumie pod terminem "przypadek standardowy".
>>> IMHO standardowy przypadek do dane "merytoryczne"/dziedzinowe.
>>
>> Przecież o tym piszę. Coś można wyciagnać i wykalibrować
>> algorytm, jeśli wiadoom, jakich danych statystycznie się spodziewać.
>
> Jak już przeciągamy, to ja ciekawy jestem, dla jakich danych najszybszy
> będzie będzie algorytm O(N^2). Jakie N, jaki procent duplikatów i jaki
> rozstęp, aby był najszybszy. Coś w ten deseń (z góry sory za błędy):
>
> bool exists( int t[] , int N, int v ) {
>    for( i=0 ; i<N ; i++ )
>      if( t[i] == v )
>         return true;
>    return false;
> }
>
> int uniq( int t[] , int N ) {
>     for( i=j=0 ; i<N ; i++ ) {
>        if( ! exist( t , j , t[i] ) )
>          t[j++] = t[i];
>     }
>     return j;
> }
>
> Dla N=100 mamy około 2500 operacji. Przy N*LogN mamy
> tylko 600, ale implementacja algorytmu kwadratowego
> jest zabójczo wydajna.

Pewnie jak przy sortowaniu. Tam granica to kilkadziesiąt
elementów.
Z tablicą hashującą jeszcze mniejsza. Kilka?

pzdr
bartyekltg