- Érintésnélküli fizetési megoldások - PayPass via NFC
- Ezek a OnePlus 12 és 12R európai árai
- Mobil flották
- Milyen okostelefont vegyek?
- Samsung Galaxy S24 Ultra - ha működik, ne változtass!
- Galaxy S22 One UI 6.1 frissítés: volt, nincs
- Két új verzióban érhető el két Huawei okosóra
- Samsung Galaxy Z Fold3 5G - foldi evolúció
- Telekom mobilszolgáltatások
- Samsung Galaxy Z Fold5 - toldozás-foldozás
Hirdetés
-
Megjelent az EasySMX, okostelefonok mellé szánt, multiplatformos kontrollere
ph Az 5,9, 6,4, illetőleg 6,8 hüvelykes készülékeket is fogadó "gamepadból" a Bluetooth lapka sem hiányzik.
-
A vártnál kevesebb iPad Pro fogyhat
ma A tandem OLED panel előremutató, ám drága, az olcsóbb iPadek lehetnek népszerűek.
-
Spyra: akkus, nagynyomású, automata vízipuska
lo Type-C port, egy töltéssel 2200 lövés, több, mint 2 kg-os súly, automata víz felszívás... Start the epic! :)
-
Mobilarena
Új hozzászólás Aktív témák
-
P.H.
senior tag
válasz
danesz17
#3492
üzenetére
A 3. és a 4. példánál a következő két dologra kell alapozni:
- olyan ciklusokat kell írni mindkettőben, ami az előző ciklus több eredményét felhasználja, pl. a harmadik esetben x^5 és x! kiszámítható az előző ciklus x^3 és 3! értékeiből, x^7 és 7! az x^5 és 5! értékekből, stb.
- a ciklus záró feltétele a bemeneti pontosság, ezt akkor érted el, ha a harmadik feladatban a ciklus előző és mostani lefutása által produkált eredmény eltérése kisebb, mint a kívánt pontosság, a negyedik példában az intervallum két határának különbsége kisebb annál.
Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙
-
P.H.
senior tag
Van egy fejtörőm Windows-os többszálú programozással kapcsolatban. Röviden leírom az előzményeket, amit tudni kell hozzá, illetve milyen Windows API-hívásokat használ:
Adott egy egyszálú program, ami számításokat végez több 10000 lefutású ciklusban, minden lefutáshoz 1-8 db 16 MB méretű memória kell neki munkaterületnek (ilyen egységekben, tehát mindig x-szer 16 MB, sosem mondjuk 1x32 vagy 1x48); sosem több, mint 8x16 MB, és ez ki van nullázva, ezek a kezdőértékek. Ezeket egy-egy ciklus végén felszabadítja a program, majd a következő ciklustörzshöz megint lefoglal valahányszor 16 MB memóriát, használja, felszabadítja, stb...
Ezt a GlobalAlloc(GMEM_ZERO,méret) API-hívás meg is oldja, nullázott memóriaterületet ad a programnak, viszont a program contextusában nulláz, ezért lassítja a programot.Az első továbblépési ötlet az volt, hogy lefoglalok előre 8x 16 MB puffert, írok egy gyors nullázót (SSE non-temporal store-ral), illetve ehhez egy pár kezelőrutint:
- minden pufferhez tartozik egy bit a LOCKBITS változóban, a megfelelő x. bit 1 értéke jelzi, ha foglalt az x. puffer, 0 ha szabad
- GETBUFFER: kinulláz egy szabad puffert és ezt adja eredményül, illetve bejegyzi a LOCKBITS bitjébe, hogy foglalt, aztán visszaadja eredményül
- FREEBUFFER: megjelöli a puffert szabadnak a LOCKBITS bitjében
- RESTARTBUFFERS: alapállapotot állít vissza, azaz az összes puffert megjelöli szabadnak (pl. hiba volt a számításban, így nem futnak le a megfelelő FREEBUFFER-ek); azaz praktikusan a LOCKBITS minden bitjét törli
Ez még mindig egyszálú program, viszont nincs GlobalAlloc és GlobalFree hívás futás közben, tehát gyorsabb.A továbblépéshez az SSD-k TRIM megoldását használtam fel: a puffert nem a GETBUFFER hívásnál nullázom ki, amikor már szükség van rá, hanem a felszabadításkor a FREEBUFFER hívásban. Mivel akkor már nem kell az a memóriaterület, ezért egy külön szálon (CREATETHREAD) hívom meg a nullázó eljárást, így a számítási szál nyugodtan futhat tovább, nem zavarják egymást. A kezelés is kicsit módosult:
- bevezettem egy PENDINGS változót a LOCKBITS mellé, amelynek 1 bitje jelzi, ha az adott puffer már nem használt, de még nem szabad, mert nullázása folyamatban van. Ez mindjárt kiderül, hogy miért kell, mivel a fenti kezelőrutinok a következőképpen módosultak:
- FREEBUFFER: megjelöli a puffert a PENDINGS bit-jében 1-re, és kreál egy szálat, ami kinullázza majd valamikor azt. A szál ha elindul majd valamikor, akkor kinullázza a memóriát, és »miután« kész van, akkor egyszerre törli a puffer bitjét a LOCKBITS és a PENDINGS változóban is.
- GETBUFFER: átnézem a LOCKBITS-ben, hogy van-e szabad puffer. Ha nincs, akkor a PENDINGS-ben bejelölt puffer-ek szálait összegyűjtöm és várok addig, amíg egy el nem készül a nullázással (WAITFORMULTIPLEOBJECTS any), aztán az ő címe lesz az eredmény.
- RESTARTBUFFER: összegyűjti a PENDINGS-ben bejelölt puffer-ek szálait, megvárja, amíg az összes elkészül a nullázással (WAITFORMULTIPLEOBJECTS all), majd azokra, amik foglaltak maradtak (A LOCKBITS bit be van állítva), meghívja a nullázót az összes pufferre, a program contextusában (ezt már nem szépítsük, hiba volt, úgyis mindegy).
Tehát a state-átmenetek egy pufferre:
1. szabad (LOCKBITS = 0) felhasználható
-> 2. foglalt (LOCKBITS = 1, PENDINGS = 0)
-> 3. még nem szabad (LOCKBITS = 1, PENDINGS = 1) erre érdemes várni
-> 1. szabad (LOCKBITS = 0)Ez a megoldás így konzisztens, működőképes (kb. 60-70%-ra terhel egy 8 magos gépet). Viszont mivel minden törléshez új szálat hozok létre és a lefutás után megszüntetem, a kernelidő nagyobb, mint szeretném (kb. 5%). Ezért jobb lenne egy olyan megoldás, ami előre létrehozná a 8 szálat is mindegyik puffer mellé, amik "végtelen" ciklusok lennének, csak egy-egy nullázás után egy event-re várnának (WAITFORSINGLEOBJECT), ezt a FREEBUFFER állítja be nekik, akkor lefuthat a következő nullázás; ha készen vannak, akkor beállítanak egy event-et, végeztek. Gyakorlatilag watchdog-szerűségek lennének, amik várnak, viszont rájuk is kell várni néha.
A nehézséget azok az esetek jelentik, amikhez a fenti működő megoldásban WAITFORMULTIPLEOBJECTS kell: mivel egy-egy thread-nek van default egy event-je (ezt a Windows hozza létre), ami 0, ha még fut és 1, ha lefutott. A program 3 esetet különböztet meg ezáltal:
-> szabad puffer
-> foglalt puffer és nincs törlőszála (felhasználás alatt)
-> foglalt puffer és van törlőszála (mindjárt szabad)A probléma az, hogy az event-ek ugyan 1 bites változóknak tűnnek, de nem lehet lekérdezni közvetlenül az értéküket, csak a következő játékszerek vannak:
- SETEVENT: beállítja 1-re az event-et
- RESETEVENT törli 0-ra az event-et
- WAITFORSINGLEOBJECT: megállítja a szálat és megvárja, amíg 1 lesz az event, amit kapott, akkor engedi tovább a szál futását
- WAITFORMULTIPLEOBJECTS any: megállítja a szálat és megvárja, amíg a paraméterül kapott eventek bármelyike 1 lesz, akkor engedi tovább a szál futását
- WAITFORMULTIPLEOBJECTS all: megállítja a szálat és megvárja, amíg a paraméterül kapott eventek mindegyike 1 lesz, akkor engedi tovább a szál futását
Továbbá az event-et lehet kreálni úgy, hogy csak addig maradjon 1, amíg ki nem olvassa WAITFORMULTIPLEOBJECTS vagy WAITFORSINGLEOBJECT, úgy is lehet kreálni, hogy mindig kézzel kelljen törölni 0-ra.Rövidre lehetne zárni az egészet, ha a főszál, aminek várnia kell (a GETBUFFER-ben vagy a RESTARTBUFFER-ben) beolvassa a PENDINGS biteket egy regiszterbe majd elindít egy ciklust, ami folyamatosan hasonlítja össze az aktuális PENDINGS biteket a regisztettel, hogy van-e változás, de ez ugye egy magot teljesen leterhel; ha beiktatok a ciklusba egy SWITCHTOTHREAD hívást is, akkor nem terheli le a magot, de ki tudja, hova kerül a vezérlés (csak elkapcsol innen, nincs paramétere) és mikor kerül vissza. Ennél elegánsabb megoldás jobb lenne.
Ha van valakinek ötlete, hogy hogyan lehetne hatékony konzisztens rendszert felépíteni a fenn vázolt feladatra event-ekkel és az 5(+1) eszközzel, vagy valami mással, ne tartsa magában
[ Szerkesztve ]
Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙
-
P.H.
senior tag
válasz
#89874944
#6934
üzenetére
A gyűrű azt jelenti, hogy a lehető legrövidebb a 2D-távolság az összekötött pontok között, azaz az összekötések összhossza minimális, ezzel visszavezetted a TSP (Traveling Salesman Problem) szituációra a kérdést, ez pedig NP-teljes. Letehetsz róla, hogy egyszerűbb algoritmust találsz a pontos megoldásra, mint a TSP, ez a bonyolultságelmélet szépsége, a visszavezethetőség. NP-teljes problémára pedig n pont esetén - ahogy cucka és Jester01 is írta - n! nagyságrendű (azaz nem polinomiális) műveletigényű általános megoldás van. Ha találsz egyet, ami polinomiális lesz, akkor esély van a matematikai Nobel-díjra és pár egyéb nagy összegű pénzdíj elnyerésére is.
Persze lehet keresni részben másképp is megoldást, nem kell végigpróbálni az összes n! megoldást - a metszés jó ötlet -, de akkor is kiszámíthatatlan lesz az időigény (pl. felveszel 100 pontot, arra x idő alatt talál megoldást a programod; elveszel belőle 20-at, azaz 80 marad és 3x-osára nő az időigénye).
[ Szerkesztve ]
Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙
-
P.H.
senior tag
Ha nem is kell a legrövidebbnek lennie, akkor is le kell fektetni, hogy mi a 'jó megoldás'. Ha a legjobbhoz viszonyítjuk (pl. legfejlebb 10%-kal hosszabb), akkor NP-teljes marad, mert akkor is ismerni kell hozzá a legrövidebbet, hogy ezt el tudjuk dönteni.
#6951: bármikor felírható olyan bemeneti adatsor, aminél nem fog működni. Elég sokat foglalkoztam a TSP-vel (asm megvalósítási szempontból és többszálúsítással is gyorsítva), de a bemeneti adatok mibenlététől és azok sorrendjétől való függőségén (pl. az összes pont egyetlen egyenesre vagy pl. pontosan 2 hatványai távolságra esnek egymástól) nemigen lehet változtatni.
[ Szerkesztve ]
Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙
-
P.H.
senior tag
válasz
bambano
#6952
üzenetére
A TSP egy gráf bizonyos pontjainak (azaz részgráfjának) bejárása, a gráf pedig adott jelen esetben is: pl. úgy, hogy két pont közötti adott a legrövidebb úttól (2D távolság mint közvetlen összeköttetés) a leghosszabbig (végtelen távolság) az összes él. Így nem kell utat "építeni".
Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙
-
P.H.
senior tag
válasz
bambano
#6956
üzenetére
Ponthalmaz, amelyeket összeköthetünk bármilyen módon: egyenes szakasszal összekötve megvan a legrövidebb távolságuk, de bármilyen más módon összekötve őket (akár más pontokon keresztül, akár a monitort körbekerülve egy görbével) is létezik él, azaz végtelen (élszámú) a gráf.
Ebből - mint a feladvány is mondja - célszerű azt a részgráfot kiválasztani, amiben minden gép minden géppel közvetlenül össze van kötve, ez már véges. "Az lenne a feladat, hogy adott pontokat(csomópontok, node) úgy kéne összekötni, hogy egy gyűrűt alkossanak." Ez nem bonyolult feladat, n node-ra:
pl. 1 <-> 2 <->...<-> n-1 <-> n <-> 1
Olyan gyűrűt keresni viszont ebben a részgráfban, amely nem metszi önmagát, és csak node-ban tudja egyáltalán (nyilván), ez NP-teljes.#6958: ezért mondtam, hogy a metszés jó ötlet. Nem ok nélkül ragaszkodik hozzá
[ Szerkesztve ]
Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙
-
P.H.
senior tag
válasz
bambano
#6960
üzenetére
A "Szerk"-edre mondtam gyakorlatilag, hogy nem ez bonyolult (ha a bemeneti pontok fokszáma 2):
1 <-> 2 <->...<-> n-1 <-> n <-> 1
Ha mindegyik mindegyikkel össze van kötve (a pontok fokszám n-1), és abból kell kiválasztani a gyűrűt, az már az. Ha pedig nincsenek előre definiáltan összekötve, akkor végtelen a fokszám: bármerre indulsz el, eljuthatsz bármely más ponthoz (ezért célszerű összekötnünk mindent mindennel közvetlenül és ebből kiindulni: miért indulnál el pl. az ellenkező irányba? Az csak egyrészt hosszabb élt eredményez, és a fenti triviális megoldást).
A 'legrövidebb' pedig vonatkozik a szélsőséges esetekre: egy egyenesre eső pontokra, szimmetrikus bináris fákra, stb.Nyilván ha van egy bármilyen (nem szükségesen legrövidebb) megoldásod, ott már lehet 'törni' pl. a metszésnek köszönhetően. Ez ugyanaz, mint kiindulni 2 pontból és mindig a legjobb helyre beilleszteni a következő pontot (ez sem polinomiális, mert n pontos gyűrűnél legrosszabb esetben n-1! próbát jelent - ha a próba mindig metsz a meglevő gyűrűvel az említett szélsőséges esetekben ).
Arguing on the Internet is like running in the Special Olympics. Even if you win, you are still ... ˙˙˙ Real Eyes Realize Real Lies ˙˙˙
Új hozzászólás Aktív témák
● olvasd el a téma összefoglalót!
Állásajánlatok
Cég: Promenade Publishing House Kft.
Város: Budapest
Cég: Ozeki Kft.
Város: Debrecen