@Stephen C: Ниже согласно вашему запросу, мой тест код, который я говорил о в комментариях (C# - не Java).
Обратите внимание, что для лучшей точности следует использовать секундомер вместо даты и времени, но в остальном это нормально.
Я не тестировал, если итерация предоставляет файлы с одинаковыми номерами, как рекурсия, но должна.
На самом деле, если вы обратите внимание на медианную, вы заметите, что это уже начинает показываться только с очень небольшим количеством файлов. (папка «Мой рабочий стол» содержит 2210 файлов, 415 папок, 3,2 ГБ, большинство из них - большие файлы в папке загрузки, AppData и большее количество файлов из-за большого проекта C# [почтового сервера] на моем рабочем столе).
Чтобы получить номера, о которых я говорил в комментарии, установите cygwin (со всем [примерно 100 ГБ, я думаю]) и индексирую папку cygwin.
Как уже упоминалось в комментариях, это не совсем правильно говорить, это не имеет значения.
Хотя для небольшого дерева каталогов рекурсия пренебрежимо эффективнее, чем итерация (порядка нескольких десятков миллисекунд), для очень большого дерева рекурсия - это минуты (и, следовательно, заметно) медленнее, чем итерация. Не все сложно понять, почему и то. Если вам нужно выделять и возвращать новый набор переменных стека, каждый раз вызывайте функцию и сохраняйте все предыдущие результаты до тех пор, пока вы не вернетесь, вы, конечно, медленнее, чем когда вы инициируете структуру стека в куче один раз и используйте это для каждой итерации.
Дерево не должно быть патологически глубоким, чтобы этот эффект был замечен (в то время как медленная скорость не является переполнением стека, ее очень негативные последствия мало чем отличаются от StackOverflow-Bug). Также я бы не назвал наличие большого количества файлов «патологическими», потому что если вы делаете указатель на своем главном диске, у вас, естественно, будет много файлов. У вас есть HTML-документация, и количество файлов взрывается. Вы обнаружите, что во множестве файлов итерация завершается менее чем за 30 секунд, в то время как для рекурсии требуется приложение. 3 минуты.
using System;
using System.Data;
using System.Linq;
namespace IterativeDirectoryCSharp
{
public class SearchStrategy
{
//Iterative File and Folder Listing in VB.NET
public static bool IterativeSearch2(string strPath)
{
System.IO.DirectoryInfo dirInfo = new System.IO.DirectoryInfo(strPath);
System.IO.FileSystemInfo[] arrfsiEntities = null;
arrfsiEntities = dirInfo.GetFileSystemInfos();
// Creates and initializes a new Stack.
System.Collections.Stack strLastPathStack = new System.Collections.Stack();
System.Collections.Stack iIndexStack = new System.Collections.Stack();
int iIndex = 0;
int iMaxEntities = arrfsiEntities.Length;
do
{
while (iIndex < iMaxEntities)
{
if (arrfsiEntities[iIndex].Attributes == System.IO.FileAttributes.Directory)
{
//Console.WriteLine("Searching directory " + arrfsiEntities[iIndex].FullName);
strLastPathStack.Push(System.IO.Directory.GetParent(arrfsiEntities[iIndex].FullName).FullName);
strLastPathStack.Push(arrfsiEntities[iIndex].FullName);
iIndexStack.Push(iIndex);
dirInfo = null;
Array.Clear(arrfsiEntities, 0, arrfsiEntities.Length);
dirInfo = new System.IO.DirectoryInfo(strLastPathStack.Pop().ToString());
arrfsiEntities = dirInfo.GetFileSystemInfos();
iIndex = 0;
iMaxEntities = arrfsiEntities.Length;
continue;
}
else
{
//Console.WriteLine(arrfsiEntities[iIndex].FullName);
}
iIndex += 1;
} // Whend
dirInfo = null;
Array.Clear(arrfsiEntities, 0, arrfsiEntities.Length);
// Dont try to do move the next line in the loop while/until statement, null reference when pop on an empty stack...
if (strLastPathStack.Count == 0)
break;
dirInfo = new System.IO.DirectoryInfo(strLastPathStack.Pop().ToString());
arrfsiEntities = dirInfo.GetFileSystemInfos();
iIndex = (int)iIndexStack.Pop() + 1;
iMaxEntities = arrfsiEntities.Length;
} // End do
while (true);
return true;
} // End Function IterativeSearch2
public static bool IterativeSearch1(string path)
{
System.IO.DirectoryInfo dirInfo = new System.IO.DirectoryInfo(path);
System.IO.FileSystemInfo[] arrfsiEntities = null;
arrfsiEntities = dirInfo.GetFileSystemInfos();
// Creates and initializes a new Stack.
System.Collections.Stack myStack = new System.Collections.Stack();
//Console.WriteLine("Stack is empty when \t stack.count={0}", myStack.Count);
int iIndex = 0;
int iMaxEntities = arrfsiEntities.Length - 1;
do
{
for (iIndex = 0; iIndex <= iMaxEntities; iIndex += 1)
{
if (arrfsiEntities[iIndex].Attributes == System.IO.FileAttributes.Directory)
{
//Console.WriteLine("Searching directory " + arrfsiEntities[iIndex].FullName);
myStack.Push(arrfsiEntities[iIndex].FullName);
}
else
{
//Console.WriteLine("{0}", arrfsiEntities[iIndex].FullName);
}
} // Next iIndex
dirInfo = null;
Array.Clear(arrfsiEntities, 0, arrfsiEntities.Length);
// Dont try to do move the next line in the loop while/until statement, null reference when pop on an empty stack...
if (myStack.Count == 0)
break;
dirInfo = new System.IO.DirectoryInfo(myStack.Pop().ToString());
arrfsiEntities = dirInfo.GetFileSystemInfos();
iIndex = 0;
iMaxEntities = arrfsiEntities.Length - 1;
}
while (true);
return true;
} // End Function IterativeSearch1
//Recursive File and Folder Listing VB.NET
public static bool RecursiveSearch(string path)
{
System.IO.DirectoryInfo dirInfo = new System.IO.DirectoryInfo(path);
//System.IO.FileSystemInfo fileObject = default(System.IO.FileSystemInfo);
foreach (System.IO.FileSystemInfo fsiThisEntityInfo in dirInfo.GetFileSystemInfos())
{
if (fsiThisEntityInfo.Attributes == System.IO.FileAttributes.Directory)
{
//Console.WriteLine("Searching directory " + fsiThisEntityInfo.FullName);
RecursiveSearch(fsiThisEntityInfo.FullName);
}
else
{
//Console.WriteLine(fsiThisEntityInfo.FullName);
}
} // Next fiThisFileInfo
return true;
} // End Function RecursiveSearch
// http://forums.asp.net/p/1414929/3116196.aspx
public class TimeFrame
{
public DateTime dtStartTime;
public DateTime dtEndTime;
public TimeFrame(DateTime dtStart, DateTime dtEnd)
{
this.dtStartTime = dtStart;
this.dtEndTime = dtEnd;
} // End Constructor
} // End Class TimeFrame
// Small amount of files
// Iter1 Iter2 Recurs.
// Median 1206.231 3910.367 1232.4079
// Average 1216.431647 3940.147975 1239.092354
// Minimum 1172.5827 3832.0984 1201.2308
// Maximum 1393.4091 4400.4237 1440.3386
public static System.Data.DataTable TestStrategies(string strDirectoryToSearch)
{
System.Data.DataTable dt = new System.Data.DataTable();
System.Collections.Generic.Dictionary<int, string> dictResults = new System.Collections.Generic.Dictionary<int, string>();
dt.Columns.Add("TestRun", typeof(string));
dt.Columns.Add("IterativeSearch1", typeof(double));
dt.Columns.Add("IterativeSearch2", typeof(double));
dt.Columns.Add("RecursiveSearch", typeof(double));
System.Data.DataRow dr = null;
System.Collections.Generic.Dictionary<string, TimeFrame> dictPerformance = null;
for (int i = 0; i < 100; ++i)
{
dr = dt.NewRow();
dr["TestRun"] = i + 1;
dictPerformance = new System.Collections.Generic.Dictionary<string, TimeFrame>();
DateTime startTime;
DateTime endTime;
Console.WriteLine("*********************************************************");
startTime = DateTime.Now;
IterativeSearch1(strDirectoryToSearch);
endTime = DateTime.Now;
dictPerformance.Add("IterativeSearch1", new TimeFrame(startTime, endTime));
Console.WriteLine("*********************************************************");
startTime = DateTime.Now;
IterativeSearch2(strDirectoryToSearch);
endTime = DateTime.Now;
dictPerformance.Add("IterativeSearch2", new TimeFrame(startTime, endTime));
Console.WriteLine("*********************************************************");
startTime = DateTime.Now;
RecursiveSearch(strDirectoryToSearch);
endTime = DateTime.Now;
dictPerformance.Add("RecursiveSearch", new TimeFrame(startTime, endTime));
Console.WriteLine("*********************************************************");
string strResult = "";
foreach (string strKey in dictPerformance.Keys)
{
TimeSpan elapsedTime = dictPerformance[strKey].dtEndTime - dictPerformance[strKey].dtStartTime;
dr[strKey] = elapsedTime.TotalMilliseconds;
strResult += strKey + ": " + elapsedTime.TotalMilliseconds.ToString() + Environment.NewLine;
} // Next
//Console.WriteLine(strResult);
dictResults.Add(i, strResult);
dt.Rows.Add(dr);
} // Next i
foreach(int iMeasurement in dictResults.Keys)
{
Console.WriteLine("Measurement " + iMeasurement.ToString());
Console.WriteLine(dictResults[iMeasurement]);
Console.WriteLine(Environment.NewLine);
} // Next iMeasurement
double[] adblIterSearch1 = dt
.AsEnumerable()
.Select(row => row.Field<double>("IterativeSearch1"))
.ToArray();
double[] adblIterSearch2 = dt
.AsEnumerable()
.Select(row => row.Field<double>("IterativeSearch2"))
.ToArray();
double[] adblRecursiveSearch = dt
.AsEnumerable()
.Select(row => row.Field<double>("RecursiveSearch"))
.ToArray();
dr = dt.NewRow();
dr["TestRun"] = "Median";
dr["IterativeSearch1"] = Median<double>(adblIterSearch1);
dr["IterativeSearch2"] = Median<double>(adblIterSearch2);
dr["RecursiveSearch"] = Median<double>(adblRecursiveSearch);
dt.Rows.Add(dr);
dr = dt.NewRow();
dr["TestRun"] = "Average";
dr["IterativeSearch1"] = dt.Compute("Avg(IterativeSearch1)", string.Empty);
dr["IterativeSearch2"] = dt.Compute("Avg(IterativeSearch2)", string.Empty);
dr["RecursiveSearch"] = dt.Compute("Avg(RecursiveSearch)", string.Empty);
dt.Rows.Add(dr);
dr = dt.NewRow();
dr["TestRun"] = "Minimum ";
dr["IterativeSearch1"] = dt.Compute("Min(IterativeSearch1)", string.Empty);
dr["IterativeSearch2"] = dt.Compute("Min(IterativeSearch2)", string.Empty);
dr["RecursiveSearch"] = dt.Compute("Min(RecursiveSearch)", string.Empty);
dt.Rows.Add(dr);
dr = dt.NewRow();
dr["TestRun"] = "Maximum ";
dr["IterativeSearch1"] = dt.Compute("Max(IterativeSearch1)", string.Empty);
dr["IterativeSearch2"] = dt.Compute("Max(IterativeSearch2)", string.Empty);
dr["RecursiveSearch"] = dt.Compute("Max(RecursiveSearch)", string.Empty);
dt.Rows.Add(dr);
return dt;
} // End Sub TestMain
public static double Median<T>(T[] numbers)
{
int numberCount = numbers.Count();
if (numberCount == 0)
return 0.0;
int halfIndex = numbers.Count()/2;
var sortedNumbers = numbers.OrderBy(n => n);
double median;
if ((numberCount % 2) == 0)
{
median =
(
(
System.Convert.ToDouble(sortedNumbers.ElementAt<T>(halfIndex)) +
System.Convert.ToDouble(sortedNumbers.ElementAt<T>((halfIndex - 1))
)
)/2);
}
else
{
median = System.Convert.ToDouble(sortedNumbers.ElementAt<T>(halfIndex));
}
return median;
} // End Function GetMedian
// http://msmvps.com/blogs/deborahk/archive/2010/05/07/linq-mean-median-and-mode.aspx
public static double CalcMedian(int[] numbers)
{
int numberCount = numbers.Count();
int halfIndex = numbers.Count()/2;
var sortedNumbers = numbers.OrderBy(n => n);
double median;
if ((numberCount % 2) == 0)
{
median = ((sortedNumbers.ElementAt(halfIndex) +
sortedNumbers.ElementAt((halfIndex - 1)))/2);
}
else
{
median = sortedNumbers.ElementAt(halfIndex);
}
return median;
} // End Function CalcMedian
} // End Class SearchStrategy
} // End Namespace IterativeDirectoryCSharp
Есть ли причина, вы решили не использовать рекурсию? в некоторых случаях это быстрее, чем без него. –
Потому что я не знаю, сколько каталогов будет в директории с разложенными файлами, поэтому я думал о проблемах с памятью. – dierre
Вы проверили http://stackoverflow.com/questions/1086907/can-find-or-any-other-tool-search-for-files-breadth-first – Jayan