@dkuppitz found an optimization trick for MultiComparator. The startIndex for comparing should start after the last Order.shuffle.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/341ebf98 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/341ebf98 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/341ebf98 Branch: refs/heads/TINKERPOP-1602 Commit: 341ebf9811c15d65231ea31c3617723c2fd0ab09 Parents: 379a6e5 Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Thu Jan 19 08:23:42 2017 -0700 Committer: Marko A. Rodriguez <okramma...@gmail.com> Committed: Thu Jan 19 08:23:42 2017 -0700 ---------------------------------------------------------------------- CHANGELOG.asciidoc | 2 +- .../gremlin/structure/io/gryo/GryoVersion.java | 4 +- .../gremlin/util/function/MultiComparator.java | 15 +++-- .../util/function/MultiComparatorTest.java | 69 ++++++++++++++++++++ 4 files changed, 81 insertions(+), 9 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/341ebf98/CHANGELOG.asciidoc ---------------------------------------------------------------------- diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc index 88cbf32..5f28790 100644 --- a/CHANGELOG.asciidoc +++ b/CHANGELOG.asciidoc @@ -26,7 +26,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima TinkerPop 3.2.4 (Release Date: NOT OFFICIALLY RELEASED YET) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -* `GroupBiOperator` no longer maintains state and thus, no more side-effect related OLAP inconsistencies. +* `GroupBiOperator` no longer maintains a detached traversal and thus, no more side-effect related OLAP inconsistencies. * Added `ProjectedTraverser` which wraps a traverser with a `List<Object>` of projected data. * Fixed an optimization bug in `CollectionBarrierSteps` where the barrier was being consumed on each `addBarrier()`. * `OrderGlobalStep` and `SampleGlobalStep` use `ProjectedTraverser` and now can work up to the local star graph in OLAP. http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/341ebf98/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java index f4e31fd..7818f6b 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/io/gryo/GryoVersion.java @@ -292,13 +292,13 @@ public enum GryoVersion { add(GryoTypeReg.of(Operator.class, 107)); add(GryoTypeReg.of(FoldStep.FoldBiOperator.class, 108)); add(GryoTypeReg.of(GroupCountStep.GroupCountBiOperator.class, 109)); - add(GryoTypeReg.of(GroupStep.GroupBiOperator.class, 117, new JavaSerializer())); // because they contain traversals + add(GryoTypeReg.of(GroupStep.GroupBiOperator.class, 117, new JavaSerializer())); add(GryoTypeReg.of(MeanGlobalStep.MeanGlobalBiOperator.class, 110)); add(GryoTypeReg.of(MeanGlobalStep.MeanNumber.class, 111)); add(GryoTypeReg.of(TreeStep.TreeBiOperator.class, 112)); add(GryoTypeReg.of(GroupStepV3d0.GroupBiOperatorV3d0.class, 113)); add(GryoTypeReg.of(RangeGlobalStep.RangeBiOperator.class, 114)); - add(GryoTypeReg.of(OrderGlobalStep.OrderBiOperator.class, 118, new JavaSerializer())); // because they contain traversals + add(GryoTypeReg.of(OrderGlobalStep.OrderBiOperator.class, 118, new JavaSerializer())); add(GryoTypeReg.of(ProfileStep.ProfileBiOperator.class, 119)); }}; } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/341ebf98/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java index 5d24ddf..d97d147 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/util/function/MultiComparator.java @@ -33,6 +33,7 @@ public final class MultiComparator<C> implements Comparator<C>, Serializable { private List<Comparator> comparators; private boolean isShuffle; + int startIndex = 0; private MultiComparator() { // for serialization purposes @@ -41,6 +42,10 @@ public final class MultiComparator<C> implements Comparator<C>, Serializable { public MultiComparator(final List<Comparator<C>> comparators) { this.comparators = (List) comparators; this.isShuffle = !this.comparators.isEmpty() && Order.shuffle == this.comparators.get(this.comparators.size() - 1); + for (int i = 0; i < this.comparators.size(); i++) { + if (this.comparators.get(i) == Order.shuffle) + this.startIndex = i + 1; + } } @Override @@ -48,12 +53,10 @@ public final class MultiComparator<C> implements Comparator<C>, Serializable { if (this.comparators.isEmpty()) { return Order.incr.compare(objectA, objectB); } else { - for (int i = 0; i < this.comparators.size(); i++) { - if (Order.shuffle != this.comparators.get(i)) { - final int comparison = this.comparators.get(i).compare(this.getObject(objectA, i), this.getObject(objectB, i)); - if (comparison != 0) - return comparison; - } + for (int i = this.startIndex; i < this.comparators.size(); i++) { + final int comparison = this.comparators.get(i).compare(this.getObject(objectA, i), this.getObject(objectB, i)); + if (comparison != 0) + return comparison; } return 0; } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/341ebf98/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/util/function/MultiComparatorTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/util/function/MultiComparatorTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/util/function/MultiComparatorTest.java new file mode 100644 index 0000000..de2a741 --- /dev/null +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/util/function/MultiComparatorTest.java @@ -0,0 +1,69 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.tinkerpop.gremlin.util.function; + +import org.apache.tinkerpop.gremlin.process.traversal.Order; +import org.junit.Test; + +import java.util.Arrays; +import java.util.Collections; +import java.util.Random; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +/** + * @author Marko A. Rodriguez (http://markorodriguez.com) + */ +public class MultiComparatorTest { + + private static final Random RANDOM = new Random(); + + @Test + public void shouldHandleShuffleCorrectly() { + MultiComparator<Object> comparator = new MultiComparator<>(Arrays.asList(Order.incr, Order.decr, Order.shuffle)); + assertTrue(comparator.isShuffle()); // because its a shuffle, the comparator simply returns 0 + for (int i = 0; i < 100; i++) { + assertEquals(0, comparator.compare(RANDOM.nextInt(), RANDOM.nextInt())); + } + // + comparator = new MultiComparator<>(Arrays.asList(Order.incr, Order.shuffle, Order.decr)); + assertEquals(1, comparator.compare(1, 2)); + assertEquals(-1, comparator.compare(2, 1)); + assertEquals(0, comparator.compare(2, 2)); + assertEquals(2, comparator.startIndex); + assertFalse(comparator.isShuffle()); + // + comparator = new MultiComparator<>(Arrays.asList(Order.incr, Order.shuffle, Order.decr, Order.shuffle, Order.incr)); + assertEquals(-1, comparator.compare(1, 2)); + assertEquals(1, comparator.compare(2, 1)); + assertEquals(0, comparator.compare(2, 2)); + assertEquals(4, comparator.startIndex); + assertFalse(comparator.isShuffle()); + // + comparator = new MultiComparator<>(Collections.emptyList()); + assertEquals(-1, comparator.compare(1, 2)); + assertEquals(1, comparator.compare(2, 1)); + assertEquals(0, comparator.compare(2, 2)); + assertEquals(0, comparator.startIndex); + assertFalse(comparator.isShuffle()); + } +}
