현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

회사 과제 질문드합니다. 파일 검색 프로그램!

tops1950의 이미지
글쓴이: tops1950 / 작성시간: 월, 2016/10/31 - 4:49오후

지금 Everything 이라는 프로그램을 모방하여 파일 검색 프로그램을 제작하고 있습니다.

위 프로그램이 1분 정도 인덱싱 과정을 거치면, 모든 파일이 거의 실시간을 0.5초 안에 검색이 되더라구요.

저가 현제 C 드라이브에서 파일들을 읽어와 메모리에 연결리스트로 저장한 후

이름순으로 정렬하고, strstr 명령어로 비교하면서,

검색 문자열이 이름에 포함되어 있는지 검사하도록 했습니다.

20만개 정도 있을때, 한 글자를 입력하면 0.35 초 가량 나오더라구요..

좀 더 빠른 정렬을 위해서, 아스키 코드 별로 1글자 검색결과를 미리 저장하려고 하다가

메모리 부족현상으로 인해 다른 방법을 찾아보고 있습니다...

연결리스트를 배열로 바꿔서 접근속도를 높이거나, 문자열 검색 시

해시를 계산해서 비교 속도를 높인다던지 가능성 있는 방법들을 생각해보고 있습니다.

더 큰 문제는 MFC에서 결과를 출력해주는 과정인데요.

대략 50만개의 아이템을


for (int i = 0; i < 500000; i++) {
m_LC_result.InsertItem(i, _T("1")); // i번째 행 1번째열
m_LC_result.SetItem(i, 1, LVIF_TEXT, _T("Test"), NULL, NULL, NULL, NULL); // i번째 행 2번째열
}

이런식으로 테이블에 삽입하는데만, 1분 가량이 소요됩니다.
10만개도 거의 24초..
삭제는 그나마 50만일때, 10초 / 10만일 때 2초 가량 소요되는데.
Everything 프로그램처럼 1초 안에 모든 검색을 보여주는것이 불가능한 상황입니다...

제 입사 테스트문제라 꼭 해결을 해야해서
실력자 분들의 조언이 절실합니다. ㅠㅠ

부분일치 문자열을 탐색하는 과정 중 아이디어나,
MFC 결과를 어떻게 빨리 출력할 수 있는지 조언을 듣고 싶습니다.

Forums: 
프로그래밍 QnA
chocokeki의 이미지

글쓴이: chocokeki / 작성시간: 월, 2016/10/31 - 5:22오후

이거는 알고리즘 문제 같은데요
순서대로 저장하시면 안될꺼같아요!

tops1950의 이미지

글쓴이: tops1950 / 작성시간: 월, 2016/10/31 - 11:51오후

저도 이름으로 정렬한 순서대로 넣어서 비교하는 것보단 좋은 방법이 있을거라 생각하는데..
이게 한글자가 아니라 문자열이라.. 뭘 기준으로 잡아야 하는지 애매하네요 ㅠㅠ

Anti-Lock의 이미지

글쓴이: Anti-Lock / 작성시간: 월, 2016/10/31 - 6:19오후

수십만개의 검색결과가 나왔다고 해도,
이것을 전부 리스트컨트롤에 넣을려면 시간이 오래걸립니다.
이럴때는 화면에 보이는 정도만 추가하고, 나머지는 리스트 콘트롤을 스크롤할때 보여줄수도 있죠.
virtual list control 키워드로 한번 찾아보세요.

tops1950의 이미지

글쓴이: tops1950 / 작성시간: 목, 2016/11/03 - 10:27오전

감사합니다.ㅎㅎ

twinwings의 이미지

글쓴이: twinwings / 작성시간: 화, 2016/11/01 - 3:48오전

1. 문자열은 고정길이 배열로 사용하고
(*파일명은 전체 경로를 포함하여 최대 259 글자이며, 루트 폴더에 가장 긴 255 글자의 파일을 만들 수 있다. 출처: http://hizstory.tistory.com/14)

2. 자료구조 종류에 따른 장단점을 잘 모르시는 것 같습니다.

인덱싱 한번 하면 삽입/삭제가 없고 검색이 대부분의 시간을 차지한다고 할 때

최적의 자료구조는 우선순위큐, 힙, 균형 이진트리 등이 적합합니다.

표준라이브러리로는 std::map, std::set등이 있으니 그걸 이용하면 될 듯 합니다.

검색을 위한 자료구조는 리스트의 경우 효율이 안좋습니다.

tops1950의 이미지

글쓴이: tops1950 / 작성시간: 목, 2016/11/03 - 10:35오전

직접 구현이라 표준라이브러리는 사용 못하지만,
확실히 트리 같은 자료주고는 괜찮다고 생각합니다.
그런데, 길이가 각각 다르고, 입력 문자열이 다른 파일이름들은 어떻게 구성해야 할지 몰라 애를 먹고 있네요 ㅠㅠ

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 목, 2016/11/03 - 2:24오후

스트링 서치트리는 이놈이 널리쓰입니다. https://en.wikipedia.org/wiki/Trie

twinwings의 이미지

글쓴이: twinwings / 작성시간: 일, 2016/11/06 - 7:51오전

"길이가 각각 다르고, 입력 문자열이 다른 파일이름들은 어떻게 구성해야 할지 몰라 애를 먹고 있네요 ㅠㅠ"
>> 말씀드렸드시, 윈도우에서 경로를 포함한 파일이름의 최대길이는 259? 라고 합니다. 이걸 타입지정하세요

#define MAX_PATH_LEN (259)
#define MAX_FILE     (500000) // 50만개
typedef char file_path_t[MAX_PATH_LEN+1]; // 널문자 포함
 
typedef struct file_array {
    int size;
    file_path_t files[MAX_FILE];
} file_array_t;

파일개수가 50만개라고 하셨으니까, 그걸 상한선으로 모든 파일 이름을 담을 수 있는file_array_t 구조체를 저렇게 정의하면 고작 150MB밖에 차지 않합니다.

1. 루트로 부터 파일이름을 읽어 배열끝에 추가한다.
2. qsort(), strcmp() 이용 정렬한다.
3. 정렬되어있으므로 이진탐색이 가능하다.

그리고 MFC에서 사용하는 자료구조는 검색 결과만 넣고 출력하세요.

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.