代码之家 › 专栏 › 技术社区 › rubenvb

将前缀和名称与名称列表匹配的算法

algorithm c++

rubenvb · 技术社区 · 14 年前

我有一个 std::vector<std::string> 目录中的所有文件:

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

和A 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) 这似乎很内敛,有没有更好的方法让这些比赛?

谢谢!

附言:更好的还是一种跟踪双打的方法,这样我就可以警告用户。

4 回复 | 直到 14 年前

James Curran 14 年前

你不清楚的一个方面是:

给定上述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;
    }

}

strager 14 年前

简单:迭代 fileList 一次,生成前缀(set 2 entry)和文件名(set 1 entry),并检查它们是否在各自的集合中。如果两者都匹配,则返回匹配项;否则,不返回该项的任何内容。

此外,这还处理了您提到的“双精度”问题。

maxschlepzig 14 年前

只需使用助手哈希表获取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;

或者类似的事情。在boost(或tr1)中提供无序_集,在o(1)中提供插入/查找操作。

ZXX 14 年前

您期望的结果看起来像是在文件列表中搜索与set1和set2中的行匹配的后缀是无关紧要的。

set2的大小决定了实际匹配的方向。如果它相当小,您可以将其转换为regex,并添加regex锚以匹配字符串结尾或预处理文件列表(只提取文件名,同时保留结果的原始字符串)。您还可以反转两个列表中的字符串,使其实际上成为前缀匹配。

如果set2很大,那么您需要从中构建哈希表,在这种情况下,您需要预处理文件列表以提取文件名为“keys”,您将尝试在哈希表中“find”。如果这是一个潜在的问题,请确保处理大小写敏感问题(如将所有键转换为大写)。有了它,只需打印出文件列表中的每一行,它的键就出现在从集合1构建的哈希表中。

如果set 2确实有一些意义(在这种情况下,您的预期结果是错误的),那么这是第二次传递来筛选第一次传递的结果-使用第二个过滤器的另一个哈希表。