PLearn 0.1
|
00001 // -*- C++ -*- 00002 00003 // PLearn (A C++ Machine Learning Library) 00004 // Copyright (C) 1998 Pascal Vincent 00005 // Copyright (C) 1999-2001 Pascal Vincent, Yoshua Bengio, Rejean Ducharme and University of Montreal 00006 // Copyright (C) 2002 Pascal Vincent, Julien Keable, Xavier Saint-Mleux 00007 // Copyright (C) 2003 Olivier Delalleau 00008 // 00009 // Redistribution and use in source and binary forms, with or without 00010 // modification, are permitted provided that the following conditions are met: 00011 // 00012 // 1. Redistributions of source code must retain the above copyright 00013 // notice, this list of conditions and the following disclaimer. 00014 // 00015 // 2. Redistributions in binary form must reproduce the above copyright 00016 // notice, this list of conditions and the following disclaimer in the 00017 // documentation and/or other materials provided with the distribution. 00018 // 00019 // 3. The name of the authors may not be used to endorse or promote 00020 // products derived from this software without specific prior written 00021 // permission. 00022 // 00023 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR 00024 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00025 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN 00026 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00027 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 00028 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 00029 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 00030 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00031 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00032 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00033 // 00034 // This file is part of the PLearn library. For more information on the PLearn 00035 // library, go to the PLearn Web site at www.plearn.org 00036 00037 00038 /* ******************************************************* 00039 * $Id: SortRowsVMatrix.cc 9408 2008-08-27 17:47:25Z nouiz $ 00040 ******************************************************* */ 00041 00042 #include "SortRowsVMatrix.h" 00043 #include "SubVMatrix.h" 00044 #include <plearn/math/TMat_sort.h> 00045 00046 namespace PLearn { 00047 using namespace std; 00048 00051 PLEARN_IMPLEMENT_OBJECT( 00052 SortRowsVMatrix, 00053 "Sort the samples of a VMatrix according to one (or more) given columns.", 00054 "The implementation is not efficient at all, feel free to improve it !" 00055 ); 00056 00058 // SortRowsVMatrix // 00060 SortRowsVMatrix::SortRowsVMatrix(): 00061 ignore_missing_fields(false), 00062 increasing_order(true) 00063 { 00064 warn_if_all_rows_selected = false; 00065 } 00066 00068 // declareOptions // 00070 void SortRowsVMatrix::declareOptions(OptionList &ol) 00071 { 00072 declareOption(ol, "sort_columns", &SortRowsVMatrix::sort_columns, 00073 OptionBase::buildoption, 00074 "Indices of the column(s) that must be sorted (the first one is the\n" 00075 "first criterion)."); 00076 00077 declareOption(ol, "sort_columns_by_name", 00078 &SortRowsVMatrix::sort_columns_by_name, 00079 OptionBase::buildoption, 00080 "Names of the column(s) that must be sorted (the first one is the\n" 00081 "first criterion). This option is optional and, if provided, the\n" 00082 "'sort_columns' option will be ignored."); 00083 00084 declareOption(ol, "ignore_missing_fields", 00085 &SortRowsVMatrix::ignore_missing_fields, 00086 OptionBase::buildoption, 00087 "If true, then no error will be thrown when a column given in\n" 00088 "sort_columns or sort_columns_by_name is missing."); 00089 00090 declareOption(ol, "increasing_order", &SortRowsVMatrix::increasing_order, OptionBase::buildoption, 00091 " if set to 1, the data will be sorted in increasing order"); 00092 00093 inherited::declareOptions(ol); 00094 00095 // Hide unused options. 00096 00097 redeclareOption(ol, "indices", &SortRowsVMatrix::indices, OptionBase::nosave, 00098 "The indices are computed at build time."); 00099 redeclareOption(ol, "indices_vmat", &SortRowsVMatrix::indices_vmat, OptionBase::nosave, 00100 "Unused."); 00101 } 00102 00104 // makeDeepCopyFromShallowCopy // 00106 void SortRowsVMatrix::makeDeepCopyFromShallowCopy(CopiesMap& copies) 00107 { 00108 deepCopyField(sort_columns, copies); 00109 deepCopyField(sort_columns_by_name, copies); 00110 inherited::makeDeepCopyFromShallowCopy(copies); 00111 } 00112 00114 // build // 00116 void SortRowsVMatrix::build() 00117 { 00118 inherited::build(); 00119 build_(); 00120 } 00121 00123 // build_ // 00125 void SortRowsVMatrix::build_() 00126 { 00127 if (sort_columns_by_name.isNotEmpty() && source) { 00128 // Convert column names into column indices. 00129 sort_columns.resize(0); 00130 for (int i = 0; i < sort_columns_by_name.length(); i++) { 00131 int idx = source->getFieldIndex(sort_columns_by_name[i], 00132 !ignore_missing_fields); 00133 if (idx >= 0) 00134 sort_columns.append(idx); 00135 } 00136 } 00137 // Check we don't try to sort twice by the same column (this can be confusing). 00138 // Also verify fields do exist, just in case. 00139 if (sort_columns.isNotEmpty()) { 00140 for (int i = 0; i < sort_columns.length(); i++) { 00141 if (!ignore_missing_fields && 00142 (sort_columns[i] < 0 || sort_columns[i] >= source->width())) 00143 PLERROR("In SortRowsVMatrix::build_ - Field with index %d " 00144 "cannot exist in the source VMatrix, whose width is " 00145 "%d", sort_columns[i], source->width()); 00146 for (int j = i + 1; j < sort_columns.length(); j++) { 00147 if (sort_columns[j] == sort_columns[i]) { 00148 PLERROR("In SortRowsVMatrix::build_ - You have a duplicated index in the 'sort_columns' vector"); 00149 } 00150 } 00151 } 00152 } 00153 // Construct the indices vector. 00154 if (source) { 00155 updateMtime(source); 00156 indices = TVec<int>(0, source.length()-1, 1); 00157 if (sort_columns.length() > 1) { 00158 // We need to sort many columns: we use the unefficient method. 00159 sortRows(source, indices, sort_columns, 0, source->length()-1, 0, increasing_order); 00160 } else if (sort_columns.length() > 0) { 00161 // Only sorting one column: we can do this more efficiently. 00162 Mat to_sort(source->length(), 2); 00163 // Fill first column with the column to sort. 00164 to_sort.column(0) << source.subMatColumns(sort_columns[0], 1); 00165 // Fill 2nd column with indices. 00166 to_sort.column(1) << Vec(0, to_sort.length() - 1, 1); 00167 00168 if (to_sort.column(0).hasMissing()) { 00169 // We have missing values, so we use the unefficient method 00170 sortRows(source, indices, sort_columns, 0, source->length()-1, 00171 0, increasing_order); 00172 } else { 00173 // Perform the sort. 00174 PLearn::sortRows(to_sort, 0, increasing_order); 00175 // Get the indices. 00176 indices << to_sort.column(1); 00177 } 00178 } 00179 inherited::build(); // Since we have just changed the indices. 00180 } 00181 updateMtime(indices_vmat); 00182 } 00183 00185 // sortRows // 00187 void SortRowsVMatrix::sortRows(VMat& m, TVec<int>& indices, TVec<int>& sort_columns, int istart, int iend, int colstart, bool increasing_order) { 00188 real best = 0; // Initialization only to prevent compiler warning. 00189 real jval; 00190 int tmp; 00191 bool better; 00192 if (sort_columns.size() > colstart) { 00193 int col = sort_columns[colstart]; // The current column used to perform sorting. 00194 for (int i = istart; i <= iend-1; i++) { 00195 // Let's look for the i-th element of our result. 00196 int i_nan = i; 00197 // Find first non-missing. 00198 while (i_nan <= iend && is_missing(best = m(indices[i_nan],col))) i_nan++; 00199 if (i_nan > iend) 00200 // All nan ! 00201 break; 00202 else if (i_nan > i) { 00203 // There were some nans. We swap i_nan and i. 00204 tmp = indices[i]; 00205 indices[i] = indices[i_nan]; 00206 indices[i_nan] = tmp; 00207 } 00208 for (int j = i+1; j <= iend; j++) { 00209 better = false; 00210 jval = m(indices[j],col); 00211 if (increasing_order && jval < best) 00212 better = true; 00213 else if (!increasing_order && jval > best) 00214 better = true; 00215 if (better) { 00216 // Swap i and j. 00217 tmp = indices[j]; 00218 indices[j] = indices[i]; 00219 indices[i] = tmp; 00220 best = jval; 00221 } 00222 } 00223 } 00224 // At this point, we have only sorted according to one column. 00225 if (sort_columns.length() > colstart + 1) { 00226 // There are other sorting criteria. 00227 // Let's find where we need to apply them. 00228 int i = istart; 00229 real val; 00230 while (i <= iend - 1) { 00231 val = m(indices[i],col); 00232 int j = i+1; 00233 while ( j <= iend 00234 && ( is_equal(m(indices[j],col), val, 1.0))) 00235 j++; 00236 j--; 00237 if (j > i) { 00238 // There are consecutive elements with the same value for the sorting 00239 // criterion, thus we must use the other criteria to sort them correctly. 00240 sortRows(m, indices, sort_columns, i, j, colstart + 1, increasing_order); 00241 } 00242 i = j+1; 00243 } 00244 } 00245 } 00246 } 00247 00248 } // end of namespace PLearn 00249 00250 00251 /* 00252 Local Variables: 00253 mode:c++ 00254 c-basic-offset:4 00255 c-file-style:"stroustrup" 00256 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00257 indent-tabs-mode:nil 00258 fill-column:79 00259 End: 00260 */ 00261 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :