Блог

Я решал эту проблему: — Вам даны строки J, представляющие типы камней, которые являются драгоценными камнями, и S, представляющие камни, которые у вас есть. Каждый символ в S — это тип камня, который у вас есть. Вы хотите знать, сколько камней у вас есть, также являются драгоценными камнями.

Буквы в J гарантированно различаются, а все символы в J и S являются буквами. Буквы чувствительны к регистру, поэтому «a» считается камнем, отличным от «A».

Пример 1:

Ввод: J = «aA», S = «aAAbbbb» Вывод: 3 Пример 2:

Ввод: J = «z», S = «ZZ» Вывод: 0

Моя логика для решения 1.
Хэшируйте камни (unordered_map), чтобы у нас была частота каждого типа, и нам нужно было найти только разные камни в заданных драгоценностях один раз. Функция поиска принимает o (n) для каждого камня n, следовательно, временная сложность равна O (n ^ 2).

 int numJewelsInStones(string j, string s) {
        
        unordered_map<char, int>stones;
        for(char s1:s)
              stones[s1];
       
        auto it = stones.begin(); 
        int count = 0;
        for(it = stones.begin(); it != stones.end();   it)
        {
            char s1 = it->first;
            if(j.find(s1) != string::npos)
                count  = it->second;
            
        }
        return count;
  

Итак, я подумал, что o (n ^ 2) слишком много, и решил попытаться оптимизировать это.
Поэтому я также хэшировал драгоценности, поместив их в unordered_set . Таким образом, все дубликаты удаляются, и требуется o (1) времени, чтобы найти в нем камень.
Итак, для каждого камня требуется o (1) времени, и, следовательно, временная сложность становится o (n).

 int numJewelsInStones(string j, string s) {
        
        unordered_map<char, int>stones;
        for(char s1:s)
              stones[s1];
        unordered_set<char>uset(j.begin(), j.end()); 
        auto it = stones.begin(); 
        int count = 0;
        for(it = stones.begin(); it != stones.end();   it)
        {
            char s1 = it->first;
            
            if(uset.find(s1) != uset.end())
                count  = it->second;
                
        }
        return count;
  

Проблема возникает здесь — когда я использовал функцию clock от time.h для измерения времени
выполнения решения 1 я получил 0,000126 единиц времени
, для решения 2 я получил 0,000145 единиц времени
, что не имеет смысла, когда первое равно o (n ^ 2), а второе — o (n).

кстати, это мой код для получения времени-

 int main()
{
    clock_t tStart = clock();
    Solution ob;
    string j = "aA", s = "aAAbbbb";
    cout << ob.numJewelsInStones(j, s) << endl;
    cout << (double)(clock() - tStart)/CLOCKS_PER_SEC;
    cout << endl;
    return 0;
}
  

Кто-нибудь может объяснить мне эту аномалию?

TL; DR Протестируйте свой алгоритм с достаточно большим n

При малых значениях n производительность кэша является более доминирующей. unordered_set реализовано в виде хеш-таблицы в C , следовательно, поиск включает в себя обход указателей (здесь, я полагаю, вы знаете, как реализованы хеш-карты). Перемещение указателей означает чтение из разных частей памяти. Это влияет на производительность кэша, поскольку следующий объект, который хочет проверить хэш-карта, скорее всего, отсутствует в кэше и должен быть извлечен с более высокого уровня памяти.
Массивы, с другой стороны, отображают локальность ссылки. Это позволяет эффективно использовать кеш, следовательно, вы достигаете лучшей производительности с массивами на небольших примерах.

Временная сложность алгоритма используется для определения того, насколько хорошо ваш алгоритм масштабируется в зависимости от размера. O(n^2) Алгоритм может работать лучше, чем O(n) алгоритм на меньших входных данных (как это происходит в этом примере), но на достаточно больших входных данных алгоритм с меньшей временной сложностью должен работать лучше.