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?

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?