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$ 00041 * AUTHORS: Yoshua Bengio 00042 * This file is part of the PLearn library. 00043 ******************************************************* */ 00044 00045 00048 #ifndef BoundedMemoryTVec_INC 00049 #define BoundedMemoryTVec_INC 00050 00051 #include <map> 00052 #include <plearn/base/DoublyLinkedList.h> 00053 #include <plearn/base/general.h> 00054 00055 namespace PLearn { 00056 using namespace std; 00057 00071 template <class KeyType, class ValueType> 00072 class BoundedMemoryCache 00073 { 00074 protected: 00075 int n_elements; 00076 int max_memory; 00077 int current_memory; 00078 public: 00079 DoublyLinkedList<KeyType>* doubly_linked_list; 00080 mutable int n_successful_hits; 00081 mutable int n_failures; 00083 map<KeyType, pair<ValueType,DoublyLinkedListElement<KeyType>*> > elements; 00085 inline BoundedMemoryCache(int max_memory_=0) 00086 : n_elements(0), max_memory(max_memory_), current_memory(0), doubly_linked_list(new DoublyLinkedList<KeyType>), 00087 n_successful_hits(0), n_failures(0) 00088 {} 00089 00090 inline void clear() { 00091 /* 00092 int mm = max_memory; 00093 max_memory = 0; 00094 removeExcess(); // this is mostly useful when removeExcess is redefined, e.g. in sub-class Cache 00095 max_memory = mm; 00096 elements.clear(); 00097 */ 00098 removeAll(); // this is mostly useful when removeAll is redefined, e.g. in sub-class Cache 00099 if (elements.size() != 0) 00100 PLERROR("Weird"); 00101 } 00102 00105 const ValueType* operator()(const KeyType& key) const { 00106 typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::const_iterator it = elements.find(key); 00107 if (it==elements.end()) 00108 { 00109 n_failures++; 00110 return 0; 00111 } 00112 n_successful_hits++; 00113 doubly_linked_list->moveToFront(it->second.second); 00114 #ifdef BOUNDCHECK 00115 if (!doubly_linked_list->last || doubly_linked_list->last->next) 00116 PLERROR("something wrong with last element of doubly linked list!"); 00117 if (dbg) 00118 verifyInvariants(); 00119 #endif 00120 return &(it->second.first); 00121 } 00122 ValueType* operator()(const KeyType& key) { 00123 typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.find(key); 00124 if (it==elements.end()) 00125 { 00126 n_failures++; 00127 return 0; 00128 } 00129 n_successful_hits++; 00130 doubly_linked_list->moveToFront(it->second.second); 00131 #ifdef BOUNDCHECK 00132 if (!doubly_linked_list->last || doubly_linked_list->last->next) 00133 PLERROR("something wrong with last element of doubly linked list!"); 00134 if (dbg) 00135 verifyInvariants(); 00136 #endif 00137 return &(it->second.first); 00138 } 00139 00140 typedef int* pointer; 00141 00144 void set(const KeyType& key, const ValueType& value) { 00145 typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.find(key); 00146 if (it==elements.end()) { // first time set 00147 DoublyLinkedListElement<KeyType>* p=doubly_linked_list->pushOnTop(key); 00148 #ifdef BOUNDCHECK 00149 if (!doubly_linked_list->last || doubly_linked_list->last->next) 00150 PLERROR("something wrong with last element of doubly linked list!"); 00151 #endif 00152 pair<ValueType,DoublyLinkedListElement<KeyType>*> el(value,p); 00153 elements[key] = el; 00154 current_memory += sizeInBytes(el); 00155 n_elements++; 00156 #ifdef BOUNDCHECK 00157 if (dbg) 00158 verifyInvariants(); 00159 #endif 00160 } 00161 else { // already there, move it to front of list and update the value 00162 ValueType& v = elements[key].first; 00163 current_memory += sizeInBytes(value) - sizeInBytes(v); 00164 doubly_linked_list->moveToFront(it->second.second); 00165 #ifdef BOUNDCHECK 00166 if (!doubly_linked_list->last || doubly_linked_list->last->next) 00167 PLERROR("something wrong with last element of doubly linked list!"); 00168 #endif 00169 v = value; 00170 #ifdef BOUNDCHECK 00171 if (dbg) 00172 verifyInvariants(); 00173 #endif 00174 } 00175 removeExcess(); 00176 } 00178 inline bool isCached(const KeyType& key) const { return elements.find(key)!=elements.end(); } 00179 inline int nElements() const { return n_elements; } 00180 inline int currentMemory() const { return current_memory; } 00181 inline int maxMemory() const { return max_memory; } 00182 inline void setMaxMemory(int new_max_memory) { 00183 max_memory=new_max_memory; 00184 removeExcess(); 00185 } 00186 00187 inline float successRate() { return float(n_successful_hits)/(n_successful_hits + n_failures); } 00188 00189 inline virtual ~BoundedMemoryCache() { clear(); } 00190 00191 // check that all pointers to doubly linked list elements are still valid 00192 void verifyInvariants() { 00193 if (!doubly_linked_list->last || doubly_linked_list->last->next) 00194 PLERROR("something wrong with last element of doubly linked list!"); 00195 if (max_memory - current_memory>500) return; 00196 typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator it = elements.begin(); 00197 for (;it!=elements.end();++it) 00198 { 00199 DoublyLinkedListElement<KeyType>* p = it->second.second; 00200 if (!p) 00201 PLERROR("BoundedMemoryCache::verifyInvariants(): null linked list pointer!"); 00202 DoublyLinkedListElement<KeyType>* next = p->next; 00203 DoublyLinkedListElement<KeyType>* previous = p->previous; 00204 if (previous && previous->next != p) 00205 PLERROR("BoundedMemoryCache::verifyInvariants(): element not part of list (previous->next != element)\n"); 00206 if (next && next->previous != p) 00207 PLERROR("BoundedMemoryCache::verifyInvariants(): element not part of list (next->previous != element)\n"); 00208 typename map<KeyType,pair<ValueType,DoublyLinkedListElement<KeyType>*> >::iterator pi = elements.find(p->entry); 00209 if (pi->second.second!=p) 00210 PLERROR("BoundedMemoryCache::verifyInvariants(): incoherent pointers between map and list\n"); 00211 if (pi->first!=p->entry) 00212 PLERROR("BoundedMemoryCache::verifyInvariants(): incoherent keys between map and list\n"); 00213 } 00214 } 00215 00216 protected: 00218 inline virtual void removeExcess() 00219 { 00220 while (current_memory > max_memory) 00221 { 00222 KeyType& key = doubly_linked_list->last->entry; 00223 current_memory -= sizeInBytes(elements[key]); 00224 elements[key].second=0; elements.erase(key); 00225 doubly_linked_list->removeLast(); 00226 n_elements--; 00227 #ifdef BOUNDCHECK 00228 if (!doubly_linked_list->last || doubly_linked_list->last->next) 00229 PLERROR("something wrong with last element of doubly linked list!"); 00230 if (dbg) 00231 verifyInvariants(); 00232 #endif 00233 } 00234 } 00235 00237 inline virtual void removeAll() 00238 { 00239 while (n_elements) 00240 { 00241 KeyType& key = doubly_linked_list->last->entry; 00242 // current_memory -= sizeInBytes(elements[key]); 00243 elements[key].second=0; elements.erase(key); 00244 doubly_linked_list->removeLast(); 00245 n_elements--; 00246 #ifdef BOUNDCHECK 00247 if (!doubly_linked_list->last || doubly_linked_list->last->next) 00248 PLERROR("something wrong with last element of doubly linked list!"); 00249 if (dbg) 00250 verifyInvariants(); 00251 #endif 00252 } 00253 current_memory = 0; 00254 } 00255 00256 }; 00257 00258 } // end of namespace PLearn 00259 00260 00261 #endif 00262 00263 00264 /* 00265 Local Variables: 00266 mode:c++ 00267 c-basic-offset:4 00268 c-file-style:"stroustrup" 00269 c-file-offsets:((innamespace . 0)(inline-open . 0)) 00270 indent-tabs-mode:nil 00271 fill-column:79 00272 End: 00273 */ 00274 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :