Algoritmus zapis pozic co nejusporneji – JavaScript, AJAX, jQuery – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 
Hledat
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno
Pergoly a střechy Brno

peter
~ Anonymní uživatel
3714 příspěvků
3. 8. 2017   #1
-
0
-

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

Nahlásit jako SPAM
IP: 2001:718:2601:258:c8d1:c6...–
peter
~ Anonymní uživatel
3714 příspěvků
3. 8. 2017   #2
-
0
-

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

Nahlásit jako SPAM
IP: 2001:718:2601:258:c8d1:c6...–
gna
~ Anonymní uživatel
1508 příspěvků
3. 8. 2017   #3
-
0
-

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).

Nahlásit jako SPAM
IP: 213.211.51.–
peter
~ Anonymní uživatel
3714 příspěvků
4. 8. 2017   #4
-
0
-

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 :)

Nahlásit jako SPAM
IP: 2001:718:2601:258:ad7c:aa...–
peter
~ Anonymní uživatel
3714 příspěvků
4. 8. 2017   #5
-
0
-

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 :)

Nahlásit jako SPAM
IP: 2001:718:2601:258:ad7c:aa...–
peter
~ Anonymní uživatel
3714 příspěvků
4. 8. 2017   #6
-
0
-

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
 

Nahlásit jako SPAM
IP: 2001:718:2601:258:ad7c:aa...–
peter
~ Anonymní uživatel
3714 příspěvků
4. 8. 2017   #7
-
0
-

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) }
 

Nahlásit jako SPAM
IP: 2001:718:2601:258:ad7c:aa...–
MilanL+1
Expert
4. 8. 2017   #8
-
0
-

#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?

Nahlásit jako SPAM
IP: 91.139.9.–
peter
~ Anonymní uživatel
3714 příspěvků
4. 8. 2017   #9
-
0
-

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 :)

Nahlásit jako SPAM
IP: 2001:718:2601:258:ad7c:aa...–
peter
~ Anonymní uživatel
3714 příspěvků
25. 8. 2017   #10
-
0
-

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.

Nahlásit jako SPAM
IP: 2001:718:2601:258:25af:c4...–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 3 hosté

Podobná vlákna

Ohrožování pozic jezdcem — založil MaxDJs

Algoritmus — založil Jirina.K

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032021 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý