DFS需求背景
在开发过程中难免会遇到类似 上传文件夹的功能,但是上传文件夹会遇到一种情况
1
2
3
1. 如果文件里面包含子文件夹的N层嵌套
2. 如何过滤非空文件夹
3. 如何处理根层文件夹没有文件那么文件目录也需要创建
举例例子
这种文件夹如何 此文件夹为空且是叶子结点
走上传逻辑(就是发个 http请求 create一下 dir就行了) 我们要的结果是 过滤出这个路径走上传逻辑 创建一下这个最深处目录 那么下次再遇到它的父目录 /1/
的话应该就不用创建了.
还有一种情况
eg: ~/Downloads/A/B/C/ 里面有个 1.txt
路径是: ~/Downloads/A/B/C/1.txt
一般如果广度优先做上传的话 Downloads、A、B、C分别要发4个http请求 如果深度优先发一个上传这个文件~/Downloads/A/B/C//A/B/C/1.txt就可以了,因为一般server都会做 容错处理发现父目录有没有没有就创建之类的逻辑。
算法
不要害怕, 很简单 一般我们处理这种问题都是采用自己写的递归算法, 估计是鄙人算法不咋好没搞出来什么好的递归,最后找到了 苹果自带的递归方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//搞个点击事件 在这里我拿macOS上的 文件选择面板做一下测试
- (IBAction)dfsAction:(NSButton *)sender
{
NSOpenPanel *panelPath = [NSOpenPanel openPanel];
[panelPath setCanChooseFiles:YES];
[panelPath setCanChooseDirectories:YES];
[panelPath setTitle:@"上传文件选择"];
[panelPath setCanCreateDirectories:YES];
[panelPath setPrompt:@"上传"];
[panelPath setMessage:@"这就是message"];
panelPath.allowsMultipleSelection = YES;
[panelPath beginSheetModalForWindow:self.window completionHandler:^(NSInteger result) {
if (result == NSFileHandlingPanelOKButton) {
[self dfsUrls:panelPath.URLs];
}
}];
}
然后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
选择文件夹的目录
@param urls 所有选中的目录/文件URL
*/
- (void)dfsUrls:(NSArray *)urls
{
//开一个线程在异步处理这些耗时任务
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
NSLog(@"所有URLs%@",urls);
if (urls.count == 0) { return; }
NSTimeInterval currentTime = [[NSDate date] timeIntervalSince1970];
//深度遍历
NSFileManager *fileManager = [NSFileManager defaultManager];
NSMutableArray *urlDirFiles = [[NSMutableArray alloc] initWithCapacity:0];
NSArray *keys = [NSArray arrayWithObjects:NSURLIsDirectoryKey,NSURLParentDirectoryURLKey, nil];
NSUInteger *total = 0;
for (NSURL *localUrl in urls) {
NSDirectoryEnumerator *enumerator = [self enumeratorPathByFileManager:fileManager atURL:localUrl propertiesForKeys:keys options:0];
//这里包含的元素是 有子文件的忽略父路径结点
//eg: /A/1/2/ (这个就需要移除) /A/1/2/sun.txt(保留这个文件即可)
for (NSURL *url in enumerator) {
total++;
NSError *error;
NSNumber *isDirectory = nil;
if (![url getResourceValue:&isDirectory forKey:NSURLIsDirectoryKey error:&error]) {
// handle error
}
//是否为文件夹
if ([isDirectory boolValue]) {
//方案1
// NSDirectoryEnumerator *dirEnumerator = [self enumeratorPathByFileManager:fileManager atURL:url propertiesForKeys:@[NSURLIsDirectoryKey] options:NSDirectoryEnumerationSkipsSubdirectoryDescendants];
// if (dirEnumerator.allObjects.count > 0) {
// NSLog(@"文件夹内有文件,忽略此条路径 %@",[url path]);
// } else {
// [urlDirFiles addObject:[url path]];
// }
//方案2
NSError *error = nil;
NSArray *listOfFiles = [fileManager contentsOfDirectoryAtPath:[url path] error:nil];
if (listOfFiles != nil && listOfFiles.count == 0) {
[urlDirFiles addObject:[url path]];
} else if (error == nil){
NSLog(@"文件夹内有文件,忽略此条路径 %@",[url path]);
} else {
NSLog(@"文件遍历该层出错:%@",error);
}
} else {
[urlDirFiles addObject:[url path]];
}
}
NSLog(@"所有可上传文件列表:\n%@",urlDirFiles);
}
NSTimeInterval nowTime = [[NSDate date] timeIntervalSince1970];
NSLog(@"\n文件数量:%zd 遍历总数:%zd\n耗时:%.2f 秒",urlDirFiles.count,total,(nowTime - currentTime));
total = 0;
dispatch_async(dispatch_get_main_queue(), ^{
NSLog(@"scan end");
});
});
}
接下来就是最核心的代码块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
- (NSDirectoryEnumerator *)enumeratorPathByFileManager:(NSFileManager *)fileManager
atURL:(NSURL *)url
propertiesForKeys:(nullable NSArray<NSString *> *)keys
options:(NSDirectoryEnumerationOptions)mask
{
NSDirectoryEnumerator *enumerator = [fileManager
enumeratorAtURL:url
includingPropertiesForKeys:keys
options:mask
errorHandler:^(NSURL *url, NSError *error) {
// Handle the error.
// Return YES if the enumeration should continue after the error.
NSLog(@"深度遍历出错%@",error);
return YES;
}];
return enumerator;
}
NSDirectoryEnumerator
是一个路径枚举迭代器
talk is cheap, show me the result.
下面是我扫描本地下载
目录的结果
结果还是比较快的
单从数据上来讲 比广度优先节省至少7万次Http请求
我怀疑是macOS对系统目录有索引或者缓存 第二次扫码速度比较快
总结
总体来看,效果还可以,如果你有更好的算法来解决这种问题 欢迎@我 或者发邮件我也学习一下.
也可学一下:Swift Depth First Search