2009년 2월 9일 월요일

C#으로 본 자료운용 구조[DFS와 BFS 비교]

얼마전 파일 검색 함수를 작성해 보면서 탐색 방법에 대한 고찰을 하게 되었다.

폴더에 대한 검색..

서브 폴더를 포함한 검색을 하며 검색되는 속도에 의해 얼마나 느려 질 수 있는지...

처음 사용하던 탐색 방법은 DFS(Depth First Search - 깊이 우선 방식)으로 Stack 구조의 재귀함수를 사용하는 방법이다.

아래는 C#으로 만들어본 DFS 방식의 파일 검색 함수이다.

private List DirSearch(string sDir, string extName)
{
    List tmpList = new List();

    try
    {
        foreach (string f in Directory.GetFiles(sDir, extName))
            tmpList.Add(f);
        foreach (string d in Directory.GetDirectories(sDir))
        {
            tmpList.AddRange(DirSearch(d, extName).ToArray());
        }
    }
    catch (Exception excpt)
    {
        MessageBox.Show(excpt.Message);
        //return tmpList;
    }

    return tmpList;
}


자주 다니는 사이트에서 BFS(Breadth First Search - 너비 우선 방식)을 알게되어 이를 운용해 봤는데 확실히 이 방법이

빠른 속도를 보인다. 다만.. 저장공간 사용량이 DFS에 비해 많다는 것...

하지만 요즘 PC들이 메모리가 좀 많은가... 많이 쓴다고 해봤자 메모리양에 비하면 새발의 피지... ㅎㅎ

아래는 BFS 방식의 파일 검색 함수 예제이다.

private List DirSearch(string sDir, string extName)
{
	List tmpDir = new List();
	List fileList = new List();

	int head = 0, tail = 0;
	tmpDir.Add(sDir);
	tail++;

	while (head != tail)
	{
		try
		{
			foreach (string d in Directory.GetDirectories(tmpDir[head]))
			{
				tmpDir.Add(d);
				tail++;
			}
			
			foreach (string f in Directory.GetFiles(tmpDir[head++], extName))
				fileList.Add(f);
		}
		catch (Exception excpt)
		{
			MessageBox.Show(excpt.Message);
			//return tmpList;
		}
	}
	return fileList;
}


좀.. 당황스러운건... C#으로 두 함수를 만들어 비교해 봤지만...

시간 차이가 거의 없다는 것... ㅡ_ㅢ;;;

나 실패한건가 T^T

댓글 2개:

  1. 리소스보단 속도인가요..;;

    답글삭제
  2. @Jelly君 - 2009/02/11 14:00
    펜티엄 4를 넘어서면서 이전에 사용하던 리소스의 개념이 많이 무뎌졌죠.. 펜티엄3 시절만 해도 1GB 메모리 사용하시는 분들이 많지 않았지만... 지금은 1GB도 모자라 2GB를 기본으로 많이들 사용합니다. 이만큼의 자원에서 검색할 때 사용하는 메모리 자원은 큰 의미가 없어지더군요...

    요즘 프로그밍에서도 자원에대해서는 크게 신경쓰지는 않고 만들고 있으니까요..;;

    그만큼.. HW 쪽이 든든히 받쳐준다고나 할까요..

    답글삭제