gnumeric r16492 - in branches/gnumeric-1-8: . plugins/fn-tsa src src/tools

[mortenw svn gnome org]

Author: mortenw
Date: Tue Apr  8 18:19:17 2008
New Revision: 16492
URL: http://svn.gnome.org/viewvc/gnumeric?rev=16492&view=rev

Log:
2008-04-08  Morten Welinder  <terra gnome org>

	* src/collect.c (gnm_strip_missing): Don't return a value; take
	list directly, not as reference; make O(n) instead of O(n^2).  All
	callers changed.



Modified:
   branches/gnumeric-1-8/ChangeLog
   branches/gnumeric-1-8/NEWS
   branches/gnumeric-1-8/plugins/fn-tsa/functions.c
   branches/gnumeric-1-8/src/collect.c
   branches/gnumeric-1-8/src/collect.h
   branches/gnumeric-1-8/src/tools/ChangeLog
   branches/gnumeric-1-8/src/tools/analysis-tools.c

Modified: branches/gnumeric-1-8/NEWS
==============================================================================
--- branches/gnumeric-1-8/NEWS	(original)
+++ branches/gnumeric-1-8/NEWS	Tue Apr  8 18:19:17 2008
@@ -15,6 +15,7 @@
 	* Fix check for bogus xls files.  [#524926]
 	* Fix inc/dec buttons for General.  [#510252]
 	* Fix CONCATENATE's empty case.
+	* Improve performance of analysis tools for large ranges.
 
 --------------------------------------------------------------------------
 Gnumeric 1.8.2

Modified: branches/gnumeric-1-8/plugins/fn-tsa/functions.c
==============================================================================
--- branches/gnumeric-1-8/plugins/fn-tsa/functions.c	(original)
+++ branches/gnumeric-1-8/plugins/fn-tsa/functions.c	Tue Apr  8 18:19:17 2008
@@ -532,7 +532,7 @@
 			gval = g_array_new (FALSE, FALSE, sizeof (gnm_float));
 			gval = g_array_append_vals (gval, vals0, n0);
 			g_free (vals0);
-			gval = gnm_strip_missing (gval, &missing);
+			gnm_strip_missing (gval, missing);
 			vals0 = (gnm_float *) gval->data;
 			n0 = gval->len;
 			g_array_free (gval, FALSE);
@@ -540,7 +540,7 @@
 			gval = g_array_new (FALSE, FALSE, sizeof (gnm_float));
 			gval = g_array_append_vals (gval, vals1, n1);
 			g_free (vals1);
-			gval = gnm_strip_missing (gval, &missing);
+			gnm_strip_missing (gval, missing);
 			vals1 = (gnm_float *) gval->data;
 			n1 = gval->len;
 			g_array_free (gval, FALSE);
@@ -731,7 +731,7 @@
 			gval = g_array_new (FALSE, FALSE, sizeof (gnm_float));
 			gval = g_array_append_vals (gval, ord, n0);
 			g_free (ord);
-			gval = gnm_strip_missing (gval, &missing);
+			gnm_strip_missing (gval, missing);
 			ord = (gnm_float *) gval->data;
 			n0 = gval->len;
 			g_array_free (gval, FALSE);
@@ -739,7 +739,7 @@
 			gval = g_array_new (FALSE, FALSE, sizeof (gnm_float));
 			gval = g_array_append_vals (gval, absc, n1);
 			g_free (absc);
-			gval = gnm_strip_missing (gval, &missing);
+			gnm_strip_missing (gval, missing);
 			absc = (gnm_float *) gval->data;
 			n1 = gval->len;
 			g_array_free (gval, FALSE);
@@ -821,7 +821,7 @@
 			gval = g_array_new (FALSE, FALSE, sizeof (gnm_float));
 			gval = g_array_append_vals (gval, ord, n0);
 			g_free (ord);
-			gval = gnm_strip_missing (gval, &missing0);
+			gnm_strip_missing (gval, missing0);
 			ord = (gnm_float *) gval->data;
 			n0 = gval->len;
 			g_array_free (gval, FALSE);

Modified: branches/gnumeric-1-8/src/collect.c
==============================================================================
--- branches/gnumeric-1-8/src/collect.c	(original)
+++ branches/gnumeric-1-8/src/collect.c	Tue Apr  8 18:19:17 2008
@@ -254,23 +254,6 @@
 /* ------------------------------------------------------------------------- */
 
 /*
- *  cb_int_descending:
- *  @a:
- *  @b:
- *
- */
-static gint
-cb_int_descending (gconstpointer a, gconstpointer b)
-{
-	guint a_int = GPOINTER_TO_UINT (a);
-	guint b_int = GPOINTER_TO_UINT (b);
-
-	if (b_int > a_int) return 1;
-	if (b_int < a_int) return -1;
-	return 0;
-}
-
-/*
  *  gnm_slist_sort_merge:
  *  @list_1: a sorted list of ints with no duplicates
  *  @list_2: another one
@@ -282,18 +265,18 @@
  */
 
 GSList *
-gnm_slist_sort_merge (GSList   *l1,
-		    GSList   *l2)
+gnm_slist_sort_merge (GSList *l1,
+		      GSList *l2)
 {
-	GSList list, *l, *m;
+	GSList list, *l;
 
-	l=&list;
+	l = &list;
 
 	while (l1 && l2) {
-		if (l1->data <= l2->data) {
-			if (l1->data == l2->data) {
+		if (GPOINTER_TO_UINT (l1->data) <= GPOINTER_TO_UINT (l2->data)) {
+			if (GPOINTER_TO_UINT (l1->data) == GPOINTER_TO_UINT (l2->data)) {
 				/* remove duplicates */
-				m = l2;
+				GSList *m = l2;
 				l2 = l2->next;
 				m->next = NULL;
 				g_slist_free_1 (m);
@@ -310,46 +293,31 @@
 	return list.next;
 }
 
-/*
- *  cb_remove_missing_el :
- *  @data:
- *  @user_data: really a GArray **
- *
- */
-static void
-cb_remove_missing_el (gpointer data, gpointer user_data)
-{
-	GArray **the_data = (GArray **) (user_data);
-	guint the_item = GPOINTER_TO_UINT (data);
-
-	*the_data = g_array_remove_index (*the_data, the_item);
-	return;
-}
-
-
 
 /*
- *  strip_missing:
+ *  gnm_strip_missing:
  *  @data:
  *  @missing:
  *
- * Note this implementation returns the same array as passed in!
- * The order of the elements in the list may be changed.
  */
-GArray*
-gnm_strip_missing (GArray * data, GSList **missing)
+void
+gnm_strip_missing (GArray *data, GSList *missing)
 {
-	GArray *new_data = data;
-
-	g_return_val_if_fail (missing != NULL, data);
-
-	if ((*missing == NULL) || (g_slist_length (*missing) == 0))
-		return data;
+	unsigned src, dst;;
 
-	*missing = g_slist_sort (*missing, cb_int_descending);;
-	g_slist_foreach (*missing, cb_remove_missing_el, &new_data);
+	if (missing == NULL)
+		return;
 
-	return new_data;
+	for (src = dst = 0; src < data->len; src++) {
+		if (missing && src == GPOINTER_TO_UINT (missing->data))
+			missing = missing->next;
+		else {
+			g_array_index (data, gnm_float, dst) =
+				g_array_index (data, gnm_float, src);
+			dst++;
+		}
+	}
+	g_array_set_size (data, dst);
 }
 
 GnmValue *
@@ -367,14 +335,14 @@
 	GSList *missing1 = NULL;
 
 	vals0 = collect_floats_value_with_info (val0, ei->pos, flags,
-				      &n0, &missing0, &error);
+						&n0, &missing0, &error);
 	if (error) {
 		g_slist_free (missing0);
 		return error;
 	}
 
 	vals1 = collect_floats_value_with_info (val1, ei->pos, flags,
-				      &n1, &missing1, &error);
+						&n1, &missing1, &error);
 	if (error) {
 		g_slist_free (missing0);
 		g_slist_free (missing1);
@@ -393,7 +361,7 @@
 			gval = g_array_new (FALSE, FALSE, sizeof (gnm_float));
 			gval = g_array_append_vals (gval, vals0, n0);
 			g_free (vals0);
-			gval = gnm_strip_missing (gval, &missing);
+			gnm_strip_missing (gval, missing);
 			vals0 = (gnm_float *)gval->data;
 			n0 = gval->len;
 			g_array_free (gval, FALSE);
@@ -401,7 +369,7 @@
 			gval = g_array_new (FALSE, FALSE, sizeof (gnm_float));
 			gval = g_array_append_vals (gval, vals1, n1);
 			g_free (vals1);
-			gval = gnm_strip_missing (gval, &missing);
+			gnm_strip_missing (gval, missing);
 			vals1 = (gnm_float *)gval->data;
 			n1 = gval->len;
 			g_array_free (gval, FALSE);

Modified: branches/gnumeric-1-8/src/collect.h
==============================================================================
--- branches/gnumeric-1-8/src/collect.h	(original)
+++ branches/gnumeric-1-8/src/collect.h	Tue Apr  8 18:19:17 2008
@@ -61,7 +61,7 @@
 
 GSList *gnm_slist_sort_merge (GSList * list_1, GSList * list_2);
 
-GArray *gnm_strip_missing (GArray * data, GSList **missing);
+void gnm_strip_missing (GArray * data, GSList *missing);
 
 
 G_END_DECLS

Modified: branches/gnumeric-1-8/src/tools/analysis-tools.c
==============================================================================
--- branches/gnumeric-1-8/src/tools/analysis-tools.c	(original)
+++ branches/gnumeric-1-8/src/tools/analysis-tools.c	Tue Apr  8 18:19:17 2008
@@ -45,6 +45,7 @@
 #include "regression.h"
 #include "sheet-style.h"
 #include "workbook.h"
+#include "collect.h"
 #include "gnm-format.h"
 #include "sheet-object-cell-comment.h"
 #include "workbook-control.h"
@@ -225,105 +226,6 @@
 }
 
 /*
- *  cb_insert_diff_elements :
- *  @data:
- *  @user_data: really a GSList **
- *
- */
-static void
-cb_insert_diff_elements (gpointer data, gpointer user_data)
-{
-	GSList **the_list = (GSList **) (user_data);
-
-	if (g_slist_find (*the_list, data) == NULL) {
-		*the_list = g_slist_prepend (*the_list, data);
-	}
-	return;
-}
-
-/*
- *  cb_int_descending:
- *  @a:
- *  @b:
- *
- */
-static gint
-cb_int_descending (gconstpointer a, gconstpointer b)
-{
-	guint a_int = GPOINTER_TO_UINT (a);
-	guint b_int = GPOINTER_TO_UINT (b);
-
-	if (b_int > a_int) return 1;
-	if (b_int < a_int) return -1;
-	return 0;
-}
-
-/*
- *  union_of_int_sets:
- *  @list_1:
- *  @list_2:
- *
- */
-static GSList*
-union_of_int_sets (GSList * list_1, GSList * list_2)
-{
-	GSList *list_res = NULL;
-
-	if (list_1 == NULL)
-		return g_slist_copy (list_2);
-	if (list_2 == NULL)
-		return g_slist_copy (list_1);
-
-	list_res = g_slist_copy (list_1);
-	g_slist_foreach (list_2, cb_insert_diff_elements, &list_res);
-
-	return list_res;
-}
-
-/*
- *  cb_remove_missing_el :
- *  @data:
- *  @user_data: really a GArray **
- *
- */
-static void
-cb_remove_missing_el (gpointer data, gpointer user_data)
-{
-	GArray **the_data = (GArray **) (user_data);
-	guint the_item = GPOINTER_TO_UINT (data);
-
-	*the_data = g_array_remove_index (*the_data, the_item);
-	return;
-}
-
-
-
-/*
- *  strip_missing:
- *  @data:
- *  @missing:
- *
- */
-static GArray*
-strip_missing (GArray * data, GSList * missing)
-{
-	GArray *new_data;
-	GSList * sorted_missing;
-
-	if ((missing == NULL) || (g_slist_length (missing) == 0))
-		return data;
-
-	sorted_missing = g_slist_sort (g_slist_copy (missing), cb_int_descending);;
-	new_data = g_array_new (FALSE, FALSE, sizeof (gnm_float));
-	g_array_set_size (new_data, data->len);
-	g_memmove (new_data->data, data->data, sizeof (gnm_float) * data->len);
-	g_slist_foreach (sorted_missing, cb_remove_missing_el, &new_data);
-	g_slist_free (sorted_missing);
-
-	return new_data;
-}
-
-/*
  *  analysis_tools_remove_label:
  *  @val: range to extract label from
  *  @info: analysis_tools_data_generic_t info
@@ -3060,7 +2962,6 @@
 	GSList       *missing       = NULL;
 	GPtrArray    *x_data        = NULL;
 	data_set_t   *y_data        = NULL;
-	GArray       *cleaned       = NULL;
 	char         *text          = NULL;
 	char         *format;
 	gnm_regression_stat_t   *regression_stat = NULL;
@@ -3093,21 +2994,14 @@
 	for (i = 0; i < xdim; i++) {
 		data_set_t *this_data = g_ptr_array_index (x_data, i);
 		GSList *this_missing = this_data->missing;
-		GSList *the_union =
-			union_of_int_sets (missing, this_missing);
-		g_slist_free (missing);
-		missing = the_union;
+		missing = gnm_slist_sort_merge (missing, g_slist_copy (this_missing));
 	}
 
 	if (missing != NULL) {
-		cleaned = strip_missing (y_data->data, missing);
-		g_array_free (y_data->data, TRUE);
-		y_data->data = cleaned;
+		gnm_strip_missing (y_data->data, missing);
 		for (i = 0; i < xdim; i++) {
 			data_set_t *this_data = g_ptr_array_index (x_data, i);
-			cleaned = strip_missing (this_data->data, missing);
-			g_array_free (this_data->data, TRUE);
-			this_data->data = cleaned;
+			gnm_strip_missing (this_data->data, missing);
 		}
 		g_slist_free (missing);
 	}