[upstream-challenge] [Anul 4] Apache Mahout 1202

[Dan Filimon]

Commit-urile [1, 2, 3] rezolvă issue-ul [4]. Patch-ul este împărțit în 3
fiindcă sunt modificări mai ample.
Design document-ul este aici [5], spreadsheet-ul cu (numeroase versiuni de)
benchmarkuri este aici [6] și aici [7] a fost o versiune mai veche a
codului; îmbunătățirea finală este la [8].

Scopul, pe scurt este accelerarea operațiilor cu vectori în Mahout.
Există 3 tipuri de vectori: DenseVectors (reprezentați ca array-uri de
double-uri) și 2 tipuri de vectori rari (sunt ținute doar elementele
nenule), RandomAccessSparseVectors (reprezentați ca hashtable-uri de la
indici la valori) și SequentialAccessSparseVector (reprezentați ca 2
array-uri sortate, unul de indici, și unul de valori double).

Înainte, majoritatea operațiilor în clasa de bază, AbstractVector se făceau
accesând fiecare elemnt din vector după indice, cu un for de la 0 la size -
1.
În special pentru SequentialAccessSparseVector, asta e o operație extrem de
costisitoare, O(log n) pentru căutare binară pentru un get() și înca atât
pentru un set().

Rezultatul este că operații care trebuiau să aibă complexitate teoretică
O(n), aveau complexitate O(n log n) cu constante destul de mari.

Am discutat și identificat cazuri particulare de operații de optimizat:
assign() (un map pe fiecare pereche de elemente din 2 vectori urmat de o
atribuire a rezultatului la cel din stânga) și aggregate() (un map pe
fiecare pereche de elemente din 2 vectori urmat de un fold cu rezultatul cu
o altă funcție de agregare).

Cazurile speciale sunt descrise extrem de detaliat în design doc [5], dar
se bazează pe ideea că dacă funcțiile folosite se comportă similar cu + sau
* față de 0, sunt asociative sau comutative, se poate itera doar printr-un
vector, sau doar prin elementele nenule.

Commit-urile fac:
1. adaugă suport pentru metodele care verifică proprietățile pe care
trebuie să le îndeplinească funcțiile aplicate (asociativitate, f(x, 0) = x
etc.) cu teste

2. extind structura dintr-un SequentialAccessSparseVector,
OrderedIntDoubleMapping să suporte interclasarea cu un alt OIDM pentru
inserarea a n elemente în O(n) (altfel, pentru inserarea unui element,
trebuie căutat binar poziția pe care trebuie pus, mutat restul elementelor
din dreapta mai la dreapta cu o poziție și atribuit => O(n + log n) per
element!)

3. adaugă un framework cu 2 clase abstracte care descriu operațiile binare
VectorBinaryAssign și VectorBinaryAggregate; ele sunt moștenite de diverși
algoritmi care implementează cazurile descrise în design doc și este ales
cel mai bun (după o estimare a costului) algoritm posibil

Pot veni cu mai multe detalii, dar simt c-am scris prea multe despre asta
în ultima perioadă și e oricum [5]. :)

[1]
https://github.com/apache/mahout/commit/5f859ab6646c2d3f0eb34b6bbd7b9e37064cda76
[2]
https://github.com/apache/mahout/commit/bf82164c28244ca857ff7a9bc2ed93ad2e45c537
[3]
https://github.com/apache/mahout/commit/221b59509527fae2edb02f5857d947a1aad15bd8
[4] https://issues.apache.org/jira/browse/MAHOUT-1202
[5]
https://docs.google.com/document/d/1g1PjUuvjyh2LBdq2_rKLIcUiDbeOORA1sCJiSsz-JVU/edit#heading=h.koi571fvwha3
[6]
https://docs.google.com/spreadsheet/ccc?key=0AochdzPoBmWodG9RTms1UG40YlNQd3ByUFpQY0FLWmc&pli=1#gid=10
[7] https://reviews.apache.org/r/10669/
[8]
https://docs.google.com/spreadsheet/ccc?key=0AhewTD_ZgznddGFQbWJCQTZXSnFULUYzdURfWDRJQlE#gid=3
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rosedu.org/pipermail/upstream-challenge/attachments/20130507/0a7e2718/attachment-0001.html>