[Pntool-developers] SF.net SVN: pntool:[208] spnbox
Brought to you by:
compaqdrew,
miordache
Menu
▾
▴
[Pntool-developers] SF.net SVN: pntool:[208] spnbox
|
From: <Ste...@us...> - 2009-07-28 16:38:40
|
Revision: 208
http://pntool.svn.sourceforge.net/pntool/?rev=208&view=rev
Author: StephenCamp
Date: 2009-07-28 16:38:30 +0000 (Tue, 28 Jul 2009)
Log Message:
-----------
Further optimized row & column removal - now it skips allocating even a new ar member if possible.
Added OptimizeColumns and OptimizeRows, functions that set a given matrix up for speed-optimized column or row operations.
Modified the test routine as appropriate.
Modified Paths:
--------------
spnbox/extendedmatrix.c
spnbox/extendedmatrix.h
spnbox/tests/test-extendedmatrix.c
spnbox/tests/test-extendedmatrix.txt
Modified: spnbox/extendedmatrix.c
===================================================================
--- spnbox/extendedmatrix.c 2009-07-27 01:47:57 UTC (rev 207)
+++ spnbox/extendedmatrix.c 2009-07-28 16:38:30 UTC (rev 208)
@@ -217,15 +217,19 @@
{
matrix result;
- /*Prepare the result matrix.*/
+ /*Allocate the result matrix. Preserve transpose state.*/
+ int nr = m->trans ? NumberOfColumns(*m) : NumberOfRows(*m) - rows;
+ int nc = m->trans ? NumberOfRows(*m) - rows : NumberOfColumns(*m);
if (mode)
{
- AllocateMatrixType(mode, &result, NumberOfRows(*m) - rows, NumberOfColumns(*m));
+ AllocateMatrixType(mode, &result, nr, nc);
}
else
{
- AllocateMatrix(&result, NumberOfRows(*m) - rows, NumberOfColumns(*m));
+ AllocateMatrix(&result, nr, nc);
}
+ if (m->trans) TransposeMatrix(&result);
+
/*Copy the first-half block.*/
if (row)
{
@@ -240,30 +244,21 @@
}
matrix RemoveRowsOrig(matrix* m, int row, int rows)
-{
- mtype** newAr;
+{
int i;
/*Check to see if the remove can be optimized.*/
if (m->type == 2 && (! m->trans))
{
- newAr = tcalloc(m->nr, sizeof(mtype*));
- for (i = 0; i < m->nr; i++)
+ /*Do not allocate a new ar member if we can help it. Just leave the old one
+ and move the memory.*/
+ for (i = row; i < row + rows; i++)
{
- if (i < row)
- {
- newAr[i] = m->ar[i];
- }
- else if (i < row + rows)
- {
- free(m->ar[i]);
- }
- else
- {
- newAr[i - rows] = m->ar[i];
- }
+ free(m->ar[i]);
}
- free(m->ar);
- m->ar = newAr;
+ for (i = row + rows; i < m->nr; i++)
+ {
+ m->ar[i - rows] = m->ar[i];
+ }
m->nr -= rows;
}
else
@@ -280,15 +275,19 @@
matrix InsertNullRowsCopy(matrix *m, int row, int rows, int mode)
{
matrix result;
- /*Allocate the result matrix.*/
+ /*Allocate the result matrix. Preserve transpose state.*/
+ int nr = m->trans ? NumberOfColumns(*m) : NumberOfRows(*m) + rows;
+ int nc = m->trans ? NumberOfRows(*m) + rows : NumberOfColumns(*m);
if (mode)
{
- AllocateMatrixType(mode, &result, NumberOfRows(*m) + rows, NumberOfColumns(*m));
+ AllocateMatrixType(mode, &result, nr, nc);
}
else
{
- AllocateMatrix(&result, NumberOfRows(*m) + rows, NumberOfColumns(*m));
+ AllocateMatrix(&result, nr, nc);
}
+ if (m->trans) TransposeMatrix(&result);
+
/*Copy the first-half block.*/
if (row)
{
@@ -339,3 +338,22 @@
}
return *m;
}
+
+void OptimizeRows(matrix* m)
+{
+ matrix newM;
+ if (m->type != 2 || m->trans)
+ {
+ AllocateMatrixType(2, &newM, NumberOfRows(*m), NumberOfColumns(*m));
+ CopyMatrix(m, &newM);
+ DeallocateMatrix(m);
+ *m = newM;
+ }
+}
+
+void OptimizeColumns(matrix *m)
+{
+ TransposeMatrix(m);
+ OptimizeRows(m);
+ TransposeMatrix(m);
+}
Modified: spnbox/extendedmatrix.h
===================================================================
--- spnbox/extendedmatrix.h 2009-07-27 01:47:57 UTC (rev 207)
+++ spnbox/extendedmatrix.h 2009-07-28 16:38:30 UTC (rev 208)
@@ -83,4 +83,12 @@
RemoveColumns is able to employ the same type of optimization as RemoveRows
(reducing computational complexity by a factor at least equal to the number of
rows in the matrix) if and only if the matrix is a type-2 transposed.*/
+
+void OptimizeRows(matrix *m);
+/*OptimizeRows modifies the matrix passed to it so that its use with the row-
+manipulation functions will be optimized for speed.*/
+
+void OptimizeColumns(matrix *m);
+/*OptimizeColumns modifies the matrix passed to it so that its use with the
+column-manipulation functions will be optimized for speed.*/
#endif
Modified: spnbox/tests/test-extendedmatrix.c
===================================================================
--- spnbox/tests/test-extendedmatrix.c 2009-07-27 01:47:57 UTC (rev 207)
+++ spnbox/tests/test-extendedmatrix.c 2009-07-28 16:38:30 UTC (rev 208)
@@ -27,6 +27,8 @@
static void SInsertNullC(int Size, int Reps, int Col, int Cols, int Optimized);
static void TInsertNullR(matrix *A, int Row, int Rows, int Mode, int Optimized);
static void TInsertNullC(matrix *A, int Col, int Cols, int Mode, int Optimized);
+static void TOptimizeR(matrix *A);
+static void TOptimizeC(matrix *A);
static void PrintPercent(int num, int denom);
static matrix* AllocateMatrices(int rows, int cols, int Reps, int Transpose);
@@ -125,6 +127,14 @@
TRemoveC(&A, Column, Columns, Mode, Optimized);
}
}
+ else if (! strcmp(Operation, "OptimizeRows"))
+ {
+ TOptimizeR(&A);
+ }
+ else if (! strcmp(Operation, "OptimizeColumns"))
+ {
+ TOptimizeC(&A);
+ }
else
{
printf("Warning: Unrecognized operation '%s'.\n", Operation);
@@ -428,6 +438,22 @@
if (Mode >= 0) DeallocateMatrix(&result);
}
+void TOptimizeR(matrix *A)
+{
+ ShowMatrix(A, "A before row optimization");
+ OptimizeRows(A);
+ ShowMatrix(A, "A after row optimization");
+ printf("A is %stransposed", A->trans ? "" : "un");
+}
+
+void TOptimizeC(matrix *A)
+{
+ ShowMatrix(A, "A before column optimization");
+ OptimizeColumns(A);
+ ShowMatrix(A, "A after column optimization");
+ printf("A is %stransposed.\n", A->trans ? "" : "un");
+}
+
/*Display a progress percentage that changes with time instead of being left
in the output buffer.*/
void PrintPercent(int num, int denom)
@@ -490,4 +516,4 @@
*Reps = 1;
*Size = 2;
strcpy(speedtest, "no");
-}
\ No newline at end of file
+}
Modified: spnbox/tests/test-extendedmatrix.txt
===================================================================
--- spnbox/tests/test-extendedmatrix.txt 2009-07-27 01:47:57 UTC (rev 207)
+++ spnbox/tests/test-extendedmatrix.txt 2009-07-28 16:38:30 UTC (rev 208)
@@ -3,7 +3,8 @@
rem speedtest: string = "yes", "no". Sets whether a speedtest should be done.
rem Defaults to "no".
rem operation. string = InsertRows, InsertColumns, InsertNullRows,
-rem InsertNullColumns, RemoveRows, RemoveColumns. Selects the operation to test.
+rem InsertNullColumns, RemoveRows, RemoveColumns, OptimizeRows, OptimizeColumns.
+rem Selects the operation to test.
rem mode: integer. Sets the mode of the operation (>=0 performs a copy-type
rem operation and <0 performs an operation on the original matrix.) Defaults to
rem 0.
@@ -197,4 +198,21 @@
row 1
rows 2
done
+
+echo Problem 19. Row optimization.
+A 3 5
+1 2 3 4 5
+5 4 3 2 1
+1 2 3 4 5
+operation OptimizeRows
+done
+
+echo Problem 20. Column optimization.
+A 3 5
+1 2 3 4 5
+5 4 3 2 1
+1 2 3 4 5
+operation OptimizeColumns
+done
+
quit
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
