Drzewo katalogów do pamięci - wydajniej

Witam!
Mam następujący problem. Około 500.000 plików spakowanych w archiwum. Do każdego pliku przypisana jest ścieżka. Pojedynczy wpis pliku wygląda mniej więcej tak:

Assets/Graphics/Effects/CrazyFire.eff

Chcę informacje o tych plikach wyświetlić w windowsowskim tree view, zatem muszę je sobie pokatalogować - zrobić sprytne drzewko w którym nie powtarzają się nazwy katalogów, ale mogą się powtarzać nazwy ścierzek. Cały problem pojawił się przy niepowtarzaniu nazw katalogów. Przy każdym nowym wpisie muszę sprawdzać czy taki katalog istnieje, co oznacza gigantyczne iteracje. Zaimplementowałem to na szybko (kod poniżej), żeby sprawdzić jak poradzi sobie z tym zadaniem procesor. Cały proces zajmuje ponad 5min (dalej nie chciało mi się czekać :D ). Jest oczywiście możliwość przyspieszenia tego - chociażby przez zapisanie ostatniej ścieżki w drzewie, albo sprytne (czyli jakie? ) sortowanie drzewka i wyszukiwanie binarne (jeden katalog może zawierać dziesiątki tysięcy plików) i inne tego typu optymalizacje z którymi dałem sobie na chwilę obecną spokój. Mam wrażenie, że to co robię to próba wynalezienia koła od nowa. Z góry zaznaczam, że property_tree z boosta mi jakoś nie odpowiada ;).

Komentarze do kodu:

• Pliki nie są wypakowywane. Pobierane są tylko ścieżki do nich.
• Wąskim gardłem jest: CurrEntry = CurrEntry->AddChild( Name.c_str() );
• CurrEntry jest wskaźnikiem na klasę DirEntry.
• fs oznacza namespace boost::filesystem
• Implementacja jest testowa - miała iść do przepisania gdyby się sprawdziła. Stąd brak komentarzy i piękna w kodzie ;).
• m_RootDir jest obiektem typu DirEntry - katalog główny = TreeView.
• CArchive to moja klasa - przetestowana, skalkulowana jeśli chodzi o czas. Działa bez zarzutu.

Klasa DirEntry:
http://wklej.org/hash/fe486ecc210/

Umieszczanie pliczków w drzewie:
http://wklej.org/hash/2ad1e4cbad1/

Po pierwsze użyj std::map
Po drugie użyj VirtualTreeView

A co to za archiwum?

Duuuużo zipów w jednym pliku pliku zip. Nie moje pliki :)

Z tego co właśnie przeczytałem o VirtualTreeView(Dzięki za źródło) to nie rozumiem po co mi std::map skoro wszystkie dane mogą być w drzewq? :D

Chodzi o to, żeby Childs był kontenerem posortowanym, dzięki czemu wyszukiwanie konkretnej nazwy będzie efektywniejsze niż to, co masz teraz.

Zrezygowałem w ogóle z VTV. Childs zmieniłem na mapy, dodałem zapisywanie ostatniej ścieżki, żeby w razie powtórki nie musieć szukać i jakoś to wszystko śmiga. Zastanawiam się tylko co jaki interwał std::map sortuje swoje dane.

Interwał? :| std::map to drzewo binarne, więc dane od razu wstawiane są w odpowiednie miejsce.

Przeglądanie tej mapy w debuggerze mówi o niej co innego.

Skoro używasz boost::hash to może idź za ciosem i użyj boost::unordered_map

http://www.boost.org/doc/libs/1_54_0/doc/html/unordered.html

Nie jestem pewien, czy w Visualu 2010 std::map nie działa zgodnie ze standardem C++0x, więc prawie identycznie jak boostowska mapa.

W tym projekcie pierwszy raz używałem boosta i nie miałem jeszcze czasu go dokładnie przejrzeć, ale dzięki za link. Zrobię porównanie wydajności. ;)