2015. december 23., szerda

avsort

Az elmúlt egy évemet, mióta minden tárgyamat abszolváltam a főiskolán, a szakdolgozatom szövegének megszülésével töltöttem. Ez töltötte ki a szabadidőm legnagyobb részét, még úgy is hogy csak szaros 80 oldal a teljes produktum.

Na de lássuk hogy miről is van szó:

Talán láttátok már a fenti videót, vagy esetleg ennek a lokalizált verzióját:

Az első videón Timo Bingmann sound-of-sorting nevű szoftvere látható működés közben. Ez a program mindenféle számítógépes rendező algoritmus működését mutatja be animációval, és azzal az édes 8-bites fütyüléssel. Az animáció során látható ahogy az algoritmus összehasonlít és megcserél értékeket, és a vizsgált értékek nagyságával arányos frekvenciájú hang is hallható. Az egész játék arról szól, hogy nem csak nézni, hallgatni is érdekes ahogy az értékek növekvő sorrendbe rendeződnek.


avsort

A szakdolgozatom témája ennek a szoftvernek egy javascriptes implementációjáról szól. Természetesen egyáltalán nem titkoltam hogy honnan ered az ötlet, de kifejezetten nem klónt akartam készíteni. A programom, az avsort, elég sok mindenben különbözik a sound-of-sortingtól, elsősorban renderelési lehetőségekben (a sound-of-sorting javára), de egy szerintem egész izgalmas funkcióval sikerült ellátnom, még hozzá hogy nem csak elolvasható a betöltött algoritmus forráskódja, de szerkeszthető is. Tehát a program limitációin belül bárki írhat magának saját algoritmusokat, és mutogathatja őket a csajoknak.

Mivel minden eszköz amit a dolgozat elkészítéséhez felhasználtam nyílt és szabad szoftver, ezért az avsort is egy nyílt alkalmazás, és ezzel együtt a dolgozat teljes szövegét is publikusan elérhető mostantól. (Persze a személyes információkat kigereblyéztem a pdfből)

Akit érdekel a program az a slapec.github.io/avsort címen kipróbálhatja. A projekt forráskódja elérhető githubon. A dolgozat szövegét pedig itt lehet elolvasni.

2015. december 12., szombat

Advent of Code 03-04

Ebben a sorozatban az Advent of Code nevű weboldal kis adventi programozói feladványainak megoldásait írom le. Lássuk a 3. és 4. nap feladatait:

#03 — Day 3: Perfectly Spherical Houses in a Vacuum —

A mese most az, hogy a télapó a végtelen 2D-s térben osztogatja az ajándékait. Azt, hogy épp merre kell haladni a térben a következő ház felé, egy részeg manó diktálja neki a CB-n. Ha az utasítás ^ akkor északra, ha v akkor délre, > esetén keletre, < esetén pedig nyugatra kell repülnie.

Mivel a manó teljesen be van baszva ezért előfordul hogy rossz irányt diktál, így télapó kétszer ugyan abba a kéménybe dobja az ajándékot.

A kérdés: hány házba érkezik legalább egy ajándék?

Például:
- Egy darab > irány esetén 2 otthonba érkezik ajándék: egy a kiindulási, és egy az érkezési helyre.
- ^>v< esetén 4 házba jön ajándék. Négyzet alakban haladt a télapó, és a végén vissza jutott a kiindulási házba, így azt nem számoljuk még egyszer.
- A ^v^v^v^v^v hatására a télapó 2 ház között ugrál folyamatosan.

Nem készültem semmi fancy adatstruktúrával, dehát nem is az a célja ennek a feladatnak.

santa = [0, 0]
positions = set()

route = input()

positions.add(tuple(santa))
for direction in route:
    if direction == '^':
        santa[0] += 1
    elif direction == 'v':
        santa[0] -= 1
    elif direction == '>':
        santa[1] += 1
    elif direction == '<':
        santa[1] -= 1
    positions.add(tuple(santa))
print(len(positions))

Mivel a télapó a kétdimenziós térben mászkál, ezért deklaráltam a santa változót, ami egy két elemű tömb, a 0. indexen az x, 1. pedig az y koordinátát tárolja majd. Az origóból indulunk.
A positions halmaz tárolni fogja a télapó összes egyedi koordinátáját. A halmaz típus gondoskodik róla, hogy kétszer ugyan az az objektum ne kerüljön tárolásra (ettől halmaz, minden érék egyedi benne). A koordináták sorrendje elvész ugyan, de nem lesz rájuk szükség később.

Ahogy megkaptuk a route változóba az útvonalat, úgy egyből hozzá is adjuk a halmazhoz a kiindulási pontot (ezt még az inicializálásnál is meg lehetett volna tenni, nem számít igazából).
Ez után karakterenként végig megyünk az útvonalon, és módosítjuk a santa tömb értékeit annak függvényében hogy az x vagy y koordinátán melyik irányba mozdulunk el. Az egész végén a positons-höz adjuk az aktuális pozíciót. Fontos, hogy a position objektum list, ami unhashable, ezért tuple-é kell alakítani.
Az egész végén egyszerűen kiírjuk a halmaz méretét, ami az összes egyedi pozíció lesz.

2. rész

A feladat folytatásában a télapó munkájának gyorsításához munkába állítják a Robo-Santa robotot, így ketten haladnak végig az útvonalon.

A kérdés ugyan az: hány otthonba érkezik legalább egy ajándék?

  • ^v esetén 3 házba, mert a télapó egyet megy északra, és a robotélapó egyet délre
  • ^>v< esetén szintén 3 helyre, és a végén a télapó és a robotélapó is visszaérnek a kiindulási pontba
  • ^v^v^v^v^v esetén 11 házba érnek oda, mert a télapó folyamatosan északra, míg a robotélapó folyamatosan délre halad.
# coding: utf-8

santa = [0, 0]
robo_santa = [0, 0]

positions = set()

route = input()

positions.add(tuple(santa))
positions.add(tuple(robo_santa))

for i, direction in enumerate(route):
    if i % 2 == 0:
        position = santa
    else:
        position = robo_santa

    if direction == '^':
        position[0] += 1
    elif direction == 'v':
        position[0] -= 1
    elif direction == '>':
        position[1] += 1
    elif direction == '<':
        position[1] -= 1
    positions.add(tuple(position))
print(len(positions))

Sokat nem változott a feladat, egyszerűen a robotélapó is kapott egy tömböt a pozíciójához robo_santa névvel. A beolvasás után mindkét pozíciót hozzá adjuk a positions halmazhoz. Igazából, mivel azonos helyről indulnak mind ketten, ezért felesleges a robo_santa-t hozzá adni a positions-höz, de aki ezt nem ismeri fel, abban felmerülhetne a kérdés hogy:

Oszt’ a robo_santa-t miért lehetett kihagyni?

Visszakanyarodva tehát, a ciklus kap egy számlálót, és ez után egyszerű oszthatósággal vizsgáljuk hogy az épp feldolgozott irány az a télapóé vagy a robotélapóé-e. Itt a position referenciáját ráállítom a megfelelő halmazra, és ez után minden pontosan úgy folyik tovább mint az első feladatban.

#04 — Day 4: The Ideal Stocking Stuffer —

A feladat szerint a télapó egy kis AdventCoint szeretne bányászni, amit kioszthat a kisfiúk és kislányok között. Ehhez olyan MD5 hashekre van szüksége, amik hexadecimálisan pontosan 5 darab 0-ás számjeggyel kezdődnek. A bányászathoz a hashelő algoritmus egy egymás után fűzött titkos kulcsot és egy decimális számot kap. A sikeres bányászathoz azt a legkisebb decimális számot kell megtalálni, ami a titkos kulccsal együtt 5 db nullával kezdődő MD5 hasht produkál. Most szépen sikerült leírnom kétszer ugyan azt a gondolatot, de így biztos éri mindenki hogy mi a helyzet.

Pár példa:
- Ha a titkos kulcsod abcdef akkor a válasz 609043, mert ha az abcdef609043 MD5-ölve 000001dbbfa3a5c83a2d506429c7b00e, ami 5 darab nullással kezdődik.
- Ha a kulcsod pqrstuv akkor a válasz 1048970.

Ez bizony egy nem túl bonyolult feladat, de jobb ötlet híján brute force módszerrel kell megtalálni a választ, azaz addig kell próbálgatni a számokat amíg olyan hasht nem kapunk ami teljesíti a fenti követelményt.

# coding: utf-8

import hashlib
from time import time

secret = input('Secret: ')

start = time()
i = 0
while True:
    md5 = hashlib.md5('{0}{1}'.format(secret, i).encode())

    if md5.hexdigest().startswith('00000'):
        break
    i += 1

print('Answer:', i)
print('Found in {0:.2f}s'.format(time() - start))

A secret beolvasása után sajnos lövésünk sincs hogy mégis mennyi számot kell kipróbálni mire jó hasht találunk, ezért egy szép kis végtelen ciklus indul, ami majd talán egyszer megáll majd a jövőben.

A 6. sorban előállítjuk a hasht, amihez egyszerűen egy format stringben egymás mellé kerül a secret és az i. Az md5() bytest típust vár, így az egész stringet encode()-olni kell. Ez után a hexdigest() visszatér az MD5 hashel stringként, amit aztán jól megnézünk hogy '00000'-el kezdődik-e. Az egész végén nem elfelejteni növelni az i változót!

Hogy látszódjon hogy hány percig bambuljuk az üres képernyőt miközben a számítógép bőszen melegszik, a ciklus végén kiírom a keresésre szánt időt (nálam 0.25s alatt végzett).

2. rész

A második rész annyira rövid, hogy be se másolom a forráskódot. A feladat annyi, hogy most találjuk meg azt a hast, ami 6 darab 0-val kezdődik. Ehhez egyszerűen a fenti forráskódban át kell írni a 11. sorban a '00000'-t '000000'-ra.

Kis várakozás után meg is lesz az eredmény, ez nálam 5.59s volt.

Gyorsabban multiprocessinggel

Miközben szegény CPU0 majd meghal a munkában a maradék 3 nem csinál semmit se a gépemben, és közben nekem meg 6 másodpercet kell várakoznom, szóval ideje többszálasítani a programot, meg minden lófaszt belepakolni amivel a legutolsó kis energia fröccs is kipréselhető a jó öreg PC-ből.

# coding: utf-8

import hashlib
from time import time
from multiprocessing import cpu_count, Process, Queue


def miner(secret: bytes, ranges: Queue, requests: Queue):
    requests.put(True)
    while True:
        range_object = ranges.get()

        for i in range_object:
            if hashlib.md5(secret % i).digest()[:3] == b'\x00\x00\x00':
                requests.put(i)
                break
        requests.put(True)


if __name__ == '__main__':
    BATCH_SIZE = 10**6

    secret = input('Secret: ')

    start = time()

    secret_bytes = secret.encode() + b'%i'
    processes = []
    ranges = Queue()
    requests = Queue()

    for _ in range(cpu_count()):
        process = Process(target=miner, args=(secret_bytes, ranges, requests))
        process.start()
        processes.append(process)

    i = 0
    while True:
        request = requests.get()
        if request is True:
            ranges.put(range(i * BATCH_SIZE, (i+1) * BATCH_SIZE))
            i += 1
        else:
            print('Answer:', request)
            break

    print('Found in {0:.2f}s'.format(time() - start))

    for process in processes:
        process.terminate()

Ez gyakorlatilag a jó öreg producer-consumer pattern, ahol a producer a main thread, a consumerek pedig a Process objektumok. A hashelő logika kikerült a miner függvénybe. Ez paraméterül kapja a titkos kulcsot, és két Queue objektumot: a ranges-ben range objektumok lesznek. A sorból mindegyik process kivesz egy darabot, és szépen végig iterálja a maga intervallumát. A requests Queue-ba teszi bele mindegyik process a kérését újabb intervallum generálásához.

A miner függvényben, a 14. sorban, az md5()-nek átadott paraméter is változott: a secret várhatóan bytes típusú lesz, és mivel Python 3.5.0-ban támogatott a bytes interpolation (PEP 461), ezért pofon egyszerűen mindenféle lószarok nélkül össze tudom fűzni a két értéket és még encode-olnom se kell. A hexdigest() is eltávozott, helyette a digest()-el bytest-ként megkapom a hasht. Felesleges hexadecimális értéket tartalmazó unicode stringgé alakítani a hasht, hiszen a bytest típusú értékben pontosan ugyan az szerepel, csak binárisan. Éppen ezért az összehasonlítás is bytest-hoz történik. Ha a feltétel igaz, akkor a requests-ek közé bekerül az érték maga amire igaz volt a feltétel, és kimászunk a ciklusból.

A 9. és 17. sorban szerepelnek a kérések. Ahogy elindul egy process, az azonnal berak a requests-be egy értéket. Ez most nálam egy sima True de akár az is lehetne hogy 'ready' vagy bármi ami serialize-álható. A 17. sorban, mivel befejeződött az intervallum iterálása, újra bekerül egy érték a requests-be. Ennyit csinál a miner.

Odalent, a 27. sorban gyors bytes-é alakítjuk a begépelt secret-et, és a végére csapjuk a format-ot, hogy a miner-nek már csak interpolálnia kelljen. A 32. sorban aztán elindulnak a Process objektumok, pont annyi mint ahány processzormag van.

A 38. sorban kezdődik a móka. Itt is egy végtelen ciklus indul, mert nem tudjuk előre hogy meddig kell majd várni. A main thread ki is vesz a requests-ek közül egyet. A get() az blocking utasítás, tehát itt addig áll a futás amíg nem lesz akármi amivel vissza lehetne térni. Eddigre jó eséllyel minden process fut már és mindegyik berakott valamit a requests-ek közé, de ha mégse, akkor ugye tovább várunk. Ez után egy gyors érték ellenőrzés következik. Ha a request True objektum (itt használhatjuk az is operátort) akkor generálunk egy új range objektumot. Python 3-ban a range már nem list-el tér vissza ugye, és az objektum gond nélkül berakható a queue-ba. A range méretének képlete elég egyértelmű szerintem. A szelet méretét a BATCH_SIZE szabályozza, ami 10**6 (1,000,000). Ezt így hasraütésre írtam.. Ja és ne felejtsd el növelni azt a nyomorult i-t, kérlek (nem úgy mint én ~)

Ugye ha a request objektum nem True akkor minden bizonnyal egy int-et kaptunk, ami az eredmény. Ezt gyorsan kiírjuk, és az egész végén angolosan killeljük az összes processt, majd az oprendszer gondoskodik memóriáról.

Ezzel a módosítással sikerült 2.08s-ra lenyomni a hashelést, ami már tűrhető szerintem. Ez 2.68x gyorsabb mint egy szálon.

2015. december 5., szombat

Advent of Code 01-02

Azt hiszem időszerű újra írni valami kis bejegyzést, elvégre már majdnem vége az évnek!

Redditen találtam az Advent of Code nevű kezdeményezést, ami arról szól, hogy a programozói adventi kalendáriumnak minden ablaka 2 kis kódolni való feladványt rejt. A történt ismertetése után adnak pár kisebb példát hogy milyen inputra milyen outputot kell adni, majd elengedik az ember kezét, és egyedül kell onnantól válaszolni. A részvételhez regisztráció szükséges, de a feladatok szövege a nélkül is elolvasható. Ebben a bejegyzésben a feladat címére kattintva elolvashatjátok a részleteket is. Ahogy a címből látszik, ez post az első 2 ablakról szól, összesen 4 példáról. A teljes sorozatot itt ki lehet listázni.

Na akkor lássuk is őket:

#01 — Day 1: Not Quite Lisp —

A történt szerint a jó öreg télapó mászkál egy végtelen magas és végtelen mély épületben ajándékokat kézbesítve, és az inputján a ) karakterek azt jelenik, hogy egy emeletet lejjebb kell másznia, míg a ( egy emeletet felfelé jelent.

A kérdés az, hogy az input beolvasása végén melyik emeleten áll majd a télapó?

Ezek szerint:
- A (()) és ()() ugyan úgy a 0. emeletet redeményezi
- A ((( és (()(()( a 3. emeletet
- A ))((((( is a 3. emelet
- A (() és ))( egyaránt a -1. emelet
- A ))) és )())()) egyaránt a -3.

Az egyszerű végénél fogtam meg a problémát: külön-külön megszámolom hogy hányszor halad fel vagy le és kivonom őket egymásból:

data = input()
print(data.count('(') - data.count(')'))

2. rész

A második részben az a kérdés, hogy hányadik volt az az utasítás, amikor először érkezett meg a pincébe a télapó?

Példa:
- Ha az input egy ) akkor az 1. utasításnál érkezett a pincébe
- ()()) esetén az 5. utasításnál

Ez egy picit hosszabb már:

data = input()

position = 0
for i, c in enumerate(data, 1):
    if c == '(':
        position += 1
    elif c == ')':
        position -= 1

    if position < 0:
        print(i)
        break
else:
    print('Never entered the basement')

Az aktuális pozíciót a position változó tárolja. A feladat specifikálta hogy ez a 0. Ez után karakterenként iteráljuk az inputot, az enumerate() gondoskodik a szorszámozásról. Fontos: a feladat szerint 1-től indul a számozás, így itt ezt meg is adtam paraméterül.

Ezek után egyszerűen ( esetén csökkentjük a pozíciót, ) esetén növeljük. Amint a position kisebb mint 0, kiírjuk a karakter sorszámát és brake-el elhagyjuk a terepet.
Ha sose lépünk be a ciklusba, vagy sose érünk le a pincébe, akkor a rend kedvéért kiírjuk hogy Never entered the basement.

#02 — Day 2: I Was Told There Would Be No Math —

Ebben a feladatban azt kellett kiszámolni, hogy a tégla alakú csomagokhoz mennyi csomagoló papírra van szükség. A felületet a 2*l*w + 2*w*h + 2*h*l képlettel lehet kiszámolni. Extra csavar, hogy van egy kis ráhagyás is a csomagolásnál: a legkisebb oldal felülete.

A kérdés: mennyi csomagolóanyag kell összesen?

A példák szerint:
- A 2x3x4-es dobozhoz 2*2*3 + 2*3*4 + 2*4*2 = 52 négyzetláb* mennyiségű csomagolás és 2*3=6 négyzetláb ráhagyás kell, összesen tehát 52 + 6 = 58 négyzetláb csomagolóanyag.
- A 1x1x10-es dobozhoz 2*1*1 + 2*1*10 + 2*10*1 = 42 négyzetláb csomagolóanyag és 1*1 = 1 ráhagyás, összesen 42 + 1 = 43 négyzetláb tehát.
*A mértékegységnek nincs jelentősége ebben a példában

total = 0

while True:
    dimension = input()
    if dimension == '':
        print(int(total))
        break
    else:
        l, w, h  = [int(_) for _ in dimension.split('x')]

        areas = [(2 * l * w), (2 * w * h), (2 * h * l)]
        total += sum(areas) + (min(areas)/2)

A jó öreg Pythonos hátultesztelő patternnel indul a kód: addig olvasunk be méreteket amíg üres sort nem kapunk eredményül (tehát az utolsó adat után egy sima ENTER-t kell nyomni). Ha megvolt az üres sor akkor kiíródik a számláló (amit formai okokból int-é alakítok) és távozunk a ciklusból.

Ha viszont nem üres sort kaptunk, akkor a 'x' karakterek mentén szétvágjuk a beolvasott sort, minden értékét int-é castoljuk és szépen kicsomagoljuk őket 3 változóba: l, w és h.

Ezt követően kiszámoljuk a test 3 oldalának felületeit, ami bekerül az areas tömbbe. A legvégén pedig a számlálóhoz hozzáadjuk az oldalak felületeinek összegét, és a min(areas)-al a legkisebb felületet is. Itt kell még egy plusz osztás, mert korábban fel lett szorozva minden érték!

2. rész

A második részben azt kell kiszámolni hogy egy csomaghoz mennyi szalagra van szükség. Ebbe bele kell számolni a masnihoz szükséges mennyiséget is. A szalag hossza a doboz legkisebb kerületével egyenlő. A masnihoz szükséges plusz mennyiség pedig annyi mint az ajándék térfogata (mértékegység nélkül)

A kérdés az, hogy mennyi szalag kell az összes ajándékhoz?

A példák szerint:
- A 2x3x4-es doboznál egyszer 2+2+3+3 = 10 lábnyi sima szalag és 2*3*4 = 24 láb masnis szalag kell, összesen tehát 10 + 24 = 34 láb.
- A 1x1x10-es doboznál 1+1+1+1 = 4 lábnyi szalag és 1*1*10 = 10 masni szalag kell, összesen 4 + 10 = 14 láb.

total = 0

while True:
    dimension = input()
    if dimension == '':
        print(int(total))
        break
    else:
        l, w, h  = sorted([int(_) for _ in dimension.split('x')])

        total += (l + l + w + w) + (l * w * h)

Ez a kód szinte tök ugyan az mint az előző. A különbség, hogy a szétvágott adat értékeit növekvő sorrendbe rendezem még mielőtt változókba rakosgatnám őket. Így az l és w változó összeadásával megkapom a legkisebb kerületet. A térfogatnak meg mindegy hogy milyen sorrendben jönnek a számok, a szorzás amúgy is kommutatív.

Jóéjt

Ez a kis rövid jutott így ma estére. Igyekszem nem jövő márciusban folytatni a sorozatot.

-slp

2015. március 27., péntek

Google keresés kép alapján Python alól

Elég régóta létező funkció a Google képkeresőjében a Keresés kép alapján, tehát amikor belinkelsz vagy feltöltesz egy képet a Google-nek és az visszahányja hogy milyen weboldalakon található meg az a kép. A kereső sor jobb szélén, a kis fényképező ikonra kattintva lehet előhozni.

Még a múlt hétvégén alakult úgy hogy sok képet akartam visszaellenőrizni. Persze semmi se garantálja hogy attól hogy ha egy kép keresésére nincs eredmény akkor az a kép tényleg egyedi, de azért ahogy az embereket ismerem, nem az internet legsötétebb oldalairól vesznek elő képeket, ha identitást kell hazudni.

Egy rövidebb keresés után kiderült, hogy nincs publikus HTTP API amin keresztül egyszerűen lehetne kereséseket intézni, de semmi probléma, ott a HTML az lesz most az API.

Egy egyszerű kis generátor függvényt raktam össze a feladat elvégzésére, ami egy fájlt és betöltendő találati oldalak maximális számát várja, és visszatér a találatok feliratával és az URL-jével.

Függőségek

TL;DR pip install requests requests_toolbelt lxml cssselect

Sok scrapert írtam már, úgyhogy van egy jól bejáratott hálózati stackem ami úgy pumpálja ki a HTTP kéréseket, ahogy én akarom, de fájl feltöltést nem próbáltam még vele, illetve a képkereső form multipart/form-data formátumban várja az adatokat, tehát kellett volna valami serializálót írnom, amihez épp nem volt kedvem. Megnéztem hogy a nagyon népszerű requests library képes-e out-of-box a fenti formában POST-olni a kérésemet, de sajnos úgy láttam hogy nem, viszont request_toolbelt libraryben van olyan encoder ami képes erre. Ezek türkében úgy döntöttem, hogy akkor most nem szarakodok a saját stackemmel.

A hálózati részen kívül már csak egy HTML parserre van szükség. Én mindig az lxml-t használom. Régebben próbálkoztam a Beautiful Souppal, és azon kívül hogy vagy 7x tovább tart leírni a nevét mint azt hogy lxml, még lassú is volt, meg a CSS selectorokat se ismerte. Évekkel ezelőtt volt ez, azóta rá se néztem, lehet azóta már jobb a helyzet. Az külön felbasz hogy a /r/Python-ban állandóan a Beautiful Soup-os kódokat mutogatnak. Ok, aláírom hogy az lxml-t fordítani kell, dehát annyira nem kurva nehéz ám az. Az lxml-hez kell még a cssselect csomag, és akkor végre boldogan állhatunk neki a programozásnak.

Generátorok

Azért döntöttem úgy hogy generátor függvényt írok, mert több találati oldalt akarok majd végig iterálni. Nem szeretném viszont hogy 100 oldal végignézését végig kelljen várni. Helyette inkább szépen iterálgatom a generátort, és ha mondjuk baromi régóta csinálom már ezt, és semmi extra találat nincs, akkor abbahagyom az egészet.

Két ilyen generátor függvényt írtam. Kezdjük az egyszerűbbel. Ez az amelyik visszaadja a találatokat az oldalról:

def extract(soup):
    for elem in soup.cssselect('.rc h3 a'):
        yield {'text': elem.text_content(), 'url': elem.get('href')}

A függvény már egy lxml fát vár. Note: azért soup megmaradt a Beautiful Soup-ból.
A 2. sorban a .rc h3 a selectort kézzel raktam össze. Ennek a történetét most nem részletezem, külön bejegyzést lehetne írni arról, hogy hogy kell selectorokat írni.
A ciklus törzsében egyszerűen visszatérünk egy dict-el, benne a link szövegével és az URL-jével.

Most veszem csak észre, hogy igazából a visszatérés nem a legjobb kifejezés ebben az esetben, hisz nem return utasítás áll a függvény végén, hanem yield. Meg amúgy nem is igazán van értelme ezt a függvényt generátornak megtenni, elég lenne egy sima list-el visszatérni, viszont ki akartam próbálni egy új nyelvei elemet, amit a Python 3.3 vezetett be, és ez pont egy jó szituáció volt a próbára.

Ezt a függvényt most hagyjuk így, és lássuk azt, amelyik a tényleges feltöltést végzi:

import requests
from lxml.html import fromstring
from requests_toolbelt.multipart.encoder import MultipartEncoder

def reverse(fp, walk_limit=5):
    walked = 0
    user_agent = 'Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/41.0.2272.89 Safari/537.36'
    m = MultipartEncoder({'encoded_image': (fp.name, fp, 'image/jpeg'), 'image_url': None, 'image_content': None, 'filename': None, 'btnG': None})

    r = requests.post('http://www.google.hu/searchbyimage/upload', data=m, headers={'Content-Type': m.content_type, 'User-Agent': user_agent})
    soup = fromstring(r.text, base_url='http://www.google.hu')
    soup.make_links_absolute()
    yield from extract(soup)

    next = soup.cssselect('#pnnext')
    while walked < walk_limit and next:
        walked += 1

        url = next[0].get('href')
        r = requests.get(url, headers={'User-Agent': user_agent})
        soup = fromstring(r.text, base_url='http://www.google.hu')
        soup.make_links_absolute()

        next = soup.cssselect('#pnnext')
        yield from extract(soup)

A reverse() két paramért vár: egy fájl-szerű objektumot, és a bejárt találati oldalak limitjét.
Az első izgalmas rész a 4. sorban van. Itt jön létre az encoder, ami kap egy szép dict-et. Az itt megjelenő kulcs-érték párokat úgy kaptam, hogy figyeltem Chrome Development Tools Network fülén hogy mi megy ki a POST-ban.

A legizgalmasabb rész a 9. sorban van, a yield from extract(soup). Itt szépen delegáljuk az extract() generátort.

Delegáció nélkül ez így nézne ki:

for hit in extract(soup):
   yield hit

Vagy ha az extract() list-el térne vissza, és akkor yield extract(soup), de az olyan unalmas.

A 11. sorban megint egy kis selector van. Az oldal alján a ‘Következő’ feliratú link id-je a #pnnext, ezt is választja ki a metódus. Szerencsére a cssselect() üres tömbbel tér vissza ha nincs a selectornak megfelelő elem a levesben. Ezt a 12. sorban ki is használom, mivel a [] logikai értéke False. Nem úgy mint Javascriptben ahol az Isten se tudja hogy mi.
Ebben a 12. sorban még azt ellenőrzöm hogy kevesebb oldalt töltöttem-e be mint mint a walk_limit.
A 13. sorban gyors növelem is a betöltött oldalak számát, még mielőtt elfelejteném, és végignézném mind a 7,800,000,000 találatot. JA VÁRJ az amúgy se következik be olyan könnyen, mert laponként iterálgatunk. Köszi generátorok.

A 15. sortól gyakorlatilag minden úgy megy, mint a függvény elején az első oldal lekérésénél. Ez egy szép iteratív bejárás, ennyi bőven elég is ide.
A 20. sorban gyorsan, még mielőtt a 21. sorban delegálnánk a linkeket megjegyezzük a következő oldalra mutató elemet, ha van ilyen. De mellékesen, mivel a függvény ugye nem tér vissza, ez a két sor akár meg is cserélhetné egymást. úgy is működne.

Az egész kóceráj végén a ciklus szépen megy tovább addig, amíg a feltétel igaz ~

Próba

A Python.org oldaláról letöltöttem a logót onnan az oldal tetejéről (remélem nem haragudnak meg érte). Nézzük hogy megtaláljuk-e a képet.

from google_reverse import reverse
results = reverse(open('/tmp/python-logo.png', 'rb'))
next(results)
#>>> {'url': 'http://hu.wikipedia.org/wiki/Python_%28programoz%C3%A1si_nyelv%29', 'text': 'Python (programozási nyelv) – Wikipédia'}

Ez bizony megtalálta.

Az összes (5 oldalnyi) találat behúzásához csak iteráljuk végig:

from google_reverse import reverse
results = reverse(open('/tmp/python-logo.png', 'rb'))
for result in results:
    print(result)
#>>> {'url': 'http://hu.wikipedia.org/wiki/Python_%28programoz%C3%A1si_nyelv%29', 'text': 'Python (programozási nyelv) – Wikipédia'}
#>>>{'url': 'http://hu.metapedia.org/wiki/F%C3%A1jl:Python_logo.svg', 'text': 'Fájl:Python logo.svg - Metapedia'}
#>>> ...

És így tovább.

Figyelem: mivel képről (bináris adatról) van szó, ezért bináris olvasásra nyissuk meg a fájlt!

Ennyi mára

Huh, ez a bejegyzés még épp belefért ebbe a hónapba. Persze a havi 1 post még mindig szegényes, de még mindig jobb mint az évi 1.

A teljes kód megtekinthető ezen a Gist-en.

-slp

2015. február 8., vasárnap

Javascript függvény paraméterének kiolvasása PyV8-al

(Ez a bejegyzés egy kicsit módosítva lett 2015. február 9-én)

Rendbe, most hogy ilyen szépen elkészítettük a saját PyV8 példányunkat, ideje lenne kipróbálni valami kóddal, hogy működik-e rendesen.

A saját projektjeim közül hoztam a mostani témát: egy weboldalon egy Javascript Object értékét szeretném megkapni és átalakítani dict-é. A mostani történetben a csavar az, hogy ez az objektum egy függvény paramétere, ami ráadásul a jQuery ready() metódusába van belenyomogatva. Tehát nem holmi pi=3.14 változót kellene kipiszkálni.

(A projektről homályosan: Van egy weboldal, amin egy Google Maps-es térkép látható. Erre a térképre valamilyen saját library-vel markereket tesznek. Én egy adott, sokszög alapú területen levő markereket akarom kigyűjteni. A probléma megoldásának első részével foglalkozik a mai bejegyzés: a weboldal térképén látható összes koordináta összegyűjtésével. Egy későbbi részben majd kitaláljuk, hogy hogyan lehet kiválogatni azokat, amik egy területen belül vannak.)

Lássuk a kódot

Ebben a kis részletben csak a lényeg látszódik. Azzal hogy hogy halásztam ki a DOM-ból most nem foglalkozok (amúgy lxml-el):

$(document).ready(function(){
    new AwesomeLibrary.PutMarkers('#map', {
        data: [{id: '1', lat: '47.160971', lng: '16.4878386'}]
    });
});

Maga a forráskód nagyon egyértelmű, a PutMarkers() második paraméterének az értékére van szükség ({data:[{id: 1, lat: '47.160971', lng: '16.4878386'}]})

Megoldás

A jó multkor egyszerűbbnek találtam, ha először egy fake Javascript kódot eval()-olok a contextben, amivel módosítottam a később ténylegesen meghívott metódusok működését. Ahhoz hogy ez most is működjön kézzel deklarálnom kell a $, document (mivel itt nincs DOM), ready(), AwesomeLibrary, PutMarkers értékeit, hogy ne kapjak sehol se undefined is not a function errort. Így szépen végig fut az egész kóceráj, de a sajnos a PutMarkers visszatérési értékét az eredeti függvény nem teszi ki globális változónak, és maga az anonim függvény se tér vissza semmivel se (főleg nem a koordinátákkal). Jobb ötlet híján a saját PutMarkers implementációmban kiraktam globális változóba a kapott paramétereket, de aztán inkább úgy döntöttem, hogy kipróbálok valami mást, és minden hiányzó függvényt egy Python osztályból rakosgatok a contextbe.

class Globals(PyV8.JSClass):
    def __init__(self):
        super(Globals, self).__init__()
        self.coords = []

    def PutMarkers(self, selector, coords):
        coords = PyV8.convert(coords)

        for coord in coords['data']:
            self.coords.append({
                'lat': float(coord['lat']),
                'lng': float(coord['lng']),
                'id': int(coord['id'])
            })

    def ready(self, function):
        function()

    def __call__(self, *args, **kwargs):
        return self

    def __getattr__(self, *args):
        return self

Az osztály legfontosabb metódusa a __getattr__(). Ez minden olyan esetben meghívódik, ha a Python nem találja az objektum egy property-jét. Mivel ez a metódus a globális névtérbe került, ezért minden olyan esetbe, amikor a V8 a globális névtérből keres egy változót, ez a Python metódus fog lefutni. Ide kerül minden olyan logika ami azokat az eseteket kezeli le, amikor valami deklarálatlan értéket keres a V8, de egyáltalán nem fontos, hogy mi annak az értéke. Másik fontos metódus a __call__(). Ennek segítségével a Globals példányunk függvényekhez hasonlóan tud viselkedni (meg lehet hívni).

A két magic method kombinációjával meg lehet oldani, hogy a számunkra nem érdekes változókat és metódusokat ne kelljen kézzel deklarálgatni. Amikor a V8 egy property-t keres, akkor szépen megkapja a objektumunkat a __getattr__()-ből. Ha abban a property-ben még egy propertyt keres, akkor megint csak megkapja az objektumot, de ha a proprty értékét callable-nek tekinti az is működni fog, mivel az objektum függvényként is tud viselkedni.

Magyarul tehát a Javascript kódban bármikor is egy deklarálatlan változót talál a V8, akkor azt mindig a Globals objektum attribútumai között keresi, és bármikor is talál egy deklarálatlan függvényt, meg fogja tudni hívni, mert a Globals példánya callable. Gyakorlatilag ez egy lánc (method chaining), így mindig minden keresett érték deklarált lesz. (Nem kerülünk rekurzióba, mivel a property-k kibontogatása véges).

Ha ez megvan, akkor jöhetnek az “érdekes metódusok”, szóval azok, amik ténylegesen végeznek valami munkát. A Javascript forráskódban ezek a ready() és PutMarkers().

A $ mindegy hogy mit csinál, csak függvény legyen, és valami olyan objektummal térjen vissza, amiben létezik a ready() metódus. A __getattr__() visszatér egy objektummal, ami függvényként viselkedik, és függvény által visszakapott objektumban létezik a ready() metódus (lásd kicsit lejjebb).
A document, AwesomeLibrary értékei hasonlóan. Egy csomót spóroltunk!

A ready() metódus a Globals osztályban magkapja az anonim függvény, egy JSFunction Python objektumként. Ezt ugyan úgy meg lehet hívni mint bármelyik sima függvényt, de természetesen a kódot a V8 futtatja, a kontextusban.

A történet vége a PutMarkers() metódus. Ez 2 paramétert vár, egy css selectort, amivel nem csinálunk semmit, és magát az értékes adatot, szóval a koordinátákat. Innen már nagyon egyszerű a dolog, a PyV8.convert() átalakítja dict-é az Javascript Object-et (így kikerül a context-ből az adat), majd egy sima iterációval bepakolgatjuk az összes koordinátát a self.coords tömbbe.

script_content = """
$(document).ready(function(){
    new AwesomeLibrary.PutMarkers('#map', {
        data: [{id: '1', lat: '47.160971', lng: '16.4878386'}]
    });
});"""

context_globals = Globals()
with PyV8.JSContext(context_globals) as ctx:
    ctx.eval(script_content)

print(context_globals.coords)

Példányosítjuk a Globals osztályt, majd nyitunk egy JSContext-et. Paraméternek átadjuk a csinos objektumunkat. A contextben pedig futtatjuk a Javascript kódot (script_content).

A kontextuson kívül a context_globals.coords propertyben már ott is vannak a koordináták

>>> print(context_globals.coords)
[{'lat': 47.160971, 'id': 1, 'lng': 16.4878386}]

Zárás

Azt hiszem jól látszódik, hogy kivállóan együtt tudnak működni a Python-os osztályok és a V8. Lényegesen elegánsabb ez a megoldás, mint kézzel kikapuzni egy másik Javascript fájlban az összes előforduló de haszontalan változót és aztán betölteni azt a context elején.

A teljes kód megtekinthető ezen a Gist-en.

A következő részben kitaláljuk, hogy hogy lehet kiválogatni az egy területen levő koordinátákat.

-slp

2015. január 25., vasárnap

PyV8 még egyszer (Python 3 + pyenv)

Ma rendesen megszopattam magam, ugyanis nem kisebb probléma megoldásának álltam neki mint hogy lefordítom Python 3 alá a PyV8-at (Python 2 alá ez már egyszer sikerül). Az extra csavar a történetben az, hogy az interpreterem pyenv környezetben létezik.

A jövőben mindenképp írok még egy teljes bejegyzést a pyenvről. Egyelőre elég annyit tudni róla, hogy ez egy nagyszerű shell script, amivel pofonegyszerűen lehet menedzselni és váltogatni ugyan azon az operációs rendszeren a különböző verziójú Python interpretereket. Akár minden könyvtárban, minden shellben más verziót lehet futtatni, sőt, a virtualenv-ek kezelését is rá lehet bízni. Innen lehet beszerezni

Térjünk a tárgyra

Ez a mai menet kicsit trükkösebb mint a múltkori, mivel mindent forrásból kell elkészíteni. A PyV8 wikin kívül hatalmas segítség volt a ez a bejegyzés, ez is, meg ez is. Ezúton is köszönet értük.

Előkészületek

Steril gépen szükség lehet ezekre a csomagokra:

$ sudo apt-get install build-essential subversion

Ha ez megvan akkor rakjuk fel a Python 3-as verzióját (3.4.2 volt a legutolsó amikor ezt a bejegyzést írtam). Ha kész a fordítás akkor készítsünk egy virtualenvet.

$ pyenv install 3.4.2
$ pyenv virtualenv 3.4.2 v8
$ pyenv shell v8

Hozzunk létre egy könyvtárat amibe a forrásokat pakolásszuk majd:

$ cd ~
$ mkdir v8
$ cd v8

Jöhetnek a források

$ svn checkout http://v8.googlecode.com/svn/trunk/ v8
$ svn checkout http://pyv8.googlecode.com/svn/trunk/ pyv8

Állítsuk be a V8_HOME környezeti változót, hogy a setup.py megtalálja majd a V8 forrását:

$ export V8_HOME=/home/slapec/v8/v8

A Boostra is szükség lesz, a nélkül nem fordul a PyV8. Jelenleg az 1.57.0-ás verzió a legújabb.

$ wget http://sourceforge.net/projects/boost/files/boost/1.57.0/boost_1_57_0.tar.gz
$ tar -xvzf boost_1_57_0.tar.gz

A boost_1_57_0.tar.gz-t törölhetjük is akár.

Boost fordítás

A Boosttal kezdünk. A 3.4.2-es verzió ellen kell lefordítani. Mivel a pyenv is minden alkalommal forrásból fordítja a feltelepített Python verziót, ezért a header fájlokat megtaláljuk majd a .pyenv könyvtárban.

$ cd boost_1_57_0
$ ./bootstrap.sh --with-python-version=3.4 
                 --with-python-root=/home/slapec/.pyenv/versions/3.4.2/ 
                 --with-python=/home/slapec/.pyenv/versions/3.4.2/bin/python

Az argumentumokat nem kell új sorba írni, csak az olvashatóság miatt írtam így őket. Fontos: a scriptnek abszolút elérési útvonalakat kell adni.

Ha kész a bootstrap akkor pedig:

$ ./b2 include="/home/slapec/.pyenv/versions/3.4.2/include/python3.4m"

És lehet menni ebédelni amíg ezen gondolkozik a számítógép.

A The Boost C++ Libraries were successfully built! üzenet után installáljuk a libraryt, frissítsük a cache-t és állítsuk be a BOOST_HOME környezeti változót hogy a boost könyvtárára mutasson:

$ sudo ./b2 install
$ sudo ldconfig
$ export BOOST_HOME=/home/slapec/v8/boost_1_57_0

V8 fordítás

A V8 fordítása kicsit trükkösebb. Egy patchet kéne alkalmazni a PyV8 setup.py fájljának, ami bekapcsolja a V8 RTTI és Exception támogatását. Ez a setup.py viszont nem Python 3 kompatibilis. Ez még a kisebb probléma.

A nagyobb probléma, hogy a V8 fordításához is szükség van a Pythonra, de ott is csak a 2-es verzió a megfelelő. Lassan 7 éve hogy megjelent az első Python 3 verzió, és még mindig ilyen gyakoriak a problémák.

Jobb ötlet híján úgy döntöttem, hogy a PyV8 setup scriptjét módosítom egy kicsit, hogy elvégezze a patchelést, de a V8 fordítását már nem, de kiírja a parancsot amivel a V8-at fordíthatom, amit aztán kézzel, Python 2 környezetben futtatok is.

Tehát a pyv8/setup.py fájlban két dolgot kell szerkeszteni:

Az 523. sorban ebből:

os.makedirs(build_path, 0755)

Ez lesz:

os.makedirs(build_path, 0o755)

Ugyanis Python 3-ban az octal literal is megváltozott.

Az 513. sorban ebből az egy sorból

exec_cmd(cmdline, "build v8 from SVN")

Ez a három lesz:

#exec_cmd(cmdline, "build v8 from SVN")
print('Now switch to a Python 2 environment and build V8 with the following command')
exit(cmdline)

(Természetesen az első print() elhagyható.)

Ezek után jöhet is a build.

$ python setup.py build

A script a végén kiírja a parancsot amivel a V8-at lefordíthatjuk és kilép.

Ha ez megvan, akkor váltsunk át egy Python 2-es környezetre (pyenv shell system ha az alapértelmezett interpreter ilyen, vagy egyszerűen nyissunk egy új shellt).

$ cd v8
$ make -j 8 disassembler=off vtunejit=off library=shared werror=no strictaliasing=on gdbjit=off debuggersupport=on extrachecks=off visibility=on regexp=native objectprint=off backtrace=on i18nsupport=off liveobjectlist=off snapshot=on verifyheap=off x64.release

(Természetesen mindenki a saját make parancsát használja)

Ameddig ez lefordul, addig megtárgyalhatjuk hogy nem-e gáz hogy a build scriptből félúton kiléptünk.

A buld osztályban a run() metódu a prepare_v8() függvényt hívja meg, itt látszódnak a V8 fordításának lépései. Feljebb a build_v8() függvényt írogattuk át kicsit, ez mellékesen az utolsó előtti lépés. A következő a generate_probes() lenne, ami nálam amúgy is meghal dtrace not found errorral, úgyhogy annak mindegy hogy lefut-e vagy sem (természetesen annyira nem mindegy, de ezzel a hibával egyelőre nem tudtam mit kezdeni).

Mostanra remélhetőleg elkészült a V8. Menjünk vissza a PyV8 könyvtárába, váltsunk vissza Python 3-ra (pyenv shell v8) és jöhet az install:

$ cd pyv8
$ python setup.py install

Ha szerencsénk van akkor Finished processing dependencies for PyV8==1.0-dev üzenet fogad. Már csak ki kell próbálni hogy működik-e a vadiúj librarynk :3

$ cd ~
$ python -m unittest PyV8
...
FAILED (failures=2)

Sajna 2 teszt elhasalt, dehát semmi se tökéletes, nem :) ?

Aftermath

Vannak megoldásra váró problémái a PyV8 projektnek, de én nagyon örülök neki, hogy dolgoznak rajta hogy Javascript kódot lehessen futtatni Python alól. Az a példányom, amit még a régi projektemhez fordítottam a mai napig jól működik, csak én már szeretnék Python 3-ra váltani, ezért voltam kénytelen újra elővenni ezt a problémát.

Mindenkinek kellemes fordítgatást : )

-slp

2015. január 1., csütörtök

Ég a pofám

Te jó Isten. Azért most rendesen ég a pofám: több mint 1 éve nem írtam egyetlen bejegyzést se. Az utóbbi napokban pedig pont azon agyaltam, hogy hogyan tudnék a jövőben több időt tölteni a kódok írásával, és kevesebbet a bejegyzés formázásával.
Mert úgy érzem, hogy nem azért nem írok semmit hónapokig évekig, mert semmit se csinálok a számítógép előtt, csak a macskás videókat bámulom, hanem mert borzalmasan körülményes igényesre megformázni a szöveget. Szerencsére most, hogy egyre többet használom a Markdown és reStructedText leírónyelveket, lehet -nagyon remélem- hogy a jövőben tényleg úgy írhatok majd bejegyzéseket, hogy nem kell állandóan elengednem a billentyűzetet, és akkor több kedvem lesz kis bejegyzéseket írni.

Addig is, BUÉK mindenkinek!