You are viewing a plain text version of this content. The canonical link for it is here.
Posted to hdfs-issues@hadoop.apache.org by "Andrew Wang (JIRA)" <ji...@apache.org> on 2012/09/26 00:42:08 UTC
[jira] [Created] (HDFS-3976) SampleQuantiles#query is O(N^2)
instead of O(N)
Andrew Wang created HDFS-3976:
---------------------------------
Summary: 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
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)
Posted by "Hadoop QA (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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
[jira] [Commented] (HDFS-3976) SampleQuantiles#query is O(N^2)
instead of O(N)
Posted by "Todd Lipcon (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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] [Updated] (HDFS-3976) SampleQuantiles#query is O(N^2)
instead of O(N)
Posted by "Andrew Wang (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Andrew Wang updated HDFS-3976:
------------------------------
Target Version/s: 2.0.3-alpha
Status: Patch Available (was: Open)
> 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)
Posted by "Andrew Wang (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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] [Updated] (HDFS-3976) SampleQuantiles#query is O(N^2)
instead of O(N)
Posted by "Andrew Wang (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Andrew Wang updated HDFS-3976:
------------------------------
Attachment: hdfs-3976-1.patch
Small patch. TestMutableMetrics still passes, so I think correctness is fine.
I can run a real performance test if people want to see that too, but it seems strictly better to me.
> 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)
Posted by "Aaron T. Myers (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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)
Posted by "Todd Lipcon (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HDFS-3976?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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