find_any_of_and_tell_me_which_one



  • Ich bin extrem unzufrieden mit einem "finde den ersten substring aus einer Auswahl und gib mir an wo und welcher" Algorithmus.
    Mir geht es hier um Geschwindigkeit.

    Das muss doch schöner gehen als das hier:
    (Suchstring = zu suchender String)
    (String = String in dem gesucht wird)

    template <typename FindIteratorT, typename ListIteratorT>
    class FindPair
    {
    public:
        explicit operator bool() const
        {
            return found_;
        }
        FindIteratorT where() const
        {
            return where_;
        }
        ListIteratorT which() const
        {
            return which_;
        }
        FindPair(FindIteratorT where, ListIteratorT which, bool found = false)
            : where_(std::move(where)), which_(std::move(which)), found_(found)
        {}
    private:
        FindIteratorT where_;
        ListIteratorT which_;
        bool found_;
    };
    
    // Die convenience function unten zeigt die Benutzung dieser Funktion, das macht es vermutlich einfacher zu verstehen
    template <typename FindIteratorT, typename ListIteratorT>
    FindPair <FindIteratorT, ListIteratorT> get_first_occurence_of (FindIteratorT Fbegin, FindIteratorT Fend, ListIteratorT Lbegin, ListIteratorT Lend)
    {
        for (auto i = Fbegin; i != Fend; ++i) // Schleife über den String
        {
            for (auto j = Lbegin; j != Lend; ++j) // Schleife über alle Suchstrings
            {
                auto before = i;
                bool found = true;
                for (auto k = std::begin(*j); k != std::end(*j); ++k) // Schleife über den aktuellen Suchstrings
                {
                    if (*k != *i)
                    {
                        found = false; // bei mismatch abbrechen und nächsten Suchstring ausprobiere
                        break;
                    }
                    if (i != Fend)
                        ++i;
                    else
                    {
                        found = false; // Suchstring ist länger als verbleibender String
                        break;
                    }
                }
                if (found)
                {
                    return {--i, j, true};
                }
                else
                {
                    i = before;
                }
            }
        }
        return { Fend, Lend, false };
    }
    
    template <template <typename ElemT, typename = std::allocator<ElemT>> class ContainerT = std::vector>
    inline FindPair <std::string::const_iterator, std::vector<std::string>::const_iterator> get_first_occurence_of (std::string const& str, ContainerT <std::string> const& alts)
    {
        return get_first_occurence_of (str.cbegin(), str.cend(), alts.cbegin(), alts.cend());
    }
    
    int main()
    {
        std::vector <std::string> alts = {
            "//",
            "/*",
            "\"",
            "'"
        };
        auto results = get_first_occurence_of("abcd//'//troll/*\"", alts);
        if (results)
        {
            std::cout << *results.where() << "\n";
            std::cout << *results.which();
        }
        return 0;
    }
    

    Hat boost string algo was nettes?



  • Da es dir offensichtlich nicht um Geschwindigkeit geht, wieso loopst du nicht einfach über alle Pattern, rufst für jedes Pattern std::search/strstr auf und merkst dir dann den ersten Treffer?



  • http://en.wikipedia.org/wiki/String_searching_algorithm#Algorithms_using_a_finite_set_of_patterns
    ?

    ps:

    Tim06TR schrieb:

    Mir geht es hier um Geschwindigkeit.

    Das muss doch schöner gehen

    Such dir eins aus. Schön oder schnell. Beides wird wohl nix. (Ausser natürlich du nimmst ne fertige Library, die du nur noch aufrufen musst :D)



  • hustbaer schrieb:

    Such dir eins aus. Schön oder schnell. Beides wird wohl nix.

    Den Rabin–Karp kann man in weit weniger als 84 Zeilen implementieren.



  • Schön == "in weit weniger als 84 Zeilen implementierbar"?
    Uff. Wusste ich gar nicht.



  • not_going_to_tell_ya schrieb:

    Da es dir offensichtlich nicht um Geschwindigkeit geht, wieso loopst du nicht einfach über alle Pattern, rufst für jedes Pattern std::search/strstr auf und merkst dir dann den ersten Treffer?

    Das habe ich vorher gemacht, aber das ist noch viel schlimmer als das da oben.
    Das sind hübsche 5 Zeilen.


Log in to reply