You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@tajo.apache.org by "ASF GitHub Bot (JIRA)" <ji...@apache.org> on 2016/02/15 07:13:18 UTC
[jira] [Commented] (TAJO-2059) Binary search in BST reader does
compare too frequently
[ https://issues.apache.org/jira/browse/TAJO-2059?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15146948#comment-15146948 ]
ASF GitHub Bot commented on TAJO-2059:
--------------------------------------
Github user jihoonson commented on a diff in the pull request:
https://github.com/apache/tajo/pull/945#discussion_r52862691
--- Diff: tajo-storage/tajo-storage-hdfs/src/main/java/org/apache/tajo/storage/index/bst/BSTIndex.java ---
@@ -794,42 +794,79 @@ private int binarySearch(Tuple[] arr, Tuple key, int startPos, int endPos) {
int offset = -1;
int start = startPos;
int end = endPos;
+ int prevCenter = -1;
//http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6412541
int centerPos = (start + end) >>> 1;
if (arr.length == 0) {
LOG.error("arr.length: 0, loadNum: " + loadNum + ", inited: " + inited.get());
+ return -1;
}
+
+ correctable = false;
+ if (arr.length == 1) {
+ int comp = comparator.compare(arr[0], key);
+
+ if (comp < 0) {
+ return 0;
+ } else if (comp > 0) {
+ return -1;
+ }
+
+ correctable = true;
+ return 0;
+ }
+
while (true) {
- if (comparator.compare(arr[centerPos], key) > 0) {
- if (centerPos == 0) {
- correctable = false;
- break;
- } else if (comparator.compare(arr[centerPos - 1], key) < 0) {
- correctable = false;
- offset = centerPos - 1;
+ if (end - start == 1) {
+ int comp;
+ // prevCenter should be either end or start
+ if (end == prevCenter) {
+ comp = comparator.compare(arr[start], key);
+
+ if (comp == 0) {
+ correctable = true;
+ offset = start;
+ } else if (comp < 0) {
+ offset = start;
+ }
break;
} else {
- end = centerPos;
- centerPos = (start + end) / 2;
- }
- } else if (comparator.compare(arr[centerPos], key) < 0) {
- if (centerPos == arr.length - 1) {
- correctable = false;
- offset = centerPos;
- break;
- } else if (comparator.compare(arr[centerPos + 1], key) > 0) {
- correctable = false;
- offset = centerPos;
+ if (end == arr.length) {
+ if (comparator.compare(arr[start], key) == 0) {
+ correctable = true;
+ }
+ offset = start;
+ break;
+ }
+
+ comp = comparator.compare(arr[end], key);
+ if (comp == 0) {
+ correctable = true;
+ offset = end;
+ } else if (comp > 0) {
+ offset = start;
+ }
break;
- } else {
- start = centerPos + 1;
- centerPos = (start + end) / 2;
}
- } else {
+ }
+
+ int compareResult = comparator.compare(arr[centerPos], key);
+
+ if (compareResult == 0) {
correctable = true;
offset = centerPos;
break;
+ } else {
+ prevCenter = centerPos;
+
+ if (compareResult > 0) {
+ end = centerPos;
+ } else {
+ start = centerPos;
+ }
+
+ centerPos = (start + end) / 2;
--- End diff --
This line also looks to be changed to ```centerPos = (start + end) >>> 1;```
> Binary search in BST reader does compare too frequently
> -------------------------------------------------------
>
> Key: TAJO-2059
> URL: https://issues.apache.org/jira/browse/TAJO-2059
> Project: Tajo
> Issue Type: Improvement
> Components: Storage
> Affects Versions: 0.11.0
> Reporter: Jongyoung Park
> Assignee: Jongyoung Park
>
> Current binary search logic do comparing twice each iteration.
> It should be refined.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)