алгоритм сопоставления префикса и имени со списком имен

Question

У меня есть std::vector<std::string> всех файлов в каталоге:

// fileList
folder/file1
folder/file2
file3
file4.ext

и std::set<std::string> имен файлов и то же самое для всех используемых префиксов папок:

// set1
file2
file4.ext

// set2
folder

Мне нужно сгенерировать полные (относительные) пути ко ВСЕМ файлам в set1, но я не вижу способа сделать это без итерации по set2 set1.size() раз, умноженному на fileList.size()

ОБНОВЛЕНИЕ: некоторые пояснения:

Ожидаемый вывод для приведенного выше примера:

folder/file2
file4.ext

Предлагаемое (неэффективное?) Решение, возможно, слишком многословное и с глупой реализацией:

// pseudo-code!
vector<string> allpossibleFullPaths( set1.size()*set2.size() );
vector<string> output;
foreach( prefix_in_set2 )
    foreach( filename_in_set1 )
        allpossibleFullpaths.push_back( set2[i] + "/" set1[i] )

foreach( filename_in_fileList )
    files.push_back( find( fileList[i] in allpossibleFullPaths ) );

(быстрый псевдокод-ish) Это кажется очень неэффективным, есть ли лучший способ сделать эти совпадения?

Спасибо!

PS: лучше бы еще был способ отследить удвоения, чтобы я мог предупредитьпользователь об этом.

Answer 1

Одна область, о которой вам неясно, это:

• Учитывая set1 и set2, как описано выше, что если fileList имеет «file4.ext» и «folder \ file4.ext». Хотели бы вы оба? Или список файлов в set1 гарантированно будет уникальным?

Предполагая, что вы хотите оба, псевдокод:

 foreach(pathname in fileList)
    separate pathname into path & filename.
    if path is not empty, but not in set2, skip to next pathname.
    if filename is in set1, output pathname.

Поскольку поиск набора должен быть O (1), общая сложность составляет O (2 * fileList.Length)

Если имена файлов в set1 уникальны, вы можете посчитать количество выходных путей и выйти досрочно при достижении set1.Length.

Может показаться нелогичным проходить по самой длинной коллекции, но он также имеет самый медленный поиск, поэтому операции с fileList должны быть сведены к минимуму.

ОБНОВЛЕНИЕ: Вот полный рабочий код C ++ (включая и использованные)

void ListFiles()
{
    vector<string> fileList;
    fileList.push_back("folder/file1");
    fileList.push_back("folder/file2");
    fileList.push_back("file3");
    fileList.push_back("file4.ext");

    set<string> set1;
    set1.insert("file2");
    set1.insert("file4.ext");

    set<string> set2;
    set2.insert("folder");

    for(vector<string>::iterator iter = fileList.begin();
        iter != fileList.end();
        ++iter)
    {
        string pathname = *iter;
        string filename;
        string path;
        size_t pos = pathname.find('/');
        if (pos == string::npos || pos == 0)
            filename = pathname;
        else
        {
            path = pathname.substr(0, pos);
            if (set2.find(path) == set2.end())
                continue;
            filename = pathname.substr(pos+1);
        }
        if (set1.find(filename) != set1.end())
            cout << pathname << endl;
    }

}

Answer 2

Простой: переберите fileList один раз, сгенерируйте префикс (запись набора 2) и имя файла (запись набора 1) и проверьте, находятся ли они в соответствующих наборах. Если оба есть, у вас есть совпадение, так что верните его; в противном случае ничего не возвращайте для этого товара.

Кроме того, это решает проблему двойников, о которой вы упомянули.

Answer 3

Ваши ожидаемые результаты выглядят так, как будто вы ищете суффиксы в FileList, которые соответствуют строкам в set1 и set2, несущественны.

Размер set2 решает, какой путь выбрать для фактического соответствия.Если он достаточно мал, вы можете превратить его в регулярное выражение и либо добавить привязки регулярного выражения, чтобы соответствовать концу строки, либо предварительно обработать FileList (путем извлечения только имени файла, но также сохраняя исходную строку для результата).Вы также можете обратить строки в обоих списках так, чтобы они действительно соответствовали префиксам.

Если set2 велико, вам нужно построить из него хеш-таблицу, и в этом случае вам нужно предварительно обработать FileList для извлеченияимена файлов в виде «ключей», которые вы попытаетесь «найти» в хеш-таблице.Убедитесь, что вы обрабатываете чувствительность к регистру, если это потенциальная проблема (например, преобразование всех ключей в верхний регистр).С этим на месте просто распечатайте каждую строку в FileList, для которой ее ключ присутствует в сборке хеш-таблицы из набора 1.

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

Answer 4

Просто используйте вспомогательную хэш-таблицу для получения времени выполнения set1.size () + fileList.size ()

Псевдокод:

unordered_set<string, list<string> > hash;
foreach (i in fileList):
  (fprex, fname) = split(i)
  hash[fname].push_back(fprex)
foreach (j in set1):
  a = hash.contains(j)
  if (a != hash.end())
    foreach(k in a)
       print k +'/' + j;

Или что-то в этом роде. unordered_set доступен в Boost (или tr1), а операция вставки / поиска выполняется в O (1).