From b10c453d8d7eedcbd92c6f4492adf67d0e1df738 Mon Sep 17 00:00:00 2001 From: Wolfgang Bangerth Date: Mon, 4 May 1998 08:36:03 +0000 Subject: [PATCH] Optimisations in the compress function by using standard algorithms and thinking about what needs sorting and copying and what not. git-svn-id: https://svn.dealii.org/trunk@235 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/lac/source/dsmatrix.cc | 247 +++++++++++++-------------------- 1 file changed, 99 insertions(+), 148 deletions(-) diff --git a/deal.II/lac/source/dsmatrix.cc b/deal.II/lac/source/dsmatrix.cc index 2c56b9bf8a..6ca5d49372 100644 --- a/deal.II/lac/source/dsmatrix.cc +++ b/deal.II/lac/source/dsmatrix.cc @@ -7,112 +7,7 @@ #include #include #include - -/*----------------- from sort.h -------------------------*/ - - -////////// -template -inline void swap (T* a, T* b) -{ - T x = *a; - *a = *b; - *b = x; -} - -////////// -template -inline void simple_sort (const long n, T* field) -{ - long i,j; - for (i=1;i -inline void heapsort_sift (T* a, const long l, const long r) -{ - long i = l; - long j = 2*i; - T x = a[i]; - - while (j<=r) - { - if (j -inline void heapsort (const int n, T* field) -{ - field--; - - long l =(n/2)+1; - long r = n; - - while (l>1) - { - l--; - heapsort_sift(field,l,r); - } - while (r>1) - { - swap(field+l,field+r); - r--; - heapsort_sift(field,l,r); - } -} - -////////// -template -inline void _quicksort (const long r, T* a, const long l) -{ - long i = l; - long j = r; - T* x = &a[(l+r)/2]; - do - { - while (a[i] < *x) i++; - while (*x < a[j]) j--; - if (i<=j) - { - swap(a+i,a+j); - i++; - j--; - } - } - while (i<=j); - if (l -inline void quicksort (const long r, T* a) -{ - _quicksort(r,a,1); -} - - -/*----------------- end: from sort.h -------------------------*/ - +#include @@ -179,14 +74,13 @@ dSMatrixStruct::reinit (const unsigned int m, const unsigned int n, for (unsigned int i=0; i<=rows; i++) rowstart[i] = i * max_per_row; - for (int i = vec_len-1; i>=0; i--) - colnums[i] = -1; + fill_n (&colnums[0], vec_len, -1); if (rows == cols) for (unsigned int i=0;i=0) - if (((signed int)i!=entries[l]) || (rows!=cols)) - colnums[k++] = entries[l]; - - rowstart[i] = s; - s = k; - } - vec_len = rowstart[i] = s; + // copy used entries, break if + // first unused entry is reached + row_length = 0; + for (unsigned int j=rowstart[line]; j(line)), + ExcInternalError()); + // assert that the first entry + // does not show up in + // the remaining ones and that + // the remaining ones are unique + // among themselves (this handles + // both cases, quadratic and + // rectangular matrices) + Assert (find (&colnums[rowstart[line]+1], + &colnums[next_row_start], + colnums[rowstart[line]]) == + &colnums[next_row_start], + ExcInternalError()); + Assert (adjacent_find(&colnums[rowstart[line]+1], + &colnums[next_row_start]) == + &colnums[next_row_start], + ExcInternalError()); + }; + + vec_len = rowstart[rows] = next_row_start; compressed = true; - delete[] entries; -} + delete[] tmp_entries; +}; + int @@ -236,10 +165,31 @@ dSMatrixStruct::operator () (const unsigned int i, const unsigned int j) const { Assert (i(j) == colnums[rowstart[i]]) + return rowstart[i]; + } + else + // no first entry exists for this + // line + return -1; + + // all other entries are sorted, so + // we can use a binary seach algorithm + const int* p = lower_bound (&colnums[rowstart[i]+1], + &colnums[rowstart[i+1]], + static_cast(j)); + if (*p == static_cast(j)) + return (p - &colnums[0]); + else + return -1; } @@ -248,6 +198,7 @@ dSMatrixStruct::add (const unsigned int i, const unsigned int j) { Assert (i