Geek Answers Handbook

The speed of the permutation function using different methods leads to unexpected results.

I implemented a function isPermutationthat defined two lines, will return trueif they are permutations of each other, otherwise it will return false.

One uses the C ++ sorting algorithm twice, while the other uses an int array to track the number of rows.

I ran the code several times and every time the sorting method is faster. Is array implementation wrong?

Here is the result:

1
0
1
Time: 0.088 ms
1
0
1
Time: 0.014 ms

And the code:

#include <iostream> // cout
#include <string>   // string
#include <cstring> // memset
#include <algorithm> // sort
#include <ctime> // clock_t

using namespace std;

#define MAX_CHAR 255


void PrintTimeDiff(clock_t start, clock_t end) {
    std::cout << "Time: " << (end - start) / (double)(CLOCKS_PER_SEC / 1000) << " ms" << std::endl;
}


// using array to keep a count of used chars
bool isPermutation(string inputa, string inputb) {
    int allChars[MAX_CHAR];
    memset(allChars, 0, sizeof(int) * MAX_CHAR);

    for(int i=0; i < inputa.size(); i++) {
        allChars[(int)inputa[i]]++;
    }

    for (int i=0; i < inputb.size(); i++) {
        allChars[(int)inputb[i]]--;
        if(allChars[(int)inputb[i]] < 0) {
            return false;
        }   
    }

    return true;
}


// using sorting anc comparing
bool isPermutation_sort(string inputa, string inputb) {

    std::sort(inputa.begin(), inputa.end());
    std::sort(inputb.begin(), inputb.end());

    if(inputa == inputb) return true;
    return false;
}



int main(int argc, char* argv[]) {

    clock_t  start = clock();
    cout << isPermutation("god", "dog") << endl;
    cout << isPermutation("thisisaratherlongerinput","thisisarathershorterinput") << endl;
    cout << isPermutation("armen", "ramen") << endl;
    PrintTimeDiff(start, clock());


    start = clock();
    cout << isPermutation_sort("god", "dog") << endl;
    cout << isPermutation_sort("thisisaratherlongerinput","thisisarathershorterinput") << endl;
    cout << isPermutation_sort("armen", "ramen") << endl;
    PrintTimeDiff(start, clock());

    return 0;
}
+4
source share
3 answers

  • , mix std::cout. isPermutation isPermutation_sort , std::cout (, , \n std::endl).

  • . , - , , , .

:

int main()
{
  const std::vector<std::string> bag
  {
    "god", "dog", "thisisaratherlongerinput", "thisisarathershorterinput",
    "armen", "ramen"
  };

  static std::mt19937 engine;
  std::uniform_int_distribution<std::size_t> rand(0, bag.size() - 1);

  const unsigned stop = 1000000;

  unsigned counter = 0;
  std::clock_t start = std::clock();
  for (unsigned i(0); i < stop; ++i)
    counter += isPermutation(bag[rand(engine)], bag[rand(engine)]);

  std::cout << counter << '\n';
  PrintTimeDiff(start, clock());

  counter = 0;
  start = std::clock();
  for (unsigned i(0); i < stop; ++i)
    counter += isPermutation_sort(bag[rand(engine)], bag[rand(engine)]);

  std::cout << counter << '\n';
  PrintTimeDiff(start, clock());

  return 0;
}

2.4s isPermutations_sort vs 2s isPermutation ( Hal). g++ clang++.

counter :

isPermutation :

  • const

    bool isPermutation(const std::string &inputa, const std::string &inputb)

    0.8s (, isPermutation_sort).

  • std::array std::fill memset ( ++: -)

  • . postincrement,
  • signed unsigned for (inputa.size() i). i std::size_t
  • , , .

- :

bool isPermutation(const std::string &inputa, const std::string &inputb)
{
  std::array<int, MAX_CHAR> allChars;
  allChars.fill(0);

  for (auto c : inputa)
    ++allChars[(unsigned char)c];

  for (auto c : inputb)
  {
    --allChars[(unsigned char)c];
    if (allChars[(unsigned char)c] < 0)
      return false;
  }

  return true;
}

isPermutation isPermutation_sort :

  if (inputa.length() != inputb.length())
    return false;

0.55s isPermutation vs 1.1s isPermutation_sort.

, : std::is_permutation:

for (unsigned i(0); i < stop; ++i)
{
  const std::string &s1(bag[rand(engine)]), &s2(bag[rand(engine)]);

  counter += std::is_permutation(s1.begin(), s1.end(), s2.begin());
}

(0.6s)

BeyelerStudios, Mersenne-Twister .

.:

static std::linear_congruential_engine<std::uint_fast32_t, 48271, 0, 2147483647> engine;

. , .

, , , .

+4

, . - , 1000 , 10 . , . , (, - ).

, . .

method 1 array Time: 0.768 us
method 2 sort Time: 0.840333 us

method 1 array Time: 0.621333 us
method 2 sort Time: 0.774 us

method 1 array Time: 0.769 us
method 2 sort Time: 0.856333 us

method 1 array Time: 0.766 us
method 2 sort Time: 0.850333 us

method 1 array Time: 0.802667 us
method 2 sort Time: 0.89 us

method 1 array Time: 0.778 us
method 2 sort Time: 0.841333 us

rdtsc, . 3000 , , , , .

#if defined(__x86_64__)
static uint64_t rdtsc()
{
    uint64_t    hi, lo;

    __asm__ __volatile__ (
                            "xor %%eax, %%eax\n"
                            "cpuid\n"
                            "rdtsc\n"
                            : "=a"(lo), "=d"(hi)
                            :: "ebx", "ecx");

    return (hi << 32)|lo;
}
#else
#error wrong architecture - implement me
#endif

void PrintTimeDiff(uint64_t start, uint64_t end) {
    std::cout << "Time: " << (end - start)/double(3000)  << " us" << std::endl;
}
+5

Counting Sort , , count, .

, 255 . 256B 4 * 256B , , count .

, . L1, count read-modify-write. . , , ( , ). x86 , + .

inputa :

.L15:
        movsx   rdx, BYTE PTR [rax]
        add     rax, 1
        add     DWORD PTR [rsp-120+rdx*4], 1
        cmp     rax, rcx
        jne     .L15

: char . ABI x86-64 char , allChars[(int)inputa[i]]++; sign- . (movsx movzx). , ASCII, . allChars[(unsigned char)inputa[i]]++;. , (unsigned) (. ).

, clang (v3.7.1 v3.8, -O3), std::basic_string<...>::_M_leak_hard() . (, , , .) @manlio , , for (auto c : inputa) clang , .

, std::string, char[], std::string. , .

GNU libc std::is_permutation :

-, , .

inputa:

  • inputb. , inputa.

:

  • : , inputa, , .
  • , inputb != 0 inputa.

, , . (, int64_t ).

, , , , . , , , , , .

std::is_permutation std::count, SSE/AVX. , - - , gcc, clang. 64- , , . , , , , , ( -O2 -O3 -fno-tree-vectorize).

, count - pcmpeqb/psubb, psadbw 255 . pcmpeqb/pmovmskb/popcnt/add, .

Template specializations in the library can help a lot std::countfor 8, 16, and 32-bit types, whose equality can be checked using bitwise equality (integer ==).

+3
source

More articles:


All Articles