[jira] [Commented] (HDFS-3976) SampleQuantiles#query is O(N^2) instead of O(N)
[ https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13466054#comment-13466054 ] Aaron T. Myers commented on HDFS-3976: -- The patch looks good to me as well. Committing momentarily. SampleQuantiles#query is O(N^2) instead of O(N) --- Key: HDFS-3976 URL: https://issues.apache.org/jira/browse/HDFS-3976 Project: Hadoop HDFS Issue Type: Improvement Affects Versions: 2.0.3-alpha Reporter: Andrew Wang Assignee: Andrew Wang Priority: Minor Attachments: hdfs-3976-1.patch SampleQuantiles#query() does O(N) calls LinkedList#get() in a loop, rather than using an iterator. This makes query O(N^2), rather than O(N). -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HDFS-3976) SampleQuantiles#query is O(N^2) instead of O(N)
[
https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13463330#comment-13463330
]
Todd Lipcon commented on HDFS-3976:
---
While you're at it, why not get rid of size() and numeric iteration too?
eg:
{code}
for (SampleItem item : samples) {
if (prev == null) {
prev = item;
continue;
}
...
prev = item;
}
{code}
SampleQuantiles#query is O(N^2) instead of O(N)
---
Key: HDFS-3976
URL: https://issues.apache.org/jira/browse/HDFS-3976
Project: Hadoop HDFS
Issue Type: Improvement
Affects Versions: 2.0.3-alpha
Reporter: Andrew Wang
Assignee: Andrew Wang
Priority: Minor
Attachments: hdfs-3976-1.patch
SampleQuantiles#query() does O(N) calls LinkedList#get() in a loop, rather
than using an iterator. This makes query O(N^2), rather than O(N).
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HDFS-3976) SampleQuantiles#query is O(N^2) instead of O(N)
[
https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13463349#comment-13463349
]
Andrew Wang commented on HDFS-3976:
---
I suppose, though I think we need to keep a counter to pass to
{{allowableError()}}. Would you still prefer to see the foreach-style syntax?
SampleQuantiles#query is O(N^2) instead of O(N)
---
Key: HDFS-3976
URL: https://issues.apache.org/jira/browse/HDFS-3976
Project: Hadoop HDFS
Issue Type: Improvement
Affects Versions: 2.0.3-alpha
Reporter: Andrew Wang
Assignee: Andrew Wang
Priority: Minor
Attachments: hdfs-3976-1.patch
SampleQuantiles#query() does O(N) calls LinkedList#get() in a loop, rather
than using an iterator. This makes query O(N^2), rather than O(N).
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HDFS-3976) SampleQuantiles#query is O(N^2) instead of O(N)
[ https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13463358#comment-13463358 ] Todd Lipcon commented on HDFS-3976: --- I guess what you're doing now makes more sense then, sorry I missed that. +1 pending Jenkins SampleQuantiles#query is O(N^2) instead of O(N) --- Key: HDFS-3976 URL: https://issues.apache.org/jira/browse/HDFS-3976 Project: Hadoop HDFS Issue Type: Improvement Affects Versions: 2.0.3-alpha Reporter: Andrew Wang Assignee: Andrew Wang Priority: Minor Attachments: hdfs-3976-1.patch SampleQuantiles#query() does O(N) calls LinkedList#get() in a loop, rather than using an iterator. This makes query O(N^2), rather than O(N). -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HDFS-3976) SampleQuantiles#query is O(N^2) instead of O(N)
[
https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13463460#comment-13463460
]
Hadoop QA commented on HDFS-3976:
-
{color:red}-1 overall{color}. Here are the results of testing the latest
attachment
http://issues.apache.org/jira/secure/attachment/12546602/hdfs-3976-1.patch
against trunk revision .
{color:green}+1 @author{color}. The patch does not contain any @author
tags.
{color:red}-1 tests included{color}. The patch doesn't appear to include
any new or modified tests.
Please justify why no new tests are needed for this
patch.
Also please list what manual steps were performed to
verify this patch.
{color:green}+1 javac{color}. The applied patch does not increase the
total number of javac compiler warnings.
{color:green}+1 javadoc{color}. The javadoc tool did not generate any
warning messages.
{color:green}+1 eclipse:eclipse{color}. The patch built with
eclipse:eclipse.
{color:green}+1 findbugs{color}. The patch does not introduce any new
Findbugs (version 1.3.9) warnings.
{color:green}+1 release audit{color}. The applied patch does not increase
the total number of release audit warnings.
{color:red}-1 core tests{color}. The patch failed these unit tests in
hadoop-common-project/hadoop-common:
org.apache.hadoop.ha.TestZKFailoverController
{color:green}+1 contrib tests{color}. The patch passed contrib unit tests.
Test results:
https://builds.apache.org/job/PreCommit-HDFS-Build/3236//testReport/
Console output: https://builds.apache.org/job/PreCommit-HDFS-Build/3236//console
This message is automatically generated.
SampleQuantiles#query is O(N^2) instead of O(N)
---
Key: HDFS-3976
URL: https://issues.apache.org/jira/browse/HDFS-3976
Project: Hadoop HDFS
Issue Type: Improvement
Affects Versions: 2.0.3-alpha
Reporter: Andrew Wang
Assignee: Andrew Wang
Priority: Minor
Attachments: hdfs-3976-1.patch
SampleQuantiles#query() does O(N) calls LinkedList#get() in a loop, rather
than using an iterator. This makes query O(N^2), rather than O(N).
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
