Qt Forum

    • Login
    • Search
    • Categories
    • Recent
    • Tags
    • Popular
    • Users
    • Groups
    • Search
    • Unsolved

    Update: Forum Guidelines & Code of Conduct

    Unsolved An interesting technical article

    The Lounge
    5
    11
    488
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • JonB
      JonB last edited by JonB

      I happenstanced across https://thesmithfam.org/blog/2011/02/12/when-faster-is-actually-slower/.

      A read for you algorithmers. I found it interesting [including the comments at the end] (and the blog is well written/presented) :)

      1 Reply Last reply Reply Quote 0
      • SGaist
        SGaist Lifetime Qt Champion last edited by

        Hi,

        Interesting article indeed !

        There's also this benchmark from Woboq that is more recent.

        One thing to take into account though, there's a new implementation in the works for Qt 6.

        Interested in AI ? www.idiap.ch
        Please read the Qt Code of Conduct - https://forum.qt.io/topic/113070/qt-code-of-conduct

        JonB 1 Reply Last reply Reply Quote 3
        • JonB
          JonB @SGaist last edited by

          @SGaist
          Nice to see someone else is as interested-geeky as I am! (No offence intended :) )

          1 Reply Last reply Reply Quote 0
          • JKSH
            JKSH Moderators last edited by

            Thanks for sharing!

            Dave Smith's blog refers to the Qt docs' claim that QHash "provides significantly faster lookups" than QMap, but showed that for long QString keys, QHash is actually slower than QMap with his dataset.

            First, it helps to better understand the meaning of Big-O notation. Big-O describes the what happens when the dataset size tends towards inifinity. QHash's complexity for look-up and insertion are both amortised O(1), which means that on average (ignoring rare expensive events like memory reallocation), the time to look-up/insert data in a tiny QHash is the same as an infinitely huge QHash. It makes no claim on the actual speed, and it doesn't really allow us to compare the speed of 2 containers with a particular dataset.

            QHash's look-up complexity is amortized O(1) while QMap's look-up complexity is O(log n). So, we must understand this to mean that an infinitely huge QHash is significantly faster to look-up than an infinitely huge QMap. This doesn't knowledge doesn't tell us anything about a small QHash vs a small QMap. It also doesn't tell us where the crossover point is between "huge" and "small".

            Woboq's blog that @SGaist linked to contains a good graph which shows the crossover occuring:

            Benchmark of QMap, QHash, std::map, and std::unordered_map

            Depending on the types of keys used, the crossover point will shift, as David Smith has found.

            Nice to see someone else is as interested-geeky as I am!

            Geek is good. Geeks and nerds will rule the world one day

            Here's a must-read for all geeks interested in the internal workings of Qt containers: https://marcmutz.wordpress.com/effective-qt/containers/

            Qt Doc Search for browsers: forum.qt.io/topic/35616/web-browser-extension-for-improved-doc-searches

            JonB 1 Reply Last reply Reply Quote 3
            • JonB
              JonB @JKSH last edited by

              @JKSH
              Thank you for further enlightenment.

              I have heard that geeky is attractive for young ladies these days, but haven't seen any empirical evidence at all for this in my case ;-)

              One thing struck me in the first comment in the article:

              But QHash will be faster on VERY huge data sets, because if you have
              2^100 items or more (well, that should not be so often…) then QHash is faster again.

              I believe that 2 ^ 100 is more than the number of atoms in the Universe --- it's good to know that if we want to locate a single atom we can look for it very quickly :) I'm wondering what datasets we use of this size? More to the point, how are we going to have a dataset/QHash/QMap for this number of elements on a 64-bit machine?

              JKSH 1 Reply Last reply Reply Quote 0
              • fcarney
                fcarney last edited by fcarney

                @JonB said in An interesting technical article:

                I have heard that geeky is attractive for young ladies these days

                Was at the bank. Teller asked me what my profession was. When I said I was a computer programmer she started asking more personal questions. I headed it off, but she is in her twenties and I am in my forties. Not sure what to think of that interaction.

                C++ is a perfectly valid school of magic.

                JonB JKSH 2 Replies Last reply Reply Quote 0
                • JonB
                  JonB @fcarney last edited by JonB

                  @fcarney
                  Well, obviously we must not get serious/personal here, just lighthearted. You're 40-geek, she's 20, my thought: she'd like to get hold of your bank account password ;-)

                  1 Reply Last reply Reply Quote 0
                  • JKSH
                    JKSH Moderators @JonB last edited by JKSH

                    @JonB said in An interesting technical article:

                    I believe that 2 ^ 100 is more than the number of atoms in the Universe... I'm wondering what datasets we use of this size? More to the point, how are we going to have a dataset/QHash/QMap for this number of elements on a 64-bit machine?

                    We can't.

                    2^100 32-bit integers requires 5 x 10^18 TB (or 5 x 10^6 yottabytes) of storage, at the very minimum. More if we use non-contiguous memory.

                    "Yotta-" is the largest SI prefix we currently have; there's no term to describe a multiplier bigger than that.

                    Qt Doc Search for browsers: forum.qt.io/topic/35616/web-browser-extension-for-improved-doc-searches

                    JonB 1 Reply Last reply Reply Quote 0
                    • JKSH
                      JKSH Moderators @fcarney last edited by

                      @fcarney said in An interesting technical article:

                      Not sure what to think of that interaction.

                      It could be an overly-friendly lass who simply needs a bit more professionalism/maturity when it comes to building rapport with customers.

                      It could be a case of a modern-day Beatlemania or Belieberism where rationality evaporates in the presence of a celebrity. (Programmer is the new Rock Star)

                      It could be a gold digger putting out feelers, as @JonB implied.

                      Whatever the case, it sounds like you handled the situation well!

                      Qt Doc Search for browsers: forum.qt.io/topic/35616/web-browser-extension-for-improved-doc-searches

                      1 Reply Last reply Reply Quote 0
                      • JonB
                        JonB @JKSH last edited by JonB

                        @JKSH

                        2^100 32-bit integers requires 5 x 10^18 TB

                        Yes, my point was I didn't think that poster's analysis could relate to a real, current situation. Nonetheless, I suppose his mathematical analysis about the behaviour would still hold.

                        You've also shed some light on something I didn't understand. You're saying 2^100 is somewhere near 10^18 (I know that you're talking about different base units, so I ought to divide by a bit, but still...) Now, I thought my guess of 2^100 sounded a bit low for the supposed number of atoms in the Universe. I have a feeling that figure is something like 10^76 or some such. So 10^n is a lot bigger than 2^n, right? I thought in X^y that the magnitude of y was much more significant than the magnitude of X? I know I could work it out, but how do you figure what m is in 10^m == 2^n?

                        [Please don't tell me it's m == n/5, that would be too obvious...? Hang on: since 10 == 2^3.something, that means m == n/3.something, so I divide/multiply the exponent by the 3.something to convert between 10^m == 2^n, is that it?! 10^100 == 2^(300+something), 2^100 =~ 10^30-ish?]

                        It could be a gold digger putting out feelers, as @JonB implied.

                        Hang on, my reply was intended purely frivolously! I have no reason to imply that the person in question wasn't genuinely interested in the OP. Besides, gold-digging into programmer-geeks is probably not lucrative as we are underpaid & undervalues (speaking for myself) :)

                        Whatever the case, it sounds like you handled the situation well!

                        I'd have asked for her phone number ;-)

                        In the modern world perhaps we are not allowed to jest about these things, so we'd better stick to the question about exponents above....

                        1 Reply Last reply Reply Quote 0
                        • M
                          Michale Banned last edited by

                          This post is deleted!
                          1 Reply Last reply Reply Quote 0
                          • First post
                            Last post