W dniu sobota, 24 listopada 2012 10:09:58 UTC-5 użytkownik e...@g...com
napisał:
> W dniu sobota, 24 listopada 2012 10:07:08 UTC-5 użytkownik e...@g...com
napisał:

> > Tymczasem w Edkolandzie: zredukowalem problem 2-bajtowych ciagow
> > do 3 12bitowych binow, 1 pass czytania, 1 pass obrobki. Za N-bajtowy sie zabieram
dopiero.

> Nie 3 tylko czterech 12bitowych binow, czyli cos jak histogram. Chce sie podobnie
zabrac za dluzsze sekwencje.

Robie to tak:
bajty dziele na pol, mam 4bitowe liczby. Niemniej, wazne sa bajty. W sekwencji
mam takie 4bitowce:
0 1 2 3

Zliczam z wchodzacych danych takie liczby zalozone z 4bitowych:
[0][1][2] - a
[0][1][3] - b
[0][2][3] - c
[1][2][3] - d
Sa to oczywiscie liczby 12bitowe, wiec mam po 4K licznikow, cztery zestawy.
Dotad jest latwo, mam 16K licznikow zamiast 64K (dwu bajtowe sekwencje).

Potem, da sie jadac po istniejacych wpisach z a i pasujacych [0][1] z b
zregenerowac istniejace sekwencje, przy czym c i d (o ile sie nie pomylilemK)
waliduja, ile ich bylo i czy w ogole. Wiec, z generowanej tak sekwencji
mamy ich liczbe wystapien, wystarczy pamietac najczesciej dotychczas
wystepujaca, oraz jednoczesnie zmniejszac liczniki o liczbe tych sekwencji,
przez co kolejne maja prawdziwa liczebnosc.

Musze zerknac na jakies CRC, aby miec to samo dla wiecej niz 4-ro podzialu
2och bajtow - bo taki na razie podzial mi (chyba) dziala.

--
Edek

do góry

W dniu 2012-11-24 16:26, e...@g...com pisze:
> W dniu sobota, 24 listopada 2012 10:09:58 UTC-5 użytkownik e...@g...com
napisał:
>> W dniu sobota, 24 listopada 2012 10:07:08 UTC-5 użytkownik e...@g...com
napisał:
>
>>> Tymczasem w Edkolandzie: zredukowalem problem 2-bajtowych ciagow
>>> do 3 12bitowych binow, 1 pass czytania, 1 pass obrobki. Za N-bajtowy sie zabieram
dopiero.
>
>> Nie 3 tylko czterech 12bitowych binow, czyli cos jak histogram. Chce sie podobnie
zabrac za dluzsze sekwencje.
>
> Robie to tak:
> bajty dziele na pol, mam 4bitowe liczby. Niemniej, wazne sa bajty. W sekwencji
> mam takie 4bitowce:
> 0 1 2 3
>
> Zliczam z wchodzacych danych takie liczby zalozone z 4bitowych:
> [0][1][2] - a
> [0][1][3] - b
> [0][2][3] - c
> [1][2][3] - d
> Sa to oczywiscie liczby 12bitowe, wiec mam po 4K licznikow, cztery zestawy.
> Dotad jest latwo, mam 16K licznikow zamiast 64K (dwu bajtowe sekwencje).
>
> Potem, da sie jadac po istniejacych wpisach z a i pasujacych [0][1] z b
> zregenerowac istniejace sekwencje, przy czym c i d (o ile sie nie pomylilemK)
> waliduja, ile ich bylo i czy w ogole. Wiec, z generowanej tak sekwencji
> mamy ich liczbe wystapien, wystarczy pamietac najczesciej dotychczas
> wystepujaca, oraz jednoczesnie zmniejszac liczniki o liczbe tych sekwencji,
> przez co kolejne maja prawdziwa liczebnosc.
>
> Musze zerknac na jakies CRC, aby miec to samo dla wiecej niz 4-ro podzialu
> 2och bajtow - bo taki na razie podzial mi (chyba) dziala.
>


Ale o co chodzi?

pzdr
bartekltg

do góry

W dniu sobota, 24 listopada 2012 10:31:36 UTC-5 użytkownik bartekltg napisał:

> Ale o co chodzi?

Probuje rozwiazac problem znacznie prostszy, ale taki jak slawek postawil
zadanie. Czy to ma wiekszy sens, nie wiem, ale wyglada na to, ze sie
da dla tego prostszego problemu - przy M=2, gdzie M to dlugosc sekwencji,
chociaz nie sprawdzilem zlozonosci worst-case.

--
Edek

do góry

On 2012-11-24, e...@g...com <e...@g...com> wrote:
> Robie to tak:

Słowo daję... czyta się to gorzej niż niektóre ustawy. Rozumiem, że
to jest sposób, w jaki myślisz o problemie, ale mógłbyś go przetworzyć
przed zaprezentowaniem.

Niestety nie jestem w stanie ogarnąć, co napisałeś poniżej "Robię to
tak:". Napisz to po polsku albo po matematycznemu. Albo zrób schemat
blokowy.

Poza tym nie jest prawdą, aby suma 3 liczb 4-bitowych wymagała 12 bitów,
choć nikt Ci nie broni tak jej zapisywać.

pozdrawiam,
PK

do góry

W dniu 2012-11-24 16:25, PK pisze:
> On 2012-11-24, bartekltg <b...@g...com> wrote:
>> Niedawno był to całkiem niezły watek o sortowaniu.
>> Sortowania pozycyjne tez były omówione;)
>
> Wiem. W nim również zwróciłem slawkowi uwagę, że nie rozumie sortowania,
> a potem przestałem się udzielać, bo po prostu żal mi było czasu. Nie
> mniej widzę, że Wasza dyskusja (trwająca chyba kilka tygodni) była
> dla niego zupełnie bezowocna.

Hmm, dyskusja była chyba głownie w około fira.
Zresztą, nie pamiętam dokładnie.


>> Ale posortować beż użycia > na elementach sortowanych się da;)
>> Pewnych specyficznych elementów, jak liczby naturalne.
>
> Można zastąpić relację ">" obliczeniem pewnych f(a,b) i g(a,b), ale
> wyniki tych funkcji trzeba przyrównać do zera.
> Poza tym operacja "=" jest zazwyczaj wolniejsza niż ">".

Ale czasem złożonością jednak przebija. Posortowanie
miliarda bajtów będzie szybsze 'sortowaniem przez zliczanie'
niz qsortem. Tylko jak często mamy taką potrzebę;-)


Odkopałem test, który robiłem w tamtej dyskusji.
Wygląda, że i inty lecą szybciej. Pod warunkiem,
że tablica jest dostatecznie duża.

A, to nizej to kod chyba niepoprawiony, sortowanie
nie jest stabilne. Trzeba gdzieś zamienić kierunek pętli.

pzdr
bartekltg


***
Przetestowane, porównane z std::sort
Na przedziale n 10^5 - 10^7 przewaga 2 do 3.5 raza
szybsze. Co ciekawe, przewaga pozycyjnego od pewnego
momentu maleje.


void pozycyjne(unsigned int * tab, int n)
{
const int shift = 16;
const int K = 1<<shift;

int * h = new int [K];
unsigned int * temp = new unsigned int [n];


for (int j=0;j<K;j++) //zerowanie
h[j]=0;

for (int j=0;j<n;j++)//zliczanie wystąpień
h[(unsigned short)(tab[j])]++;

for (int j=1;j<K;j++) //akumulacja/zmiana liczby wystąpień
h[j]+=h[j-1]; //na indeksy

for (int j=0;j<n;j++)//kopiowanie
{
temp[--h[(unsigned short)tab[j]]]=tab[j];
}
///////////faza druga
for (int j=0;j<K;j++) //zerowanie
h[j]=0;

for (int j=0;j<n;j++)//zliczanie wystąpień
h[(unsigned short)(temp[j]>>shift)]++;

for (int j=1;j<K;j++) //akumulacja/zmiana liczby wystąpień
h[j]+=h[j-1]; //na indeksy

for (int j=n-1;j>=0;j--)//kopiowanie
{
tab[--h[(unsigned short)temp[j]>>shift]]=temp[j];
}

delete[]temp;
delete[]h;

}

*****


pzdr
bartekltg

do góry

W dniu sobota, 24 listopada 2012 10:43:02 UTC-5 użytkownik PK napisał:
> On 2012-11-24, e...@g...com <e...@g...com> wrote:

> Słowo daję... czyta się to gorzej niż niektóre ustawy. Rozumiem, że
> to jest sposób, w jaki myślisz o problemie, ale mógłbyś go przetworzyć
> przed zaprezentowaniem.

> Niestety nie jestem w stanie ogarnąć, co napisałeś poniżej "Robię to
> tak:". Napisz to po polsku albo po matematycznemu. Albo zrób schemat
> blokowy.

> Poza tym nie jest prawdą, aby suma 3 liczb 4-bitowych wymagała 12 bitów,
> choć nikt Ci nie broni tak jej zapisywać.

No suma 3 liczb 4bitowych faktycznie nie wymaga 12bitow ani tu ani nigdzie
indziej. Ja tworze 4 12bitowe liczby z 16 bitow. Uwzgledniajac to, reload,
czyli przeczytaj jeszcze raz.

Na dodatek nie przedstawilem kodu, z czego sobie zdaje sprawe. Jutro
postaram sie albo powiedziec, ze sie gdzies sypnalem, albo przedstawic
kod.

--
Edek

do góry

On 2012-11-24, PK <P...@n...com> wrote:
> On 2012-11-24, Stachu 'Dozzie' K. <d...@g...eat.some.screws.spammer.invalid>
wrote:
>> Ze dwa lata temu, przy ostatniej przeprowadzce. Dostęp zdalny
>> i wirtualizacja czynią cuda, wiesz.
>
> Dostępem zdalnym wpinasz kable? To chyba jakaś nowa technologia!

To ty masz jakiś wypaczony obraz roboty admina, skoro uważasz, że musi
wpinać kable. Od tego są technicy, zwłaszcza gdy ma się pod opieką
maszyny w parunastu krajach niekoniecznie znajdujących się w Europie.

--
Secunia non olet.
Stanislaw Klekot

do góry

On 2012-11-24, Stachu 'Dozzie' K. <d...@g...eat.some.screws.spammer.invalid> wrote:
> To ty masz jakiś wypaczony obraz roboty admina, skoro uważasz, że musi
> wpinać kable. Od tego są technicy, zwłaszcza gdy ma się pod opieką

Myślę, że to Ty masz wypaczony obraz roboty admina, skoro uważasz,
że wszyscy admini siedzą w biurze i administrują zdalnie komputerami
w biurach rozsianych po Europie :D. Wyraźnie osobiste doświadczenia
obciążają Ci statystykę :].

W moim biurze większość tych rzeczy robi jedna osoba (od konfigurowania
komputerów stu pracownikom po organizację kabli itp). Technicy są wzywani
z zewnątrz do wiercenia, kładzenia podłogi itp. Nie musi się zajmować
pocztą, bo od tego są ludzie w centrali. No i jest prawdopodobnie
najbardziej lubianą (i oczekiwaną!) osobą w firmie, czego chyba
zdalny dostęp nie oferuje :D.

pozdrawiam,
PK

do góry

On 2012-11-24, Jacek <a...@o...pl> wrote:
> Dnia 24 Nov 2012 14:39:01 GMT, PK napisał(a):
>
>> On 2012-11-24, Jacek <a...@o...pl> wrote:
>>> Wita Ciebie pinda, bo takie firma ma założenia. Pinda jest po 100
>>
>> Zacznijmy od tego, że na pierwszej rozmowie w każdej sensownej pracy
>> zawsze jest obecna osoba, z którą będziesz pracował. Zazwyczaj jest to
>> szef zespołu czy dyrektor. Jeśli startujesz na dyrektora, to nawet
>> członek zarządu.
[...]
>> Pierwszą rozmowę zazwyczaj prowadzi kilka osób. Większość
>> pytań zadaje osoba, która szuka do zespołu (ona wypytuje Cię o wiedzę).
>> Obok niej siedzi osoba z HR i ona Cię obserwuje. Czasem zadaje jakieś
>> pytania ogólne - czasem żeby sprawdzić kandydata, czasem żeby mu pomóc
>> (jeśli jest zmęczony pytaniami merytorycznymi). Czasem nie odzywa się
>> wcale, ale sporo notuje.
[...]
> Panie PK, to co napisałem to nie moje wymyślanie, a to, co jest w firmie:
> http://www.mondigroup.pl/
> To tak dla przykłądu.

Przykładowa firma, w której nie jestem pewny czy chcę pracować, skoro
tak sobie uwidzieli.

> A pinda dla mnie zawsze będzie pindą.
> To taka osoba, która... jest podobna do Ciebie.

No nie powiedziałbym. Z PK mamy dość sensowną dyskusję, nawet jeśli
trochę za dużo sobie nietrafnie założył o mojej wiedzy o korporacjach.

--
Secunia non olet.
Stanislaw Klekot

do góry

On 2012-11-24, Stachu 'Dozzie' K. <d...@g...eat.some.screws.spammer.invalid> wrote:
> Przykładowa firma, w której nie jestem pewny czy chcę pracować, skoro
> tak sobie uwidzieli.

Ale bardzo ciekawa. Jak to możliwe, że firma zatrudniająca 1000 osób
ma 4 oferty pracy?

pozdrawiam,
PK

do góry