You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kylin.apache.org by sh...@apache.org on 2015/10/19 10:51:30 UTC
incubator-kylin git commit: KYLIN-1068 code refine
Repository: incubator-kylin
Updated Branches:
refs/heads/KYLIN-1068 589a0bca2 -> 64a1fcb63
KYLIN-1068 code refine
Project: http://git-wip-us.apache.org/repos/asf/incubator-kylin/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-kylin/commit/64a1fcb6
Tree: http://git-wip-us.apache.org/repos/asf/incubator-kylin/tree/64a1fcb6
Diff: http://git-wip-us.apache.org/repos/asf/incubator-kylin/diff/64a1fcb6
Branch: refs/heads/KYLIN-1068
Commit: 64a1fcb63d90d008fc18494bbde82c819d4f94fa
Parents: 589a0bc
Author: shaofengshi <sh...@apache.org>
Authored: Mon Oct 19 16:51:15 2015 +0800
Committer: shaofengshi <sh...@apache.org>
Committed: Mon Oct 19 16:51:15 2015 +0800
----------------------------------------------------------------------
.../kylin/common/topn/DoublyLinkedList.java | 66 ++------------------
.../apache/kylin/common/topn/TopNCounter.java | 38 ++++++-----
.../kylin/common/topn/TopNCounterTest.java | 2 +-
.../kylin/metadata/measure/TopNAggregator.java | 6 +-
.../serializer/TopNCounterSerializer.java | 24 +++----
5 files changed, 42 insertions(+), 94 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/64a1fcb6/core-common/src/main/java/org/apache/kylin/common/topn/DoublyLinkedList.java
----------------------------------------------------------------------
diff --git a/core-common/src/main/java/org/apache/kylin/common/topn/DoublyLinkedList.java b/core-common/src/main/java/org/apache/kylin/common/topn/DoublyLinkedList.java
index bf0e582..d268a30 100644
--- a/core-common/src/main/java/org/apache/kylin/common/topn/DoublyLinkedList.java
+++ b/core-common/src/main/java/org/apache/kylin/common/topn/DoublyLinkedList.java
@@ -26,11 +26,11 @@ import java.util.Iterator;
*
* @param <T>
*/
-public class DoublyLinkedList<T> implements Iterable<T> {
+public class DoublyLinkedList<T> {
- protected int size;
- protected ListNode2<T> tail;
- protected ListNode2<T> head;
+ private int size;
+ private ListNode2<T> tail;
+ private ListNode2<T> head;
/**
* Append to head of list
@@ -133,54 +133,7 @@ public class DoublyLinkedList<T> implements Iterable<T> {
public int size() {
return size;
}
-
-
- @Override
- public Iterator<T> iterator() {
- return new DoublyLinkedListIterator(this);
- }
-
- protected class DoublyLinkedListIterator implements Iterator<T> {
-
- protected DoublyLinkedList<T> list;
- protected ListNode2<T> itr;
- protected int length;
-
- public DoublyLinkedListIterator(DoublyLinkedList<T> list) {
- this.length = list.size;
- this.list = list;
- this.itr = list.tail;
- }
-
- @Override
- public boolean hasNext() {
- return itr != null;
- }
-
- @Override
- public T next() {
- if (length != list.size) {
- throw new ConcurrentModificationException();
- }
- T next = itr.value;
- itr = itr.next;
- return next;
- }
-
- @Override
- public void remove() {
- throw new UnsupportedOperationException();
- }
-
- }
-
- public T first() {
- return tail == null ? null : tail.getValue();
- }
-
- public T last() {
- return head == null ? null : head.getValue();
- }
+
public ListNode2<T> head() {
return head;
@@ -194,13 +147,4 @@ public class DoublyLinkedList<T> implements Iterable<T> {
return size == 0;
}
- @SuppressWarnings("unchecked")
- public T[] toArray() {
- T[] a = (T[]) new Object[size];
- int i = 0;
- for (T v : this) {
- a[i++] = v;
- }
- return a;
- }
}
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/64a1fcb6/core-common/src/main/java/org/apache/kylin/common/topn/TopNCounter.java
----------------------------------------------------------------------
diff --git a/core-common/src/main/java/org/apache/kylin/common/topn/TopNCounter.java b/core-common/src/main/java/org/apache/kylin/common/topn/TopNCounter.java
index 593058b..1856010 100644
--- a/core-common/src/main/java/org/apache/kylin/common/topn/TopNCounter.java
+++ b/core-common/src/main/java/org/apache/kylin/common/topn/TopNCounter.java
@@ -182,18 +182,17 @@ public class TopNCounter<T> implements ITopK<T>, Iterable<Counter<T>> {
return sb.toString();
}
- public void fromExternal(int size, double[] counters, List<T> items) {
- this.counterList = new DoublyLinkedList<Counter<T>>();
-
- this.counterMap = new HashMap<T, ListNode2<Counter<T>>>(size);
-
- for (int i = 0; i < size; i++) {
- Counter<T> c = new Counter<T>();
- c.count = counters[i];
- c.item = items.get(i);
- ListNode2<Counter<T>> node = counterList.add(c);
- counterMap.put(c.item, node);
- }
+ /**
+ * Put element to the head position;
+ * The consumer should call this method with count in ascending way; the item will be directly put to the head of the list, without comparison for best performance;
+ * @param item
+ * @param count
+ */
+ public void offerToHead(T item, double count) {
+ Counter<T> c = new Counter<T>(item);
+ c.count = count;
+ ListNode2<Counter<T>> node = counterList.add(c);
+ counterMap.put(c.item, node);
}
/**
@@ -246,12 +245,12 @@ public class TopNCounter<T> implements ITopK<T>, Iterable<Counter<T>> {
assert newCapacity > 0;
this.capacity = newCapacity;
if (newCapacity < this.size()) {
- ListNode2<Counter<T>> tail = counterList.tail;
+ ListNode2<Counter<T>> tail = counterList.tail();
while (tail != null && this.size() > newCapacity) {
- Counter<T> bucket = counterList.tail.getValue();
+ Counter<T> bucket = tail.getValue();
this.counterMap.remove(bucket.getItem());
this.counterList.remove(tail);
- tail = this.counterList.tail;
+ tail = this.counterList.tail();
}
}
@@ -271,6 +270,7 @@ public class TopNCounter<T> implements ITopK<T>, Iterable<Counter<T>> {
index++;
}
+ assert index == size();
return counters;
}
@@ -285,6 +285,7 @@ public class TopNCounter<T> implements ITopK<T>, Iterable<Counter<T>> {
items.add(b.item);
}
+ assert items.size() == this.size();
return items;
}
@@ -294,12 +295,15 @@ public class TopNCounter<T> implements ITopK<T>, Iterable<Counter<T>> {
return new TopNCounterIterator();
}
+ /**
+ * Iterator from the tail (smallest) to head (biggest);
+ */
private class TopNCounterIterator implements Iterator {
private ListNode2<Counter<T>> currentBNode;
private TopNCounterIterator() {
- currentBNode = counterList.head();
+ currentBNode = counterList.tail();
}
@Override
@@ -311,7 +315,7 @@ public class TopNCounter<T> implements ITopK<T>, Iterable<Counter<T>> {
@Override
public Counter<T> next() {
Counter<T> counter = currentBNode.getValue();
- currentBNode = currentBNode.getPrev();
+ currentBNode = currentBNode.getNext();
return counter;
}
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/64a1fcb6/core-common/src/test/java/org/apache/kylin/common/topn/TopNCounterTest.java
----------------------------------------------------------------------
diff --git a/core-common/src/test/java/org/apache/kylin/common/topn/TopNCounterTest.java b/core-common/src/test/java/org/apache/kylin/common/topn/TopNCounterTest.java
index 560f32f..a6aa610 100644
--- a/core-common/src/test/java/org/apache/kylin/common/topn/TopNCounterTest.java
+++ b/core-common/src/test/java/org/apache/kylin/common/topn/TopNCounterTest.java
@@ -165,7 +165,7 @@ public class TopNCounterTest {
if (consumers.length == 1)
return consumers;
- TopNCounterTest.SpaceSavingConsumer merged = new TopNCounterTest.SpaceSavingConsumer(Integer.MAX_VALUE);
+ TopNCounterTest.SpaceSavingConsumer merged = new TopNCounterTest.SpaceSavingConsumer(TOP_K * SPACE_SAVING_ROOM);
for (int i=0, n=consumers.length; i<n; i++) {
merged.vs.merge(consumers[i].vs);
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/64a1fcb6/core-metadata/src/main/java/org/apache/kylin/metadata/measure/TopNAggregator.java
----------------------------------------------------------------------
diff --git a/core-metadata/src/main/java/org/apache/kylin/metadata/measure/TopNAggregator.java b/core-metadata/src/main/java/org/apache/kylin/metadata/measure/TopNAggregator.java
index 0de5fe8..9567fe6 100644
--- a/core-metadata/src/main/java/org/apache/kylin/metadata/measure/TopNAggregator.java
+++ b/core-metadata/src/main/java/org/apache/kylin/metadata/measure/TopNAggregator.java
@@ -37,8 +37,8 @@ public class TopNAggregator extends MeasureAggregator<TopNCounter<ByteArray>> {
@Override
public void aggregate(TopNCounter<ByteArray> value) {
if (sum == null) {
- sum = new TopNCounter<ByteArray>(Integer.MAX_VALUE);
capacity = value.getCapacity();
+ sum = new TopNCounter<ByteArray>(capacity);
}
sum.merge(value);
@@ -47,13 +47,13 @@ public class TopNAggregator extends MeasureAggregator<TopNCounter<ByteArray>> {
@Override
public TopNCounter getState() {
- sum.retain(capacity);
+ //sum.retain(capacity);
return sum;
}
@Override
public int getMemBytesEstimate() {
- return 8 * capacity;
+ return 8 * capacity / 4;
}
}
http://git-wip-us.apache.org/repos/asf/incubator-kylin/blob/64a1fcb6/core-metadata/src/main/java/org/apache/kylin/metadata/measure/serializer/TopNCounterSerializer.java
----------------------------------------------------------------------
diff --git a/core-metadata/src/main/java/org/apache/kylin/metadata/measure/serializer/TopNCounterSerializer.java b/core-metadata/src/main/java/org/apache/kylin/metadata/measure/serializer/TopNCounterSerializer.java
index 56ed85d..f96dd00 100644
--- a/core-metadata/src/main/java/org/apache/kylin/metadata/measure/serializer/TopNCounterSerializer.java
+++ b/core-metadata/src/main/java/org/apache/kylin/metadata/measure/serializer/TopNCounterSerializer.java
@@ -18,7 +18,7 @@
package org.apache.kylin.metadata.measure.serializer;
-import com.google.common.collect.Lists;
+import org.apache.kylin.common.topn.Counter;
import org.apache.kylin.common.topn.DoubleDeltaSerializer;
import org.apache.kylin.common.topn.TopNCounter;
import org.apache.kylin.common.util.ByteArray;
@@ -26,6 +26,7 @@ import org.apache.kylin.common.util.BytesUtil;
import org.apache.kylin.metadata.model.DataType;
import java.nio.ByteBuffer;
+import java.util.Iterator;
import java.util.List;
/**
@@ -76,15 +77,15 @@ public class TopNCounterSerializer extends DataTypeSerializer<TopNCounter<ByteAr
@Override
public void serialize(TopNCounter<ByteArray> value, ByteBuffer out) {
double[] counters = value.getCounters();
- List<ByteArray> items = value.getItems();
- int keyLength = items.size() > 0 ? items.get(0).length() : 0;
+ List<ByteArray> peek = value.peek(1);
+ int keyLength = peek.size() > 0 ? peek.get(0).length() : 0;
out.putInt(value.getCapacity());
out.putInt(value.size());
out.putInt(keyLength);
dds.serialize(counters, out);
-
- for (ByteArray item : items) {
- out.put(item.array());
+ Iterator<Counter<ByteArray>> iterator = value.iterator();
+ while(iterator.hasNext()) {
+ out.put(iterator.next().getItem().array());
}
}
@@ -94,16 +95,15 @@ public class TopNCounterSerializer extends DataTypeSerializer<TopNCounter<ByteAr
int size = in.getInt();
int keyLength = in.getInt();
double[] counters = dds.deserialize(in);
- List<ByteArray> items = Lists.newArrayList();
-
+
+ TopNCounter<ByteArray> counter = new TopNCounter<ByteArray>(capacity);
+ ByteArray byteArray;
for(int i=0; i<size; i++) {
- ByteArray byteArray = new ByteArray(keyLength);
+ byteArray = new ByteArray(keyLength);
in.get(byteArray.array());
- items.add(byteArray);
+ counter.offerToHead(byteArray, counters[i]);
}
- TopNCounter<ByteArray> counter = new TopNCounter<ByteArray>(capacity);
- counter.fromExternal(size, counters, items);
return counter;
}
}