You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@stdcxx.apache.org by "Anton Pevtsov (JIRA)" <ji...@apache.org> on 2006/02/07 11:00:00 UTC
[jira] Created: (STDCXX-138) Complexity tests are not strict enough
for some algorithms when the expected complexity is a function of the given
sequence length (not exact count)
Complexity tests are not strict enough for some algorithms when the expected complexity is a function of the given sequence length (not exact count)
----------------------------------------------------------------------------------------------------------------------------------------------------
Key: STDCXX-138
URL: http://issues.apache.org/jira/browse/STDCXX-138
Project: C++ Standard Library
Type: Improvement
Components: 25. Algorithms
Versions: 4.1.3
Environment: all
Reporter: Anton Pevtsov
Priority: Minor
Fix For: 4.1.4
Affects tests for sort, stable_sort, partial_sort, partial_sort_copy, nth_element, etc algorithms where the complexity is O(f(N)), where N is the length of the test sequence, f(N) - some function of N: log N, N log N, N.
It is necessary to investigate each algorithm to find the worst case for it and use the complexity on this worst sequence as the upper bound in tests. Currently "magic" coefficients are used.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (STDCXX-138) algorithms complexity tests not strict
enough
Posted by "Martin Sebor (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/STDCXX-138?page=all ]
Martin Sebor updated STDCXX-138:
--------------------------------
Fix Version: 4.2
(was: 4.1.4)
> algorithms complexity tests not strict enough
> ---------------------------------------------
>
> Key: STDCXX-138
> URL: http://issues.apache.org/jira/browse/STDCXX-138
> Project: C++ Standard Library
> Type: Improvement
> Components: Tests
> Versions: 4.1.3
> Environment: all
> Reporter: Anton Pevtsov
> Priority: Minor
> Fix For: 4.2
>
> Affects tests for sort, stable_sort, partial_sort, partial_sort_copy, nth_element, etc algorithms where the complexity is O(f(N)), where N is the length of the test sequence, f(N) - some function of N: log N, N log N, N.
> It is necessary to investigate each algorithm to find the worst case for it and use the complexity on this worst sequence as the upper bound in tests. Currently "magic" coefficients are used.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Commented: (STDCXX-138) Complexity tests are not strict
enough for some algorithms when the expected complexity is a function of
the given sequence length (not exact count)
Posted by "Martin Sebor (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/STDCXX-138?page=comments#action_12365508 ]
Martin Sebor commented on STDCXX-138:
-------------------------------------
See this thread for background:
http://mail-archives.apache.org/mod_mbox/incubator-stdcxx-dev/200602.mbox/%3c43E80945.4060503@roguewave.com%3e
> Complexity tests are not strict enough for some algorithms when the expected complexity is a function of the given sequence length (not exact count)
> ----------------------------------------------------------------------------------------------------------------------------------------------------
>
> Key: STDCXX-138
> URL: http://issues.apache.org/jira/browse/STDCXX-138
> Project: C++ Standard Library
> Type: Improvement
> Components: 25. Algorithms
> Versions: 4.1.3
> Environment: all
> Reporter: Anton Pevtsov
> Priority: Minor
> Fix For: 4.1.4
>
> Affects tests for sort, stable_sort, partial_sort, partial_sort_copy, nth_element, etc algorithms where the complexity is O(f(N)), where N is the length of the test sequence, f(N) - some function of N: log N, N log N, N.
> It is necessary to investigate each algorithm to find the worst case for it and use the complexity on this worst sequence as the upper bound in tests. Currently "magic" coefficients are used.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (STDCXX-138) algorithms complexity tests not strict
enough
Posted by "Martin Sebor (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/STDCXX-138?page=all ]
Martin Sebor updated STDCXX-138:
--------------------------------
Component: Tests
(was: 25. Algorithms)
Summary: algorithms complexity tests not strict enough (was: Complexity tests are not strict enough for some algorithms when the expected complexity is a function of the given sequence length (not exact count))
Abbreviated long subject line and assigned to the right component.
> algorithms complexity tests not strict enough
> ---------------------------------------------
>
> Key: STDCXX-138
> URL: http://issues.apache.org/jira/browse/STDCXX-138
> Project: C++ Standard Library
> Type: Improvement
> Components: Tests
> Versions: 4.1.3
> Environment: all
> Reporter: Anton Pevtsov
> Priority: Minor
> Fix For: 4.1.4
>
> Affects tests for sort, stable_sort, partial_sort, partial_sort_copy, nth_element, etc algorithms where the complexity is O(f(N)), where N is the length of the test sequence, f(N) - some function of N: log N, N log N, N.
> It is necessary to investigate each algorithm to find the worst case for it and use the complexity on this worst sequence as the upper bound in tests. Currently "magic" coefficients are used.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Updated: (STDCXX-138) algorithms complexity tests not strict
enough
Posted by "Martin Sebor (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/STDCXX-138?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Martin Sebor updated STDCXX-138:
--------------------------------
Affects Version/s: 4.1.4
Fix Version/s: (was: 4.2)
4.2.1
Added 4.1.4 to the list of affected versions and rescheduled for 4.2.1.
> algorithms complexity tests not strict enough
> ---------------------------------------------
>
> Key: STDCXX-138
> URL: https://issues.apache.org/jira/browse/STDCXX-138
> Project: C++ Standard Library
> Issue Type: Improvement
> Components: Tests
> Affects Versions: 4.1.3, 4.1.4
> Environment: all
> Reporter: Anton Pevtsov
> Priority: Minor
> Fix For: 4.2.1
>
>
> Affects tests for sort, stable_sort, partial_sort, partial_sort_copy, nth_element, etc algorithms where the complexity is O(f(N)), where N is the length of the test sequence, f(N) - some function of N: log N, N log N, N.
> It is necessary to investigate each algorithm to find the worst case for it and use the complexity on this worst sequence as the upper bound in tests. Currently "magic" coefficients are used.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (STDCXX-138) algorithms complexity tests not strict
enough
Posted by "Martin Sebor (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/STDCXX-138?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Martin Sebor updated STDCXX-138:
--------------------------------
Affects Version/s: 4.2.0
Fix Version/s: (was: 4.2.1)
4.3
Like STDCXX-139, this also seems too big to do in the 4.2.1 timeframe. Deferred.
> algorithms complexity tests not strict enough
> ---------------------------------------------
>
> Key: STDCXX-138
> URL: https://issues.apache.org/jira/browse/STDCXX-138
> Project: C++ Standard Library
> Issue Type: Improvement
> Components: Tests
> Affects Versions: 4.1.3, 4.1.4, 4.2.0
> Environment: all
> Reporter: Anton Pevtsov
> Priority: Minor
> Fix For: 4.3
>
>
> Affects tests for sort, stable_sort, partial_sort, partial_sort_copy, nth_element, etc algorithms where the complexity is O(f(N)), where N is the length of the test sequence, f(N) - some function of N: log N, N log N, N.
> It is necessary to investigate each algorithm to find the worst case for it and use the complexity on this worst sequence as the upper bound in tests. Currently "magic" coefficients are used.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.