Algoritmusok

Referenciaszámlálás, elszálló mc

Fórumok

Korábbi topikokban már írtam, hogy az mc sajnos nagyon elszállós, és ez a hajlama az idő múltával nem csökken hanem inkább verzióról verzióra nő. Leggyakoribb esetek: Kijelölöm inserttel a törölni kívánt fájlokat, F8-at nyomok, mire az mc el-SIGSEGV-zik, és hagy egy core fájlt. Vagy csak ki akarok lépni, F10-et nyomok, mire keletkezik egy core fájl. A jelenség nem determinisztikus, néha előjön, néha nem.

Hogy hardverhibás a gépem. Persze, mind a húsz, és mindegyiknél éppen az mc-ben jön elő a hardverhiba. Más fórumokon is panaszkodnak az F8-as elszállásra. Egy helyen a Fejlesztő Úr azt válaszolta, hogy ő többezer fájlon tesztelte sikeresen az F8-as törlést, és szerinte a program jó. Persze hibás a logikája, millió fájlon végzett sikeres tesztből is csak annyi következik, hogy a program nem biztosan rossz.

Gondoltam, megnézem hol szálldos el az mc. A /etc/rc.local-ba bettettem ezt a sort:


echo '/var/crash/%e-%t.core' >/proc/sys/kernel/core_pattern

Ha ezután bármi elszáll, akkor /var/crash-ben keletkezik egy egyedi core fájl (lásd man core). Az mc esetében ilyesmi:


mc-1452426735.core

Hogy kényelmes legyen nézelődni, az mc-t úgy konfiguráltam, hogy az ilyen fájlon entert ütve rögtön induljon el az adott fájlra a gdb (debugger), amiben a bt parancs mutatja a callstacket. Ilyeneket látok:


...
Core was generated by `mc'.
Program terminated with signal SIGABRT, Aborted.
#0  0x00007f8404de0cc9 in __GI_raise (sig=sig@entry=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:56
(gdb) bt
#0  0x00007f8404de0cc9 in __GI_raise (sig=sig@entry=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:56
#1  0x00007f8404de40d8 in __GI_abort () at abort.c:89
#2  0x00007f8404e1d394 in __libc_message (do_abort=do_abort@entry=1, fmt=fmt@entry=0x7f8404f2bb28 "*** Error in `%s': %s: 0x%s ***\n") at ../sysdeps/posix/libc_fatal.c:175
#3  0x00007f8404e2966e in malloc_printerr (ptr=<optimized out>, str=0x7f8404f2bcc8 "free(): invalid next size (fast)", action=1) at malloc.c:4996
#4  _int_free (av=<optimized out>, p=<optimized out>, have_lock=0) at malloc.c:3840
#5  0x0000000000471043 in release_hotkey (hotkey=...) at widget-common.c:103
#6  0x000000000048680e in menu_entry_free (entry=0x25464a0) at menu.c:791
#7  0x00007f84053d2648 in g_list_foreach () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#8  0x00007f84053d266b in g_list_free_full () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#9  0x0000000000486991 in destroy_menu (menu=0x25c9060) at menu.c:831
#10 0x00007f84053d2648 in g_list_foreach () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#11 0x00007f84053d266b in g_list_free_full () from /lib/x86_64-linux-gnu/libglib-2.0.so.0
#12 0x0000000000486a82 in menubar_set_menu (menubar=0x25cedb0, menu=0x0) at menu.c:862
#13 0x0000000000486312 in menubar_callback (w=0x25cedb0, sender=0x0, msg=MSG_DESTROY, parm=0, data=0x0) at menu.c:618
#14 0x000000000041c2ea in send_message (w=0x25cedb0, sender=0x0, msg=MSG_DESTROY, parm=0, data=0x0) at ../../lib/widget/widget-common.h:162
#15 0x000000000041c48e in dlg_broadcast_msg_to (h=0x25ce030, msg=MSG_DESTROY, reverse=0, flags=0) at dialog.c:148
#16 0x000000000041dd49 in dlg_broadcast_msg (h=0x25ce030, msg=MSG_DESTROY) at dialog.c:986
#17 0x000000000041e4c4 in dlg_destroy (h=0x25ce030) at dialog.c:1268
#18 0x000000000044b3da in do_nc () at midnight.c:1793
#19 0x00000000004099e2 in main (argc=1, argv=0x7ffeefc18588) at main.c:400
(gdb) q

Ebből annyi látszik, hogy a widget-common.c modul 103. sorában meghívott release_hotkey függvényben következett be a baj. Lássuk, mi van ott:


void
release_hotkey (const hotkey_t hotkey)
{
    g_free (hotkey.start);
    g_free (hotkey.hotkey);
    g_free (hotkey.end);   //  <-- 103-dik sor
} 

Mi a tanulság. A gobject rendszer referenciaszámlálós szemétgyűjtést használ. Ha "valaki" használ egy objektumot, azaz referenciát tart fenn az objektumra, az megnöveli 1-gyel az objektumban tárolt referenciaszámlálót. Ha már nem kell az objektum, akkor meg 1-gyel csökkenti. Az objektum figyeli a saját referenciaszámlálóját, és ha a számláló 0-ra csökken, az azt jelenti, hogy már senkinek sincs rá szüksége, és megszünteti magát. Egyszerű, de sajnos több sebből vérző módszer. Ott vannak a körök. Ha az objektumok kölcsönösen referenciát tartanak fenn egymásra, akkor a referenciszámlálójuk sosem csökken 0-ra, zárványként beragadnak. Még nagyobb baj, hogy a referenciaszámláló módosítgatása sok esetben az alkalmazási program részévé válik, és nem világos, hogy kinek, és milyen időzítéssel kell elvégezni a módosítást. Az mc esetében is ez lehet a baj. A program g_free-vel meg akar szüntetni egy olyan objektumot, amelynek (vagy egy beágyazott objektumának) a refszámlálója korábban (tévesen) már le volt csökkentve. Na és persze a program elszállása, nem a hiba elkövetésekor következik be, hanem jóval később. Vagyis a hiba helyéről nem tudtunk meg semmit. Az ilyet baromi nehéz kinyomozni.

A referenciaszámlálós szemétgyűjtést nem is tekintik igazi szemétgyűjtésnek. Őszintén szólva az IT tudományban dilettáns modszernek számít. Éppen ezért kár, hogy ilyen rendszerek, mint a gtk (gnome, xfce4), python, referenciaszámlálós szemétgyűjtésre épülnek. Agyaglábakon állnak.

Sorozat függvény keresése

Fórumok

Adott egy játék (https://portal.gacivs.info), ahol a napokban jutottam el oda, hogy lehet a szárazföldi egységeket vízi járművekkel szállítani, így az élvezhetőbb játékmenet okán az eddigi "egy kontinens" térképgenerálás helyett szigeteket generálok

A szigetek generálása viszonylag egyszerű algoritmus alapján történik, az alábbi ábrán egy négyzet az egy 16x16 csempéből álló térképszelvény, szóval lesznek nagyjából 32x32 csempéből álló nagyobb szigetek, köztük pedig 32 csempéből álló tenger, amelyet néhány kisebb sziget tarkít (a kisebb szigeteket nem ábrázoltam):
https://twitter.com/gacivs/status/686923625140715520

A problémám az, hogy az időben folyamatosan regisztráló játékosokat el kellene helyeznem a szigeteken, némi harc kikényszerítése okán egy szigetre négy játékost kellene tennem, az alábbi két képen ábrázolt algoritmus szerint:
https://twitter.com/gacivs/status/687211310673739776
https://twitter.com/gacivs/status/687208408957620224

Az első lenne jobb, de a második se annyira rossz, csak ott a külsőbb körökön össze tud kerülni több olyan játékos, akik nagyon eltérő fejlettségi szinten vannak... :)

Tegnap óta forgatom az algoritmust, mint medve a sünt, de nem tudtam kitalálni olyan függvényt, amelyik a sorszámból visszaad egy koordinátát... :(

Több szem többet lát: van valami ötletetek? :)

Példa az első ábrára (a szürke négyzet bal alsó koordinátája):

sorszám -> (x,y)
0 -> (1,2)
1 -> (2,2)
2 -> (2,1)
3 -> (1,1)
4 -> (1,-2)
5 -> (2,-2)
...
12 -> (-3,2)
13 -> (-2,2)
...
16 -> (5,6)
17 -> (6,6)
18 -> (6,5)
19 -> (5,5)
20 -> (5,2)
...
24 -> (5,-1)

Kártyajáték és Kriptográfia

Fórumok

Egy kis kártyajáték implementációjának tervezése közben lukadtam ki az alábbi problémára:

A, B, C és D kártyáznának távolról, kölcsönösen ismerik egymás nyílt kulcsait.

Kellene generálni egy leosztást (N lap egy permutációját) úgy, hogy minden játékos biztos lehessen benne, véletlenszerű a leosztás már a játék elején, de ne ismerje a többi játékos lapjait, csak a sajátjait. Zero-knowledge proof?

Valahogy úgy indulnék neki, mint a Diffie-Hellman kulcsgenerálásnál, de lényeges szempont, hogy a résztvevők ne ismerhesség meg a teljes kulcsot.

Van valami ötletetek, milyen irányba nézelődjek analóg problémák iránt?
Köszi

Jól tervezett kód Mock/Stub-bal

Fórumok

A napokban létrehoztam egy blogbejegyzést: Mock & Stub, avagy hogyan tesztelünk rosszul tervezett kódot. Érdemes a videót (és esetleg a hozzászólásokat) megnézni!

Ott van egy nagyon jó videó Ken Scambler-től, aminek a végkövetkeztetése röviden ennyi:
Ha mock/stub kell a teszteléshez, akkor rosszul tervezett a kódom és érdemes áttervezni.

Egyik fórumtársunk szerint lehet jól tervezett kódunk akkor is, ha Mock/Stub kell a teszteléséhez.

Arra szeretném kérni minden programozó fórumtársamat, hogy ha tud ilyenre példát mutatni, akkor ne tartsa magában és ossza meg velünk!

Ui.: Kódot szeretnék kérni, akármilyet, akár pszeudo is lehet (legfeljebb nem értem meg :), és ne egy leírást adjatok.

Programozó felelőssége meddig terjed?

Fórumok

Sziasztok!

http://hup.hu/cikkek/20151009/az_amerikai_vw_vezer_a_szoftverfejlesztok…

A fenti cikk nyomán egy kérdés merült fel: ha a munkahelyeden szoftverfejlesztőként kapnál egy feladatot, amiről tudod hogy a végkimenetele szabálysértő vagy szabályozást kijátszó lesz, mit tartasz helyesnek?

a) ellentmondani, akár kirúgatás kockázata mellett

b) írásban (pl. emailben) felhívni a főnök figyelmét a szabálysértésre és ezután ha ennek tudatában még mindig erre utasít a főnök

1. szóban utasítva is elfogadod
2. csak írásban utasítva fogadod el - persze írásba jó eséllyel nem akarja adni

c) szó nélkül megcsinálhatod, hiszen neked csak programozói szerepköröd van

Szoftverfejlesztő alvállalkozóként ugyanerre a helyzetre mit lépnél?

Tendencia elteresek eszlelese

Fórumok

Sziasztok!

Biztos van mar valami kesz megoldas a problemamra, csak nem tudom rendesen megfogalmazni igy relevans eredmenyt se talaltam gugliban keresve, de remelem utba tudtok igazitani.
Olyanra keresnek valami altalanos megoldast, hogy grafikonok adatokat hogy lehetne osszehasonlitani, hogy lehessen latni a megszokott tendenciahoz kepest hany szazalek az elteres vagy ha van kiugro ertek.

Peldanak vegyuk pl bix forgalmi grafikonokat:
http://www.bix.hu/index.php?lang=hu&page=graph&swid=Summary&portid=BIX-…
ahol tegyuk fel eszlelni szeretnem ha grafikon tegnapi resze (vagy ha kulon grafikonok vannak naponta akkor tegnapi grafikon) jelentosen elter a megszokottol, altalanosan tobb mint 20%-al nagyobb a forgalom megszokotthoz kepest, avagy ha nem az egesz tegnapi, csak abban van egy kiugro ertek (pl megszakad par link es beesett a forgalom a harmadara fel orara).

Ez az elteres lehet akar elozo naphoz viszonyitva vagy elozo het ugyanazon napjahoz, a lenyeg az lenne hogy szazalekos elterest lehessen szamolni a tendencia valtozasra, ne konkret hatarertekeket kelljen figyelni, hanem automatan lekovesse ha pl atlagosan hetente 2%-al novekszik a forgalom, de eszlelje ha 20% elteres van adott napon az utobbi hetekben megszokotthoz kepest.

Milyen (fel)kesz megoldasok vannak ilyesmire, lehetoleg linux cronjob jelleggel futtathato megoldaskent?

Knapsack (?) probléma megoldása

Fórumok

Van egy valós életbeli problémám, a lényeg, hogy vannak értékek, emellett egy darabszám és egy összeg. A bruteforce megoldás 99%-ban jól működik, de ott az az 1%, ami bármikor bejöhet és mint tudjuk, ez be is jön.

A lényeg, hogy az alábbi listában a végén látható darabszámban vegyünk ki értékeket úgy, hogy a végén látható összeg kijöjjön.

Knapsack vagy ennek egy változata volt talán az, amit nézegettem, de egyelőre nem tudom eldönteni, hogy melyik megoldásnak kellene nekiállni, a dinamikus programozás változata ilyen értékeknél, ha jól értelmeztem, akkor elég halál memória szempontból.

Esetleg valakinek van javaslata, merre lenne érdemes nézelődni még?

NDX: 0 OSSZEG: 119709
NDX: 1 OSSZEG: 84657
NDX: 2 OSSZEG: 68233
NDX: 3 OSSZEG: 50364
NDX: 4 OSSZEG: 40664
NDX: 5 OSSZEG: 37626
NDX: 6 OSSZEG: 32079
NDX: 7 OSSZEG: 31902
NDX: 8 OSSZEG: 28440
NDX: 9 OSSZEG: 26180
NDX: 10 OSSZEG: 20632
NDX: 11 OSSZEG: 20535
NDX: 12 OSSZEG: 18548
NDX: 13 OSSZEG: 17824
NDX: 14 OSSZEG: 16424
NDX: 15 OSSZEG: 16406
NDX: 16 OSSZEG: 15864
NDX: 17 OSSZEG: 14909
NDX: 18 OSSZEG: 14907
NDX: 19 OSSZEG: 14131
NDX: 20 OSSZEG: 13956
NDX: 21 OSSZEG: 12374
NDX: 22 OSSZEG: 12047
NDX: 23 OSSZEG: 11621
NDX: 24 OSSZEG: 11269
NDX: 25 OSSZEG: 11230
NDX: 26 OSSZEG: 10917
NDX: 27 OSSZEG: 10316
NDX: 28 OSSZEG: 9826
NDX: 29 OSSZEG: 9690
NDX: 30 OSSZEG: 9594
NDX: 31 OSSZEG: 9367
NDX: 32 OSSZEG: 8231
NDX: 33 OSSZEG: 8056
NDX: 34 OSSZEG: 7779
NDX: 35 OSSZEG: 7454
NDX: 36 OSSZEG: 6947
NDX: 37 OSSZEG: 6877
NDX: 38 OSSZEG: 6501
NDX: 39 OSSZEG: 6325
NDX: 40 OSSZEG: 6147
NDX: 41 OSSZEG: 6147
NDX: 42 OSSZEG: 6074
NDX: 43 OSSZEG: 5791
NDX: 44 OSSZEG: 4039
NDX: 45 OSSZEG: 3682
NDX: 46 OSSZEG: 3650
NDX: 47 OSSZEG: 3639
NDX: 48 OSSZEG: 3159
NDX: 49 OSSZEG: 2610
NDX: 50 OSSZEG: 2331
NDX: 51 OSSZEG: 2256
NDX: 52 OSSZEG: 2136
NDX: 53 OSSZEG: 1553
NDX: 54 OSSZEG: 1470
NDX: 55 OSSZEG: 891
NDX: 56 OSSZEG: 235

DB: 27 OSSZEG: 344710

Password encoding

Fórumok

Van egy Fisotech 16 960H DVR-ünk aminek az IP alapú képességeivel nem vagyok teljesen megelégedve.

A webes felülete activeX-ben van megírva. 64 biten nem működik sem a webes sem a standalone kliens.

Elkezdtem revengelni a protokollt, h.264-et tol ki, amit az mplayer visz ügyesen átpipolva.

Más is csinált már ilyet egy másfajta DVR-hez:
http://tanidvr.sourceforge.net/

Ha már szívtam vele sokat akkor megcsinálnám normálisan mint a fenti programot.

Egy problémám van: a jelszó nem plaintextben utazik az authentikáció során a DVR felé, hanem valahogy enkódolva, amit nem ismerek.
Kipróbáltam 3 féle jelszóval amikre az alábbi hasheket küldte:



Jelszó 123456789:
80 c2 28 e7 47 96 f8 33 68 a9 12 c1 4a 93 eb ea

Jelszó 123456
96 ab f6 de 40 aa 36 44 d7 16 ea 49 82 73 c2 11

Jelszó 12345
fc ef bc 94 21 e8 7e 1e d7 16 ea 49 82 73 c2 11

Nem vagyok expert a szakmában, de hátha valaki ránézésre vágja, hogy milyen kódolás ez.

Ha van valami ötletetek esetleg, akár a kliensprogram revengelésére (valószínűleg .NET-ben írták, legalábbis .NET-es DLL-ek vannak a mappájában) akkor azt is szívesen veszem.

Köszi!

Kábelvágási probléma

Fórumok

Sziasztok,

A következő problémára szeretnék hatékony algoritmust találni:
- Adott több, különböző méretű kábel darab (pl: 1m, 3m, 4m, 5m, 32m, 47m, 57m, 500m, stb.)
- Adott több, különböző méretű kábel igény (pl: 45m, 100m, 110m, 18500m, stb.)

A cél az lenne, hogy megkeressük a legpontosabb egyezést, azaz ne vágjunk kábeldarabot további darabokra, ha van a kábel daraboknak olyan csoportja, amelynek összege kiadja a kábel igényt. Az igényt azonban minden esetben teljesíteni kell, tehát a kábelek darabolása néha elkerülhetetlen.
A jelenlegi megoldásomban azt vizsgálom, hogy x db tetszőleges szám összege ad-e pontos egyezést valamelyik kábelre, amiben x-et 1-től indulva folyamatosan növelem.
A problémám, hogy már 10 alatti x esetén is elérem a gép memóriájának határait és a futási sebesség is percekben mérhető (a kábel darabok száma és az igények száma is 100 feletti).

Előre is köszönöm a javaslatokat!

Legrövidebb utak keresése gráfokban

Fórumok

Sziasztok!

Dijkstra algoritmusát szeretném módosítani a következő problémára:
Adott egy súlyozott, irányítatlan gráf. Ebben a gráfban szeretném megkeresni bizonyos csúcspontok között a legrövidebb utakat olyan módon, hogy a csúcsok közötti utak ne tartalmazzanak előre meghatározott más csúcspontokat. Tehát az eljárás bemenete legyen például az (f1, f2, f3, f4, f5) ponthalmaz, tehát keresem ezen halmaz elemeiből képzett csúcspárok közti legrövidebb utakat a gráfban, azonban ez az út nem tartalmazhatja a bemeneti halmaz többi elemét. Azaz ha f1-f3 közötti legrövidebb utat keresem, akkor az f2, f4, f5 csúcspontokat nem szabad érinteni (csak ha tényleg nincs más megoldás).

Van már egy megoldásom, azonban az kissé számításigényes, ezért kérem a segítségetek.

Köszönöm előre is.

Üdv,
kormanyos