Использование регулярных выражений для анализа и идентификации различных типов данных
Без включения регулярных выражений в моей записи у меня есть неофициальная сложность времени O (n ^ 3)
и формальная запись
О (20.33n ^ 3 + 84.22n ^ 2 + 3n + 14)
Десятичные числа из-за запуска n через 9 потоков для его сегментирования.
Мне требуется первый цикл for, чтобы сгруппировать совпадения регулярных выражений (всего 9 регулярных выражений для повторения) для каждой строки
Для циклов sregex используется слой n ^ 2 для циклов
И слой циклов n ^ 3 используется для проверки того, что сохраняемое совпадение не является дублирующим совпадением
Первоначально я пытался разделить эту функцию синтаксического анализа на 9 потоков, и в то время как она сбрила много обработки; Мой код теперь составляет в среднем ~ 8 секунд для 750 подходящих случаев
При скорости выполнения ~ 0,01 с на случай.
Что совсем не так, как я ожидал бы от случаев регулярных выражений
Я указал свое регулярное выражение настолько, насколько я могу, и я извлекаю подстроки из строки соответствия для каждого соответствия случая, чтобы было меньше данных для передачи следующему регулярному выражению, чтобы еще больше сократить продолжительность.
(я использую std :: regex)
Regex, будучи самой дорогостоящей частью моей программы, в своем нынешнем состоянии должен быть таким же сложным, как и я, так как я сравниваю как имена файлов / пути, так и домены, и лучшую теорию для дифференциации этих двух Я ' Мы думаем, что это список TLD (ccTLD также и т.д.)
Мне в основном интересно, есть ли какой-нибудь теоретический или реальный способ улучшить общую концепцию моего кода, поскольку функция O (n ^ 3), даже разделенная на 9, все еще довольно медленная.
Все, что я могу придумать, это либо удалить первый n + 1 для цикла и подставить его, используя двумерный вектор для хранения значений индекса, чтобы показать связь строк, либо реализовать больше условных операторов и функций, не являющихся регулярными выражениями, для уменьшения вероятности наихудших случаев, но я не обладаю достаточными знаниями и не обладаю достаточными знаниями, чтобы знать, является ли один из них лучшим способом повышения производительности
Полный n + 1 для цикла выглядит следующим образом (я опустил переменные регулярного выражения и функцию переноса для удобства чтения):
for(unsigned int i = 0;i < lc; i++) {
this->iocGroupHeader(this->finalpath);
for(std::sregex_iterator i2 = std::sregex_iterator(lines[i].begin(), lines[i].end(), hashregfull);i2 != std::sregex_iterator();++i2 ) {
string debugline = lines[i];
unsigned long sv = termassoc.size();
smatch hashmatch = *i2;
unsigned long k = 0;
newline = "";
if( sv > k){
int added = 0;
for(unsigned int i4 = 0;i4 < termassoc.size(); i4++) {
if(termassoc[i4] == hashmatch.str() && added == 0) {
added++;
}
if(added != 0) break;
}
if(added == 0){
termassoc.emplace_back(hashmatch.str());
string hash = hashmatch.str();
if(hash.size() == 32) {
this->md5info(hash,this->finalpath );
} else if(hash.size() == 40) {
this->sha1info(hash,this->finalpath );
} else if(hash.size() == 64) {
this->sha256info(hash,this->finalpath );
}
added++;
unsigned long pos = lines[i].find(hashmatch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((hashmatch.str().size()) + pos, lines[i].size() - 1);
}else break;
} else {
termassoc.emplace_back(hashmatch.str());
string hash = hashmatch.str();
if(hash.size() == 32) {
this->md5info(hash,this->finalpath );
} else if(hash.size() == 40) {
this->sha1info(hash,this->finalpath );
} else if(hash.size() == 64) {
this->sha256info(hash,this->finalpath );
}
string str = hashmatch.str();
unsigned long pos = lines[i].find(str);
newline += lines[i].substr(0, pos);
newline += lines[i].substr((str.size()) + pos, lines[i].size() - 1);
}
}
if(newline != ""){
lines[i] = newline;
} else { this->iocGroupFooter(this->finalpath); continue; }
for(std::sregex_iterator i2 = std::sregex_iterator(lines[i].begin(), lines[i].end(), emailregfull);i2 != std::sregex_iterator();++i2 ) {
unsigned long sv = termassoc.size();
smatch emailmatch = *i2;
newline = "";
unsigned long k = 0;
if( sv > k){
int added = 0;
for(unsigned int i4 = 0;i4 < termassoc.size(); i4++) {
if(termassoc[i4] == emailmatch.str() && added == 0) {
added++;
}
if(added != 0) break;
}
if(added == 0){
termassoc.emplace_back(emailmatch.str());
this->emailinfo(emailmatch.str(),this->finalpath );
added++;
unsigned long pos = lines[i].find(emailmatch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((emailmatch.str().size()) + pos, lines[i].size() - 1);
}else break;
} else {
termassoc.emplace_back(emailmatch.str());
string output = emailmatch.str();
this->emailinfo(emailmatch.str(),this->finalpath );
unsigned long pos = lines[i].find(emailmatch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((emailmatch.str().size()) + pos, lines[i].size() - 1);
}
}
if(newline != ""){
lines[i] = newline;
} else { this->iocGroupFooter(this->finalpath); continue; }
if(file == false){
if(!(regex_search(lines[i], ipregfull) || this->containsRemoveHKEY(lines[i]) == "" || regex_search(lines[i], fileregblacklist2)) && (regex_search(lines[i], fileregpart2) || regex_search(lines[i], fileregpart1))) {
for(std::sregex_iterator i2 = std::sregex_iterator(lines[i].begin(), lines[i].end(), fileregpart1);i2 != std::sregex_iterator();++i2 ){
unsigned long sv = termassoc.size();
smatch filematch = *i2;
newline = "";
unsigned long k = 0;
if( sv > k){
int added = 0;
if(added == 0){
termassoc.emplace_back(filematch.str());
this->fileinfo(filematch.str(),this->finalpath );
added++;
unsigned long pos = lines[i].find(filematch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((filematch.str().size()) + pos, lines[i].size() - 1);
}else break;
} else {
termassoc.emplace_back(filematch.str());
string output = filematch.str();
this->fileinfo(filematch.str(),this->finalpath );
unsigned long pos = lines[i].find(filematch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((filematch.str().size()) + pos, lines[i].size() - 1);
}
}
if(newline != ""){
lines[i] = newline;
} else { this->iocGroupFooter(this->finalpath); continue; }
for(std::sregex_iterator i2 = std::sregex_iterator(lines[i].begin(), lines[i].end(), fileregpart2);i2 != std::sregex_iterator();++i2 ){
unsigned long sv = termassoc.size();
smatch filematch = *i2;
newline = "";
unsigned long k = 0;
if( sv > k){
int added = 0;
if(added == 0){
termassoc.emplace_back(filematch.str());
this->fileinfo(filematch.str(),this->finalpath );
added++;
unsigned long pos = lines[i].find(filematch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((filematch.str().size()) + pos, lines[i].size() - 1);
}else break;
} else {
termassoc.emplace_back(filematch.str());
string output = filematch.str();
this->fileinfo(filematch.str(),this->finalpath );
unsigned long pos = lines[i].find(filematch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((filematch.str().size()) + pos, lines[i].size() - 1);
}
}
}
if(newline != ""){
lines[i] = newline;
} else { this->iocGroupFooter(this->finalpath); continue; }
}
for(std::sregex_iterator i2 = std::sregex_iterator(lines[i].begin(), lines[i].end(), hkeyregfull);i2 != std::sregex_iterator();++i2 ){
unsigned long sv = termassoc.size();
smatch hkeymatch = *i2;
newline = "";
unsigned long k = 0;
if( sv > k){
int added = 0;
for(unsigned int i4 = 0;i4 < termassoc.size(); i4++) {
if(termassoc[i4] == hkeymatch.str() && added == 0) {
added++;
}
if(added != 0) break;
}
if(added == 0){
termassoc.emplace_back(hkeymatch.str());
this->reginfo(hkeymatch.str(),this->finalpath );
added++;
unsigned long pos = lines[i].find(hkeymatch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((hkeymatch.str().size()) + pos, lines[i].size() - 1);
}else break;
} else {
termassoc.emplace_back(hkeymatch.str());
string output = hkeymatch.str();
this->reginfo(hkeymatch.str(),this->finalpath );
unsigned long pos = lines[i].find(hkeymatch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((hkeymatch.str().size()) + pos, lines[i].size() - 1);
}
}
if(newline != ""){
lines[i] = newline;
} else { this->iocGroupFooter(this->finalpath); continue; }
for(std::sregex_iterator i2 = std::sregex_iterator(lines[i].begin(), lines[i].end(), ipregfull);i2 != std::sregex_iterator();++i2 ){
unsigned long sv = termassoc.size();
smatch ipmatch = *i2;
newline = "";
unsigned long k = 0;
if( sv > k){
int added = 0;
for(unsigned int i4 = 0;i4 < termassoc.size(); i4++) {
if(!(termassoc[i4] == ipmatch.str()) && added == 0) {
added++;
}
if(added != 0) break;
}
if(added == 0){
termassoc.emplace_back(ipmatch.str());
this->ipinfo(ipmatch.str(),this->finalpath );
added++;
unsigned long pos = lines[i].find(ipmatch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((ipmatch.str().size()) + pos, lines[i].size() - 1);
}else break;
} else {
termassoc.emplace_back(ipmatch.str());
string output = ipmatch.str();
this->ipinfo(ipmatch.str(),this->finalpath );
unsigned long pos = lines[i].find(ipmatch.str());
newline += lines[i].substr(0, pos);
newline += lines[i].substr((ipmatch.str().size()) + pos, lines[i].size() - 1);
}
}
if(newline != ""){
lines[i] = newline;
} else { this->iocGroupFooter(this->finalpath); continue; }
for(std::sregex_iterator i2 = std::sregex_iterator(lines[i].begin(), lines[i].end(), domainregfull);i2 != std::sregex_iterator();++i2 ){
unsigned long sv = termassoc.size();
smatch domainmatch = *i2;
unsigned long k = 0;
if( sv > k){
int added = 0;
for(unsigned int i4 = 0;i4 < termassoc.size(); i4++) {
if(!(termassoc[i4] == domainmatch.str()) && added == 0) {
termassoc.emplace_back(domainmatch.str());
this->domaininfo(domainmatch.str(),this->finalpath );
added++;
}
if(added != 0) break;
}
} else {
termassoc.emplace_back(domainmatch.str());
string output = domainmatch.str();
this->domaininfo(domainmatch.str(),this->finalpath );
}
}
this->iocGroupFooter(this->finalpath);
}
Минимальная концепция будет выглядеть так:
for(i = 0; i < linecount; i++){
for(i2 = regex iterator;i2 != regex iterator;i2++){
for(i3 = 0; i3 < termstorage; i3++){
}
}
for(i2 = regex iterator;i2 != regex iterator;i2++){
for(i3 = 0; i3 < termstorage; i3++){
}
}
for(i2 = regex iterator;i2 != regex iterator;i2++){
for(i3 = 0; i3 < termstorage; i3++){
}
}
for(i2 = regex iterator;i2 != regex iterator;i2++){
for(i3 = 0; i3 < termstorage; i3++){
}
}
for(i2 = regex iterator;i2 != regex iterator;i2++){
for(i3 = 0; i3 < termstorage; i3++){
}
}
for(i2 = regex iterator;i2 != regex iterator;i2++){
for(i3 = 0; i3 < termstorage; i3++){
}
}
for(i2 = regex iterator;i2 != regex iterator;i2++){
for(i3 = 0; i3 < termstorage; i3++){
}
}
Редактировать Другие возможности, которые я подумал о расширении концепции индексации совпадений, я думаю, что можно уменьшить сложность времени до O (n), также заменив O (n ^ 3) цикл с функцией фильтра пост-обработки и генерация результатов впоследствии?
edit2 Все вызовы функций в цикле n ^ 3 + 1 являются функциями O (1), поэтому их можно рассматривать как таковые