On 16.09.2015 19:57, AK wrote:
> Użytkownik "M.M." <m...@g...com> napisał:
>
>> Gdzie n to ilosc unikalnych w zbiorze, a nie rozmiar calego zbioru.
>> Przy perfect-hash ilość bitów * ( max_value - min_value + 1). Dla
>> małej rozpiętości można łatwo zrobić perfect-hash.
>>
>> Dróg jest wiele, a jaką wybrać, to zależy od konkretnych danych.
>
> Ano wlasnie, a to jest czesto omijana sprawa ana rzecz "generycznosci".
> Zawsze warto przeanalizowac dane (chocby tylko po min i max).
> Koszt maly. Tylko jeden przebieg.
> Zysk (niekiedy) ogromny


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.

Za to jeśli wiemy coś o rozkładzie od początku, można dobrać
algorytm, choćby czy tworzyć zbiór dynamicznie zaczynając od
małej pamięći dla tej tablicy, powiększając, a więc realokując i
rehaszując w mairę potrzeby (jeśli liczba unikalnych wpisów jest
mała) czy budować od razu w tablicy hashującej wielkośći 2n (dla k=~=n).

Sprawdzanie min/max ma jedną neidogodność. Unikalnych wpisów może
być mało, a rozpiętość ich wartośći duża.


pzdr
bartekltg

do góry

Użytkownik "bartekltg" <b...@g...com> 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.
Jesli to sa dane "merytoryczne" to max -min << MAX_UINT
a wtedy mozna "zjechac" zznacznie z pamiecia gdyz zamiast hasha pelnego
uinta mozna uzyc bitseta na rzeczywiscie uzywawanej maxymalnej ilosci bitow
/czyli bits(max - min)/.

> Za to jeśli wiemy coś o rozkładzie od początku, można dobrać
> algorytm, choćby czy tworzyć zbiór dynamicznie zaczynając od
> małej pamięći dla tej tablicy, powiększając, a więc realokując i rehaszując w mairę
potrzeby
> (jeśli liczba unikalnych wpisów jest
> mała) czy budować od razu w tablicy hashującej wielkośći 2n (dla k=~=n).

I taki wlasnie jest (mniej wiecej) algorytm pythonowy ktory podalem szemranemu.

AK


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

do góry

On 16.09.2015 23:27, AK wrote:
> Użytkownik "bartekltg" <b...@g...com> 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ć.


> Jesli to sa dane "merytoryczne" to max -min << MAX_UINT


Bardzo dziwne załozenie. Pewnie prawdziwe, w _neiktórych_
dziedzinach.

> a wtedy mozna "zjechac" zznacznie z pamiecia gdyz zamiast hasha pelnego
> uinta mozna uzyc bitseta na rzeczywiscie uzywawanej maxymalnej ilosci bitow
> /czyli bits(max - min)/.

Główny spadek zapotrzebowania pamięciowego bierze się stąd,
że tablica będzie nie większa niż O(max-min).
Jak max-min zejdzie do zakresu bajta-dwóch, to w ogole
nie bawiłbym się w hashowanie, tylko zliczał. A to było
opisane jako pierwsza metoda w tym wątku.
Jest to jednak bardzo sztuczny przypadek (tak, tak, są
"dziedziny" gdzie to przypadek standardowy).



pzdr
bartekltg

do góry

On Wed, 16 Sep 2015 11:34:13 +0200, bartekltg <b...@g...com>
wrote:
> Dlatego proponowałem (unordered_)set zamiast (...)map.

A jest set w Fortranie?

do góry

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.

Pozdrawiam

>
>
> > Jesli to sa dane "merytoryczne" to max -min << MAX_UINT
>
>
> Bardzo dziwne załozenie. Pewnie prawdziwe, w _neiktórych_
> dziedzinach.
>
> > a wtedy mozna "zjechac" zznacznie z pamiecia gdyz zamiast hasha pelnego
> > uinta mozna uzyc bitseta na rzeczywiscie uzywawanej maxymalnej ilosci bitow
> > /czyli bits(max - min)/.
>
> Główny spadek zapotrzebowania pamięciowego bierze się stąd,
> że tablica będzie nie większa niż O(max-min).
> Jak max-min zejdzie do zakresu bajta-dwóch, to w ogole
> nie bawiłbym się w hashowanie, tylko zliczał. A to było
> opisane jako pierwsza metoda w tym wątku.
> Jest to jednak bardzo sztuczny przypadek (tak, tak, są
> "dziedziny" gdzie to przypadek standardowy).
>
>
>
> pzdr
> bartekltg

do góry

On 17.09.2015 08:12, slawek wrote:
> On Wed, 16 Sep 2015 11:34:13 +0200, bartekltg <b...@g...com> wrote:
>> Dlatego proponowałem (unordered_)set zamiast (...)map.
>
> A jest set w Fortranie?


A w Formula Translator jest coś poza macierzami zespolonymi? ;-)

Jak nie ma, to trzeba napisać.
Albo użyć języka, który lepiej nadaje się do naszych zadań.

pzdr
bartekltg

do góry

Użytkownik "bartekltg" <b...@g...com> napisał:

> Jak nie ma, to trzeba napisać.

Juz dawno napisane. Np:

http://flibs.sourceforge.net/sets.html

AK


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

do góry

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

do góry

On Thu, 17 Sep 2015 15:14:54 +0200, bartekltg <b...@g...com>
wrote:
> A w Formula Translator jest coś poza macierzami zespolonymi? ;-)

Są coarray. Jest OMP i ACC. BLAS. Jest operator potęgowania.

do góry

On 18.09.2015 07:22, slawek wrote:
> On Thu, 17 Sep 2015 15:14:54 +0200, bartekltg <b...@g...com> wrote:
>> A w Formula Translator jest coś poza macierzami zespolonymi? ;-)
>
> Są coarray. Jest OMP i ACC. BLAS. Jest operator potęgowania.

Czyli możesz mnożyć zespolone macierze równolegle i na GPU ;-)

FORTRAN jest bardzo dobrym językiem, ale jednek też o dość wąskiej
specjalizacji. Można tworzyć tam odpowiednik wszystkich struktur STLa.
Tylko po co skoro jest to bardzo upierdliwe i niewygodne. W COBOLu też
można ;-)


pzdr
bartgekltg

do góry