Sprintul din ianuarie 2010¶

• Compilarea Temeliei în ținte
  • shared object (.so) [OK]
  • dynamic-link library (.dll) [FAIL]
• Implementarea unei noi structuri de date: matrice rară (sparse matrix)
• Diverse implementări de graf
  1. Cu listă de adiacență
  2. Cu matrice rară

Descriere¶

• Legături de studiat
  1. Compilare încrucișată (cross-compiling) pe Linux
  2. Compilare Win32 pe Linux

Evoluție¶

• [19-01-2010] Matrice rară implementată
  • De ce țin 2 păduri de arbori în oglindă ?
    • Pentru că poți decide unde să cauți o cheie: deasupra diagonalei principale sau sub ea
      

       1 /*!
       2  * @brief Returns key at position in a sparse_matrix.
       3  * Complexity O(min(rows, columns))
       4  *
       5  * @param Sparse matrix
       6  * @param Row
       7  * @param Column
       8  * @param Additional info about the distribution of matrix elements; -1
       9  * for row dense matrix, 1 for column dense matrix and 0 if you don't
      10  * have any opinion about your matrix
      11  */
      12 void *sparse_matrix_get_key_at(sparse_matrix_t sparse_matrix, int row,
      13         int column, int preference);
      

    • Pentru că numărul de chei este foarte mic și oglindirea ar trebui să fie mică
      

       1 struct _sparse_matrix_t
       2 {
       3     /*! tree of rows with not null keys */
       4     red_black_tree_t *rows;
       5 
       6     /*! tree of columns with not null keys */
       7     red_black_tree_t *columns;
       8 
       9     /*! number of rows */
      10     int n_rows;
      11 
      12     /*! number of columns */
      13     int n_columns;
      14 
      15     /*! maximum not null keys */
      16     int size;
      17 
      18     /*! number of not null keys */
      19     int not_null;
      20 };
      21 
      22 struct _sparse_matrix_key_t
      23 {
      24     int index;
      25     void *key;
      26 };
      

  • Pentru fiecare linie și coloană țin un arbore roșu negru în care inserez informații lipsă: cheie și index
    • Un index îl știu deja pentru arborele este deja referit.
  • De ce pădure de arbori și nu o variantă mai simplă, standard, bazată pe liste sau vectori ?
    • Pentru că Temelia este o bibliotecă cu utilizare generică, nu are o anumită țintă și operațiile pe arborii Roșu-Negru sunt echilibrat implementate
    • Din testele de performanță reiese că arborii Roșu-Negru obțin cei mai buni timpi pentru operațiile de uz general: inserție, căutare, ștergere
• [20-01-2010] Îmbunătățire matrici rare
  • 3 variante de matrici rare
    

    samples(SPARSE_MATRIX_ROW_DENSE);
    samples(SPARSE_MATRIX_COLUMN_DENSE);
    samples(SPARSE_MATRIX_ROW_DENSE | SPARSE_MATRIX_COLUMN_DENSE);
    

  • Fiecare varianta alocă o listă de arbori Roșu-Negru, în care ține vecinii
  • Varianta ROW_DENSE folosește o pădure de arbori doar pentru reținerea liniilor, pădurea de arbori pentru coloane este nulă
  • Varianta COLUMN_DENSE este asemănătoare cu ROW_DENSE, diferența fiind entitatea asupra căreia lucrează: coloană sau linie
  • ROW_DENSE | COLUMN_DENSE activează cele două păduri de arbori
    

    ROW_DENSE: total heap usage: 110 allocs, 110 frees, 1,648 bytes allocated
    COLUMN_DENSE: total heap usage: 124 allocs, 124 frees, 2,336 bytes allocated
    ROW_DENSE | COLUMN_DENSE: total heap usage: 225 allocs, 225 frees, 3,664 bytes allocated
    

  • Diferența între ROW_DENSE și COLUMN_DENSE este dată de numărul de arbori alocați; matricile de test nu sunt toate pătratice