Рекурсия vs итерации , на правах Холивара

[Qraizer]

Выделил в отдельную тему, заслуживает. Автоудаление отменено.

[mkudritsky]

Можно и я влезу? (Может быть невпопад).
При поиске по структурам рекомендую отказаться от использования рекурсии, которой так гордятся в C/C++.
Программирование без рекурсии будет посложнее, но оно того стоит.

Имею опыт отказа от рекурсии в двух задачах поиска.
В обоих случаях скорость поиска возросла в ТРИ-ЧЕТЫРЕ (!!!) раза!

Какие это задачи, на которых было обнаружено отрицательное влияние рекурсии?
1. Более чем классическая задача - поиск всех файлов в файловой системе (в каталоге + подкаталогах) по маске.
Алгоритм с рекурсией есть даже в Википедии (вроде как).
2. Задача поиска векторного минимакса в математическом программировании.
Думаю, что если копнуть поглубже, то в математическом и в целочисленном программировании полно задач использует рекурсию - программы писать проще.
Но вот если отказаться от рекурсии, попотеть над программой, то быстродействие вырастет минимум в 3 раза.

P.S. Конечно, когда в файловой системе по маске ищутся несколько десятков файлов, отказ от рекурсии не заметен - поиск идет "мгновенно".
Но ситуация резко меняется, когда в поиске по маске находятся десятки и сотни тысяч файлов...

Эта тема была разделена из темы "Поиск по заданному полю большой структуры"

[Qraizer]

Цитата mkudritsky @ 05.06.22, 02:34

Можно и я влезу? (Может быть невпопад).
...
Программирование без рекурсии будет посложнее, но оно того стоит.

unsigned long op(unsigned long x, unsigned long y, int n)
{
 if(n==0) x=n=1;
 
 std::vector<unsigned long> res(n+1);
 std::vector<unsigned long> tmp(n);
 std::vector<unsigned long> idx(n);
 int            lev=n-1;
 unsigned long  temp;
 
 tmp[lev]=y;
 res[lev]=x;
 idx[lev]=1;
 do
  if(lev==0)
  {
   temp=x+tmp[lev];
   do
    res[++lev]=temp;
   while(lev!=n && ++idx[lev] >= tmp[lev]);
  }
  else
  {
   tmp[lev-1]=res[lev];
   res[--lev]=x;
   idx[lev]=1;
  }
 while(lev!=n);
 
 temp=res[lev];
 return temp;
}
 
unsigned long f_nm(unsigned long m, unsigned long n)
{
 return op(2, n+3, static_cast<int>(m))-3;
}

Кто-нибудь догадается, что такое эта f_nm()?

[Qraizer]

Цитата Qraizer @ 05.06.22, 09:01

Кто-нибудь догадается, что такое эта f_nm()?

Что, никто? Подсказываю: это дважды рекурсивная функция, названная именем математика. Его же имя носит один из нетривиальных счётных ординалов. Операции +3 и -3 и константа 2 в её тексте должны тоже намекать.

P.S. Это к вопросу о полезности рекурсий. Любой рекурсивный алгоритм может быть переведён в итерационный и наоборот. Вопрос же "а нужно ли" всегда не имеет однозначного ответа.

[Majestio]

Цитата Qraizer @ 06.06.22, 17:11

Вопрос же "а нужно ли" всегда не имеет однозначного ответа.

Ну нееет - не всегда. Если тебе данные кагбэ намекают, что стек ты "съешь" не просчитав и десятой части на предполагаемых данных - нафик мучать стек, нужно переводить в итерации..

[Majestio]

mkudritsky, смею предположить, что твои выводы о "разах" немного приукрашены. И объясню почему ... небойсь под виндой, люниксом или макосом тестил? То-то и оно! В одном тесте тебе грузят обновление винды, в другом обновляют зеркала аптейтов люникса... В итоге замеряешь в том, что тебе "позволила" операционная система. Чтобы понимать о чем я говорю - приведу аналог. Дали близорукому бухгалтеру испытать на точность и разброс три дальнобойные винтовки с оптическим прицелом ... продолжение истории, думаю, очевидно. Это частая беда любителей бэйнчмарков. Им кажется, что увеличение количеств повторений может дать какое-то достоверное "среднее", ни на чем не обоснованная уверенность.

Более-менее достоверные результаты можно получить на ОСРВ, типа QNX. Там система заточена на "честное квантование" вычислений. А. как по мне, лучший вариант - это какая-то однозадачная ОС типа DOS с минимумом драйверов, которые насилуют прерывания таймера. И обязательно на железном (не виртуальном) железе.

Ну это так ... к слову

[mkudritsky]

Пока верхние сообщения не удалены автоудалением, выложу код программы поиска набора файлов по маске.
Без рекурсии.
Кстати, может программа и пригодится автору ветки. Ведь файловая система - это дерево.
Программа написана на C++, но переделывается на ansi C несложно (мне просто было лень оперировать с char* вместо строк и с char** вместо списка строк):
Софт, разумеется, кроссплатформенный (Win, Linux).

#if defined(_WIN32) || defined(_WIN64) || defined(__CYGWIN__)
#define WINDOWS
#elif defined(__linux__)
#define Linux
#elif defined(__APPLE__) || defined(__MACH__)
#define MacOS
#elif defined(__FreeBSD__)
#define FreeBSD
#elif defined(__ANDROID__)
#define Android
#elif defined(sun) || defined(__sun)
#if defined(__SVR4) || defined(__svr4__)
#define SOLARIS
#else
#define SunOS
#endif
#elif defined(__QNX__) || defined(__QNXNTO__)
#define QNX
#else
#error Unknown OS
#endif
 
#ifdef WINDOWS
#define _GNU_SOURCE
#endif
 
#include <string.h>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>
#include <sys/stat.h>
#include <dirent.h>
 
#ifndef WINDOWS
char cSl = '/';
#else
char cSl = '\\';
#endif
 
using namespace std;
 
//----------------------------------------------------------------------------------------------------
 
void  ListFiles(string path, bool AllDirs, list<string>* List, string name) {
// Функция поиска файлов с именем name (с маской) рекурсивно в каталоге path (ПОЛНОЕ ИМЯ) и ниже
// AllDirs=true - файлы ищем в текущем каталоге и рекурсивно ниже; иначе - только в текущем каталоге
// Найденные файлы сохраняются в списке List
   // Связанный список деревьев-директорий
   struct Tdir {
       DIR  *Dcurr;          // Текущая директория
       char *Dname;          // Имя текущей директории (без правого слэша)
       struct dirent *Fcurr; // Указатель по поддиректориям/файлам в текущей директории
       struct Tdir *Dpriv,   // Ссылка на родительскую директорию
                   *Dnext;   // Ссылка на дочернюю поддиректорию (заходим по одной поддиректории!)
   };
   // Определение типа ОС, вычисление слэша и обработка path
   while ((path.length() > 1) && (path[path.length() - 1] == cSl))
       path.erase(path.length() - 1);
   // Работа в начальной директории
   struct Tdir *pDIR, *pDcurr; // Начальная директория и текущая (под)директория
   pDIR =  (struct Tdir*)malloc(sizeof(struct Tdir));
   // Открываем начальную директорию
   pDIR->Dname = (char *)calloc(path.length() + 1, sizeof(char));
   strcpy(pDIR->Dname, path.c_str());
   pDIR->Dcurr = opendir(pDIR->Dname);
   if (pDIR->Dcurr == NULL) {
       free(pDIR->Dname);
       free(pDIR);
       return;
   }
   pDIR->Dnext = pDIR->Dpriv = NULL;
   // Читаем начальную директорию
   pDIR->Fcurr = readdir(pDIR->Dcurr);
   // Присваиваем текущей директории значение начальной
   pDcurr = pDIR;
   // Главный цикл продолжается до тех пор, пока не будет закрыта начальная директория
   while (pDIR->Fcurr != NULL) {
       string sPath;
       // Цикл по файлам/поддиректориям текущей директории
       while (pDcurr->Fcurr != NULL) {
           sPath = string(pDcurr->Dname);
           // Короткое имя очередного файла/поддиректории в текущей директории
           string sFcurr = pDcurr->Fcurr->d_name;
           // Полное имя очередного файла/поддиректории в текущей директории
           sPath.push_back(cSl); // Добавление слэша
           sPath = sPath + sFcurr;
           // Определяем атрибуты очередного файла/поддиректории в текущей директории
           struct stat attr;
           int iSt = stat(sPath.c_str(), &attr);
           // Дальнейшая работа - только если атрибуты определены правильно
           if (!iSt) {
               // Работа с очередной поддиректорией
               if (attr.st_mode & S_IFDIR) {
                   if ((sFcurr != ".") && (sFcurr != "..") && AllDirs ) {
                       // Переход в очередную дочернюю поддиректорию и делаем ее текущей директорией
                       pDcurr->Dnext = (struct Tdir*)malloc(sizeof(struct Tdir));
                       pDcurr->Dnext->Dname = (char *)calloc(sPath.length() + 1, sizeof(char));
                       strcpy(pDcurr->Dnext->Dname, sPath.c_str());
                       pDcurr->Dnext->Dcurr = opendir(pDcurr->Dnext->Dname);
                       if (pDcurr->Dnext->Dcurr != NULL) {
                           pDcurr->Dnext->Dnext = NULL;
                           pDcurr->Dnext->Dpriv = pDcurr;
                           // Переход в очередную дочернюю поддиректорию (становится текущей)
                           pDcurr = pDcurr->Dnext;
                       // Если очередную (дочернюю) поддиректорию не удается открыть - возвращаем память
                       } else {
                           free(pDcurr->Dnext->Dname);
                           free(pDcurr->Dnext);
                           pDcurr->Dnext = NULL;
                       }
                   }
               }
               // Работа с очередным файлом
               else {
                   // Сравнение шаблона и имени файла чувствительно к регистру!
                   bool bc = true, bz; // флаг добавления файла по маске и флаг проверки символа "*"
                   int iz = -1; // Символ, следующий сразу за (последовательностью) символом "*" (и "?" - необбязательный)
                   unsigned int ic = 0, in = 0, iv; // Счетчики символов sFcurr, name и числа символов "?"
                   if (name.length()) {
                       while ((ic < sFcurr.length()) && (in < name.length())) {
                           // Считаем символы "*" и "?" и запоминаем информацию об этом
                           iv = 0; bz = false;
                           while((in < name.length()) && ((name[in] == '*') || (name[in] == '?'))) {
                               // Есть символ "*"
                               if (name[in] == '*') {bz = true;}
                               // Считаем число символов "?"
                               else {iv++;}
                               in++;
                               // Запоминаем символ, следующий за последовательностью "*" (и "?")
                               if (bz) {iz = in;}
                           }
                           // Работа с символами sFcurr по части масок из подряд идущих "*" и "?"
                           if (bz) {
                               unsigned int iSum = 0; // Подсчет числа символов до name[in]
                               while ((ic < sFcurr.length()) && (in < name.length()) && (sFcurr[ic] != name[in]))
                                   {ic++; iSum++;}
                               if (iSum < iv)
                                   {bc = false; break;}
                           // Работа только с подряд идущими символами "?"
                           } else if (iv) {
                               ic += iv;
                               if (ic > sFcurr.length())
                                   {bc = false; break;}
                           }
                           // Проверка обычных символов
                           if ((ic < sFcurr.length()) && (in < name.length()) && (sFcurr[ic] != name[in])) {
                               if (iz < 0) {
                                   bc = false; break;
                               } else {
                                   in = iz;
                                   while ((ic < sFcurr.length()) && (in < name.length()) && (sFcurr[ic] != name[in]))
                                       { ic++; }
                                   continue;
                               }
                           }
                           // Переходы к следующим символам в строке и в маске
                           ic++; in++;
                       }
                   } else
                       {bc = false;}
                   // Проверка, что все символы проверяемой строки прочитаны
                   if (ic < sFcurr.length())
                       {bc = false;}
                   // Проверка, что все символы шаблона прочитаны (остаться могут только "*")
                   while (in < name.length()) {
                       if (name[in] != '*') {bc = false; break;}
                       in++;
                   }
                   if ( bc )
                       {List->push_back(sPath);}
               }
           }
           // Читаем очередной файл или поддиректорию в текущей директории
           pDcurr->Fcurr = readdir(pDcurr->Dcurr);
       }
       // Закрытие текущей директории
       closedir(pDcurr->Dcurr);
       pDcurr->Dcurr = NULL;
       // Переход в родительскую директорию, если она существует
       if (pDcurr->Dpriv) {
           pDcurr = pDcurr->Dpriv;
           free(pDcurr->Dnext->Dname);
           free(pDcurr->Dnext);
           pDcurr->Dnext = NULL;
           pDcurr->Fcurr = readdir(pDcurr->Dcurr);
       }
   }
   free(pDIR->Dname);
   free(pDIR);
}
//---------------------------------------------------------------------------

[Qraizer]

Цитата mkudritsky @ 08.06.22, 17:16

Программа написана на C++ ...

А чё не std::filesystem? Не пришлось бы городить зоопарк на препроцессоре. Какие-то malloc/free зачем-то... Я бы не назвал это C++, скорее суржик какой-то на двух языках.

[Majestio]

Цитата mkudritsky @ 08.06.22, 17:16

Ведь файловая система - это дерево.

Это было так раньше В *nix давно существовали хард и софт линки. В винде, на NTFS тоже можно делать точки соединения (по сути аналог хард-линков). Поэтому при обходе нужно это нужно учитывать, особенно если "потомок" включает линком верхние родительские каталоги.

Для наглядности можно это понаблюдать в своей винде, на системном диске, обычно С:

DIR /AL /S C:\

А оно вон оно как

[Gonarh]

Цитата Qraizer @ 06.06.22, 17:11

P.S. Это к вопросу о полезности рекурсий. Любой рекурсивный алгоритм может быть переведён в итерационный и наоборот. Вопрос же "а нужно ли" всегда не имеет однозначного ответа.

Иногда использую рекурсию, когда точно уверен что глубина не будет больше 8-10 раз.

[shm]

А чем предмет холивара, можно мне объяснить? В процессоре нет никакой рекурсии, есть стек на базе которого она и получается. Тот же самый стек можно сделать явно в высокоуровневом коде, чтобы "развернуть" рекурсию (для хвостовой можно и без стека). В некоторых случаях такой код будет работать чуть быстрее (и есть возможность явно контролировать потребляемую память). Хотя современные оптимизаторы компиляторов сами могут это делать, по крайней мере для хвостовой рекурсии точно.

Сообщение отредактировано: shm - 09.06.22, 15:26

[mkudritsky]

Времени пока маловато.
Поэтому выложу поиск файлов, но уже не по маске, а по расширению.
Поиск при помощи рекурсии в Builder.
А то поиск файлов без рекурсии выложен в теме, а с рекурсией - нет.

//---------------------------------------------------------------------------
 
void  ListFilesBuilder(AnsiString path, bool AllDirs, TStringList* List, AnsiString EXT) {
// Функция реализует поиск файлов *.EXT рекурсивно в каталоге path и ниже средствами Builder
// AllDirs=true - файлы ищем в текущем каталоге и рекурсивно ниже; иначе - только в текущем каталоге
// Найденные полные имена файлов помещаются в список List
 
   // Создается объект для поиска нужных файлов и каталогов
   TSearchRec sr;
   // Инициализация поиска - ищется любой файл в директории path.
   //  Каталоги тоже ищутся. Если поиск завершился успешно, то делаем:
   if (FindFirst(path+"*.*", faAnyFile, sr) == 0) {
      do {
          if (sr.Attr & faDirectory) {
              // Если найдена директория, то:
                 // если она не равна текущей Dir и вышележащей Dir, делаем:
              if ( (sr.Name != ".") && (sr.Name != "..") && AllDirs ) {
                  // РЕКУРСИВНО вызываем функцию, но зайдя в найденную директорию
                  ListFilesBuilder(path + sr.Name + "\\", true, List, EXT);
              }
          } else {
              // Если же найдена НЕ директория (а файл), то делаем:
              // Вычисляем расширение найденного файла
              AnsiString Ext = ExtractFileExt(sr.Name).LowerCase();
              if ( Ext == EXT ) {
                  // Если это расширение равно *.txt, то добавляем полное имя файла в Список
                  List->Add(path + sr.Name);
              }
          }
      // Если поиск очередного файла или директории успешен, то - в начало цикла do
      } while(FindNext(sr) == 0);
      // Закрываем процедуру поиска
      FindClose(sr);
   }
   Application->ProcessMessages();
}
//---------------------------------------------------------------------------

Сообщение отредактировано: mkudritsky - 09.06.22, 16:08

[Qraizer]

Попробовал вникнуть в код mkudritsky. Если его рассматривать как Cшный, то вполне приемлемый. Избавиться от list<> и string разве что, и всё путём. Для сравнения на Плюсах:

#include <filesystem>
#include <string>
#include <list>
#include <queue>
#include <regex>
 
namespace fs = std::filesystem;
using namespace std::literals;
 
void makeList(std::list<fs::path>& list, std::string wildMask)
{
  using fs_do = fs::directory_options;
 
  for (auto i = 0; i < wildMask.length(); ++i)
    if      (wildMask[i] == '.') wildMask.replace(i++, 1, "\\."s);
    else if (wildMask[i] == '*') wildMask.replace(i++, 1, ".*?"s), ++i;
    else if (wildMask[i] == '?') wildMask[i] = '.';
 
  std::queue<fs::directory_entry> dirs;
  std::regex mask(wildMask);
 
  dirs.push(fs::directory_entry("."s));
  do
  {
    fs::path curDir = dirs.front();
 
    dirs.pop();
    for (fs::directory_iterator it(curDir, fs_do::skip_permission_denied); it != fs::directory_iterator(); ++it)
    {
      if ( it->is_directory())
        dirs.push(*it);
      if (!it->is_directory() && std::regex_match(it->path().string(), mask))
        list.emplace_back(*it);
    }
  } while(!dirs.empty());
}

Делов-то.
А рекурсивный ненамного проще:

void makeList(std::list<fs::path>& list, std::string wildMask)
{
  using fs_do = fs::directory_options;
 
  for (auto i = 0; i < wildMask.length(); ++i)
    if      (wildMask[i] == '.') wildMask.replace(i++, 1, "\\."s);
    else if (wildMask[i] == '*') wildMask.replace(i++, 1, ".*?"s), ++i;
    else if (wildMask[i] == '?') wildMask[i] = '.';
 
  std::regex mask(wildMask);
 
  for (fs::recursive_directory_iterator it("."s, fs_do::skip_permission_denied); it != fs::recursive_directory_iterator(); ++it)
  {
    if (it->is_directory()) continue;
    if (std::regex_match(it->path().string(), mask))
      list.emplace_back(*it);
  }
}

Сравнивать производительность лень: после первого же запуска ОСь закеширует системные структуры, заманаешься нейтрализовывать.

[Qraizer]

Сравнил-таки. Запустил один раз в холостую и потом уже с замером времени.
Рекурсивный вариант обогнал нерекурсивный на 0,8 секунды при общем времени исполнения 28 секунд. Поиск осуществлялся по маске *.c, найдено в общей сложности чуть более 50000 файлов. В пределах погрешности разницы не замечено. Но вот Cшный код не порадовал, исполнялся втрое медленнее. Понятно, что отнюдь не из-за IO, а из-за неоптимального алгоритма. Слишком много хипа, копирований, кастов char* к std::string итп. И нашёл не все, что по-видимому связано с недочётами в обработке входов dirent. Так, я не увидел заходов в каталоги с русскими буквами и файлов с несколькими точками в именах, типа «package_ti.sysbios.family.c28.f28m35x.c».
Это было на SSD. Дома проверю на HDD

Добавлено 10.06.22, 18:22
К слову, в моих примерах недочёт: не учитывается разница в регистре символов.

[mkudritsky]

Немного своих соображений о полностью ansi C коде.
И если для работы со строкой char* существует полно стандартных функций, то вот как вести список найденных строк?
Ясное дело, что тип char** не подойдет, так как непонятно - как эффективно выделять память для разного количества файлов?
Ведь в коде

(char **)calloc(Nfiles, sizeof(char *));

надо в программе сразу задать максимальное число файлов Nfiles, что до начала поиска неизвестно...

На ум приходит разве лишь создание и ведение связанного списка:

// Список файлов
struct pListF {
    // Полное имя найденного файла
    char *sNameF;
    struct pListF
        // Ссылка на структуру с предыдущим файлом (NULL для первого найденного файла)
        *pPrivF,
        // Ссылка на структуру со следующим файлом (NULL для завершения связанного списка)
        *pNextF;
};

В принципе, первый указатель с списке не нужен, если достаточно работы со списком в одном направлении.
Уничтожаться этот связанный список должен без проблем функцией free (после того, как он становится в программе не нужным).

P.S. В свое время мне было лень ковыряться с чистым ansi C и я принял решение воспользоваться стандартными средствами C++.

Сообщение отредактировано: mkudritsky - 11.06.22, 01:49

[Qraizer]

Цитата Qraizer @ 10.06.22, 18:19

Это было на SSD. Дома проверю на HDD

На HDD разница оказалась лишь количественная, качественно картина та же. Впрочем, фигня это. Понятно, что условия должны быть одинаковы, но предварительный запуск, чтобы одинаковость условий подразумевала кешированность служебных записей тома, ни разу не достоверно отражают реальное положение дел на практике, когда такой кешированности обычно нет.
Поэтому я взял себя в руки и ребутал машину каждый раз. И ждал окончания всех стартовых процедур. Ну, т.е. до прекращения дисковых операций. В итоге рекурсивная версия выдала 114 секунд по разделу с ~20000 файлов *.c (при общем количестве ~615000), нерекурсивный, увы, аж, 172, т.е. в полтора раза медленнее. Надо будет ещё то же с SSD сделать. Но что-то мне подсказывает, что в Win10 дисковый драйвер давно уже оптимизирован именно под рекурсивный обход дерева каталогов. По крайней мере на NTFS, где файловые атрибуты (кроме атрибутов данных разве что) практически всегда лежат в MFT. Просто потому что приложения делают это обычно именно так.

Добавлено 14.06.22, 05:33
P.S. На случай, если вдруг важно, учитывать ли разницу в регистре символов при поиске по маске, можно чуть переделать создание регулярки:

std::regex mask(wildMask, noSens ? std::regex_constants::ECMAScript | std::regex_constants::icase
                                 : std::regex_constants::ECMAScript);

Добавлено 14.06.22, 05:51
P.P.S. Если вдруг надо в ран-тайм определять, различает ли файловая система регистр символов в именах файлов, то тут возникают сложности, т.к. по-хорошему нужно учитывать нюансы локали пользователя, а это отнюдь не однозначная процедура. К примеру, разница между I и i в английском абсолютно не совпадает с таковой в турецком, где есть полный комплект из I, İ, i и ı. Так что я бы рекомендовал сделать предварительно

std::locale::global(std::locale(".utf8"));

Но если можно ограничиться лишь стандартным комплектом символов, то что-то типа:

  fs::path tempName1(fs::temp_directory_path() / "CheckCaseSens"s),
           tempName2(fs::temp_directory_path() / "checkcasesens"s);
  std::ofstream(tempName1, std::ios::ate);
  std::ofstream(tempName2, std::ios::ate);
  bool isNoCaseSens = fs::equivalent(tempName1, tempName2);
 
  fs::remove(tempName1);
  if (!isNoCaseSens) fs::remove(tempName2);

должно помочь. Поосторожнее только с последними двумя строчками.

Добавлено 14.06.22, 05:56

Цитата mkudritsky @ 11.06.22, 01:47

Ясное дело, что тип char** не подойдет, так как непонятно - как эффективно выделять память для разного количества файлов?

Запросто подойдёт. Как и для любого динамически изменяющего свой размер массива, realloc() прекрасно умеет увеличивать размер массива указателей, если есть на это память, конечно. Другое дело, что это будет уже не список, но по факту массив указателей будет эффективней списка указателей. В отличие от массива std::string, который очень вряд ли будет эффективней списка std::string.