Changeset 38579

Timestamp:

Jul 7, 2015, 11:16:18 PM (11 years ago)

Author:

eugene

Message:

update to uniq algorith: sort first then look at sequences

File:

• branches/eam_branches/ipp-20150625/Ohana/src/opihi/cmd.data/uniq.c (modified) (2 diffs)

branches/eam_branches/ipp-20150625/Ohana/src/opihi/cmd.data/uniq.c

@@ -1 +1 @@
 # include "data.h"
+// NOTE: if there are only a few uniq values, the old algorithm is not bad.  
+// for 10000 uniq values, 30M points take ~20sec in the new algorithm, 
+// 3M points takess 45 sec in the old method.
 
 int uniq (int argc, char **argv) {
   
-  int Nnew, i, j, found;
+  int Nnew, i, N;
   Vector *ivec, *ovec;
 
+  Vector *cvec = NULL;
+  if ((N = get_argument (argc, argv, "-c"))) {
+    remove_argument (N, &argc, argv);
+    if ((cvec = SelectVector (argv[N], ANYVECTOR, TRUE)) == NULL) {
+      gprint (GP_ERR, "invalid vector %s\n", argv[N]);
+      return FALSE;
+    }
+    remove_argument (N, &argc, argv);
+  }
+
   if (argc != 3) {
-    gprint (GP_ERR, "USAGE: uniq (in) (out)\n");
+    gprint (GP_ERR, "USAGE: uniq (in) (out) -c count\n");
     return (FALSE);
   }
@@ -16 +29 @@
   /* allocate the maximum possible needed */
   ResetVector (ovec, ivec->type, ivec->Nelements);
+  if (cvec) {
+    ResetVector (cvec, OPIHI_INT, ivec->Nelements);
+  }
 
   Nnew = 0;
 
   if (ivec->type == OPIHI_FLT) {
-    opihi_flt *v1 = ivec[0].elements.Flt;
-    for (i = 0; i < ivec[0].Nelements; i++, v1++) {
-      opihi_flt *v2 = ovec[0].elements.Flt;
-      found = FALSE;
-      for (j = 0; !found && (j < Nnew); j++, v2++) {
-        if (*v1 == *v2) found = TRUE;
+    // copy the input data to a temporary array to avoid damaging it with sort
+    opihi_flt *indata = NULL;
+    ALLOCATE (indata, opihi_flt, ivec[0].Nelements);
+    memcpy (indata, ivec->elements.Flt, ivec[0].Nelements*sizeof(opihi_flt));
+
+    dsort (indata, ivec->Nelements);
+
+    Nnew = 0;
+    opihi_flt *vtgt = ovec[0].elements.Flt;
+
+    opihi_flt *vsrc = indata;
+
+    for (i = 0; i < ivec->Nelements; Nnew++) {
+      vtgt[Nnew] = *vsrc;
+      int Ndup = 0;
+      opihi_flt lastValue = *vsrc;
+      while ((i < ivec->Nelements) && (*vsrc == lastValue)) {
+        i++;
+        vsrc ++;
+        Ndup ++;
       }
-      if (!found) {
-        ovec[0].elements.Flt[Nnew] = *v1;
-        Nnew ++;
+      if (cvec) {
+        cvec->elements.Int[Nnew] = Ndup;
       }
     }
+    free (indata);
   } else {
-    opihi_int *v1 = ivec[0].elements.Int;
-    for (i = 0; i < ivec[0].Nelements; i++, v1++) {
-      opihi_int *v2 = ovec[0].elements.Int;
-      found = FALSE;
-      for (j = 0; !found && (j < Nnew); j++, v2++) {
-        if (*v1 == *v2) found = TRUE;
+    // copy the input data to a temporary array to avoid damaging it with sort
+    opihi_int *indata = NULL;
+    ALLOCATE (indata, opihi_int, ivec[0].Nelements);
+    memcpy (indata, ivec->elements.Int, ivec[0].Nelements*sizeof(opihi_int));
+
+    isort (indata, ivec->Nelements);
+
+    Nnew = 0;
+    opihi_int *vtgt = ovec[0].elements.Int;
+
+    opihi_int *vsrc = indata;
+
+    for (i = 0; i < ivec->Nelements; Nnew++) {
+      vtgt[Nnew] = *vsrc;
+      int Ndup = 0;
+      opihi_int lastValue = *vsrc;
+      while ((i < ivec->Nelements) && (*vsrc == lastValue)) {
+        i++;
+        vsrc ++;
+        Ndup ++;
       }
-      if (!found) {
-        ovec[0].elements.Int[Nnew] = *v1;
-        Nnew ++;
+      if (cvec) {
+        cvec->elements.Int[Nnew] = Ndup;
       }
     }
+    free (indata);
   }
 
   // free up extra memory
   ResetVector (ovec, ivec->type, Nnew);
+  if (cvec) ResetVector (ovec, OPIHI_INT, Nnew);
 
   return (TRUE);