Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #29449 > unrolled thread

Jak zamienić ścieżki na strukturę drzewiastą?

Back to article view | Back to pl.comp.programming

Contents

  Jak zamienić ścieżki na strukturę drzewiastą? Andyy <nie@spamowac.tego> - 2017-02-24 22:01 +0100
    Re: Jak zamienić ścieżki na strukturę drzewiastą? Andyy <nie@spamowac.tego> - 2017-02-24 22:03 +0100
      Re: Jak zamienić ścieżki na strukturę drzewiastą? bartekltg <bartekltg@gmail.com> - 2017-02-24 22:20 +0100
        Re: Jak zamienić ścieżki na strukturę drzewiastą? Andyy <nie@spamowac.tego> - 2017-02-25 10:16 +0100

#29449 — Jak zamienić ścieżki na strukturę drzewiastą?

Mam plik archiwum, w nim ścieżki:

guava-master\.gitattributes
guava-master\.gitignore
guava-master\.travis.yml
guava-master\guava\src\com\google\common\base\Absent.java
guava-master\guava-gwt\src\com\google\common\base\Absent_CustomFieldSerializer.java
guava-master\guava-tests\test\com\google\common\util\concurrent\AbstractAbstractFutureTest.java

Domyślnie posortowane po ostatnim członie ścieżki czyli nazwie
Zaczynam od posortowania po ścieżce.
Ale to nie takie łatwe, bo separator ścieżki nie jest ani pierwszym ani 
ostatnim znakiem ASCII, więc może być tak:
ab1a
ab\a
abra

Jak to zrobić prawidłowo?

[toc] | [next] | [standalone]

#29450

W dniu 24.02.2017 o 22:01, Andyy pisze:
> Ale to nie takie łatwe, bo separator ścieżki nie jest ani pierwszym ani
> ostatnim znakiem ASCII, więc może być tak:
> ab1a
> ab\a
> abra
>
> Jak to zrobić prawidłowo?

Może najpierw zamienić separator na \0 , posortować i co dalej?
Tylko aby C# czy C++ nie uznały że \0 oznacza koniec stringa

[toc] | [prev] | [next] | [standalone]

#29451

On 24.02.2017 22:03, Andyy wrote:
> W dniu 24.02.2017 o 22:01, Andyy pisze:
>> Ale to nie takie łatwe, bo separator ścieżki nie jest ani pierwszym ani
>> ostatnim znakiem ASCII, więc może być tak:
>> ab1a
>> ab\a
>> abra
>>
>> Jak to zrobić prawidłowo?
>
> Może najpierw zamienić separator na \0 , posortować i co dalej?
> Tylko aby C# czy C++ nie uznały że \0 oznacza koniec stringa


Jeśli chcesz posortować tak, by / było przed literkami,
napisz własną porównywarkę stringów, która jak natrafia
na znak \, podmienia go na zero.

Jeśli chcesz zrtobić to, co opisane w temacie postu,
zaczałbym od podzielenia stringów na vector stirongów

guava-master\guava\src\com\google\common\base\Absent.java ->

guava-master
guava
src
com
google
common
base
Absent.java

Potem drzewo budujesz przechocząc taki zestaw stringów,
jeśli kolejny element jest taki jak istneijący potomek
wierzchołka, w który jesteś, wchodzisz w niego, jeśli
nie, dodajesz do drzewa.

W sumie to nie wymaga ani przerobienia stringa na
wektor strongów, ani sortowania.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#29452

W dniu 24.02.2017 o 22:20, bartekltg pisze:
> Potem drzewo budujesz przechocząc taki zestaw stringów,
> jeśli kolejny element jest taki jak istneijący potomek
> wierzchołka, w który jesteś, wchodzisz w niego, jeśli
> nie, dodajesz do drzewa.
>
> W sumie to nie wymaga ani przerobienia stringa na
> wektor strongów, ani sortowania.

         internal void make(Chunk chunk)
         {
             this.chunk = chunk;
             List<ItemArch> list = makePathList();
             root = new Node();
             foreach (ItemArch elem in list)
             {
                 Node node = root;
                 foreach (string part in elem.parts)
                 {
                     Node node1 = node.search(part);
                     if (node1 != null) node = node1;
                     else node = node.add(part);
                 }
                 node.index = elem.index;
             }
         }

Długotrwała jest operacja search, ale gdy mamy posortowane, to jeśłi 
znajdzie to zawsze ostatni, co sprawdziłem dla Assert:
	internal Node search(string name)
         {
             if (childs == null) return null;
             for (int i=0; i<childs.Count; i++)
             {
                 Node child = childs[i];
                 if (child.name == name)
                 {
                     Debug.Assert(i== childs.Count-1);
                     Console.WriteLine("found at "+i+" where size="+ 
childs.Count);
                     return child;
                 }
             }
             return null;
         }
Czyli można zoptymalizować.

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web