1
\$\begingroup\$

Here is problem:
There is string (domain) divided by dots (like www.part1.partN.com)
Need to build reversed by dot string (like com.partN.part1.www)
Both strings are utf-8 encoded

My solution:

std::string reverseHost(const std::string& host)
{
    std::string ret;
    ret.reserve(host.size());

    size_t tail = host.size();
    size_t head = host.find_last_of('.');

    while (head != std::string::npos)
    {
        ret.append(host.c_str() + head + 1, tail - head - 1);
        ret += '.';

        tail = head;
        head = host.find_last_of('.', tail - 1);
    }

    ret.append(host.c_str(), tail);

    return ret;
}

Need to improve speed (or advice how to improve), raw memory and other tricks allowed. ty.

\$\endgroup\$
1
  • \$\begingroup\$ what if the input string is just a ".", should you handle such case? \$\endgroup\$
    – SPD
    Feb 14, 2020 at 15:46

2 Answers 2

3
\$\begingroup\$

You've misspelt std::size_t.

Apart from that, the code seems reasonably straightforward if you always need to return a copy.

A two-pass algorithm (reverse the whole string, then reverse each of the individual components) might be faster, because you can operate in-place, without having to create a new string. Of course, you'll only get the speed benefit if the caller doesn't need to retain the original (pass by value, and use std::move to control copying).

\$\endgroup\$
3
\$\begingroup\$

If you're using Boost, one readable solution is:

#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/classification.hpp>

std::string reverseHost(const std::string& host)
{
    std::vector<std::string> parts;
    boost::algorithm::split(parts, host, boost::is_any_of("."));
    std::reverse(parts.begin(), parts.end());

    return boost::algorithm::join(parts, ".");
}

In short, we split the input into parts using dot as a delimiter, reverse them, and join in reverse order.

However, this is not designed with performance in mind. A faster alternative is likely the following:

std::string reverseHost(const std::string& str)
{
    std::string rev(str.crbegin(), str.crend());
    const std::size_t len = rev.size();

    for (std::size_t j, i = 0; i < len; ++i)
    {
        j = i;

        while ((i < len) && (rev[i] != '.'))
            ++i;

        std::reverse(rev.begin() + j, rev.begin() + i);
    }

    return rev;
}
\$\endgroup\$
5
  • \$\begingroup\$ i've tested your solution 100 launches with 1m iterations each. your solution ~148 ms (per 1m) mine ~95 ms \$\endgroup\$
    – goldstar
    Feb 18, 2020 at 8:40
  • \$\begingroup\$ also boost is about ~700ms in same benchmark xD \$\endgroup\$
    – goldstar
    Feb 18, 2020 at 8:43
  • \$\begingroup\$ @goldstar I made a small optimization, but perhaps it won't matter much. A second step could be to try another method instead of std::reverse. \$\endgroup\$
    – Juho
    Feb 18, 2020 at 19:51
  • \$\begingroup\$ @goldstar: Is this function really a hotspot that needs such micro optimization? Unlikely; if not then go with the clearer solution. Which Juho has provided (the copy revered, then reverse each word) is the classic implementation. If this is the hot spot (you need the data to prove that), then go with your optimized version and add the extra documentation to make sure maintainers know that it needs to be optimized. But note the cost of this version can be optized in several ways. Do the work in place or making sure the space is pre-allocated (as in your version). \$\endgroup\$ Feb 19, 2020 at 20:33
  • \$\begingroup\$ @MartinYork, yep, this function is bottleneck and part of library so i need optimize it as well. \$\endgroup\$
    – goldstar
    Feb 20, 2020 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.