public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "pinskia at gcc dot gnu dot org" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort Date: Sat, 07 Feb 2004 08:37:00 -0000 [thread overview] Message-ID: <20040207083719.15951.qmail@sources.redhat.com> (raw) In-Reply-To: <20040207080740.14061.ctsa@u.washington.edu> ------- Additional Comments From pinskia at gcc dot gnu dot org 2004-02-07 08:37 ------- I know that this is a performance bug but note the C++ standard says this: Complexity: Approximately N log N (where N ==last-first) comparisons on the "average". If the worst case behavior is important stable_sort()(25.3.1.2) or partial_sort()(25.3.1.3) should be used. And note that stable_sort is faster than both quick_sort and std::sort in your case which you give. Also note that the only complexity is needed to O(N log N) compares on average and so this is not comforming issue. Confirmed that std::sort is much slower than quick_sort and std::stable_sort in the case you gave, note it might be faster in other cases though. -- What |Removed |Added ---------------------------------------------------------------------------- Severity|normal |enhancement Status|UNCONFIRMED |NEW Ever Confirmed| |1 Known to fail| |tree-ssa Last reconfirmed|0000-00-00 00:00:00 |2004-02-07 08:37:18 date| | http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14061
next prev parent reply other threads:[~2004-02-07 8:37 UTC|newest] Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top 2004-02-07 8:07 [Bug libstdc++/14061] New: " ctsa at u dot washington dot edu 2004-02-07 8:37 ` pinskia at gcc dot gnu dot org [this message] 2004-02-07 16:03 ` [Bug libstdc++/14061] " pcarlini at suse dot de 2004-02-07 22:09 ` ctsa at u dot washington dot edu [not found] <bug-14061-4@http.gcc.gnu.org/bugzilla/> 2015-03-27 18:10 ` jdcoxm3 at hotmail dot com
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20040207083719.15951.qmail@sources.redhat.com \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).