C++ ~13ms with sort on frequency array


  • 0
    M

    The first version of code below runs in ~ 13ms versus the shorter code further below that comes in at ~96ms.

            string frequencySort(string s)
            {
                struct freq
                {
                    char chr = 0;
                    int num = 0;
    
                    bool operator<(const freq& rhs) const
                    { return (num > rhs.num) || ((num == rhs.num) && (chr < rhs.chr)); }
                };
    
                freq freqs[128];
    
                for (auto ch : s) {
                    freqs[ch].chr = ch;
                    freqs[ch].num++;
                }
    
                sort(begin(freqs), end(freqs));
    
                int idx = 0;
                for(auto freq : freqs)
                {
                    while (freq.num-- > 0)
                        s[idx++] = freq.chr;
                }
    
                return s;
            }
    

    The cleaner version below runs slower -- maybe because of cache misses from random accesses to the frequency array?

            string frequencySort(string s)
            {
                int freqs[128] = { 0 };
                for (auto ch : s) freqs[ch]++;
    
                sort(
                    begin(s), end(s),
                    [&](char lhs, char rhs)
                    {
                        return 
                            (freqs[rhs] < freqs[lhs]) || 
                            (freqs[lhs] == freqs[rhs]) && (lhs < rhs);
                    });
    
                return s;
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.