Changeset 1527


Ignore:
Timestamp:
Sep 22, 2009 10:53:20 AM (11 years ago)
Author:
bradbell
Message:

trunk: Change get_element to next_element (do not check all element values).

This is in preparation templating the type of vector of sets and having
two options for the sparsity calculations. Both vector of sets will have
the same API and in the case where sets are implemented as std::set,
it will be more efficient to not check every possible element value.

makefile.in: set corresponding makefile.am version (missing in previous commit).

Location:
trunk
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/cppad/local/for_jac_sweep.hpp

    r1526 r1527  
    102102        // vecad_ind maps a VecAD index (the beginning of the
    103103        // VecAD object) to its from index in vecad_sparsity
    104         size_t n_to            = var_sparsity.limit();
     104        size_t limit           = var_sparsity.limit();
    105105        size_t num_vecad_ind   = play->num_rec_vecad_ind();
    106106        size_t num_vecad_vec   = play->num_rec_vecad_vec();
    107107        vector_pack      vecad_sparsity;
    108         vecad_sparsity.resize(num_vecad_vec, n_to);
     108        vecad_sparsity.resize(num_vecad_vec, limit);
    109109        size_t* vecad_ind      = CPPAD_NULL;
    110110        if( num_vecad_vec > 0 )
     
    127127# if CPPAD_FOR_JAC_SWEEP_TRACE
    128128        std::cout << std::endl;
    129         CppAD::vector<bool> z_value(n_to);
     129        CppAD::vector<bool> z_value(limit;
    130130# endif
    131131
     
    485485# if CPPAD_FOR_JAC_SWEEP_TRACE
    486486                // value for this variable
    487                 for(j = 0; j < n_to; j++)
    488                         z_value[j] = var_sparsity.get_element(i_var, j);
     487                for(j = 0; j < limit j++)
     488                        z_value[j] = false;
     489                j = var_sparsity.next_element(i_var);
     490                while( j < limit )
     491                {       z_value[j] = true;
     492                        j = var_sparsity.next_element(i_var);
     493                }
    489494                printOp(
    490495                        std::cout,
  • trunk/cppad/local/for_sparse_jac.hpp

    r1515 r1527  
    191191                // set bits that are true
    192192                for(j = 0; j < q; j++) if( r[ i * q + j ] )
    193                         for_jac_sparsity_.set_element( ind_taddr_[i], j);
     193                        for_jac_sparsity_.add_element( ind_taddr_[i], j);
    194194        }
    195195
     
    208208
    209209                // set bits
    210                 for(j = 0; j < q; j++) s[ i * q + j ] =
    211                         for_jac_sparsity_.get_element( dep_taddr_[i], j);
     210                for(j = 0; j < q; j++)
     211                        s[ i * q + j ] = false;
     212                CPPAD_ASSERT_UNKNOWN( for_jac_sparsity_.limit() == q );
     213                j = for_jac_sparsity_.next_element( dep_taddr_[i] );
     214                while( j < q )
     215                {       s[i * q + j ] = true;
     216                        j = for_jac_sparsity_.next_element( dep_taddr_[i] );
     217                }
    212218        }
    213219
  • trunk/cppad/local/rev_hes_sweep.hpp

    r1526 r1527  
    178178# if CPPAD_REV_HES_SWEEP_TRACE
    179179                for(j = 0; j < limit; j++)
    180                 {       zf_value[j] = for_jac_sparse.get_element(i_var, j);
    181                         zh_value[j] = rev_hes_sparse.get_element(i_var, j);
     180                {       zf_value[j] = false;
     181                        zh_value[j] = false;
    182182                }
    183 
     183                j = for_jac_sparse.next_element(i_var);;
     184                while( j < limit )
     185                {       zf_value[j] = true;
     186                        j = for_jac_sparse.next_element(i_var);
     187                }
     188                j = rev_hes_sparse.next_element(i_var);;
     189                while( j < limit )
     190                {       zh_value[j] = true;
     191                        j = rev_hes_sparse.next_element(i_var);
     192                }
    184193                // should also print RevJac[i_var], but printOp does not
    185194                // yet allow for this.
  • trunk/cppad/local/rev_jac_sweep.hpp

    r1526 r1527  
    145145# if CPPAD_REV_JAC_SWEEP_TRACE
    146146                for(j = 0; j < limit; j++)
    147                         z_value[j] = var_sparsity.get_element(i_var, j);
     147                        z_value[j] = false;
     148                j = var_sparsity.get_element(i_var, j);
     149                while( j < limit )
     150                {       z_value[j] = true;
     151                        j          = var_sparsity.get_element(i_var, j);
     152                }
    148153                printOp(
    149154                        std::cout,
  • trunk/cppad/local/rev_sparse_hes.hpp

    r1525 r1527  
    258258
    259259                // i is index corresponding to forward mode partial
    260                 for(i = 0; i < q; i++) h[ i * n + j ] =
    261                         rev_hes_sparsity.get_element(j + 1, i);
     260                for(i = 0; i < q; i++)
     261                        h[ i * n + j ] = false;
     262
     263                CPPAD_ASSERT_UNKNOWN( rev_hes_sparsity.limit() == q );
     264                i = rev_hes_sparsity.next_element(j + 1);
     265                while( i < q )
     266                {       h[ i * n + j ] = true;
     267                        i = rev_hes_sparsity.next_element(j + 1);
     268                }
    262269        }
    263270
  • trunk/cppad/local/rev_sparse_jac.hpp

    r1525 r1527  
    187187
    188188                for(j = 0; j < p; j++) if( s[ i * m + j ] )
    189                         var_sparsity.set_element( dep_taddr_[i], j );
     189                        var_sparsity.add_element( dep_taddr_[i], j );
    190190        }
    191191
     
    208208                // set bits
    209209                for(i = 0; i < p; i++)
    210                         r[ i * n + j ] = var_sparsity.get_element(j+1, i);
     210                        r[ i * n + j ] = false;
     211
     212                CPPAD_ASSERT_UNKNOWN( var_sparsity.limit() == p );
     213                i = var_sparsity.next_element(j+1);
     214                while( i < p )
     215                {       r[ i * n + j ] = true;
     216                        i              = var_sparsity.next_element(j+1);
     217                }
    211218        }
    212219
  • trunk/cppad/local/vector_set.hpp

    r1524 r1527  
    2727class vector_pack {
    2828private:
    29         /// type used to pack values
     29        /// type used to pack elements
    3030        typedef size_t Pack;
    3131        /// Number of bits per Pack value
     
    3434        /// (set by constructor and resize).
    3535        size_t n_set_;
    36         /// Possible element values in each set are 0, 1, ..., limit_ - 1
     36        /// Possible elements in each set are 0, 1, ..., limit_ - 1
    3737        /// (set by constructor and resize).
    3838        size_t limit_;
     
    4545        /// Pointer to the beginning of data for all the sets.
    4646        Pack*  data_;
     47        /// Previous index for which we were retrieving next_element
     48        /// (use n_set_ if no such previous index exists).
     49        size_t previous_index_;
     50        /// Previous element that we retrieved using next_element
     51        /// (use limit_ for no such element exists; i.e., past end of the set).
     52        size_t previous_element_;
    4753public:
    4854        // -----------------------------------------------------------------
     
    5056        */
    5157        vector_pack(void) :
    52         n_set_(0)                ,
    53         limit_(0)                ,
    54         n_pack_(0)               ,
    55         allocated_(false)        ,
    56         data_(CPPAD_NULL)
     58        n_set_(0)                     ,
     59        limit_(0)                     ,
     60        n_pack_(0)                    ,
     61        allocated_(false)             ,
     62        data_(CPPAD_NULL)             ,
     63        previous_index_(0)            ,
     64        previous_element_ (0)
    5765        { }
    5866        // -----------------------------------------------------------------
     
    8492
    8593        \param limit
    86         is the maximum element value plus one (the minimum element value is 0).
     94        is the maximum element plus one (the minimum element is 0).
    8795        */
    8896        void resize(size_t n_set, size_t limit)
     
    104112                                data_[i] = zero;
    105113                }
     114
     115                // values that signify past end of list
     116                previous_index_   = n_set;
     117                previous_element_ = limit;
    106118        }
    107119        // -----------------------------------------------------------------
     
    111123        is the index for this set in the vector of sets.
    112124
    113         \param value
    114         is the value of this element.
    115 
    116         \par Checked Assertions
    117         \li index  < n_set_
    118         \li value  < limit_
    119         */
    120         void set_element(size_t index, size_t value)
     125        \param element
     126        is the element we are adding to the set.
     127
     128        \par Checked Assertions
     129        \li index    < n_set_
     130        \li element  < limit_
     131        */
     132        void add_element(size_t index, size_t element)
    121133        {       static Pack one(1);
    122                 CPPAD_ASSERT_UNKNOWN( index < n_set_ );
    123                 CPPAD_ASSERT_UNKNOWN( value < limit_ );
    124                 size_t j  = value / n_bit_;
    125                 size_t k  = value - j * n_bit_;
     134                CPPAD_ASSERT_UNKNOWN( index   < n_set_ );
     135                CPPAD_ASSERT_UNKNOWN( element < limit_ );
     136                size_t j  = element / n_bit_;
     137                size_t k  = element - j * n_bit_;
    126138                Pack mask = one << k;
    127139                data_[ index * n_pack_ + j] |= mask;
    128140        }
    129141        // -----------------------------------------------------------------
    130         /*! Does a set have a specific element
     142        /*! Get the next element from a specific set
    131143       
    132144        \param index
    133145        is the index for this set in the vector of sets.
    134 
    135         \param value
    136         is the value of this element.
     146        We start with the first element of the set when one of the following
     147        conditions holds:
     148        \li
     149        If \a index is not equal its value on the previous call
     150        to \c next_element.
     151        \li If \c resize was called after the previous call
     152        to \c next_element
     153       
     154        \return
     155        is the next element in the set with the specified index.
     156        If no such element exists, \c this->limit is returned.
    137157
    138158        \par Checked Assertions
    139159        \li index  < n_set_
    140         \li value  < limit_
    141         */
    142         bool get_element(size_t index, size_t value) const
     160        */
     161        size_t next_element(size_t index)
    143162        {       static Pack one(1);
     163
     164                // initialize element to search for in this set
     165                size_t element;
    144166                CPPAD_ASSERT_UNKNOWN( index < n_set_ );
    145                 CPPAD_ASSERT_UNKNOWN( value < limit_ );
    146                 size_t j  = value / n_bit_;
    147                 size_t k  = value - j * n_bit_;
    148                 Pack mask = one << k;
    149                 mask     &= data_[ index * n_pack_ + j];
    150                 return (mask != 0);
    151         }
    152 
     167                if( previous_index_ != index )
     168                {       previous_index_ = index;
     169                        element         = 0;
     170                }
     171                else if( previous_element_ == limit_ )
     172                        return limit_;
     173                else    element         = previous_element_ + 1;
     174
     175                // initialize packed data index
     176                size_t j  = element / n_bit_;
     177
     178                // initialize bit index
     179                size_t k  = element - j * n_bit_;
     180
     181                // search for next element of the set
     182                Pack check = data_[ index * n_pack_ + j ];
     183                while( element < limit_ )
     184                {       if( check & (one << k) )
     185                        {       previous_element_ = element;
     186                                return element;
     187                        }
     188                        element++;
     189                        k++;
     190                        CPPAD_ASSERT_UNKNOWN( k <= n_bit_ );
     191                        if( k == n_bit_ )
     192                        {       k     = 0;
     193                                j++;
     194                                CPPAD_ASSERT_UNKNOWN( j < n_pack_ );
     195                                check = data_[ index * n_pack_ + j ];
     196                        }
     197                }
     198                previous_element_ = limit_;
     199                return limit_;
     200        }
    153201        // -----------------------------------------------------------------
    154202        /*! Assign the empty set to one of the sets.
  • trunk/makefile.in

    r1524 r1527  
    236236@CppAD_POSTFIX_FALSE@postfix_dir = .
    237237
    238 # $Id: makefile.am 1506 2009-09-13 17:06:17Z bradbell $
     238# $Id: makefile.am 1524 2009-09-22 03:07:03Z bradbell $
    239239# -----------------------------------------------------------------------------
    240240# CppAD: C++ Algorithmic Differentiation: Copyright (C) 2003-09 Bradley M. Bell
Note: See TracChangeset for help on using the changeset viewer.