× Kötetlen, játékon kívüli témák

normal Segítségkérés játékon kívül

Több
12 éve 4 hónapja #5492

Sziasztok,

Elég sokan vagyunk műszakisok a guildben, így gondoltam bekérdezek, hátha tud valaki segíteni. A Smith-Waterman algoritmussal ha esetleg képben van valaki, szóljon már legyen szíves.
Ragi/Jack


Up the Irons!

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5493

Szövegre kell? Vagy DNS szekvenciákhoz?


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5497

Dögrovás írta: Szövegre kell? Vagy DNS szekvenciákhoz?

Nyers szövegre..csináltam már belőle szekvenciát igazából


Up the Irons!
Utolsó szerkesztés: 12 éve 4 hónapja Írta: Ragingfist.

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5499

Na valahogy így néz ki:

Feldarabolod a 2 szöveget szavakra.
str1, str2
A mátrixod count(str1) x count(str2) -es lesz, a mátrix 0. sora és oszlopa 0-val van feltöltve.
A mátrix további elemei az alábbiak szerint töltődnek (bal fentről kezdve kell kitölteni):

Az [X,Y] hely értékének kiszámításához kell az [X-1, Y-1] értéke, ez módosúl a következők szerint:
Ha str1[X] == str2[Y] akkor növeled az [X-1, Y-1] értékét 2-vel, ha nem, akkor csökkented 1-el.
Ezen felül veszed az [X-1,Y] és az [X,Y-1] mezők értékét is, mindkettőt csökkented 1-1el. Az így kapott három érték közűl a legmagasabb lesz az [X,Y] helyen.

Az így feltöltött mátrix feldolgozása a következőképpen zajlik:
Mindíg a mátrix legmagasabb értékű pontjáról indul feldolgozás, minden esetben a [X-1,Y-1], [X-1,Y], [X,Y-1] mezők közül arra megy a feldolgozás tovább amelyiknek a legmagasabb az értéke. A bejárt mezőknek megfelelő szót (str1[X]) mindíg elrakja, ebből fog összeállni a két szöveg közti leghosszabb eggyezező rész (mindíg előre kell befüzni az eredmény stringbe).

Ez volt a kérdés? Vagy a matekjára vagy kiváncsi?


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5502

Ezzel amit te írtál negatív értékek lehetnek a mátrixban, de elvileg pont az lenne a lényeg, hogy ne legyenek, nem? Az elméletét szeretném megérteni leginkább, kérdésedre válaszolva.


Up the Irons!

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5503

Tudtommal lehet benne negatív, és a fentiekből látszik a lényege:
összehasonlítja a 2 szöveg szavait mindet mindegyikkel, Mivel mindíg az előző összehasonlítás eredményét növeli csökkenti, így a leghosszabb egyezés végén lesz a legnagyobb érték. Innen szépen visszalépked, és összerakja a sztringet. Addig megy visszafelé, amíg 0-t nem talál, vagy el nem fogynak a szavak.


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5504

The main difference to the Needleman-Wunsch algorithm is that negative scoring matrix cells are set to zero, which renders the (thus positively scoring) local alignments visible.


Ezt írták wikin, tehát akkor ami negatív simán 0-zni kéne, nem? Meg nekem vannak itt valami insert/delete súlyfüggvények is, ez lenne a +- 1?

+Bonus kérdés: mindig H[n+][m+1] lesz a legnagyobb értékű mező?


Up the Irons!
Utolsó szerkesztés: 12 éve 4 hónapja Írta: Ragingfist.

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5510

Igen feltöltéskor ebben az esetben ha <0 akkor 0-zni kell.
Az insert delete a következőt jelenti:
Ha nem átlóban halad a legnagyobb értéket követve a feldolgozás, az azt jelenti, hogy szó beszúrás, vagy szóhiány van az egyik str1-en. (ugye ha csak egyik irányba megy a feldolgozó nem átlósan -1,-1 irányba, akkor az egyik tengelyen azonos szón marad a következő vizsgálatkor is)
Ezért a feltöltéskor a [X-1,Y] mező értékét a Deletion, az [X,Y-1] mező értéket Insertion büntetéssel veszik figyelembe tehát így néz ki:

[X,Y] = max( ([X-1,Y] + Deletion), ([X,Y-1] + Insertion), [X-1,Y-1] + Match/Mismatch)

(én fentebb az Insertion, és Deletion büntetés értékét mindkettőt 1-re vettem):
4 fajta súlyozás van:
Match (ez az én példámban 2 volt)
Mismatch (ez -1)
Insert (ez -1)
Delete (ez is -1)

Mátrix

          EZ EGY PRÓBA SZÖVEG
      0    0  0    0     0
VAN-E 0   -1 -1   -1    -1
BENNE 0   -1 -2   -2    -2
EGY   0   -1  1    0    -1
PRÓBA 0   -1  0    3     2
0-zva:
          EZ EGY PRÓBA SZÖVEG
      0    0  0    0     0
VAN-E 0    0  0    0     0
BENNE 0    0  0    0     0
EGY   0    0  2    1     0
PRÓBA 0    0  1    4     3

Nem mindíg az utolsó mező a leganyobb értékű, lásd a fenti példát. A leghoszabb egyezés VÉGÉN lesz a legnagyobb érték, ez egyáltalán nem biztos, hogy a szövegek végére esik.


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…
Utolsó szerkesztés: 12 éve 4 hónapja Írta: Dögrovás.

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5513

Értem, ezek alapján megcsináltam a mátrixot, most fogok majd hozzá a tracebackhez. A súlyfüggvényeket viszont finomítanám, nem szimpatikus hogy mindegyik -1. Azt nem tudom, hogy hasraütés szerűen történik-e a változtatgatás, vagy ennek is van valami metodikája?


Up the Irons!

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5514

Attól függ milyen eredményt szeretnél kapni. Minél nagyobb a „büntetés” az adott függvényen, annál kevésbé fogja tolerálni az adott eltérést. Ha nagyokat vonsz le insert, delete-re, akkor rövidebb de teljesen azonos szövegek is bekerülhetnek. Ha nem túl nagy levonás van insert, delete-re, akkor egy két szó eltérés még bele fog férni, ha egyébként a szöveg egyezik.


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5515

Köszönöm, tiszta minden. Már csak a Java isten kegyére lesz szükségem :)


Up the Irons!

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 4 hónapja #5634

Nincs valakinek scribd acca véletlenül?Találtam pár könyvet, ami fenn van, és szívesen elolvasnám, de legalábbis problémás a dolog.

Kösz előre is!

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 3 hónapja #6012

Hátha valaki tud segíteni.
A kérdés az, hogy hogyan dönthető el GYORSAN két téglalapról, hogy van-e közös pontjuk. Mindkét téglalap élei 0 és 90 fokot zárnak be az X tengellyel. Adott a bal felső, és a jobb alsó sarkuk koordinátája. Fontos szempont a gyorsaság, tizedmásodpercenként többszáz összehasonlítást kell végezni. Csak olyan megoldás jöhet szóba, ami koordinátákkal dolgozik (tehát raszteren kitöltjük feketével az egyiket, ill másikat kékkel, és lesz-e közös rész nem játszik)


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 3 hónapja #6014

Dögrovás írta: Hátha valaki tud segíteni.
A kérdés az, hogy hogyan dönthető el GYORSAN két téglalapról, hogy van-e közös pontjuk. Mindkét téglalap élei 0 és 90 fokot zárnak be az X tengellyel. Adott a bal felső, és a jobb alsó sarkuk koordinátája. Fontos szempont a gyorsaság, tizedmásodpercenként többszáz összehasonlítást kell végezni. Csak olyan megoldás jöhet szóba, ami koordinátákkal dolgozik (tehát raszteren kitöltjük feketével az egyiket, ill másikat kékkel, és lesz-e közös rész nem játszik)

Legyenek az egyik téglalap (ezután A) bal felső sarkának a koordinátái (a_2, b_2) és a jobb alsónak (a_1, b_1), a másik téglalapnak (ezután X) pedig (x_2, y_2) illetve (x_1, y_1). Ezek alapján a_2<a_1, b_2>b_1, x_2<x_1 és y_2>y_1.

Vetítsd le a téglalapok oldalait a koordinátarendszer tengelyeire, és először dolgozzunk mondjuk csak az OY tengellyel.
Az A téglalap vetülete az OY tengelyre a i]b_1, b_2[/i zárt intervallum lesz, míg a B téglalapé az i]y_1, y_2[/i zárt intervallum. A két téglalapnak csak akkor lehet nem üres metszete, ha ez a két inervallum metszi egymást. Viszont ez pontosan akkor következhet be, ha egyszerre teljesülnek a b_2>y_1 és y_2>b_1 feltételek.

Ugyanígy, most nézzük az OX tengelyt, amelyen az i]a_2, a_1[/i és i]x_2, x_1[/i zárt intervallumokat kapjuk. A fenti gondolatmenet alapján annak feltétele, hogy a két téglalap metssze egymást az, hogy a_1>x_2 és x_1>a_2 egyszerre teljesüljön.

Nyilvánvaló, hogy a két téglalap akkor és csak akkor metszi egymást, ha a fent jelzett négy egyenlőtlenség egyszerre teljesül, vagyis

(b_2>y_1) és (y_2>b_1) és (a_1>x_2) és (x_1>a_2)

Megjegyzés: a feltételeid alapján érinthetik is egymást a téglalapok, vagyis fentebb > helyett >= kell mindenhova.

Utolsó szerkesztés: 8 éve 11 hónapja Írta: Dögrovás.

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 3 hónapja #6015

PFF automatikusan formázódtak a szögletes zárójeleim, amikkel az intervallumokat jelöltem. Érthető így?

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 3 hónapja #6016

Köszi, közben hasonlóra jutottam, bár kicsit olcsóbb (most fejeztem be az implementálást):
A két téglalapnak akkor és csak akkor van metszete, ha a mindkét téglalapot befoglaló legkisebb téglalap (fentiek szerint a min(a_2,x_2), min(b_2,y_2) és max(a_1,x_1), max(b_1,y_1) koordinátákkal leírt) megfelelő élhosszai rövidebbek mint a két vizsgálandó téglalap élhosszainak összege.

Azaz

( max(a_1,x_1)-min(a_2,x_2) < ( ( a_1 - a_2 ) + ( x_1 - x_2 ) ) ) ÉS ( max(b_1,y_1)-min(b_2,y_2) < ( ( b_1 - y_2 ) + ( b_1 - y_2 ) ) )


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 3 hónapja #6017

Frappáns megoldás, tetszik! :)
De nem lesz drágább implementálás szempontjából (bár csak két egyenlőtlenséget kell ellenőrizni, de számolsz néhány max. és min-t, meg több alapműveletet végzel)?

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 3 hónapja #6020

Szerintem nagyságrendilag azonos költsége van a két megoldásnak, min, max tulajdonképpen behelyetesíthető egy-egy egyenlőtlenséggel.
De lehet hogy az (((a_2+a_1)/2) - ((x_2+x_1)/2)) < ((a_2-a_1) + (x_2-x_1)) / 2 ) ÉS ((b_2+b_1)/2) - ((y_2+y_1)/2)) < ((b_2-b_1) + (y_2-y_1)) / 2 )) olcsóbb ezeknél, főleg, hogy a 2vel osztás elhagyható mindenhol. (Ez ugye azt mondja, hogy összeérnek, ha a két téglalap középontjainak X illletve Y koordinátában mért eltérése kisebb mint az adott irányú élhosszak átlaga)


A szar DPS-t nem megmagyarázni kell, hanem javítani rajta…
Utolsó szerkesztés: 12 éve 3 hónapja Írta: Dögrovás.

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 1 hónapja #8111

Az iránt szeretnék érdeklődni, hogy van-e itt bárki, aki - ha nem is érzi magát profinak - valamilyen szinten jártas a birkózás terén? Az angol szakkifejezések magyarításai érdekelnek, mivel a legtöbb magyar nyelvű oldalon csakis angol eredetiben találom meg őket, nekem viszont egy gyerekműsorhoz magyarul kellenének, mégsem akarok nagy hülyeségeket írni. Előre is köszi!

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Több
12 éve 1 hónapja #8292

Háelló! Na, már két hete itt vagyok a messzi távolban, és mivel esténként nem tudok mit kezdeni magammal, valamilyen módon vissza akarok jönni hozzátok. A következőre gondoltam:
Egy ilyenen dolgozom jelenleg:
http://www.dell-shop.hu/134607_adatlap_dell_nb_latitude_e5520_156_hd_int.html

És vennék hozzá egy ilyet:
http://www.saturn.de/mcs/catentry/3-5-2000-GB-USB-3.0-Spaceloop,48352,252084,201495.html
Vagy egy ugyanilyet usb 2-vel. A kérdés az lenne, hogy egyrészt a laptop integrált VGA-ja elbírná-e a wowot (nem feltétlenül full hdban), mert valahol azt olvastam igen. A másik pedig az, hogy a külső winchesterről való bootolás mekkora teljesítményromlást okoz, játszható lenne-e. A fő probléma az, hogy a céges gépre nem tudok telepíteni semmi okosságot, max egy virtuális gépet, de ahhoz nincs elég háttértára, macerás, etc.

Na, a lényeg hogy jönnék márciusban sárkányt ölni, de kellenek a releváns vélemények.
Ragi


Up the Irons!

Kérjük, hogy Bejelentkezés vagy , hogy csatlakozhass a beszélgetéshez!

Oldalmegjelenítési idő: 0.213 másodperc
Az oldal motorja a Kunena fórum