алгоритм сопоставления префикса и имени со списком имен
У меня есть std :: vector всех файлы в каталоге:
// fileList
folder/file1
folder/file2
file3
file4.ext
и std :: set имен файлов и одинаковые для всех используемых префиксов папок:
// 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 ) );
(быстрый псевдокод-иш) Это кажется очень неэффективным, есть ли лучший способ сделать эти совпадения?
Спасибо!
PS: еще лучше было бы отслеживать двойные значения, чтобы я мог предупредить пользователя об этом.
4 ответа
Одна область, в которой вы не совсем ясны, заключается в следующем:
- Учитывая set1 и set2, как описано выше, что, если в fileList есть "file4.ext" и "folder\ файл4.расш". Хотели бы вы оба? Или список файлов в 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;
}
}
Простой: выполнить итерацию по fileList один раз, сгенерировать префикс (установить 2 записи) и файл name (установите 1 запись) и проверьте, входят ли они в соответствующие наборы. Если оба совпадают, у вас есть совпадение, поэтому верните его; в противном случае ничего не возвращать для этого элемента.
Кроме того, это решает проблему «двойников», о которой вы упомянули.
Просто используйте вспомогательную хеш-таблицу, чтобы получить время выполнения 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).
Ваши ожидаемые результаты выглядят так, как будто вы ищете суффиксы в FileList, которые соответствуют строкам в set1 и set2, несущественны.
Размер множества set2 определяет, каким путем следует идти для фактического сопоставления. Если он достаточно мал, вы можете превратить его в регулярное выражение и либо добавить привязки регулярного выражения для соответствия концу строки, либо предварительно обработать FileList (путем извлечения только имени файла, но также сохранения исходной строки для результата). Вы также можете поменять местами строки в обоих списках, чтобы они действительно соответствовали префиксу.
Если set2 большой, вам нужно построить из него хеш-таблицу, и в этом случае вам нужно предварительно обработать FileList, чтобы извлечь имена файлов как «ключи», которые вы попытаетесь «найти» в хеш-таблице. Убедитесь, что вы обрабатываете чувствительность к регистру, если это потенциальная проблема (например, преобразование всех ключей в верхний регистр). После этого просто распечатайте каждую строку в FileList, для которой этот ключ присутствует в хэш-таблице, построенной из набора 1.
Если набор 2 действительно имеет какое-то значение (в этом случае ваш ожидаемый результат неверен), то это второй pass для фильтрации результатов первого прохода - с другой хеш-таблицей для 2-го фильтра.