Algoritmusok

Biztos feltalálták már azt a spanyolviaszt, ami a bináris keresésnek egy olyan válfaja, amikor nem pontos értéket keresünk, hanem csak azt, hogy melyik "résben" van a keresett érték. Azaz pl. melyik (legnagyobb) tömbelemnél nagyobb-egyenlő a keresett elem.

Pl.
[0] => 0
[1] => 0.02792
[2] => 0.05246
[3] => 0.09098
[4] => 0.126
[5] => 0.2

S itt szeretném elhelyezni mondjuk a 0.1-et, aminek 3 lenne a helyes megoldása.
Próbáltam magam is összehozni az algoritmust, de valahogy még nem szép – biztos nem nálam merült ez föl először. Mi ennek a feladatnak a hivatalos neve?

A saját megoldásom egyelőre ez:

function ge($element, $array)
{
        $top = sizeof($array) -1;
        $bot = 0;

        while($top >= $bot) {
           $p = (int)floor(($top + $bot) / 2);
           if     ($array[$p] < $element) $bot = $p + 1;
           elseif ($array[$p] > $element) $top = $p - 1;
           else return $p;
        }
        return $top;

Szerk: most látom, hogy a https://wiki.prog.hu/wiki/Logaritmikus_keresés_(algoritmus) végén az utolsó bekezdés épp ezt taglalja.

https://www.dailymail.co.uk/news/article-8695071/Fury-new-Tesco-charity-promotion.html

A Tesco nem az elso, aki ezt csinalja, bar a gyakorlat nem ismeretlen Angliaban. Altalaban eddig ettermek muveltek, volt, aki service charge-nak nezte elsore, de volt, hogy amelle raktak direkt a szamla kozepere az "adomanyozast".

Alapgondolat: felkerekiteni a £6.54-et £7-re, mert egy jotekonysagi szervezetnek jobban hianyzik az a 46p, mint a vasarlonak, aki talan eszre se vette. Vagy csak siman £1 charity-nek ha £10 folott van a szamla.

Feltehetoen az AB testinget hasznaljak, de nem meres, hanem komplett csalas celjara. 3 ugyfelcsoport:

A: self-checkout: oket megkerdezik az automata penztarnal, hogy akarnak-e charity-nek fizetni valahany penny-t. Ha nem allnak mogottuk lila haju SJW-k, talan kelloen biztonsagban erzik magukat, hogy "No"-t reagaljanak.

B: self-checkout: oket nem kerdezik meg az automata penztarnal, csak levonodjon-e a charity-nek szant osszeg a szamlarol. Fel se tunik nekik, hogy a tippre £15-18 koruli vasarlas £16.34 helyett £17 lett

C: human checkout: velhetoen jutalekot adnak a penztarosnak, ha beszedi. Termeszetesen igen valoszinu, hogy a penztarost kikepeztek, hogy "kerdezni kell". De a penztaros nem kerdez, nem tartja be a belso szabalyzatot, hanem csak rauti a szamlara. Nem is ertjuk miert.

Megjelenik rola egy ujsagcikk. Akik "A" sorsolast kaptak a Tesco lottojaban, azok a kommentekben hulyenek nezik azokat, akik "B" vagy "C" sorsolast kaptak (oszd meg es uralkodj). Talan meg tanuskodni is elmenne nemelyik, hogy a "B" aldozata valojaban csak balfasz volt abban a szcenarioban, amit o kapott.

Ha netan veletlen fel is merul, hogy "B" szcenario letezik, akkor termeszetesen bug volt.

Kivancsi leszek a followupra: ugyanis kis eselyt latok arra, hogy ebben az orszagban a Tesco ezert szignifikans birsagot kapna majd. De barki tud barmi masrol eteren, az posztolja ide az update-jet.

Adjatok halat az egnek, hogy Magyarorszagon van GVH es PSZÁF. Ok ezeket rendesen elinteznek az biztos. Helyesen.

A hétvégén volt egy érdekes beszélgetésem egy informatikussal, aki állította, hogy egyes algoritmusok nagy prímszámok keresésénél megelégszenek majdnem prím eredménnyel is, mondván, így erőforrás-takarékosabban tudnak dolgozni.

Nekem már a "majdnem biztosan prím" fogalma is eléggé ijesztő, de hogy kétkulcsos titkosításban ilyent valóban használnának, el sem tudom képzelni. Kis kulcsok esetén ugye nem lenne lényeges nyereség, nagy kulcsokat meg ott használnak, ahol fontos a biztonság, tehát ott meg nem kockáztatnának.

Mit tudtok erről? Valóban vannak ilyen erőforrás-kímélő prímkereső algoritmusok, és ezeket valóban használják is? Ha igen, hol? Mire?

A kérdést lásd a tárgyban: Ért itt valaki az ebay vagy amazon API-hoz?

Ha van gyakorlati tapasztalatod vele kérlek segíts: van mód arra hogy a vásárlásaimat tételesen letöltsem a boltból?

Van itt egy link:

https://www.fourfourtwo.com/features/champions-league-last-16-draw-probabilities-liverpool-chelsea-tottenham-man-city-real-madrid-barcelona

meg egy másik:

https://es.besoccer.com/noticia/los-enfrentamientos-mas-probables-en-los-octavos-de-la-champions-league-19-20-760373

ahol a decemberi BL 8ad döntő párosításairól van valószínűségi táblázat. Tehát, mielőtt kisorsorsolták volna a párharcokat, mennyi volt a valószínűsége, hogy X csapat Y-t kapja ellenfélül. Most már tudjuk ki kit kapott.

Először az első cikkben található legegyszerűbb verziót kódoltam le (ahol 2002 darab különböző sorsolás közül az egyik valószínűsége ugyanakkora, mint bármely másiké, és megszámoltam az egyes párharcokat, majd leosztottam 2002-vel). Ekkor a valószínűségi táblázat így fest:

                          Real Tottenham  Atalanta  Atletico    Napoli  Dortmund      Lyon   Chelsea
                 PSG    0.000%   17.333%   14.885%   17.932%   14.885%   16.683%    0.000%   18.282%
              Bayern   18.082%    0.000%   15.085%   18.881%   15.085%    0.000%   14.286%   18.581%
                City   21.878%    0.000%    0.000%   22.627%   17.682%   20.779%   17.033%    0.000%
            Juventus   20.879%   20.629%    0.000%    0.000%    0.000%   20.180%   16.733%   21.578%
           Liverpool   21.878%    0.000%   17.682%   22.627%    0.000%   20.779%   17.033%    0.000%
           Barcelona    0.000%   22.328%   18.581%    0.000%   18.581%    0.000%   17.133%   23.377%
             Leipzig   17.283%   17.033%   14.785%   17.932%   14.785%    0.000%    0.000%   18.182%
            Valencia    0.000%   22.677%   18.981%    0.000%   18.981%   21.578%   17.782%    0.000%

Ez természetesen nem jó, ugyanis nem vesszük figyelembe az UEFA sorsolási stratégiáját (ahol először kihúznak egy 2. helyezettet, majd keresnek neki egy 1. helyezett ellenfelet a fennmaradó csapatokból, aztán megint húznak egy 2. helyezettet, stb.). Ennek kódja itt van, base64-ben:

LyoKICogcm0gLXJmIC4vYS5vdXQgJiYgZ2NjIC1nIC1hbnNpIC1wZWRhbnRpYyAtV2FsbCBjbF92
MS5jICYmICh0aW1lIC4vYS5vdXQpICY+IG91dF92MQogKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CiNp
bmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHRpbWUuaD4KCiNkZWZpbmUgTUFYIDgKI2RlZmlu
ZSBEUkFXQ09VTlQgMjAwMDAwMDAKCnZvaWQgY2xlYXJfbGlzdChpbnQgbGlzdFtNQVhdKSB7Cglp
bnQgaTsKCglmb3IgKGkgPSAwOyBpIDwgTUFYOyBpKyspIHsKCQlsaXN0W2ldID0gMDsKCX0KfQoK
aW50IGFsbF90YWtlbihpbnQgbGlzdFtNQVhdKSB7CglpbnQgaTsKCglmb3IgKGkgPSAwOyBpIDwg
TUFYOyBpKyspIHsKCQlpZiAobGlzdFtpXSA9PSAwKSB7CgkJCXJldHVybiAwOwoJCX0KCX0KCXJl
dHVybiAxOwp9CgppbnQgZ2VuZXJhdGVfbmV4dChpbnQgbGlzdFtNQVhdKSB7CglpbnQgY291bnQs
IGksIHRlYW0sIHNoaWZ0OwoKCWNvdW50ID0gMDsKCWZvciAoaSA9IDA7IGkgPCBNQVg7IGkrKykg
ewoJCWlmIChsaXN0W2ldID09IDApIHsKCQkJY291bnQrKzsKCQl9Cgl9CgoJdGVhbSA9IHJhbmQo
KSAlIGNvdW50OwoKCXNoaWZ0ID0gMDsKCWZvciAoaSA9IDA7IGkgPCBjb3VudDsgaSsrKSB7CgkJ
aWYgKGxpc3RbaStzaGlmdF0gPT0gMSkgewoJCQl3aGlsZSAobGlzdFtpK3NoaWZ0XSA9PSAxKSB7
CgkJCQlzaGlmdCsrOwoJCQl9CgkJCWktLTsKCQkJY29udGludWU7CgkJfQoJCWlmIChpID09IHRl
YW0pIHsKCQkJdGVhbSA9IGkrc2hpZnQ7CgkJCWJyZWFrOwoJCX0KCX0KCglsaXN0W3RlYW1dID0g
MTsKCglyZXR1cm4gdGVhbTsKfQoKLyogbGlzdDEtYm9sIChzbmQpIGh1enVuayBlZ3kgY3NhcGF0
b3QsIGVzIGFoaG96IGtlcmVzdW5rIGVsbGVuZmVsZXQgYSBsaXN0Mi1ib2wgKGZzdCkgKi8KaW50
IGNhbl9jb250aW51ZShpbnQgbGlzdDFbTUFYXSwgaW50IGxpc3QyW01BWF0sIGludCBleGNwdG5b
TUFYXVtNQVhdLCBpbnQgZHJ3W01BWF0sIGludCB0ZWFtMSwgaW50IHRlYW0yKSB7CglpbnQgY29w
eV9saXN0MVtNQVhdLCBjb3B5X2xpc3QyW01BWF0sIGNvcHlfZHJ3W01BWF07CglpbnQgaSwgaiwg
azsKCWludCByZW1haW47CgoJZm9yIChrID0gMDsgayA8IE1BWDsgaysrKSB7CgkJY29weV9saXN0
MVtrXSA9IGxpc3QxW2tdOwoJCWNvcHlfbGlzdDJba10gPSBsaXN0MltrXTsKCQljb3B5X2Ryd1tr
XSA9IGRyd1trXTsKCX0KCS8qY29weV9saXN0MVt0ZWFtMV0gPSAxOyovIC8qIGFscmVhZHkgZG9u
ZSBieSBnZW5lcmF0ZV9uZXh0KCkgKi8KCWNvcHlfbGlzdDJbdGVhbTJdID0gMTsKCWNvcHlfZHJ3
W3RlYW0xXSA9IHRlYW0yOwoKCWZvciAoaSA9IDA7IGkgPCBNQVg7IGkrKykgewoJCWlmIChjb3B5
X2xpc3QxW2ldID09IDApIHsKCQkJYnJlYWs7CgkJfQoJfQoJaWYgKGkgPT0gTUFYKSB7CgkJcmV0
dXJuIDE7Cgl9CgoJY29weV9kcndbaV0gPSAtMTsKCXdoaWxlIChpID49IDApIHsKCQl3aGlsZSAo
Y29weV9kcndbaV0gPCBNQVggLSAxKSB7CgkJCWNvcHlfZHJ3W2ldKys7CgkJCWlmIChjb3B5X2xp
c3QyW2NvcHlfZHJ3W2ldXSA9PSAxIHx8IGV4Y3B0bltjb3B5X2Ryd1tpXV1baV0pIHsKCQkJCWNv
bnRpbnVlOwoJCQl9CgkJCWZvciAoaiA9IDA7IGogPCBNQVg7IGorKykgewoJCQkJaWYgKGNvcHlf
bGlzdDFbal0gPT0gMSAmJiBjb3B5X2Ryd1tqXSA9PSBjb3B5X2Ryd1tpXSkgewoJCQkJCWJyZWFr
OwoJCQkJfQoJCQl9CgkJCWlmIChqIDwgTUFYKSB7CgkJCQlicmVhazsKCQkJfQoJCQlmb3IgKGog
PSAwOyBqIDwgaTsgaisrKSB7CgkJCQlpZiAoY29weV9saXN0MVtqXSA9PSAwICYmIGNvcHlfZHJ3
W2pdID09IGNvcHlfZHJ3W2ldKSB7CgkJCQkJYnJlYWs7CgkJCQl9CgkJCX0KCQkJaWYgKGkgPT0g
aikgewoJCQkJcmVtYWluID0gMTsKCQkJCWZvciAoayA9IGkgKyAxOyBrIDwgTUFYOyBrKyspIHsK
CQkJCQlyZW1haW4gJj0gY29weV9saXN0MVtrXTsKCQkJCX0KCQkJCWlmIChyZW1haW4gfHwgaSA9
PSBNQVggLSAxKSB7CgkJCQkJcmV0dXJuIDE7CgkJCQl9IGVsc2UgewoJCQkJCWRvIHsKCQkJCQkJ
aSsrOwoJCQkJCX0gd2hpbGUgKGkgPCBNQVggJiYgY29weV9saXN0MVtpXSA9PSAxKTsKCQkJCQlj
b3B5X2Ryd1tpXSA9IC0xOwoJCQkJfQoJCQl9CgkJfQoJCWRvIHsKCQkJaS0tOwoJCX0gd2hpbGUg
KGkgPj0wICYmIGNvcHlfbGlzdDFbaV0gPT0gMSk7Cgl9CgoJcmV0dXJuIDA7Cn0KCi8qIGxpc3Qx
LWJvbCBodXp1bmsgZWd5IGNzYXBhdG90LCBlcyBhaGhveiBrZXJlc3VuayBlbGxlbmZlbGV0IGEg
bGlzdDItYm9sICovCmludCBnZXRfb3Bwb25lbnQoaW50IGxpc3QxW01BWF0sIGludCBsaXN0MltN
QVhdLCBpbnQgZHJ3W01BWF0sIGludCBleGNwdG5bTUFYXVtNQVhdLCBpbnQgdGVhbTEpIHsKCWlu
dCBjb3VudCwgaSwgc2hpZnQsIHRlYW0yOwoKCWNvdW50ID0gMDsKCWZvciAoaSA9IDA7IGkgPCBN
QVg7IGkrKykgewoJCWlmIChsaXN0MltpXSA9PSAwICYmIGV4Y3B0bltpXVt0ZWFtMV0gPT0gMCkg
ewoJCQljb3VudCsrOwoJCX0KCX0KCglkbyB7CgkJdGVhbTIgPSByYW5kKCkgJSBjb3VudDsKCgkJ
c2hpZnQgPSAwOwoJCWZvciAoaSA9IDA7IGkgPCBjb3VudDsgaSsrKSB7CgkJCWlmIChsaXN0Mltp
K3NoaWZ0XSA9PSAxIHx8IGV4Y3B0bltpK3NoaWZ0XVt0ZWFtMV0gPT0gMSkgewoJCQkJd2hpbGUg
KGxpc3QyW2krc2hpZnRdID09IDEgfHwgZXhjcHRuW2krc2hpZnRdW3RlYW0xXSA9PSAxKSB7CgkJ
CQkJc2hpZnQrKzsKCQkJCX0KCQkJCWktLTsKCQkJCWNvbnRpbnVlOwoJCQl9CgkJCWlmIChpID09
IHRlYW0yKSB7CgkJCQl0ZWFtMiA9IGkrc2hpZnQ7CgkJCQlicmVhazsKCQkJfQoJCX0KCX0gd2hp
bGUgKCFjYW5fY29udGludWUobGlzdDEsIGxpc3QyLCBleGNwdG4sIGRydywgdGVhbTEsIHRlYW0y
KSk7CgoJbGlzdDJbdGVhbTJdID0gMTsKCglyZXR1cm4gdGVhbTI7Cn0KCgppbnQgbWFpbigpIHsK
CS8qCgljaGFyICpmc3RbXSA9IHsiUFNHIiwgIkJheWVybiIsICJDaXR5IiwgIkp1dmVudHVzIiwg
IkxpdmVycG9vbCIsICJCYXJjZWxvbmEiLCAiTGVpcHppZyIsICJWYWxlbmNpYSJ9OwoJY2hhciAq
c25kW10gPSB7IlJlYWwiLCAiVG90dGVuaGFtIiwgIkF0YWxhbnRhIiwgIkF0bGV0aWNvIiwgIk5h
cG9saSIsICJEb3J0bXVuZCIsICJMeW9uIiwgIkNoZWxzZWEifTsKCSovCglpbnQgZXhjZXB0aW9u
W01BWF1bTUFYXSwgbWF0Y2hlc1tNQVhdW01BWF07CglpbnQgZnN0X3VzZWRbTUFYXSwgc25kX3Vz
ZWRbTUFYXSwgZHJhd1tNQVhdOwoJaW50IHRlYW1fZnN0LCB0ZWFtX3NuZDsKCWludCBpLCBqOwoK
CXNyYW5kKHRpbWUoTlVMTCkpOwoKCWZvciAoaSA9IDA7IGkgPCBNQVg7IGkrKykgewoJCWZzdF91
c2VkW2ldID0gc25kX3VzZWRbaV0gPSAwOwoJCWZvciAoaiA9IDA7IGogPCBNQVg7IGorKykgewoJ
CQltYXRjaGVzW2ldW2pdID0gZXhjZXB0aW9uW2ldW2pdID0gMDsKCQl9Cgl9CgoJZXhjZXB0aW9u
WzBdWzBdID0gMTsKCWV4Y2VwdGlvblswXVs2XSA9IDE7CglleGNlcHRpb25bMV1bMV0gPSAxOwoJ
ZXhjZXB0aW9uWzFdWzVdID0gMTsKCWV4Y2VwdGlvblsyXVsxXSA9IDE7CglleGNlcHRpb25bMl1b
Ml0gPSAxOwoJZXhjZXB0aW9uWzJdWzddID0gMTsKCWV4Y2VwdGlvblszXVsyXSA9IDE7CglleGNl
cHRpb25bM11bM10gPSAxOwoJZXhjZXB0aW9uWzNdWzRdID0gMTsKCWV4Y2VwdGlvbls0XVsxXSA9
IDE7CglleGNlcHRpb25bNF1bNF0gPSAxOwoJZXhjZXB0aW9uWzRdWzddID0gMTsKCWV4Y2VwdGlv
bls1XVswXSA9IDE7CglleGNlcHRpb25bNV1bM10gPSAxOwoJZXhjZXB0aW9uWzVdWzVdID0gMTsK
CWV4Y2VwdGlvbls2XVs1XSA9IDE7CglleGNlcHRpb25bNl1bNl0gPSAxOwoJZXhjZXB0aW9uWzdd
WzBdID0gMTsKCWV4Y2VwdGlvbls3XVszXSA9IDE7CglleGNlcHRpb25bN11bN10gPSAxOwoKCWZv
ciAoaSA9IDA7IGkgPCBEUkFXQ09VTlQ7IGkrKykgewoJCXdoaWxlICghYWxsX3Rha2VuKHNuZF91
c2VkKSkgewoJCQl0ZWFtX3NuZCA9IGdlbmVyYXRlX25leHQoc25kX3VzZWQpOwoJCQl0ZWFtX2Zz
dCA9IGdldF9vcHBvbmVudChzbmRfdXNlZCwgZnN0X3VzZWQsIGRyYXcsIGV4Y2VwdGlvbiwgdGVh
bV9zbmQpOwoJCQlkcmF3W3RlYW1fc25kXSA9IHRlYW1fZnN0OwoJCQltYXRjaGVzW3RlYW1fZnN0
XVt0ZWFtX3NuZF0rKzsKCQl9CgkJY2xlYXJfbGlzdChmc3RfdXNlZCk7CgkJY2xlYXJfbGlzdChz
bmRfdXNlZCk7Cgl9CgoJZm9yIChpID0gMDsgaSA8IE1BWDsgaSsrKSB7CgkJZm9yIChqID0gMDsg
aiA8IE1BWDsgaisrKSB7CgkJCXByaW50ZigiJTcuMmYlJSIsIDEwMC4wICogbWF0Y2hlc1tpXVtq
XSAvIERSQVdDT1VOVCk7CgkJfQoJCXByaW50ZigiXG4iKTsKCX0KCglyZXR1cm4gMDsKfQo=

Ez a kód véletlenszámokat tartalmaz, ezért mindig más eredményt kapunk, nem is lehet precízen megmondani a valószínűségeket. Aztán eszembe jutott, hogy eliminálni is lehetne a véletlenszámokat úgy, hogy megszámoljuk az összes lehetséges kimenetelét az UEFA sorsolásnak (nekem 80720640 jött ki eredményül) és megszámoljuk, hogy melyik párharc hányszor fordult elő benne. Ennek itt a base64 kódja:

LyoKICogcm0gLXJmIC4vYS5vdXQgJiYgZ2NjIC1nIC1hbnNpIC1wZWRhbnRpYyAtV2FsbCBjbF92
Mi5jICYmICh0aW1lIC4vYS5vdXQpICY+IG91dF92MgogKi8KI2luY2x1ZGUgPHN0ZGlvLmg+Cgoj
ZGVmaW5lIE1BWCA4CiNkZWZpbmUgTUFYMiAxNgoKaW50IG1haW4oKSB7CgkvKgoJY2hhciAqZnN0
W10gPSB7IlBTRyIsICJCYXllcm4iLCAiQ2l0eSIsICJKdXZlbnR1cyIsICJMaXZlcnBvb2wiLCAi
QmFyY2Vsb25hIiwgIkxlaXB6aWciLCAiVmFsZW5jaWEifTsKCWNoYXIgKnNuZFtdID0geyJSZWFs
IiwgIlRvdHRlbmhhbSIsICJBdGFsYW50YSIsICJBdGxldGljbyIsICJOYXBvbGkiLCAiRG9ydG11
bmQiLCAiTHlvbiIsICJDaGVsc2VhIn07CgkqLwoJaW50IGV4Y2VwdGlvbltNQVhdW01BWF0sIG1h
dGNoZXNbTUFYXVtNQVhdOwoJaW50IHBhaXJzW01BWDJdOwoJaW50IHNvbHV0aW9uOwoJaW50IGks
IGo7CgoJZm9yIChpID0gMDsgaSA8IE1BWDsgaSsrKSB7CgkJZm9yIChqID0gMDsgaiA8IE1BWDsg
aisrKSB7CgkJCW1hdGNoZXNbaV1bal0gPSBleGNlcHRpb25baV1bal0gPSAwOwoJCX0KCX0KCgll
eGNlcHRpb25bMF1bMF0gPSAxOwoJZXhjZXB0aW9uWzBdWzZdID0gMTsKCWV4Y2VwdGlvblsxXVsx
XSA9IDE7CglleGNlcHRpb25bMV1bNV0gPSAxOwoJZXhjZXB0aW9uWzJdWzFdID0gMTsKCWV4Y2Vw
dGlvblsyXVsyXSA9IDE7CglleGNlcHRpb25bMl1bN10gPSAxOwoJZXhjZXB0aW9uWzNdWzJdID0g
MTsKCWV4Y2VwdGlvblszXVszXSA9IDE7CglleGNlcHRpb25bM11bNF0gPSAxOwoJZXhjZXB0aW9u
WzRdWzFdID0gMTsKCWV4Y2VwdGlvbls0XVs0XSA9IDE7CglleGNlcHRpb25bNF1bN10gPSAxOwoJ
ZXhjZXB0aW9uWzVdWzBdID0gMTsKCWV4Y2VwdGlvbls1XVszXSA9IDE7CglleGNlcHRpb25bNV1b
NV0gPSAxOwoJZXhjZXB0aW9uWzZdWzVdID0gMTsKCWV4Y2VwdGlvbls2XVs2XSA9IDE7CglleGNl
cHRpb25bN11bMF0gPSAxOwoJZXhjZXB0aW9uWzddWzNdID0gMTsKCWV4Y2VwdGlvbls3XVs3XSA9
IDE7CgoJaSA9IDA7CglwYWlyc1tpXSA9IC0xOwoJc29sdXRpb24gPSAwOwoJd2hpbGUgKGkgPj0g
MCkgewoJCXdoaWxlIChwYWlyc1tpXSA8IE1BWCAtIDEpIHsKCQkJcGFpcnNbaV0rKzsKCQkJaWYg
KGkgJSAyID09IDEpIHsKCQkJCWlmIChleGNlcHRpb25bcGFpcnNbaV1dW3BhaXJzW2ktMV1dKSB7
CgkJCQkJY29udGludWU7CgkJCQl9CgkJCX0KCQkJZm9yIChqID0gaSAlIDI7IGogPCBpOyBqICs9
IDIpIHsKCQkJCWlmIChqIDwgaSAmJiBwYWlyc1tqXSA9PSBwYWlyc1tpXSkgewoJCQkJCWJyZWFr
OwoJCQkJfQoJCQl9CgkJCWlmIChqID49IGkpIHsKCQkJCWlmIChpID09IE1BWDIgLSAxKSB7CgkJ
CQkJc29sdXRpb24rKzsKCQkJCQlmb3IgKGogPSAwOyBqIDwgTUFYOyBqKyspIHsKCQkJCQkJbWF0
Y2hlc1twYWlyc1syKmorMV1dW3BhaXJzWzIqal1dKys7CgkJCQkJfQoJCQkJCS8qCgkJCQkJcHJp
bnRmICgiJWQuXG4iLCBzb2x1dGlvbik7CgkJCQkJZm9yIChqID0gMDsgaiA8IE1BWDsgaisrKSB7
CgkJCQkJCXByaW50ZigiJXMgdnMuICVzXG4iLCBmc3RbcGFpcnNbMipqKzFdXSwgc25kW3BhaXJz
WzIqal1dKTsKCQkJCQl9CgkJCQkJcHJpbnRmICgiXG4iKTsKCQkJCQkqLwoJCQkJfSBlbHNlIHsK
CQkJCQlpKys7CgkJCQkJcGFpcnNbaV0gPSAtMTsKCQkJCX0KCQkJfQoJCX0KCQlpLS07Cgl9CgoJ
cHJpbnRmICgiJWQgcG9zc2libGUgVUVGQSBkcmF3cyBmb3VuZC5cblxuIiwgc29sdXRpb24pOwoK
CWZvciAoaSA9IDA7IGkgPCBNQVg7IGkrKykgewoJCWZvciAoaiA9IDA7IGogPCBNQVg7IGorKykK
CQkJcHJpbnRmICgiJTcuM2YlJSIsIDEwMC4wICogbWF0Y2hlc1tpXVtqXSAvIHNvbHV0aW9uKTsK
CQlwcmludGYgKCJcbiIpOwoJfQoKCXJldHVybiAwOwp9Cg==

De itt ugyanazt a táblázatot kaptam mint az első esetben (amikor 2002 különböző sorsolás volt)! Hol van baj a gondolatmenettel? A tényleges valószínűségi értékeket nem is lehet megállapítani véletlenszám-generálás nélkül?

p.s.: fociban nem otthonlévőknek annyi adalék, hogy

 - minden 1. helyen végzett csapat 2. helyezettel találkozik

 - akik 1 csoportban voltak, nem kerülhetnek össze a 8ad döntőben (https://www.uefa.com/uefachampionsleague/standings)

 - azonos országból lévő csapatokat sem sorsolhatnak össze

Itt a videó, ahogy lezajlott a mostani sorsolás: https://www.youtube.com/watch?v=iSR4PaAiHn4

Legyen a feladat mindössze ennyi: van két gép, köztük hálózati kapcsolat, s át kellene vinni valahogy a hangot.

A feladat felületesen szemlélve egyszerű. Analóg jelet mintavételezzük, igény szerint tömörítünk, titkosítunk, hálózaton átküldjük az egészet, túloldalon kititkosítjuk, kitömörítjük, az adatokat átadjuk a hangszervernek, majd ő ugyanazzal a mintavételi frekvenciával lejátssza. Na persze. :)

Ahhoz, hogy ez működjön, a küldő és a fogadó oldalon hajszál pontosan azonos mintavételi frekvencia kell. Ha ez nem igaz, s a vevő lassabban nyeli a hangot, mint az adó küldi, akkor buffer overflow lesz. Ha viszont gyorsabban nyeljük a mintákat annál, mintsem azok beérkeznének, buffer underflow lesz a vége. Márpedig a küldő és fogadó oldalon lévő 44.1 kHz csak névlegesen annyi, nem pedig hajszál pontosan.

Felületesen nézve programokat, azt láttam, hogy buffer underflow esetében megnövelik a bufferelendő adatmennyiséget, tehát a buffer hosszát, s ezzel a latency-t. Ezzel megoldottunk volna bármit is? Alighanem áthúztuk a döglött lovat a szomszéd utcába: a küldő továbbra is lassabban küld, mint ahogyan a fogadó fél eszi az adatokat. Nagyobb bufferrel ritkábban fog recsegni a hang, de akkor, ha megáll, hosszabb ideig lesz csendben. A megnövekedett latency viszont teljesen hazavágja majd a visszhang elnyomó algoritmusokat.

Ámde találtam egy ígéretes nevű függvényt:

pa_stream_update_sample_rate()

Change the stream sampling rate during playback.

Arra gondoltam, a vételi oldalon figyelni kellene a buffer telítettségét, s az optimális értéktől való eltérést egy integráló típusú szabályozó alapjeleként lehetne felhasználni. Nyilván limiterek kellenek, de ez könnyen implementálható. Finoman állítani kellene a mintavételi frekvenciát, elérve azt, hogy az adó és vevő oldalon átlagosan - a szabályozás következtében - hajszál pontosan megegyezik majd a mintavételi frekvencia.

Ez persze a lejátszási sebesség és a hallható hang frekvenciájának finom modulálásával jár, de beszédhang esetén ez szerintem nem lesz zavaró.

Azt gondolom erről a függvényről, hogy a lelke mélyén újramintavételezéssé fajul, mert szerintem a hangkártyáknak nem lehet 1 Hz felbontással bármekkora mintavételi frekvenciát megadni.

Mi a véleményetek? Működni fog?

Első körben tervezek írni egy teszt programot, amely mondjuk egy 1 kHz-es szinuszos jelet játszik le, miközben változtatnám a mintavételi frekvenciát. Még nem kezdtem el, s nem tudom, mikor lesz rá időm, szóval türelem. :)

Van sok kis fájlom, amikben van némi rendundancia, jól tömöríthetőek elméletben. Nevezzük őket log bejegyzéseknek.

Önmagukban túl rövidek a bejegyzések ahhoz, hogy egy LZ-szerű tömörítő "bemelegedjen". Viszont annyira hasonlóak a bejegyzések, hogy hosszútávon kialakulhatna egy ideális prefix-szet, vagy tömörítőállapot, amivel jól lehetne tömöríteni. Például csak decimális számjegyek vannak benne space-ekkel elválasztva.

Nem szeretném viszont úgy tömöríteni őket, hogy egyetlen stream-be szedem össze őket, mert jó volna, ha random elérhető maradna az adat.

Az a kérdésem, hogy van-e erre valami standard megoldás: például betanítok egy tömörítőt, hogy jól kezelje a számokat, és ebből a tömörítőállapotból kiindulva tömörítem a fájlokat? Van erre működő példa, vagy lib, ami tudja ezt és egyszerű használni? Java-hoz kellene.

(Plusz komplexitás, hogy minden bejegyzésben van 2-3 szakasz, amiknek eltérő struktúrája van, eltérő módon tömörítendőek, de ezzel külön meg tudok küzdeni. Például van benne függvény-szerű adatsor, amit differenciális kódolással lehet jól összenyomni, egy másikban random számok vannak, egy harmadikban pedig majdnem mindig ugyanaz.)

Adathalmaz elemzése diverzitás-entrópia-információnyereség alapján.

Azzal a céllal készítettem, hogy a sok-sok inputból ki tudjam szedni azokat, amelyek leginkább (vagy: egyáltalán) hatnak az output(ok)ra.

Lépések:

(1) Egyenként meghatározom az inputok diverzitását. A meghatározás alapja a Shannon féle képlet módosított formája. A módositás abból áll hogy az egyes p*log2(p) tagokat visszaosztom az adatosztályok (kvantálási szintek) számának 2-es alapú logaritmusával. Ez azt eredményezi, hogy a kapott érték mindig 0.00 és 1.00 között lesz, így az egyes inputok diverzitása azok kvantálási metódusától függetlenül összehasonlítható lesz. Más szavakkal:

A p(x)=1/2 -> H(x)=1 helyett az lesz, hogy H(x) = 1, ha az eloszlás az adatosztályok között egyenletes.

Az adatosztályok számát és a kvantálási szinteket úgy választom meg, hogy a H(x) értéke a legnagyobb legyen, ez biztosítja a legnagyobb diverzitást.

(2) Kiszámolom az egyes inputok outputra vonatkoztatott entrópiáit, szintén a módosított Shannon-képlettel (az inputnak outputra vonakozó particionált diverzitásainak összege).

(3) A kinyerhető információt úgy kapom meg, hogy az output diverzitásából kivonom a 2. pont szerinti összeget.

Teszteltem a módszert max 72 inputtal max 1.000.000 adatsorral, több adatbázison. Tapasztalataim szerint:

- a 0.9 fölötti diverzitások és a 0.9 alatti entrópiák már jól használhatók;
- a 0.1 fölötti kinyerhető információ már erős összefüggést takar;
- a 0.01 alatti kinyerhető információval rendelkező input gyakorlatilag zaj.

A szimpla adatelemzésen kívül tudom használni a módszert arra is, hogy különböző predikciós módszerek jóságát ellenőrizzem, kiválasszam közülük azokat, amelyeket érdemes kombinálni, javitva ezzel az előrejelzés minőségét.

Köszönöm a figyelmet: m.

Egy hobbi oldalamhoz készítettem egy egyszerű futás alatti kalóriaégetést számoló űrlapot. Napokat gugliztam, mire találtam egy olyan képletet, ami konkrét futóappok által számított eredményekhez hasonló értékeket adott.
Tudom, hogy a számítás nem lehet pontos, de viszonyításnak jó ... legalábbis ezt hittem.
A bemenő adatok: testtömeg, lefutott táv, futás ideje.
Pár napja azonban sikerült 13km-t 6 perccel rövidebb idő alatt lefutnom, ami érzésem szerint nagyobb kalóriaégetés kellene, hogy jelentsen. Ennek ellenére az algoritmusom szerint kevesebb kalóriát égettem. Még szomorúbb, hogy a sportórámhoz tartozó alkalmazás szerint is.
Szinte kizártnak tartom, hogy ha jobban megterhelem magam, kevesebb kalória égjen, ezért remélem, akad itt valaki, aki már jobban beleásta magát a témába, és van olyan algoritmusa, ami a valós égetéssel arányos eredményt adhat.

Egy hónapja vettem egy GPS+GLONAS okosórát sportoláshoz. Akkor fel is frissítettem rajta mindent, majd onnantól kezdve csak használtam, további frissítések nem történtek. A GPS gyorsan és pontosan tette a dolgát. Nem volt napi használatban, de hetente többször. Mivel megbízhatónak tűnt, elfogadtam az adatait, de pár napja már olyan durván mellémért, hogy kénytelen voltam pontosabban megfigyelni:
Egy 7km-es távot 7.3km-nek mért, de úgy, hogy a táv felénél, 3.5km-nél jelezte a 4km-t. Ilyen kis távon ezt elég durva tévedésnek érzem. Másnap ugyanezen a körön 7.28km-t mért összesen, de úgy, hogy a saját szoftverében a térképen kijelzett szakaszoknál az 5. km után a 7. km jött. Nem volt egyáltalán 6. km. Valami teljes őskáosz lett a mérések eredménye.
Aztán felfrissítettem az órát, és azóta megint tűpontos.
Ebből pedig rájöttem, hogy elképzelésem sincs arról, hogyan is működhet a GPS.
Eddig azt hittem, a műholdak sugároznak egy adott 4 dimenziós (tér-idő) koordinátát, és ezekből az adatokból háromszögeléssel határozza meg az óra a saját helyzetét. De ebben a folyamatban nincs frissítendő adat. Hallottam még az A-DATA fájlról, amit szoktak frissíteni, de erről is csak annyit, hogy gyorsítja a műholdak megtalálását, nem azt, hogy pontosítja.
El tudja valaki mondani a lényegét, hogy miért kell folyamatosan frissítenem az órát ahhoz, hogy pontos legyen?