-1

I’m starting to learn C++ by doing a lot of exercises, and I need your help so I can improve, Here is how it goes, I will try to solve an exercise and post both the exercise and my solution to it, And I want you to point me to where / what improvements I can do to make my code better, this would help me both uncover missing parts that I didn’t know about, and better ways of coding,

Here it is

Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.

and here is my solution

#include <iostream>
#include <cassert>
#include <string>
#include <memory>
using namespace std;

bool isperm(const string& a, const string& b) {
    if (a.length() != b.length())
        return false;

    bool* used = new bool[a.length()]();

    for (int i = 0; i != a.length(); i++) {
        for (int j = 0; j != a.length(); j++) {
            if (a.at(i) == b.at(j) && used[j] != true) {
                used[j] = true;
                break;
            }
            

        }
    }
    unsigned test = 0;
    for (; test != a.length() && used[test] != false; ++test);
    if (test == a.length())
        return true;
    return false;
    

}
int main() {
    


    assert(isperm("long string","string long") == true);
    assert(isperm("long", "olng")  == true);
    assert(isperm("ll","lo") == false);
    //assert(isperm("lll", "ooo") == true);
    return 0;
}

side note : I included x86 tag because most of the compiler nitty gritty optimization are done at that level, and I want to see the perspective of it from that side as well.

it can't goes without thanking you for taking the time to read and help me (^_^)

Hey reader you might want to check this code improvements [ exercise 2 ] space encoder for URL

April Morrison
  • 7
  • 3
  • 2
    By the way there is another site in the stackexchange network specifically for such reviews: https://codereview.stackexchange.com/ – harold Aug 21 '22 at 13:05
  • @harold didn't know about that, thanks for pointing that to me, but is posting such question in SO against tos of SO? – April Morrison Aug 21 '22 at 13:10
  • Probably not, but the question may be considered off-topic and then be closed, depending on the average mood of the audience. The chances for a good response to this question are higher on codereview, I expect. – harold Aug 21 '22 at 13:17
  • the problem with codereview is the amount of people visiting it, it's not like SO @harold, it also would make a wonderful series for new people coming into C++, I hope the mod would make an exception, (^_^) thanks for guiding me. – April Morrison Aug 21 '22 at 13:19
  • @harold: Code-review questions *are* off-topic for Stack Overflow these days, since they're open ended and the answers are essentially opinion based. We used to have a [code-review] tag (which was created long before codereview.SE existed; last I remember the usage guidance said not to use it and directed people to cr.SE). But even the tag is gone now. This question seems to be asking for x86 micro-optimization advice, which is on-topic for Stack Overflow, but hasn't mentioned which compiler, or anything about typical use-cases to optimize for (like long vs. short strings) – Peter Cordes Aug 21 '22 at 13:43
  • This looks like an O(n^2) time complexity, so it's pretty slow for large strings. Sorting both strings would cost O(n log n) with large constant factors compared to this, but since you're using individual `char`s (not multi-byte UTF-8 characters), the alphabet is small (just 256 entries, or actually `1ULL< – Peter Cordes Aug 21 '22 at 13:54
  • Also earlier code-reviews like [Check if two strings are anagrams](https://codereview.stackexchange.com/q/69883) which uses an O(n^2) check similar to yours, again having answers that suggest the histogram method. Also [Are strings anagram](https://codereview.stackexchange.com/q/200835) / [Effective way to find two string are anagrams](//codereview.stackexchange.com/q/182372) (has some answers suggesting `std::unordered_map` which is likely less efficient than an array for normal-sized `unsigned char`) / [method to decide if two strings are anagrams](//codereview.stackexchange.com/q/165792) – Peter Cordes Aug 21 '22 at 14:00
  • [Check if two strings are anagrams](https://codereview.stackexchange.com/a/69914) looks like it gets the casts correct, using making sure to use 0..255 for indexing the counts instead of -128..127 by casting to unsigned char. There are of course ways to make it more C++ish, like static_cast, and `std::find` or something for the final check. – Peter Cordes Aug 21 '22 at 14:01
  • @PeterCordes any idea how to evaluate my performance in this small test cases ? – April Morrison Aug 21 '22 at 14:07
  • [Idiomatic way of performance evaluation?](https://stackoverflow.com/q/60291987) - microbenchmarking is hard, but benchmark frameworks like Google::Benchmark can help avoid having the work you want to measure optimized away. Of course, repeated runs means data will be hot in cache, and branch prediction will be primed correctly. But it's very hard to test a small function as part of a larger program that doesn't call it often. – Peter Cordes Aug 21 '22 at 14:12
  • BTW, this also leaks memory; you don't ever `delete` your array of bools. Use `std::vector` instead. (Yes, even though that's a bitmap instead of 1 byte per bool; that's probably good and faster to initialize.) – Peter Cordes Aug 21 '22 at 20:50

1 Answers1

1

Since for permutation the order doesn't matter but the count of each letters does, you just need to count how many of each characters appeared in both input strings.

bool isPermutation(const std::string& a, const std::string& b)
{
    if (a.length() != b.length())
    {
        return false;
    }

    constexpr int ASCII_CHAR_COUNT = 128;
    int counts[ASCII_CHAR_COUNT]{};
    const int length = static_cast<int>(a.length());
    for (int i = 0; i < length; i++)
    {
        ++counts[a[i]];
    }
    for (int i = 0; i < length; i++)
    {
        --counts[b[i]];
    }
    for (int i = 0; i < ASCII_CHAR_COUNT; i++)
    {
        if (counts[i] != 0)
        {
            return false;
        }
    }
    return true;
}
Jesús Jangwon Kim
  • 116
  • 3
  • 1
    A std::string can hold `char` values that are negative. You should `static_cast(a[i])` to avoid undefined behaviour if you strings aren't plain ASCII. This was already mentioned in comments under the question. Although that would mean you'd have to zero all 256 entries of a count array (or `1ULL << CHAR_BIT`), not just 128. – Peter Cordes Aug 21 '22 at 20:47
  • Thanks for your advice. Now my code is safer :) By the way I didn't see the comments when I was answering this, maybe because I opened this page earlier but answered this later. I must refresh the page before answering :D – Jesús Jangwon Kim Aug 22 '22 at 00:53