Algoritmus zapis pozic co nejusporneji – JavaScript, AJAX, jQuery – Fórum – Programujte.com

Potreboval bych nejaky algoritmus, ktery mi zapise pozice cisel co nejvic usporne.

Mam nejaka cisla, ktera seradim a potrebuji zapsat jejich puvodni pozice.

3211 -> 1123 -> pozice 1 byla 3, dalsi 1 byla 4, 2 byla 2, 3 byla 1 -> 3421 (8 bitu)

Ted to resim tak, odmazavam prvek a zapisuji binarne.

3211 -> 1123
1 byla na 3, 10
321 (smazana nalezena 1)
1 byla na 3, 10
32
2 byla na 2, 1 (zbyvaji 2 cisla, takze nepotrebuji tolik bitu)
a posledni zapisovat nemusim, mam seznam prvku, tak je tam posledni zbyvajici na vsech ostatnich volnych pozicich
(5 bitu)

Delam to na 255 cislech (blok), takze tam samozrejme bude tech bitu vic usporenych. Ale stale to neni dost :) potreboval bych se dostat pod 3/4

Timhle zpusobem tam mam ted
int(33964) [1]=> int(29934) [2]=> float(0.88134495348016)
 

Takže máš 255 různých čísel v rozsahu 0-254 a nějak tě napadlo, že to zhustíš na 2/3? :)

Takhle ušetříš jen pár (desítek) bajtů. Můžeš zvětšit ten blok tak, aby tam bylo dostatek opakovaných sekvencí pro klasickou kompresi, nebo data analyzovat a mít několik kódování pro různé typy sekvencí (řada hodnot s deltou na X bitů a tak).

Nejsou to nahodila data. Je to to nejhorsi z nejhorsich :) Zamichana data s temer nulovym opakovanim.
Vseta jsem mel 2 napady a dostal jsem se z 0.881 na 0.86044225069562. Coz je samozrejme nic, kdyz potrebujes 0.75 a mene :)

Jo, jinak mi bracha napsal, ze je to vlastne podobne hledani stredu pro insert sort, kdy pulis cele pole do te doby, dokud je jeste, co pulit. Cim mene prvku, tim mene puleni. Takze jsem to vymyslel dobre. Ale musi to jit lip :)

A ted jsem se dostal na 0.818. Ale myslim, ze to je maximum pro tuto metodu.
array(3) { [0]=> int(352922) [1]=> int(288683) [2]=> float(0.81797961022549) }
Pro ten puvodni soubor to vyslo takto
array(3) { [0]=> int(33964) [1]=> int(28009) [2]=> float(0.82466729478271) }
2k z 30k usetrenych
 

Ok, tak napad byl dobrej, ale spatne jsem napsal pak kod, tak jen 0.8443.
array(3) { [0]=> int(352922) [1]=> int(297969) [2]=> float(0.84429137316461) }
 

#7 peter

co použít více průchodů pokud bys dosáhl  průměru 0.86 na průchod, tak druhým průchodem jsi na cca 0.74 a případně dalším na cca <0.66

EDIT: jinak trošku mě mate zadání blok 255 čísel, myslíš číslice "0-9" (v jakém formátu BYTE/BCD) nebo Byte v plném rozsahu 0-255? 

a trváš na tom poziciování nebo ti jde o kompresi?

Popremyslim o tom. Ale takhle na prvni pohled je to nesmysl. Pri prvnim pruchodu vim kterym 8-bitum patri ktere cislo. Po te se mi rozhodi pocet bitu pro jeden znak, zmeni se znaky. Ja tam ukladam i seznam znaku, ten taky neco sezere :)

Na nic nove jsem zatim neprisel.

Mam bloky, treba 4 cisla. Cisla muzou nabyvat 0-3.
Zapisuji to tak, ze urcim pocty cisel a z poctu, kdyz soucet dosahne 4, presnanu zapisovat.
A poradi zapisuji s odmazavanim z pole cisel.
Oboje delam binarne.

Pr:
2001 (binarne 4x2 bitu)

0012 - 0:2x, 1:1x, 2:1x, 3:0x
binarne rle: 0001100 (x=0, xx=1, xxx=2...) - pocty opakovani cisel, soucasne serazeni podle velikosti

vyber ze serazeneho pole:
2001 - pozice [0] = 2, kde najde 2 v serazenem poli?
0012 - 2 je ctvrta, binarne 11
001 - [1] = 0, 0 je nulta, bin 00
01 - [2] = 0, 0 je nulta, bin 0 - jedna nula, protoze pocet prvku k zapisu klesl
11000
A posledni cislo neni treba zapisovat. Pripadne, pokud by se opakovalo vicekrat, tez neni treba zapisovat, kdyz vim, ze je to posledni z pole pocet a vim, ze pocet prvku je 4.

Cili, vysledek je 0001100 11000 = 12 bitu

Pr2:
2000 -> 0002
0001100  10 = 9 bitu

Pr3
0000 -> 0000
nic = 0 bitu, ale tady je treba si to pohlidat a zapsat aspon pocet opakovani, 0000 = 4 bity

Vim, nevypada to zajimave. Ale, u vetsiho poctu cisel, treba 256 se blizi pomer 1. A mne zajima sada cisel, kde je kazde prumerne 1x. Takze pocet cisel bude tak obvykle 1-4 pro kazde z 256.
Hm, ted mne napada, ze bych mozna mel zkusit 65.535, kdyz to tak klesa :)
U poctu cisel mam spocitane min-max 1/8 az 2/8 pro 256, pomer 0.12 az 0.25, obvykle 0.24.
U pozice cisel je to zas v podstate soucet n/2 * n + n/4 * (n-1) + n/8 * (n-1)... proste 256*8+128*7... Takze pro 65.535 je to
32768 * 16 + 16384 * 15 ... = 983040
65535 * 16 = 1048576
pomer 0,9375, to je dost na prd :) Kdyz prictu 0.24 (za pocty znaku) to presahne 1 naprosto moc.