Differences

This shows you the differences between two versions of the page.

--- treex:api-implementation [2015/12/14 11:18]
popel
+++ treex:api-implementation [2016/01/08 19:27]
popel
@@ Line 150: / Line 150: @@
 === SORTED-CHILDREN ===
-Děti se ukládají setříděně buď do pole, nebo do spojáku (tedy každý uzel má pointer _next_node, případně i obousměrně _prev_node). Buď se ukládají pravé a levé děti zvlášť, nebo se při vracení dětí s přepínačem ''add_self'' vloží jejich rodič na správnou pozici. Metoda ''descendants'' uloží potomky do pomocného pole (klasickým průchodem do hloubky) a pak dotřídí. Perl i Python mají sort optimalizovaný na předtříděné sekvence (každý trochu jinak, Perl asi o něco lépe než pythoní timsort, který bere jen sekvence začínající na indexu 2**k, ale pro naše krátké sekvence to je asi úplně jedno). Nejde to implementovat jako iterátor bez toho pomocného pole.
+Děti se ukládají setříděně buď do pole, nebo do spojáku (tedy každý uzel má pointer _next_node, případně i obousměrně _prev_node). Buď se ukládají pravé a levé děti zvlášť, nebo se při vracení dětí s přepínačem ''add_self'' vloží jejich rodič na správnou pozici. Metoda ''descendants'' uloží potomky do pomocného pole (klasickým průchodem do hloubky) a pak dotřídí. Perl i Python mají sort optimalizovaný na předtříděné sekvence (každý trochu jinak, Perl asi o něco lépe než pythoní timsort, který bere jen sekvence začínající na indexu 2^k, ale pro naše krátké sekvence to je asi úplně jedno). Nejde to implementovat jako iterátor bez toho pomocného pole.
 === SORTED-CHILDREN + ALL-NODES ===
@@ Line 162: / Line 162: @@
 Metoda ''descendants'' tedy začne nejlevějším a iteruje až do nejpravějšího (a vynechá uzel, ze kterého to volám, pokud není ''add_self'').
 Problém je jen s neprojektivitami, takovéto uzly musím přeskočit. Každý uzel má tedy seznam (spoják) uzlů, v jejichž spanu (leftmost..rightmost) se slovosledně nachází a přitom není jejich potomkem. Většina uzlů je projektivních a má tedy tento seznam prázdný, takže při iteraci mám jen jeden if navíc. Zatím se mi tato implementace líbí nejvíc.
+Vylepšení1:
+Při zavolání z kořene stromu by se vrátil speciální iterátor, který vůbec nekontroluje seznamy neprojektivit (takže se ušetří to if, ale hlavně procházení všech seznamů). Toto vylepšení mi přijde zcela jasně přínosné.
+Vylepšení2:
+V seznamech neprojektivit budou uzly setříděné vzestupně dle hloubky. Jakmile narazím na uzel s vyšší hloubkou než uzel, který testuji (ze kterého jsou ''descendants'' zavolané), tak skončím a neprocházím zbytek seznamu. Zde si vůbec nejsem jist, zda to má cenu, protože sice ušetřím procházení části seznamu u některých uzlů, jenže zase přibude testování hloubky (kterou bych musel mít v tom seznamu asi předpočítanou, a tedy ji aktualizovat, když se změní).
 Alternativa: atribut _leftmost (a obdobně _rightmost) by se vyplňoval pouze tehdy, pokud by se sledováním nejlevějšího dítěte nedalo dostat do nejlevějšího potomka. Tedy v projektivních stromech by se ty atributy nemusely vyplňovat vůbec (vůbec by nezabíraly místo v hash-based objektech). Editace by pak mohly být o něco rychlejší, pokud detekuji, že projektivní strom měním na projektivní. Čtení ale bude pomalejší, protože budu muset iterovat do těch nejlevějších dětí (a ještě navíc testovat, zda není v uzlech vyplněn _leftmost).
+===== Profiling načítání CoNLL-U v Perlu =====
+Načítám cs-ud-train-l.conllu (68 MB, 41k sentences, 0.8 MWords). Časy v sekundách. Excl(usive) časy se sčítají, krom těch označených "x", což jsou pomocné (alternativní) experimenty.
+|excl.|incl.| code                                   | note|
+| 0.5 | 0.5 | ''while (<$fh>) {chomp;}''             | načtení řádka po řádce |
+| 0.3 | 0.8 | ''$line eq "" or $line =~ /^#/''       | test prázdné řádky a komentáře |
+| 0.7 | 1.5 | ''split /\t/, $line''                  | split 9 atributů dle tabů |
+| 4.3 | 5.8 | ''my ($id, $form, $lemma,...) =''      | uložení těch hodnot do proměnných |
+|x3.9 |     | ''UD::Node->new(form=>$form,...)''     | vytvoření 0.8M uzlů se stejnými atributy, tedy 200K uzlů za sekundu, viz [[#Benchmark konstruktorů v Perlu|následující benchmark]]|
+| 4.5 |10.3 | ''UD::Node->new(form=>$form,...)''     | vytvoření 0.8M uzlů ze skutečných dat|
+|x0.4 |10.7 | ''push @all_nodes, $node''             | uzly se ukládají do pole|
+| 1.9 |12.2 | ''weaken($node->{_parent}=$root)...''  | uzly se ukládají do dokumentu, věší se na kořen, přidávají do jeho seznamu dětí|
+| 1.2 |13.4 | ''weaken($node->{_parent}=$parent)...''| uzly se věší na skutečného rodiče (v druhém průchodu, pomocné pole ''@parents'')|
+| 2.5 |15.9 | ''set_parent($parent,{cycles=>'no-check'})'' | set_parent místo optimalizovaného kódu (který neřešil předchozího rodiče atd.)|
+| 0.7 |**16.6**| ''set_parent($parent)''                | testování cyklů |
+|10.0 |26.6 | ''$root->create_child...''             | původní implementace, kde se uzly převěšují z kořene na skutečného rodiče a děti jsou pole|
+  * Původní implementace byla velmi neefektivní, protože se při převěšování z kořene musely uzly odebrat z pole dětí kořene, čili se muselo to pole překopírovat a zmenšit o jeden prvek a složitost byla kvadratická. Samotné převěšení trvalo 7s (a ještě 3s asi kvůli ''$root->create_child(...)'' místo ''UD::Node->new(...)''). Kdyby byly děti implementované spojákem místo pole (to mám stále v plánu), tak to bude míň než 7s, ale stejně je zbytečné při načítání CoNLL-U uzly dávat do spojáků dětí kořene, ze kterého vím, že je budu za chvíli odebírat.
+  * Vypuštěním testování cyklů v CoNLL-U závislostech se ušetří necelá sekunda, což za to asi nestojí.
+  * Optimalizací kódu set_parent bez volání této metody se jakoby ušetří 2.5s.
+  * Poměrně dost času (4.3s) zabere vytváření 9 proměnných ''$form, $lemma,...''. Nešikovné je, že při ''UD::Node->new(form=>$form,...)'' se tyto proměnné zkopírují do hashe a ty původní vypadnou ze scope a musejí se odalokovat. Čili vytváření uzlu zabere skoro stejný čas (4.5s).
+  * Když jsem všechny uzly ukládal do pole, tak odalokování pole (s 0.8M uzlů) trvalo cca 1s. To jsem do profilingu nezahrnul, ale benchmark jsem musel ručně spouštět víckrát.
+===== Benchmark konstruktorů v Perlu =====
+Kolik objektů (uzlů s 9 stringovými atributy) se vytvoří za 1 sekundu:
+  MooseMut   4509 Moose bez __PACKAGE__->meta->make_immutable
+  Moose     65941
+  Moo       78156
+  ManualA   99508 Manual array-based object, konstruktor vytvoří hash, aby zjistil, které atributy byly zadány
+  ManualH  191911 Manual hash-based object
+  XSAccHp  197371 Class::XSAccessor ale sub new {my $c=shift; bless {@_}, $c;}
+  XSAccAs  224108 Class::XSAccessor::Array, new bez parametrů, třeba volat settery
+  XSAccH   235633 Class::XSAccessor { constructor => 'new'}
+  --- následující implementace mají konstruktory, které berou jen hodnoty atributů, nikoli jména, tedy musejí být zadané ve správném pořadí
+  XSAccAf  324620 Class::XSAccessor::Array, sub fastnew {my $c=shift; bless [@_], $c;}
+  ManualAf 333188 Manual array-based object, sub fastnew {my $c=shift; bless [@_], $c;}

[ Back to the navigation ] [ Back to the content ]

Institute of Formal and Applied Linguistics Wiki

Differences