PLearn 0.1
|
00001 // -*- C++ -*- 00002 00003 // PLearn (A C++ Machine Learning Library) 00004 // Copyright (C) 1998 Pascal Vincent 00005 // Copyright (C) 1999-2002 Pascal Vincent, Yoshua Bengio and University of Montreal 00006 // 00007 00008 // Redistribution and use in source and binary forms, with or without 00009 // modification, are permitted provided that the following conditions are met: 00010 // 00011 // 1. Redistributions of source code must retain the above copyright 00012 // notice, this list of conditions and the following disclaimer. 00013 // 00014 // 2. Redistributions in binary form must reproduce the above copyright 00015 // notice, this list of conditions and the following disclaimer in the 00016 // documentation and/or other materials provided with the distribution. 00017 // 00018 // 3. The name of the authors may not be used to endorse or promote 00019 // products derived from this software without specific prior written 00020 // permission. 00021 // 00022 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR 00023 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00024 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN 00025 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00026 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 00027 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 00028 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 00029 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00030 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00031 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00032 // 00033 // This file is part of the PLearn library. For more information on the PLearn 00034 // library, go to the PLearn Web site at www.plearn.org 00035 00036 00037 00038 00039 /* ******************************************************* 00040 * $Id: TMat_sort.h 9649 2008-11-06 16:07:34Z ducharme $ 00041 * AUTHORS: Pascal Vincent & Yoshua Bengio & Rejean Ducharme 00042 * This file is part of the PLearn library. 00043 ******************************************************* */ 00044 00047 #ifndef TMat_sort_INC 00048 #define TMat_sort_INC 00049 00050 #include <algorithm> 00051 #include "TVec_impl.h" 00052 #include "TMat_impl.h" 00053 00054 namespace PLearn { 00055 using namespace std; 00056 00057 00058 template<class T> class SelectedIndicesCmp 00059 { 00060 private: 00061 TVec<int> indices; 00062 bool use_less_than; 00063 00064 public: 00065 typedef T first_argument_type; 00066 typedef T second_argument_type; 00067 typedef bool result_type; 00068 00069 SelectedIndicesCmp(TVec<int> the_indices, bool use_lexical_less_than=true) 00070 :indices(the_indices), use_less_than(use_lexical_less_than) 00071 {} 00072 00073 bool operator()(const T& x, const T& y) 00074 { 00075 int n = indices.length(); 00076 if(use_less_than) // lexical < 00077 { 00078 for(int k=0; k<n; k++) 00079 { 00080 int i = indices[k]; 00081 if(x[i]<y[i]) 00082 return true; 00083 else if(x[i]>y[i]) 00084 return false; 00085 } 00086 return false; 00087 } 00088 else // lexical > 00089 { 00090 for(int k=0; k<n; k++) 00091 { 00092 int i = indices[k]; 00093 if(x[i]>y[i]) 00094 return true; 00095 else if(x[i]<y[i]) 00096 return false; 00097 } 00098 return false; 00099 } 00100 } 00101 }; 00102 00103 template<class T> 00104 void sortRows(TMat<T>& mat, const TVec<int>& key_columns, bool increasing_order=true) 00105 { 00106 SelectedIndicesCmp< Array<T> > cmp(key_columns,increasing_order); 00107 sort(mat.rows_as_arrays_begin(), mat.rows_as_arrays_end(), cmp); 00108 } 00109 00110 00112 template<class T> 00113 inline void sortElements(const TVec<T>& vec, bool reverse_elems=false) 00114 { 00115 sort(vec.begin(), vec.end()); 00116 if (reverse_elems) 00117 reverse(vec.begin(), vec.end()); 00118 } 00119 00120 00129 template<class T> 00130 void partialSortRows(const TMat<T>& mat, int k, int sortk=1, int col=0) 00131 { 00132 if (k > mat.length()) 00133 PLERROR("In partialSortRows - The number of rows to sort (%d) must " 00134 "be less than the length of the matrix (%d)", 00135 k, mat.length()); 00136 vector< pair<T,int> > order(mat.length()); 00137 typename vector< pair<T,int> >::iterator it = order.begin(); 00138 T* ptr = mat.data()+col; 00139 for(int i=0; i<mat.length(); ++i, ptr+=mat.mod(), ++it) 00140 { 00141 it->first = *ptr; 00142 it->second = i; 00143 } 00144 00145 typename vector< pair<T,int> >::iterator middle = order.begin(); 00146 for(int i=0; i<k; ++i, ++middle); 00147 00148 partial_sort(order.begin(),middle,order.end()); 00149 00150 // Build the new destination position array 00151 // (destpos is the inverse map of order.second) 00152 vector<int> destpos(mat.length()); 00153 for(int i=0; i<mat.length(); ++i) 00154 destpos[order[i].second] = i; 00155 00156 // Put elements wich are in the rows k to mat.length()-1 at their place if 00157 // their destpos is in the range 0 to k-1. If not, we leave them there. 00158 for(int startpos = mat.length()-1; startpos>=k; startpos--) 00159 { 00160 int dest = destpos[startpos]; 00161 if(dest!=-1) 00162 { 00163 while(dest<k) 00164 { 00165 mat.swapRows(startpos,dest); 00166 int newdest = destpos[dest]; 00167 destpos[dest] = -1; 00168 dest = newdest; 00169 } 00170 destpos[startpos] = -1; 00171 } 00172 } 00173 00174 if(sortk) { 00175 // Put the k firsts rows in the right order 00176 for(int startpos = 0; startpos<k; startpos++) 00177 { 00178 int dest = destpos[startpos]; 00179 if(dest!=-1) 00180 { 00181 while(dest!=startpos) 00182 { 00183 mat.swapRows(startpos,dest); 00184 int newdest = destpos[dest]; 00185 destpos[dest] = -1; 00186 dest = newdest; 00187 } 00188 destpos[startpos] = -1; 00189 } 00190 } 00191 } 00192 } 00193 00201 template<class T> 00202 void sortRows(const TMat<T>& mat, int col=0, bool increasing_order=true) 00203 { 00204 vector< pair<T,int> > order(mat.length()); 00205 typename vector< pair<T,int> >::iterator it = order.begin(); 00206 T* ptr = mat.data()+col; 00207 for(int i=0; i<mat.length(); ++i, ptr+=mat.mod(), ++it) 00208 { 00209 it->first = *ptr; 00210 it->second = i; 00211 } 00212 00213 if(increasing_order) 00214 sort(order.begin(),order.end()); 00215 else 00216 sort(order.begin(), order.end(), greater< pair<T,int> >() ); 00217 00218 // Build the new destination position array 00219 // (destpos is the inverse map of order.second) 00220 vector<int> destpos(mat.length()); 00221 for(int i=0; i<mat.length(); ++i) 00222 destpos[order[i].second] = i; 00223 00224 // Now put the full rows in order... 00225 for(int startpos = 0; startpos<mat.length(); startpos++) 00226 { 00227 int dest = destpos[startpos]; 00228 if(dest!=-1) 00229 { 00230 while(dest!=startpos) 00231 { 00232 mat.swapRows(startpos,dest); 00233 int newdest = destpos[dest]; 00234 destpos[dest] = -1; 00235 dest = newdest; 00236 } 00237 destpos[startpos] = -1; 00238 } 00239 } 00240 } 00241 00242 00243 00244 /* Not taken from Numerical Recipies: This is a quickly written and hihghly unefficient algorithm! */ 00245 /* Sorts the columns of the given matrix, in ascending order of its rownum row's elements */ 00246 template<class T> 00247 void sortColumns(const TMat<T>& mat, int rownum) 00248 { 00249 int j,jj,i; 00250 T min; 00251 T tmp; 00252 int mincol; 00253 00254 if(rownum>=mat.length()) 00255 PLERROR("In sortColumns: no rownumumn %d in matrix (%dx%d)",rownum,mat.width(),mat.length()); 00256 00257 for(j=0; j<mat.width(); j++) 00258 { 00259 // look, starting from col j, for the col with the minimum rownum element 00260 mincol = j; 00261 min = mat(rownum,j); 00262 for(jj=j; jj<mat.width(); jj++) 00263 { 00264 if(mat(rownum,jj)<min) 00265 { 00266 min = mat(rownum,jj); 00267 mincol = jj; 00268 } 00269 } 00270 if(mincol>j) /* Found a col with inferior value */ 00271 { 00272 /* So let's exchange cols j and mincol */ 00273 for(i=0; i<mat.length(); i++) 00274 { 00275 tmp = mat(i,j); 00276 mat(i,j) = mat(i,mincol); 00277 mat(i,mincol) = tmp; 00278 } 00279 } 00280 } 00281 } 00282 00283 00284 00285 // returns the position k of x in src such that src[k] <= x < src[k+1] 00286 // (returns -1 if x < src[0] or N-1 if x >= src[N-1]) 00287 // BE CAREFULL: src must be sort BEFORE the fonction binary_search is called 00288 template<class T> 00289 int binary_search(const TVec<T>& src, T x) 00290 { 00291 const int len = src.length(); 00292 00293 if (x < src[0]) return -1; 00294 else if (x >= src[len-1]) return len-1; 00295 00296 int start = 0; 00297 int end = len-1; 00298 for (;;) { 00299 int k = (start+end)/2; 00300 if (x >= src[k] && x < src[k+1]) { 00301 if (src[k] == src[k+1]) { 00302 start = k; 00303 end = k+1; 00304 while (start>0 && src[start-1]==src[start]) start--; 00305 while (end<len-1 && src[end]==src[end+1]) end++; 00306 k = (start+end)/2; 00307 } 00308 return k; 00309 } 00310 else if (x > src[k]) 00311 start = k+1; 00312 else 00313 end = k; 00314 } 00315 } 00316 00317 // Binary search according to the given column c of a matrix. The column 00318 // MUST BE SORTED. Return the row k such that src(k,c) <= x < src(k+1). 00319 // Returns -1 if x < src(0,c) or N-1 if x >= src(N-1,c). 00320 template <class T> 00321 int binary_search(const TMat<T>& src, int c, T x) 00322 { 00323 const int len = src.length(); 00324 00325 if (x < src(0,c)) 00326 return -1; 00327 else if (x >= src(len-1,c)) 00328 return len-1; 00329 00330 int start = 0, end = len-1; 00331 for (;;) { 00332 int k = (start+end)/2; 00333 if (x >= src(k,c) && x < src(k+1,c)) { 00334 if (src(k,c) == src(k+1,c)) { 00335 start = k; 00336 end = k+1; 00337 while (start > 0 && src(start-1,c) == src(start,c)) 00338 --start; 00339 while (end < len-1 && src(end,c) == src(end+1,c)) 00340 ++end; 00341 k = (start+end)/2; 00342 } 00343 return k; 00344 } 00345 else if (x > src(k,c)) 00346 start = k+1; 00347 else 00348 end = k; 00349 } 00350 } 00351 00352 00353 } // end of namespace PLearn 00354 00355 #endif // TMat_sort_INC 00356 00357 00358 /* 00359 Local Variables: 00360 mode:c++ 00361 c-basic-offset:4 00362 c-file-style:"stroustrup" 00363 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00364 indent-tabs-mode:nil 00365 fill-column:79 00366 End: 00367 */ 00368 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :