Skip to content

Commit d4d4a12

Browse files
liyafan82emkornfield
liyafan82
authored and
emkornfield
committed
ARROW-6334: [Java] Improve the dictionary builder API to return the position of the value in the dictionary
This is an improvement of the addValue method. Previously, the method returns a boolean, indicating if the value has been successfully added to the dictionary. After the change, the method returns an integer, which is the position of the value in the dictionary. The purpose of this change: 1. the dictionary position contains more information, compared with a boolean indicating if the value is added successfully. 2. this information about the index in the dictionary can be useful, for example, to collect statistics about the dictionary. With the dictionary position, the information about if a value has been added can be easily determined. Closes apache#5177 from liyafan82/fly_0823_build and squashes the following commits: d45d0e9 <liyafan82> Improve the dictionary builder API to return the position of the value in the dictionary Authored-by: liyafan82 <fan_li_ya@foxmail.com> Signed-off-by: Micah Kornfield <emkornfield@gmail.com>
1 parent b4eeab0 commit d4d4a12

2 files changed

Lines changed: 25 additions & 21 deletions

File tree

‎java/algorithm/src/main/java/org/apache/arrow/algorithm/dictionary/HashTableBasedDictionaryBuilder.java‎

Lines changed: 10 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -132,29 +132,29 @@ public V getDictionary() {
132132
* @return the number of values actually added to the dictionary.
133133
*/
134134
public int addValues(V targetVector) {
135-
int ret = 0;
135+
int oldDictSize = dictionary.getValueCount();
136136
for (int i = 0; i < targetVector.getValueCount(); i++) {
137137
if (!encodeNull && targetVector.isNull(i)) {
138138
continue;
139139
}
140-
if (addValue(targetVector, i)) {
141-
ret += 1;
142-
}
140+
addValue(targetVector, i);
143141
}
144-
return ret;
142+
143+
return dictionary.getValueCount() - oldDictSize;
145144
}
146145

147146
/**
148147
* Try to add an element from the target vector to the dictionary.
149148
*
150149
* @param targetVector the target vector containing new element.
151150
* @param targetIndex the index of the new element in the target vector.
152-
* @return true if the element is added to the dictionary, and false otherwise.
151+
* @return the index of the new element in the dictionary.
153152
*/
154-
public boolean addValue(V targetVector, int targetIndex) {
153+
public int addValue(V targetVector, int targetIndex) {
155154
targetVector.getDataPointer(targetIndex, nextPointer);
156155

157-
if (!hashMap.containsKey(nextPointer)) {
156+
Integer index = hashMap.get(nextPointer);
157+
if (index == null) {
158158
// a new dictionary element is found
159159

160160
// insert it to the dictionary
@@ -167,8 +167,8 @@ public boolean addValue(V targetVector, int targetIndex) {
167167
hashMap.put(nextPointer, dictSize);
168168
nextPointer = new ArrowBufPointer(hasher);
169169

170-
return true;
170+
return dictSize;
171171
}
172-
return false;
172+
return index;
173173
}
174174
}

‎java/algorithm/src/main/java/org/apache/arrow/algorithm/dictionary/SearchTreeBasedDictionaryBuilder.java‎

Lines changed: 15 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -116,35 +116,39 @@ public V getDictionary() {
116116
* @return the number of values actually added to the dictionary.
117117
*/
118118
public int addValues(V targetVector) {
119-
int ret = 0;
119+
int oldDictSize = dictionary.getValueCount();
120120
for (int i = 0; i < targetVector.getValueCount(); i++) {
121121
if (!encodeNull && targetVector.isNull(i)) {
122122
continue;
123123
}
124-
if (addValue(targetVector, i)) {
125-
dictionary.setValueCount(dictionary.getValueCount() + 1);
126-
ret += 1;
127-
}
124+
addValue(targetVector, i);
128125
}
129-
return ret;
126+
return dictionary.getValueCount() - oldDictSize;
130127
}
131128

132129
/**
133130
* Try to add an element from the target vector to the dictionary.
134131
* @param targetVector the target vector containing new element.
135132
* @param targetIndex the index of the new element in the target vector.
136-
* @return true if the element is added to the dictionary, and false otherwise.
133+
* @return the index of the new element in the dictionary.
137134
*/
138-
public boolean addValue(V targetVector, int targetIndex) {
135+
public int addValue(V targetVector, int targetIndex) {
139136
// first copy the value to the end of the dictionary
140137
int dictSize = dictionary.getValueCount();
141138
dictionary.copyFromSafe(targetIndex, dictSize, targetVector);
142139

143140
// try to add the value to the dictionary,
144141
// if an equal element does not exist.
145-
// this operation can be done in O(logn) time.
146-
boolean ret = searchTree.add(dictSize);
147-
return ret;
142+
// this operation can be done in O(log(n)) time.
143+
if (searchTree.add(dictSize)) {
144+
// the element is successfully added
145+
dictionary.setValueCount(dictSize + 1);
146+
return dictSize;
147+
} else {
148+
// the element is already in the dictionary
149+
// find its index in O(log(n)) time.
150+
return searchTree.ceiling(dictSize);
151+
}
148152
}
149153

150154
/**

0 commit comments

Comments
 (0)