Leetcode les plus longues parenthèses valides

Question

Lien ici

Je vais inclure une solution en Python et C ++ et vous pourrez en examiner une. Je suis surtout intéressé par la révision du code C ++, une chose que j'ai récemment commencé à apprendre; ceux qui ne connaissent pas le C ++ peuvent consulter le code Python. Les deux solutions partagent une logique similaire, de sorte que l'examen s'appliquera à l'un ou l'autre.

---

Énoncé du problème

Étant donné une chaîne contenant uniquement les caractères '(' et ')', recherchez la longueur de la sous-chaîne de parenthèses valide (bien formée) la plus longue.

Exemple 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Exemple 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Exemple 3:

Input: s = ""
Output: 0

Exemple 4:

Input: s = "(()()()"
Output: 6

Exemple 5:

Input: s = "((())((((())))"
Output: 8

Les deux solutions sont Oⁿ et passent tous les cas de test, y compris la limite de temps, cependant, elles prennent plus de temps que prévu, en particulier la version c ++ bien que les deux partagent la même logique. J'ai besoin d'améliorer le temps en priorité.

longest_parentheses.py

def check_longest(s):
    opened = []
    closed = []
    cum_distance = 0
    max_distance = 0
    for i, ss in enumerate(s):
        if ss == ')':
            if opened:
                closed.append((opened.pop(), i))
        if ss == '(':
            opened.append(i)
    closed = set(sum(closed, ()))
    for j in range(len(s)):
        if j in closed:
            cum_distance += 1
        else:
            cum_distance = 0
        max_distance = max(max_distance, cum_distance)
    return max_distance


if __name__ == '__main__':
    print(check_longest(')((()()()()'))

Statistiques:

Runtime: 272 ms, faster than 5.14% of Python3 online submissions for Longest Valid Parentheses.
Memory Usage: 15.5 MB, less than 6.57% of Python3 online submissions for Longest Valid Parentheses.

longest_parentheses.h

#ifndef LEETCODE_LONGEST_PARENTHESES_H
#define LEETCODE_LONGEST_PARENTHESES_H

#include <string_view>

int calculate_distance(size_t p_size, const std::vector<size_t> &closed);
int get_longest(const std::string_view &s);

#endif //LEETCODE_LONGEST_PARENTHESES_H

longest_parentheses.cpp

#include "longest_parentheses.h"
#include <vector>
#include <iostream>


int calculate_distance(size_t p_size, const std::vector<size_t> &closed) {
    int cum_distance = 0;
    int max_distance = 0;
    for (size_t i = 0; i < p_size; ++i) {
        if (std::find(closed.begin(), closed.end(), i) != closed.end()) {
            cum_distance++;
        } else {
            cum_distance = 0;
        }
        max_distance = std::max(max_distance, cum_distance);
    }
    return max_distance;
}


int get_longest(const std::string_view &s) {
    std::vector<size_t> opened, closed;
    for (size_t i = 0; i < s.size(); ++i) {
        auto ss = s[i];
        if (ss == ')') {
            if (!opened.empty()) {
                closed.push_back({opened.back()});
                closed.push_back(i);
                opened.pop_back();
            }
        }
        if (ss == '(') {
            opened.push_back(i);
        }
    }
    return calculate_distance(s.size(), closed);
}


int main() {
    std::cout << get_longest(")()())");
}

Statistiques:

Runtime: 1276 ms, faster than 5.09% of C++ online submissions for Longest Valid Parentheses.
Memory Usage: 9.3 MB, less than 5.04% of C++ online submissions for Longest Valid Parentheses.

Answer 1

Voici quelques éléments qui peuvent vous aider à améliorer votre programme.

Version C ++

Utilisez tous les #includes requis

Le type std::vector<size_t>est utilisé dans la définition de calculate_distance()dans le fichier d' en-tête, mais il #include <vector>est absent de la liste des inclusions. En outre, std::max()est utilisé, mais #include <algorithm>est absent du .cppfichier.

Minimisez l'interface

Le .hfichier est une déclaration de l' interface avec votre logiciel. C'est .cppla mise en œuvre de cette interface. Une bonne pratique de conception consiste à minimiser l'interface à ce qui est nécessaire aux programmes extérieurs. Pour cette raison, je supprimerais la calculate_distance()fonction de l'en-tête.

Faire des fonctions locales static

Avec l'interface plus petite comme préconisée ci-dessus, la calculate_distancefonction devient un détail d'implémentation utilisé uniquement dans le .cppfichier. Pour cette raison, il doit être fait staticpour que le compilateur sache qu'il est sûr d'inline la fonction.

Utilisez switchplutôt une série d' ifinstructions

Le code contient actuellement ceci:

for (size_t i = 0; i < s.size(); ++i) {
    auto ss = s[i];
    if (ss == ')') {
        if (!opened.empty()) {
            closed.push_back({opened.back()});
            closed.push_back(i);
            opened.pop_back();
        }
    }
    if (ss == '(') {
        opened.push_back(i);
    }
}

Ce serait un peu plus rapide et un peu plus facile à lire s'il était plutôt écrit comme ceci:

for (size_t i = 0; i < s.size(); ++i) {
    switch(s[i]) {
        case ')':
            if (!opened.empty()) {
                closed.push_back({opened.back()});
                closed.push_back(i);
                opened.pop_back();
            }
            break;
        case '(':
            opened.push_back(i);
            break;
    }
}

Soyez prudent avec les signés et non signés

Que signifierait-il si calculate_distancerenvoyer un nombre négatif? Il n'a probablement pas d'interprétation sensée, donc pour cette raison, je recommanderais de lui renvoyer une unsignedquantité par rapport à une signée int.

Écrire des fonctions de test

Vous avez fourni une entrée de test dans la description du problème, mais il serait bon d'écrire un script de test complet pour exercer la fonction. Pour ce genre de chose, j'ai tendance à aimer utiliser un objet de test. Voici celui que j'ai écrit pour ce code:

class ParenTest {
public:
    ParenTest(std::string_view input, unsigned longest)
        : input{input}
        , longest{longest}
    {}
    unsigned operator()() const {
        return static_cast<unsigned>(get_longest(input));
    }
    bool test() const {
        return longest == operator()();
    }
    friend std::ostream& operator<<(std::ostream& out, const ParenTest& test) {
        auto calculated = test();
        return out << (calculated == test.longest ? "ok  " : "BAD ") 
            << "\"" << test.input << "\", " << test.longest << ", got " << calculated << "\n";
    }
private:
    std::string_view input;
    unsigned longest;
};

Voici maintenant quelques vecteurs de test et une mainroutine:

int main(int argc, char* argv[]) {
    static const std::vector<ParenTest> tests{
        { "(()", 2 },
        { ")()())", 4 },
        { "", 0 },
        { "(()()()", 6 },
        { "((())((((())))", 8 },
        { "(())(())(()))", 12 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))", 12 },
        { "(())(())(()))(())(())(())(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))"
          "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
    };
    for (const auto &test : tests) {
        std::cout << test;
    }
}

Pour assurer à la fois l'exactitude et le chronométrage, j'ai utilisé mon modèle de chronomètre . La version finale de mainressemble à ceci:

#include "longest_parentheses.h"
#include "stopwatch.h"
#include <string_view>
#include <iostream>
#include <vector>

// the ParenTest class goes here

int main(int argc, char* argv[]) {
    static const std::vector<ParenTest> tests{
        { "(()", 2 },
        { ")()())", 4 },
        { "", 0 },
        { "(()()()", 6 },
        { "((())((((())))", 8 },
        { "(())(())(()))", 12 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))", 12 },
        { "(())(())(()))(())(())(())(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
        { "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))"
          "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
    };
    for (const auto &test : tests) {
        std::cout << test;
    }
    if (argc != 2) {
        std::cout << "Usage: " << argv[0] << " num_trials\n";
        return 1;
    }
        
    auto iterations = std::stoul(argv[1]);

    Stopwatch<> timer{};
    bool valid{true}

    for (auto i{iterations}; i; --i) {
        valid &= tests.back().test();
    }

    auto elapsed{timer.stop()};
    if (!valid) {
        std::cout << "The program failed!\n";
        return 2;
    }

    std::cout << iterations << " trials took " << elapsed << " microseconds\n"
        " for an average of " << elapsed/iterations << " microseconds/trial\n";
}

Utilisez un meilleur algorithme

Le code existant n'est pas si mauvais, mais il n'est pas aussi efficace qu'il pourrait l'être. Sur ma machine avec le code ci-dessus et avec un million d'essais, il faut 5,66 microsecondes par invocation de get_longest()la plus longue entrée de test, qui est également la dernière de l'ensemble. On peut faire mieux. Voici une routine alternative qui utilise a std::vectorpour garder une trace de chacun des démarrages au (fur et à mesure qu'ils se produisent, mais qui effectue également le calcul de la longueur de la travée à mesure qu'il rencontre chaque fermeture ). Voici comment je l'ai fait:

unsigned get_longest(const std::string_view& in) {
    struct Span {
        std::size_t begin;
        std::size_t end;
        Span(std::size_t begin, std::size_t end)
            : begin{begin}
            , end{end}
        {}
        std::size_t len() const {
            return end - begin + 1;
        }
        bool is_strictly_enclosing(const Span& other) const {
            return other.begin - begin == 1 &&
                      end - other.end == 1;
        }
        bool is_contiguous_with(const Span& other) const {
            return begin - other.end == 1;
        }
    };
    std::vector<std::size_t> parenmatch;
    std::vector<Span> spans;
    std::size_t longest{0};
    for (std::size_t i{0}; i < in.size(); ++i) {
        switch(in[i]) {
            case '(':
                parenmatch.push_back(i);
                break;
            case ')':
                if (!parenmatch.empty()) {
                    Span curr_span{parenmatch.back(), i};
                    parenmatch.pop_back();
                    if (!spans.empty() && curr_span.is_strictly_enclosing(spans.back())) {
                        // destroy the last one
                        spans.pop_back();
                    }
                    if (!spans.empty() && curr_span.is_contiguous_with(spans.back())) {
                        // merge the contiguous spans
                        spans.back().end = curr_span.end;
                    } else {
                        spans.push_back(curr_span);
                    }
                    longest = std::max(longest, spans.back().len());
                } 
                break;
            default:
                parenmatch.clear();
                spans.clear();
        }
    }
    return longest;
}

Il y a probablement encore place à l'amélioration, mais voici comment cela fonctionne. Premièrement, il garde une trace de chacune Spandes parenthèses correspondantes et imbriquées. Ce ()serait donc correspondre à une telle envergure, comme le ferait (()). Le code utilise is_strictly_enclosingpour les tester. Par exemple, dans (()), la paire intérieure est trouvée en premier et aurait une étendue de {1,2}. La paire externe est trouvée en dernier et a une durée de {0,3}. Si nous examinons la logique, il est maintenant clair ce que ce code recherche:

bool is_strictly_enclosing(const Span& other) const {
    return other.begin - begin == 1 &&
              end - other.end == 1;
}

Deuxièmement, il y a le cas des parenthèses correspondantes mais non imbriquées telles que ()()ou (())(). Ici encore, nous utilisons une fonction membre de Span:

bool is_contiguous_with(const Span& other) const {
    return begin - other.end == 1;
}

En utilisant ce code, nous obtenons le rapport de synchronisation suivant:

1000000 essais ont duré 562299 microsecondes pour une moyenne de 0,562299 microsecondes / essai

Cette version du code est donc environ 10 fois plus rapide. Notez également qu'il gère correctement les entrées malformées, ((*))par exemple en signalant 0une telle chaîne.

Version Python

Utiliser elifpour des conditions mutuellement exclusives

La vérification de l'ouverture (utilise ifmais il serait plus logique de l'utiliser elifici car les deux cas (soit (ou )) sont les seuls considérés. Faire juste ce changement fait passer chaque itération (en utilisant la même très longue chaîne que dans le code C ++) de 74,167 microsecondes à 72,444 microsecondes.

Ne mettez pas à jour les valeurs inchangées

Le code a actuellement cette séquence:

for j in range(len(s)):
    if j in closed:
        cum_distance += 1
    else:
        cum_distance = 0
    max_distance = max(max_distance, cum_distance)

Un rapide coup d'œil au code vérifiera qu'il max_distancene peut obtenir une nouvelle valeur que si l' ifinstruction est vraie, alors déplaçons la ligne ici. Cela réduit le temps à 71,680 microsecondes.

Utilisez un algorithme plus rapide

Encore une fois, ce qui fonctionne dans la version C ++ fonctionne également en Python. Voici une version Python de l'algorithme ci-dessus:

def get_longest(s):
    parenmatch = []
    spans = []
    longest = 0
    for i, ss in enumerate(s):
        if ss == '(':
            parenmatch.append(i)
        elif ss == ')':
            if parenmatch:
                curr_span = (parenmatch.pop(), i)
                if spans and spans[-1][0] - curr_span[0] == 1 and curr_span[1] - spans[-1][1] == 1:
                    spans.pop()
                if spans and curr_span[0] - spans[-1][1] == 1:
                    spans[-1] = (spans[-1][0], curr_span[1])
                else:
                    spans.append(curr_span)
                longest = max(longest, spans[-1][1] - spans[-1][0] + 1)
    return longest                        

Cette fois, la différence n'est pas aussi dramatique et le temps pour cette fonction est de 64,562 microsecondes.