Changeset: 3c27c0d8eb00 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=3c27c0d8eb00
Modified Files:
gdk/gdk_aggr.c
gdk/gdk_calc.h
monetdb5/modules/kernel/aggr.c
monetdb5/modules/kernel/aggr.mal
Branch: default
Log Message:
Implemented grouped median aggregates.
Unlike other "sub" aggregates, the median aggregate is also
implemented for when no groups are specified (i.e. at the GDK level,
the group and extent bats are NULL, at the MAL level, no groups and
extents arguments).
Unlike the "official" description of median, but like the old
implementation, in case of an even number of values, we don't return
the average of the middle two values, but we return the lower of the
middle two values.
diffs (256 lines):
diff --git a/gdk/gdk_aggr.c b/gdk/gdk_aggr.c
--- a/gdk/gdk_aggr.c
+++ b/gdk/gdk_aggr.c
@@ -1428,3 +1428,149 @@ BATgroupmax(BAT *b, BAT *g, BAT *e, BAT
bn->T->nonil = nils == 0;
return bn;
}
+
+BAT *
+BATgroupmedian(BAT *b, BAT *g, BAT *e, BAT *s, int tp, int skip_nils, int
abort_on_error)
+{
+ int freeb = 0, freeg = 0;
+ oid min, max;
+ BUN ngrp;
+ BUN nils = 0;
+ BAT *bn = NULL;
+ BUN start, end, cnt;
+ const oid *cand = NULL, *candend = NULL;
+ BAT *t1, *t2;
+ BATiter bi;
+ const void *v;
+ const void *nil;
+ int (*atomcmp)(const void *, const void *);
+
+ (void) abort_on_error;
+
+ if (initgroupaggr(b, g, e, s, "BATgroupmedian", &min, &max, &ngrp,
+ &start, &end, &cnt, &cand, &candend) == GDK_FAIL)
+ return NULL;
+ assert(tp == b->ttype);
+ if (!ATOMlinear(b->ttype)) {
+ GDKerror("BATgroupmedian: cannot determine median on "
+ "non-linear type %s\n", ATOMname(b->ttype));
+ return NULL;
+ }
+
+ if (BATcount(b) == 0 || ngrp == 0) {
+ /* trivial: no medians, so return bat aligned with e with
+ * nil in the tail */
+ bn = BATconstant(tp, ATOMnilptr(tp), ngrp);
+ BATseqbase(bn, ngrp == 0 ? 0 : min);
+ return bn;
+ }
+
+ if (s) {
+ b = BATleftjoin(s, b, BATcount(s));
+ if (b->htype != TYPE_void) {
+ t1 = BATmirror(BATmark(BATmirror(b), 0));
+ BBPunfix(b->batCacheid);
+ b = t1;
+ }
+ freeb = 1;
+ if (g) {
+ g = BATleftjoin(s, g, BATcount(s));
+ if (g->htype != TYPE_void) {
+ t1 = BATmirror(BATmark(BATmirror(g), 0));
+ BBPunfix(g->batCacheid);
+ g = t1;
+ }
+ freeg = 1;
+ }
+ }
+
+ if (g) {
+ BATsubsort(&t1, &t2, NULL, g, NULL, NULL, 0, 0);
+ if (freeg)
+ BBPunfix(g->batCacheid);
+ g = t1;
+ freeg = 1;
+ } else {
+ t2 = NULL;
+ }
+ BATsubsort(&t1, NULL, NULL, b, t2, g, 0, 0);
+ if (freeb)
+ BBPunfix(b->batCacheid);
+ b = t1;
+ freeb = 1;
+ if (t2)
+ BBPunfix(t2->batCacheid);
+
+ bn = BATnew(TYPE_void, b->ttype, ngrp);
+ if (bn == NULL)
+ return NULL;
+
+ bi = bat_iterator(b);
+ nil = ATOMnilptr(b->ttype);
+ atomcmp = BATatoms[b->ttype].atomCmp;
+
+ if (g) {
+ const oid *grps;
+ oid prev;
+ BUN p, q, r;
+
+ grps = (const oid *) Tloc(g, BUNfirst(g));
+ prev = grps[0];
+ for (r = 0, p = 1, q = BATcount(g); p <= q; p++) {
+ if (p == q || grps[p] != prev) {
+ if (skip_nils) {
+ while (r < p && (*atomcmp)(BUNtail(bi,
BUNfirst(b) + r), nil) == 0)
+ r++;
+ }
+ while (BATcount(bn) < prev - min) {
+ bunfastins_nocheck(bn, BUNlast(bn), 0,
+ nil, 0, Tsize(bn));
+ nils++;
+ }
+ if (r == p) {
+ bunfastins_nocheck(bn, BUNlast(bn), 0,
+ nil, 0, Tsize(bn));
+ nils++;
+ } else {
+ v = BUNtail(bi, BUNfirst(b) + (r + p -
1) / 2);
+ bunfastins_nocheck(bn, BUNlast(bn), 0,
+ v, 0, Tsize(bn));
+ nils += (*atomcmp)(v, nil) == 0;
+ }
+ r = p;
+ if (p < q)
+ prev = grps[p];
+ }
+ }
+ while (BATcount(bn) < ngrp) {
+ bunfastins_nocheck(bn, BUNlast(bn), 0,
+ nil, 0, Tsize(bn));
+ }
+ BATseqbase(bn, min);
+ } else {
+ v = BUNtail(bi, BUNfirst(b) + (BATcount(b) - 1) / 2);
+ BUNappend(bn, v, FALSE);
+ BATseqbase(bn, 0);
+ nils += (*atomcmp)(v, nil) == 0;
+ }
+
+ if (freeb)
+ BBPunfix(b->batCacheid);
+ if (freeg)
+ BBPunfix(g->batCacheid);
+
+ bn->tkey = BATcount(bn) <= 1;
+ bn->tsorted = BATcount(bn) <= 1;
+ bn->trevsorted = BATcount(bn) <= 1;
+ bn->T->nil = nils != 0;
+ bn->T->nonil = nils == 0;
+ return bn;
+
+ bunins_failed:
+ if (freeb)
+ BBPunfix(b->batCacheid);
+ if (freeg)
+ BBPunfix(g->batCacheid);
+ BBPunfix(bn->batCacheid);
+ return NULL;
+}
diff --git a/gdk/gdk_calc.h b/gdk/gdk_calc.h
--- a/gdk/gdk_calc.h
+++ b/gdk/gdk_calc.h
@@ -125,3 +125,4 @@ gdk_export BAT *BATgroupcount(BAT *b, BA
gdk_export BAT *BATgroupsize(BAT *b, BAT *g, BAT *e, BAT *s, int tp, int
skip_nils, int abort_on_error);
gdk_export BAT *BATgroupmin(BAT *b, BAT *g, BAT *e, BAT *s, int tp, int
skip_nils, int abort_on_error);
gdk_export BAT *BATgroupmax(BAT *b, BAT *g, BAT *e, BAT *s, int tp, int
skip_nils, int abort_on_error);
+gdk_export BAT *BATgroupmedian(BAT *b, BAT *g, BAT *e, BAT *s, int tp, int
skip_nils, int abort_on_error);
diff --git a/monetdb5/modules/kernel/aggr.c b/monetdb5/modules/kernel/aggr.c
--- a/monetdb5/modules/kernel/aggr.c
+++ b/monetdb5/modules/kernel/aggr.c
@@ -497,9 +497,9 @@ AGGRsubgrouped(bat *retval, bat *bid, ba
BAT *b, *g, *e, *s, *bn;
b = BATdescriptor(*bid);
- g = BATdescriptor(*gid);
- e = BATdescriptor(*eid);
- if (b == NULL || g == NULL || e == NULL) {
+ g = gid ? BATdescriptor(*gid) : NULL;
+ e = eid ? BATdescriptor(*eid) : NULL;
+ if (b == NULL || (gid != NULL && g == NULL) || (eid != NULL && e ==
NULL)) {
if (b)
BBPreleaseref(b->batCacheid);
if (g)
@@ -508,12 +508,17 @@ AGGRsubgrouped(bat *retval, bat *bid, ba
BBPreleaseref(e->batCacheid);
throw(MAL, malfunc, RUNTIME_OBJECT_MISSING);
}
+ if (tp == TYPE_any && grpfunc == BATgroupmedian)
+ tp = b->ttype;
+
if (sid) {
s = BATdescriptor(*sid);
if (s == NULL) {
BBPreleaseref(b->batCacheid);
- BBPreleaseref(g->batCacheid);
- BBPreleaseref(e->batCacheid);
+ if (g)
+ BBPreleaseref(g->batCacheid);
+ if (e)
+ BBPreleaseref(e->batCacheid);
throw(MAL, malfunc, RUNTIME_OBJECT_MISSING);
}
} else {
@@ -521,8 +526,10 @@ AGGRsubgrouped(bat *retval, bat *bid, ba
}
bn = (*grpfunc)(b, g, e, s, tp, skip_nils, abort_on_error);
BBPreleaseref(b->batCacheid);
- BBPreleaseref(g->batCacheid);
- BBPreleaseref(e->batCacheid);
+ if (g)
+ BBPreleaseref(g->batCacheid);
+ if (e)
+ BBPreleaseref(e->batCacheid);
if (s)
BBPreleaseref(s->batCacheid);
if (bn == NULL) {
@@ -836,3 +843,27 @@ AGGRsubmaxcand(bat *retval, bat *bid, ba
return AGGRsubgrouped(retval, bid, gid, eid, sid, *skip_nils,
0, TYPE_oid, BATgroupmax,
"aggr.submax");
}
+
+aggr_export str AGGRmedian(bat *retval, bat *bid, int *skip_nils);
+str
+AGGRmedian(bat *retval, bat *bid, int *skip_nils)
+{
+ return AGGRsubgrouped(retval, bid, NULL, NULL, NULL, *skip_nils,
+ 0, TYPE_any, BATgroupmedian,
"aggr.submedian");
+}
+
+aggr_export str AGGRsubmedian(bat *retval, bat *bid, bat *gid, bat *eid, int
*skip_nils);
+str
+AGGRsubmedian(bat *retval, bat *bid, bat *gid, bat *eid, int *skip_nils)
+{
+ return AGGRsubgrouped(retval, bid, gid, eid, NULL, *skip_nils,
+ 0, TYPE_any, BATgroupmedian,
"aggr.submedian");
+}
+
+aggr_export str AGGRsubmediancand(bat *retval, bat *bid, bat *gid, bat *eid,
bat *sid, int *skip_nils);
+str
+AGGRsubmediancand(bat *retval, bat *bid, bat *gid, bat *eid, bat *sid, int
*skip_nils)
+{
+ return AGGRsubgrouped(retval, bid, gid, eid, sid, *skip_nils,
+ 0, TYPE_any, BATgroupmedian,
"aggr.submedian");
+}
diff --git a/monetdb5/modules/kernel/aggr.mal b/monetdb5/modules/kernel/aggr.mal
--- a/monetdb5/modules/kernel/aggr.mal
+++ b/monetdb5/modules/kernel/aggr.mal
@@ -846,3 +846,14 @@ command subcount(b:bat[:oid,:any_1],g:ba
address AGGRsubcountcand
comment "Grouped count aggregate with candidates list";
+command submedian(b:bat[:oid,:any_1],skip_nils:int) :bat[:oid,:any_1]
+address AGGRmedian
+comment "Median aggregate";
+
+command
submedian(b:bat[:oid,:any_1],g:bat[:oid,:oid],e:bat[:oid,:any_2],skip_nils:int)
:bat[:oid,:any_1]
+address AGGRsubmedian
+comment "Grouped median aggregate";
+
+command
submedian(b:bat[:oid,:any_1],g:bat[:oid,:oid],e:bat[:oid,:any_2],s:bat[:oid,:oid],skip_nils:int)
:bat[:oid,:any_1]
+address AGGRsubmediancand
+comment "Grouped median aggregate with candidate list";
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
