Repository: jtablesaw/tablesaw
Pull request #602 (2019-08-15 22:07:15)

Stop TableSliceGroup from making a copy of the source table while sorting.

- [x] Tick to sign-off your agreement to the [Developer Certificate of Origin (DCO) 1.1](https://developercertificate.org)

## Description
The current implementation of splitOn (which is used by summarize) makes a copy of the source table while sorting. Making unnecessary copies of tables is usually slow.

This PR.
* Implements a partitioning algorithm that does not rely on sort.
* Does not make an extra copy of the source table.
* Make the TableSlice's returned by StandardTableSliceGroup views of the original source table, not views of the sorted copy created during the implementation of TableSliceGroup. This is important for #582 

Please excuse the formatting changes. Makes it look like there are more diffs here than there really are.

## Testing

Yes. Added tests. Fixed tests that relied on the order of TableSlices in TableSliceGroup.

lwhite1: LGTM. @benmccann would you like to take a look in case i missed something? 
ryancerf: The PR creates a map of byte array to selection using LinkedHashMap. Would something from fastutils be more appropriate? If users split on a high cardinality column the map could contain a lot of entries.

Patch:
diff --git a/core/src/main/java/tech/tablesaw/table/StandardTableSliceGroup.java b/core/src/main/java/tech/tablesaw/table/StandardTableSliceGroup.java
index bab5e3a9..3ea39e7e 100644
--- a/core/src/main/java/tech/tablesaw/table/StandardTableSliceGroup.java
+++ b/core/src/main/java/tech/tablesaw/table/StandardTableSliceGroup.java
@@ -16,19 +16,25 @@ package tech.tablesaw.table;
 
 import java.nio.ByteBuffer;
 import java.util.Arrays;
+import java.util.HashMap;
+import java.util.LinkedHashMap;
 import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
 import tech.tablesaw.api.CategoricalColumn;
 import tech.tablesaw.api.Table;
 import tech.tablesaw.columns.Column;
 import tech.tablesaw.selection.BitmapBackedSelection;
 import tech.tablesaw.selection.Selection;
 
-/** A group of tables formed by performing splitting operations on an original table */
+/**
+ * A group of tables formed by performing splitting operations on an original table
+ */
 public class StandardTableSliceGroup extends TableSliceGroup {
 
   private StandardTableSliceGroup(Table original, CategoricalColumn<?>... columns) {
     super(original, splitColumnNames(columns));
-    setSourceTable(getSourceTable().sortOn(getSplitColumnNames()));
+    setSourceTable(getSourceTable());
     splitOn(getSplitColumnNames());
   }
 
@@ -41,8 +47,8 @@ public class StandardTableSliceGroup extends TableSliceGroup {
   }
 
   /**
-   * Returns a viewGroup splitting the original table on the given columns. The named columns must
-   * be CategoricalColumns
+   * Returns a viewGroup splitting the original table on the given columns. The named columns must be
+   * CategoricalColumns
    */
   public static StandardTableSliceGroup create(Table original, String... columnsNames) {
     List<CategoricalColumn<?>> columns = original.categoricalColumns(columnsNames);
@@ -58,56 +64,64 @@ public class StandardTableSliceGroup extends TableSliceGroup {
   }
 
   /**
-   * Splits the sourceTable table into sub-tables, grouping on the columns whose names are given in
-   * splitColumnNames
+   * Splits the sourceTable table into sub-tables, grouping on the columns whose names are given in splitColumnNames
    */
   private void splitOn(String... columnNames) {
+    Map<ByteArray, Selection> selectionMap = new LinkedHashMap<>();
+    Map<ByteArray, String> sliceNameMap = new HashMap<>();
+    List<Column<?>> splitColumns = getSourceTable().columns(columnNames);
+    int byteSize = getByteSize(splitColumns);
 
-    List<Column<?>> columns = getSourceTable().columns(columnNames);
-    int byteSize = getByteSize(columns);
-
-    byte[] currentKey = null;
-    String currentStringKey = null;
-    TableSlice view;
-
-    Selection selection = new BitmapBackedSelection();
-
-    for (int row = 0; row < getSourceTable().rowCount(); row++) {
-
+    for (int i = 0; i < getSourceTable().rowCount(); i++) {
+      StringBuilder stringKey = new StringBuilder();
       ByteBuffer byteBuffer = ByteBuffer.allocate(byteSize);
-      String newStringKey = "";
-
-      for (int col = 0; col < columnNames.length; col++) {
-        if (col > 0) {
-          newStringKey = newStringKey + SPLIT_STRING;
+      int count = 0;
+      for (Column<?> col : splitColumns) {
+        stringKey.append(col.getString(i));
+        if(count < splitColumns.size() - 1) {
+          stringKey.append(SPLIT_STRING);
         }
-
-        Column<?> c = getSourceTable().column(columnNames[col]);
-        String groupKey = getSourceTable().getUnformatted(row, getSourceTable().columnIndex(c));
-        newStringKey = newStringKey + groupKey;
-        byteBuffer.put(c.asBytes(row));
-      }
-      byte[] newKey = byteBuffer.array();
-      if (row == 0) {
-        currentKey = newKey;
-        currentStringKey = newStringKey;
-      }
-      if (!Arrays.equals(newKey, currentKey)) {
-        currentKey = newKey;
-        view = new TableSlice(getSourceTable(), selection);
-        view.setName(currentStringKey);
-        currentStringKey = newStringKey;
-        addSlice(view);
-        selection = new BitmapBackedSelection();
-        selection.add(row);
-      } else {
-        selection.add(row);
+        byteBuffer.put(col.asBytes(i));
+        count++;
       }
+      // Add to the matching selection.
+      ByteArray byteArray = new ByteArray(byteBuffer.array());
+      Selection selection = selectionMap.getOrDefault(byteArray, new BitmapBackedSelection());
+      selection.add(i);
+      selectionMap.put(byteArray, selection);
+      sliceNameMap.put(byteArray, stringKey.toString());
     }
-    if (!selection.isEmpty()) {
-      view = new TableSlice(getSourceTable(), selection);
-      view.setName(currentStringKey);
-      addSlice(view);
+
+    // Add all slices
+    for (Entry<ByteArray, Selection> entry : selectionMap.entrySet()) {
+      TableSlice slice = new TableSlice(getSourceTable(), entry.getValue());
+      slice.setName(sliceNameMap.get(entry.getKey()));
+      addSlice(slice);
+    }
+  }
+
+  /**
+   * Wrapper class for a byte[] that implements equals and hashcode.
+   */
+  private static class ByteArray {
+    final byte[] bytes;
+    ByteArray(byte[] bytes) {
+      this.bytes = bytes;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (this == o)
+        return true;
+      if (o == null || getClass() != o.getClass())
+        return false;
+      ByteArray byteArray = (ByteArray) o;
+      return Arrays.equals(bytes, byteArray.bytes);
+    }
+
+    @Override
+    public int hashCode() {
+      return Arrays.hashCode(bytes);
     }
   }
 }


Test patch:
diff --git a/core/src/test/java/tech/tablesaw/aggregate/AggregateFunctionsTest.java b/core/src/test/java/tech/tablesaw/aggregate/AggregateFunctionsTest.java
index ab0e680b..ac18537c 100644
--- a/core/src/test/java/tech/tablesaw/aggregate/AggregateFunctionsTest.java
+++ b/core/src/test/java/tech/tablesaw/aggregate/AggregateFunctionsTest.java
@@ -36,8 +36,12 @@ import static tech.tablesaw.aggregate.AggregateFunctions.proportionTrue;
 import static tech.tablesaw.aggregate.AggregateFunctions.standardDeviation;
 import static tech.tablesaw.aggregate.AggregateFunctions.stdDev;
 import static tech.tablesaw.aggregate.AggregateFunctions.sum;
+import static tech.tablesaw.api.QuerySupport.and;
+import static tech.tablesaw.api.QuerySupport.date;
 import static tech.tablesaw.api.QuerySupport.num;
+import static tech.tablesaw.api.QuerySupport.str;
 
+import java.time.LocalDate;
 import org.apache.commons.math3.stat.StatUtils;
 import org.junit.jupiter.api.BeforeEach;
 import org.junit.jupiter.api.Test;
@@ -186,7 +190,11 @@ class AggregateFunctionsTest {
     assertEquals(4, result.columnCount());
     assertEquals("who", result.column(0).name());
     assertEquals(323, result.rowCount());
-    assertEquals("46.0", result.getUnformatted(0, 2));
+    assertEquals("46.0",
+      result.where(and(
+        str("who").isEqualTo("fox"),
+        date("date").isEqualTo(LocalDate.of(2001, 1, 24))
+     )).getUnformatted(0, 2));
   }
 
   @Test
diff --git a/core/src/test/java/tech/tablesaw/api/TableTest.java b/core/src/test/java/tech/tablesaw/api/TableTest.java
index 313442ce..c7e261d7 100644
--- a/core/src/test/java/tech/tablesaw/api/TableTest.java
+++ b/core/src/test/java/tech/tablesaw/api/TableTest.java
@@ -29,6 +29,7 @@ import com.google.common.collect.Lists;
 import java.io.IOException;
 import java.time.LocalDate;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Comparator;
 import java.util.List;
 import java.util.Random;
@@ -63,7 +64,9 @@ public class TableTest {
     Table result = table.summarize("Injuries", mean, stdDev).by("State");
     assertEquals(49, result.rowCount());
     assertEquals(3, result.columnCount());
-    assertEquals("4.580805569368455", result.doubleColumn(1).getString(0));
+    assertEquals("4.580805569368441",
+      result.where(result.stringColumn("state").isEqualTo("AL"))
+        .doubleColumn(1).getString(0));
   }
 
   @Test
diff --git a/core/src/test/java/tech/tablesaw/table/TableSliceGroupTest.java b/core/src/test/java/tech/tablesaw/table/TableSliceGroupTest.java
index 229fdd03..1e9d241d 100644
--- a/core/src/test/java/tech/tablesaw/table/TableSliceGroupTest.java
+++ b/core/src/test/java/tech/tablesaw/table/TableSliceGroupTest.java
@@ -18,7 +18,9 @@ import static org.junit.jupiter.api.Assertions.assertEquals;
 import static org.junit.jupiter.api.Assertions.assertTrue;
 
 import com.google.common.collect.ImmutableListMultimap;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
 import org.apache.commons.math3.stat.StatUtils;
 import org.junit.jupiter.api.BeforeEach;
 import org.junit.jupiter.api.Test;
@@ -44,7 +46,8 @@ public class TableSliceGroupTest {
 
   @BeforeEach
   public void setUp() throws Exception {
-    table = Table.read().csv(CsvReadOptions.builder("../data/bush.csv"));
+    // The source data is sorted by who. Put it in a different order.
+    table = Table.read().csv(CsvReadOptions.builder("../data/bush.csv")).sortAscendingOn("approval");
   }
 
   @Test
@@ -61,6 +64,23 @@ public class TableSliceGroupTest {
     assertEquals(table.rowCount(), count);
   }
 
+  @Test
+  public void testViewGroupCreationNames() {
+
+    TableSliceGroup group = StandardTableSliceGroup.create(table, "who", "approval");
+    List<TableSlice> viewList = group.getSlices();
+    assertEquals(146, group.size());
+
+    Set<String> viewNames = new HashSet<>();
+    int count = 0;
+    for (TableSlice view : viewList) {
+      viewNames.add(view.name());
+      count += view.rowCount();
+    }
+    assertEquals(table.rowCount(), count);
+    assertTrue(viewNames.contains("zogby~~~45"));
+  }
+
   @Test
   public void testViewTwoColumn() {
     TableSliceGroup group =