Algoritmusok

Sziasztok,

Periodiszitast kell tesztelnem kulombozo fuggvenyeken. Irtam, egy megoldast (Python-ban) ami ugy nez ki mukodik:


""" Visulation """
import matplotlib.pyplot as plt


""" szamitas """
from numpy import median, mean, greater, less, array as narray, append as nappend
from scipy.signal import argrelextrema

f, sp = plt.subplots(2, sharex=True)
X = [ i for i in range(0,len(fuggveny))]
sp[0].plot( X, fuggveny, c='red' )

def periodic(threshold):
""" fuggveny eltolasa es az eredetihez kepesti kulombbsegenek szamitasa """
diff = []
for i in range(0,len(threshold)):
diff.append( sum(map(lambda x,y: abs(x-y), threshold,threshold[-i:] + threshold[0:-i])))

"""
" A fuggveny szelsoertekeinek szamitasa
"""
localmax = argrelextrema(narray(diff), greater)
localmin = argrelextrema(narray(diff), less)
if len(localmax) > len(localmin) :
periodlen = [ localmax[0][i+1]-localmax[0][i] for i in range(0,len(localmax[0])-1) ]
else:
periodlen = [ localmin[0][i+1]-localmin[0][i] for i in range(0,len(localmin[0])-1) ]

"""
" Eredmeny tesztelese:
" ha tobb mint 4 lehetseges periodosunk van
" elfogadjuk a periodicitast ha a fuggveny szelsoertekek kozotti tavolsag szimetrikusak
"""
if len(periodlen) > 4 :
medianp = median(periodlen)
if ( mean(periodlen) > 0.95*medianp) and (mean(periodlen) < 1.05*medianp):
print "There is periodicity! Length of period: " + str(int(medianp))
""" eredmeny abrazolasa """
sp[1].plot( [ i for i in range(0,len(diff)) ], diff)
return int(medianp)
else:
return periodic(diff)
else:
return 0

periodic(fuggveny)
plt.show()

A kovetkezo kerdeseim lennenek:
* helyese-e? Ugy ertem van-e olyan bemenet ami vegtelen ciklusba kuldi?
* tudtok-e gyorsabb megoldast, az eddigi teszteken elegedet voltam az eredmennyel, de ugy erzem eleg eroforras igenyes, mivel n* kell eltolnunk minden egyes tesztelesnel, igy ha jol lattom n^2 matrix-al dolgozun. Biztos, vagyok benne, hogy van valami gyorsabb algoritmus erre. Statisztikai elemzeshez kell, muszaly rubusztnak lennie.

Van egy olyan problémám, hogy adott n elem, amit m csoportba kell rendezni. Az alappélda egyszerű, adott 6 elem, amit két egyforma elemszámú csoportba kell rendezni. A kérdés, hányféleképpen tudom ezt megtenni? Emlékeim szerint ez a kérdéskör a kombinatorika témakörbe tartozik. Utoljára pont húsz éve tanultam kombinatorikát, szóval megkoptak az emlékeim.

Kérdésem, mi a pontos témakör, van erre valami ismert algoritmus amit használni lehet kevésbé egyszerű esetben (pl 10 elem, két nem feltétlen egyenlő elemszámú csoportba, de a csoportok elemszáma minimum 3; 100 elem, egyenlő elemszámú, de akárhány csoportba, stb)?

Szóval pointereket kérnék, merre olvasgassak utána (wikipédia is jöhet, abban is elvesztem).

Köszönöm,

Csaba

Arra lennék kíváncsi, hogy ki miként gondolja jónak az if-else szerkezet használatát.
Az if-else szerkezet használatára rengeteg ajánlás született az évek során.
Ezeket megpróbálom összeszedni, ha valakinek még jut az eszébe, akkor azokat is örömmel várom:

1. Ha csak lehet else-t ne használjunk, mert nehezen érthető lesz a kód! Ez főként hosszú if-es részeknél lehet, illetve egymásba ágyazottaknál.
   pl.

   
   if (cond1) {
     if (cond2) {
       if (cond3) {
       } else {
       }
     } else {
     }
   } else {
   }
   

2. Az előző pont egyik megoldásaként szokták ajánlani, hogy az összes ágára külön if készüljön.
   pl.

   
   if (cond1 && cond2 && cond3) {
   }
   if (cond1 && cond2 && !cond3) {
   }
   if (cond1 && !cond2) {
   }
   if (!cond1) {
   }
   

3. Ha használunk is else-t, akkor se használjunk egymásba ágyazott if-es szerkezetet!
4. Funkcionális programozást kedvelők szerint if-et egyáltalán ne használjunk, mert az side effect-et okoz, hanem csak az if-else-es ternary operátort (vagy ? : más nyelvekben)
5. if-ekben return-nel térjünk vissza a függvényből, így laposan (flat) tartható a struktúra. Ez szembe megy az egy függvény egy kilépési pont elvnek.
   pl.

   
   if (cond1) {
     return;
   }
   ...
   

6. if-else-ek helyett hacsak tudunk használjunk switch-et vagy pattern matching-et.
7. Többszörös típus vizsgálat helyett használjuk az OO polimorfizmusát.
8. Minden if után szerepeljen else ág is, akár üresen is, hogy lehessen látni, hogy nem felejtődött el.

Ha valaki kedvet érez, akkor refaktorálhatja a kedvenc nyelvén a Gilded Rose Kata-t, amiben rengeteg egymásba ágyazott if-else szerkezet van.
A feladat röviden:

1. Tesztek írása minden estre.
2. Kód refaktorálása, hogy könnyen érthető és módosítható legyen.
3. Új funkció hozzáadása: "Conjured" elemek kezelése

Nemrég gondolkodtam, hogy nekiállok csak úgy programozgatni szabadidőmben, egy felülről 2d mászkálós (egy kicsit klasszikus rougelike) játék lenne a cél, egy elég nagy térképen... itt jön kérdés, amire nem találtam választ: hogy lehetne leglogikusabban megoldani, hogy egy bolygó (kisbolygó :) ) gömbfelszinén a klasszkus 2D megjelenítéssel mozogjon valaki? Ugyanis ha elindul észak felé (felfelé), előbb utóbb eljut az Északi-sarkra, ahonnán tovább menve felfele, valójában már fejjel lefele megy dél felé, meg a többi problémás dolog, ami ebből a furcsa vetületből fakad...
Elsőre ilyen halva született ötletnek tűnik, de hátha valakinek lenne ötlete... :)

Üdv!

A cím nem biztos, hogy a legjobb, mert a szinkronizálás sok mindent jelenthet.

A következőt szeretném elérni: actorokat ütemezni, velük diszkrét esemény szimulációt csinálni.

A jelenlegi megvalósítás: egy actor a rendszer minden elemének küld egy "tick" üzenetet. Ennek hatására az actorok egymásnak küldenek mindenfélét, majd visszaküldenek egy "tock"-ot.

Az akka annyit garantál, hogy az egy actor által egy actornak küldött üzenetek sorban érkeznek meg. Ha ugyanannak az actornak többen küldenek üzenetet, azok valahogy összefésülődnek.

Nekem azt kellene biztosítanom, hogy a két "tick" közt küldött üzenetek a "tick"-ek közt fel is dolgozódjanak. Megoldható-e ez?

(Mobilról írtam, próbálok majd pontosítani)

Sziasztok.

Adott néhány ezer tizedes tört. Kerekíteni szeretném őket oly módon, hogy ez legyen a követendő példa az 5-re végződőeknél:

0.5 --> 0
1.5 --> 2
2.5 --> 2
3.5 --> 4
4.5 --> 4
5.5 --> 6

és ne ez:

0.5 --> 1
1.5 --> 2
2.5 --> 3
3.5 --> 4
4.5 --> 5
5.5 --> 6

Kérésem az, hogy míg utóbbinál, a felfelé kerekítés elve megy, az első verziónál valóban egyenlő valószínűséggel tudom felfelé és lefelé kerekíteni a számokat? Cél az, hogy a kerekített számok összegzésekor minél közelebbi érték legyen az eredetihez.

Másképp megfogalmazva:

a számhalmazból random módon kiválasztok 5000-et, majd kerekítés nélkül összeadom, ez legyen A.

Ezután a kerekített értékeket is összeadom, ez legyen B.

A és B különbségének abszolút értéke legyen minél közelebb a nullához, ez lenne a cél. Kérdés: Melyik kerekítés a hatásosabb, a felfelé kerekítés, vagy a másik?

Megjegyzés:
A nem 5-re végződő számok esetében a felfelé- és lefelé kerekítés hagyományos módszerei volnának.

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.

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)

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

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.