<div dir="ltr">Commit-urile [1, 2, 3] rezolvă issue-ul [4]. Patch-ul este împărțit în 3 fiindcă sunt modificări mai ample.<div>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].<br>

</div><div><br></div><div>Scopul, pe scurt este accelerarea operațiilor cu vectori în Mahout.</div><div style>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).</div>

<div style><br></div><div style>Î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.</div><div style>Î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().</div>

<div style><br></div><div style>Rezultatul este că operații care trebuiau să aibă complexitate teoretică O(n), aveau complexitate O(n log n) cu constante destul de mari.</div><div style><br></div><div style>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).</div>

<div style><br></div><div style>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.</div>

<div style><br></div><div style>Commit-urile fac:</div><div style>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</div>

<div style><br></div><div style>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!)</div>

<div style><br></div><div><div style>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</div>

<div style><br></div><div style>Pot veni cu mai multe detalii, dar simt c-am scris prea multe despre asta în ultima perioadă și e oricum [5]. :)</div><div style><br></div><div>[1] <a href="https://github.com/apache/mahout/commit/5f859ab6646c2d3f0eb34b6bbd7b9e37064cda76">https://github.com/apache/mahout/commit/5f859ab6646c2d3f0eb34b6bbd7b9e37064cda76</a></div>

<div>[2] <a href="https://github.com/apache/mahout/commit/bf82164c28244ca857ff7a9bc2ed93ad2e45c537">https://github.com/apache/mahout/commit/bf82164c28244ca857ff7a9bc2ed93ad2e45c537</a></div><div>[3] <a href="https://github.com/apache/mahout/commit/221b59509527fae2edb02f5857d947a1aad15bd8">https://github.com/apache/mahout/commit/221b59509527fae2edb02f5857d947a1aad15bd8</a></div>

<div>[4] <a href="https://issues.apache.org/jira/browse/MAHOUT-1202">https://issues.apache.org/jira/browse/MAHOUT-1202</a></div></div><div>[5] <a href="https://docs.google.com/document/d/1g1PjUuvjyh2LBdq2_rKLIcUiDbeOORA1sCJiSsz-JVU/edit#heading=h.koi571fvwha3">https://docs.google.com/document/d/1g1PjUuvjyh2LBdq2_rKLIcUiDbeOORA1sCJiSsz-JVU/edit#heading=h.koi571fvwha3</a></div>

<div>[6] <a href="https://docs.google.com/spreadsheet/ccc?key=0AochdzPoBmWodG9RTms1UG40YlNQd3ByUFpQY0FLWmc&pli=1#gid=10">https://docs.google.com/spreadsheet/ccc?key=0AochdzPoBmWodG9RTms1UG40YlNQd3ByUFpQY0FLWmc&pli=1#gid=10</a></div>

<div>[7] <a href="https://reviews.apache.org/r/10669/">https://reviews.apache.org/r/10669/</a></div><div>[8] <a href="https://docs.google.com/spreadsheet/ccc?key=0AhewTD_ZgznddGFQbWJCQTZXSnFULUYzdURfWDRJQlE#gid=3">https://docs.google.com/spreadsheet/ccc?key=0AhewTD_ZgznddGFQbWJCQTZXSnFULUYzdURfWDRJQlE#gid=3</a></div>

<div><br></div></div>