Mercurial > hg > octave-lyh

comparison liboctave/Array-d.cc @ 8651:ea8e65ca234f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
reduce memory usage in sorting
author Jaroslav Hajek <highegg@gmail.com>
date Tue, 03 Feb 2009 08:16:39 +0100
parents 25bc2d31e1bf
children 314be237cd5b
comparison
equal deleted inserted replaced
8650:a1ae2aae903e 8651:ea8e65ca234f
58 return (xisnan (b) || (a < b)); 58 return (xisnan (b) || (a < b));
59 } 59 }
60 60
61 template <> 61 template <>
62 bool 62 bool
63 ascending_compare (vec_index<double> *a, vec_index<double> *b) 63 ascending_compare (const double *a, const double *b)
64 { 64 {
65 return (xisnan (b->vec) || (a->vec < b->vec)); 65 return (xisnan (*b) || (*a < *b));
66 } 66 }
67 67
68 template <> 68 template <>
69 bool 69 bool
70 descending_compare (double a, double b) 70 descending_compare (double a, double b)
72 return (xisnan (a) || (a > b)); 72 return (xisnan (a) || (a > b));
73 } 73 }
74 74
75 template <> 75 template <>
76 bool 76 bool
77 descending_compare (vec_index<double> *a, vec_index<double> *b) 77 descending_compare (const double *a, const double *b)
78 { 78 {
79 return (xisnan (b->vec) || (a->vec > b->vec)); 79 return (xisnan (*b) || (*a > *b));
80 } 80 }
81 81
82 INSTANTIATE_ARRAY_SORT (uint64_t); 82 INSTANTIATE_ARRAY_SORT (uint64_t);
83 83
84 template <> 84 template <>
85 Array<double> 85 Array<double>
86 Array<double>::sort (octave_idx_type dim, sortmode mode) const 86 Array<double>::sort (octave_idx_type dim, sortmode mode) const
87 { 87 {
88 Array<double> m = *this; 88 Array<double> m (dims ());
89 89
90 dim_vector dv = m.dims (); 90 dim_vector dv = m.dims ();
91 91
92 if (m.length () < 1) 92 if (m.length () < 1)
93 return m; 93 return m;
97 octave_idx_type stride = 1; 97 octave_idx_type stride = 1;
98 for (int i = 0; i < dim; i++) 98 for (int i = 0; i < dim; i++)
99 stride *= dv(i); 99 stride *= dv(i);
100 100
101 double *v = m.fortran_vec (); 101 double *v = m.fortran_vec ();
102 const double *ov = data ();
102 103
103 uint64_t *p = reinterpret_cast<uint64_t *> (v); 104 uint64_t *p = reinterpret_cast<uint64_t *> (v);
105 const uint64_t *op = reinterpret_cast<const uint64_t *> (ov);
104 106
105 octave_sort<uint64_t> lsort; 107 octave_sort<uint64_t> lsort;
106 108
107 if (mode == ASCENDING) 109 if (mode == ASCENDING)
108 lsort.set_compare (ascending_compare); 110 lsort.set_compare (ascending_compare);
117 { 119 {
118 // Flip the data in the vector so that int compares on 120 // Flip the data in the vector so that int compares on
119 // IEEE754 give the correct ordering. 121 // IEEE754 give the correct ordering.
120 122
121 for (octave_idx_type i = 0; i < ns; i++) 123 for (octave_idx_type i = 0; i < ns; i++)
122 p[i] = FloatFlip (p[i]); 124 p[i] = FloatFlip (op[i]);
123 125
124 lsort.sort (p, ns); 126 lsort.sort (p, ns);
125 127
126 // Flip the data out of the vector so that int compares 128 // Flip the data out of the vector so that int compares
127 // on IEEE754 give the correct ordering. 129 // on IEEE754 give the correct ordering.
159 vtmp[l] = octave_NaN; 161 vtmp[l] = octave_NaN;
160 } 162 }
161 } 163 }
162 164
163 p += ns; 165 p += ns;
166 op += ns;
164 } 167 }
165 } 168 }
166 else 169 else
167 { 170 {
168 OCTAVE_LOCAL_BUFFER (uint64_t, vi, ns); 171 OCTAVE_LOCAL_BUFFER (uint64_t, vi, ns);
180 183
181 // Flip the data in the vector so that int compares on 184 // Flip the data in the vector so that int compares on
182 // IEEE754 give the correct ordering. 185 // IEEE754 give the correct ordering.
183 186
184 for (octave_idx_type i = 0; i < ns; i++) 187 for (octave_idx_type i = 0; i < ns; i++)
185 vi[i] = FloatFlip (p[i*stride + offset]); 188 vi[i] = FloatFlip (op[i*stride + offset]);
186 189
187 lsort.sort (vi, ns); 190 lsort.sort (vi, ns);
188 191
189 // Flip the data out of the vector so that int compares 192 // Flip the data out of the vector so that int compares
190 // on IEEE754 give the correct ordering. 193 // on IEEE754 give the correct ordering.
229 template <> 232 template <>
230 Array<double> 233 Array<double>
231 Array<double>::sort (Array<octave_idx_type> &sidx, octave_idx_type dim, 234 Array<double>::sort (Array<octave_idx_type> &sidx, octave_idx_type dim,
232 sortmode mode) const 235 sortmode mode) const
233 { 236 {
234 Array<double> m = *this; 237 Array<double> m (dims ());
235 238
236 dim_vector dv = m.dims (); 239 dim_vector dv = m.dims ();
237 240
238 if (m.length () < 1) 241 if (m.length () < 1)
239 { 242 {
246 octave_idx_type stride = 1; 249 octave_idx_type stride = 1;
247 for (int i = 0; i < dim; i++) 250 for (int i = 0; i < dim; i++)
248 stride *= dv(i); 251 stride *= dv(i);
249 252
250 double *v = m.fortran_vec (); 253 double *v = m.fortran_vec ();
254 const double *ov = data ();
251 255
252 uint64_t *p = reinterpret_cast<uint64_t *> (v); 256 uint64_t *p = reinterpret_cast<uint64_t *> (v);
253 257 const uint64_t *op = reinterpret_cast<const uint64_t *> (ov);
254 octave_sort<vec_index<uint64_t> *> indexed_sort; 258
259 octave_sort<const uint64_t *> indexed_sort;
255 260
256 if (mode == ASCENDING) 261 if (mode == ASCENDING)
257 indexed_sort.set_compare (ascending_compare); 262 indexed_sort.set_compare (ascending_compare);
258 else if (mode == DESCENDING) 263 else if (mode == DESCENDING)
259 indexed_sort.set_compare (descending_compare); 264 indexed_sort.set_compare (descending_compare);
260 else 265 else
261 abort (); 266 abort ();
262 267
263 OCTAVE_LOCAL_BUFFER (vec_index<uint64_t> *, vi, ns); 268 OCTAVE_LOCAL_BUFFER (const uint64_t *, vi, ns);
264 OCTAVE_LOCAL_BUFFER (vec_index<uint64_t>, vix, ns); 269 OCTAVE_LOCAL_BUFFER (uint64_t, vix, ns);
265 270
266 for (octave_idx_type i = 0; i < ns; i++)
267 vi[i] = &vix[i];
268
269 sidx = Array<octave_idx_type> (dv); 271 sidx = Array<octave_idx_type> (dv);
270 272
271 for (octave_idx_type j = 0; j < iter; j++) 273 for (octave_idx_type j = 0; j < iter; j++)
272 { 274 {
273 octave_idx_type offset = j; 275 octave_idx_type offset = j;
282 // Flip the data in the vector so that int compares on 284 // Flip the data in the vector so that int compares on
283 // IEEE754 give the correct ordering. 285 // IEEE754 give the correct ordering.
284 286
285 for (octave_idx_type i = 0; i < ns; i++) 287 for (octave_idx_type i = 0; i < ns; i++)
286 { 288 {
287 vi[i]->vec = FloatFlip (p[i*stride + offset]); 289 vix[i] = FloatFlip (op[i*stride + offset]);
288 vi[i]->indx = i; 290 vi[i] = vix + i;
289 } 291 }
290 292
291 indexed_sort.sort (vi, ns); 293 indexed_sort.sort (vi, ns);
292 294
293 // Flip the data out of the vector so that int compares on 295 // Flip the data out of the vector so that int compares on
294 // IEEE754 give the correct ordering 296 // IEEE754 give the correct ordering
295 297
296 for (octave_idx_type i = 0; i < ns; i++) 298 for (octave_idx_type i = 0; i < ns; i++)
297 { 299 {
298 p[i*stride + offset] = IFloatFlip (vi[i]->vec); 300 p[i*stride + offset] = IFloatFlip (*vi[i]);
299 sidx(i*stride + offset) = vi[i]->indx; 301 sidx(i*stride + offset) = vi[i] - vix;
300 } 302 }
301 303
302 // There are two representations of NaN. One will be sorted 304 // There are two representations of NaN. One will be sorted
303 // to the beginning of the vector and the other to the end. 305 // to the beginning of the vector and the other to the end.
304 // If it will be sorted to the beginning, fix things up. 306 // If it will be sorted to the beginning, fix things up.
360 return (xisnan (b) || (a < b)); 362 return (xisnan (b) || (a < b));
361 } 363 }
362 364
363 template <> 365 template <>
364 bool 366 bool
365 ascending_compare (vec_index<double> *a, 367 ascending_compare (const double *a,
366 vec_index<double> *b) 368 const double *b)
367 { 369 {
368 return (xisnan (b->vec) || (a->vec < b->vec)); 370 return (xisnan (*b) || (*a < *b));
369 } 371 }
370 372
371 template <> 373 template <>
372 bool 374 bool
373 descending_compare (double a, double b) 375 descending_compare (double a, double b)
375 return (xisnan (a) || (a > b)); 377 return (xisnan (a) || (a > b));
376 } 378 }
377 379
378 template <> 380 template <>
379 bool 381 bool
380 descending_compare (vec_index<double> *a, 382 descending_compare (const double *a,
381 vec_index<double> *b) 383 const double *b)
382 { 384 {
383 return (xisnan (b->vec) || (a->vec > b->vec)); 385 return (xisnan (*b) || (*a > *b));
384 } 386 }
385 387
386 INSTANTIATE_ARRAY_SORT (double); 388 INSTANTIATE_ARRAY_SORT (double);
387 389
388 #endif 390 #endif