Se os seus padrões forem sequências fixas, consulte agrep ( download ) (ou outros matchers baseados no algoritmo Wu-Manber). Ele irá combinar todos os padrões em paralelo.
Wu-Manber é geralmente bom para algumas centenas de milhares de padrões (talvez um milhão em um empurrão).
Para expressões regulares, acho que não há uma abordagem geralmente rápida.