[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki

• ÚFAL Wiki Home
• ÚFAL Home
• Sitemap
• RSS
• ÚFAL calendar
• Recent changes
• Login
• Hledat:

[ Back to the navigation ]

Differences

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

View differences: Side by SideInline Go

Link to this comparison view

Both sides previous revision Previous revision 2016/01/08 23:17 popel 2016/01/08 19:27 popel 2016/01/08 19:03 popel 2016/01/08 18:28 popel 2016/01/08 17:29 popel 2016/01/08 14:48 popel 2016/01/08 00:09 popel 2016/01/07 18:02 popel 2015/12/15 16:25 popel 2015/12/14 11:18 popel 2015/12/14 03:43 popel 2015/12/14 01:26 popel 2015/12/11 13:35 ufal 2015/12/11 13:34 ufal 2015/12/11 12:51 popel 2015/12/11 12:29 popel 2015/12/11 11:16 popel 2015/12/11 11:14 popel 2015/12/11 11:12 popel 2015/12/11 11:09 popel 2015/12/11 11:06 popel 2015/12/11 10:31 popel 2015/12/11 10:13 popel 2015/12/10 18:41 popel 2015/12/09 15:04 popel 2015/12/08 21:32 popel 2015/12/08 21:31 popel 2015/12/08 17:52 popel created Go Next revision		Previous revision 2016/01/08 23:17 popel 2016/01/08 19:27 popel 2016/01/08 19:03 popel 2016/01/08 18:28 popel 2016/01/08 17:29 popel 2016/01/08 14:48 popel 2016/01/08 00:09 popel 2016/01/07 18:02 popel 2015/12/15 16:25 popel 2015/12/14 11:18 popel 2015/12/14 03:43 popel 2015/12/14 01:26 popel 2015/12/11 13:35 ufal 2015/12/11 13:34 ufal 2015/12/11 12:51 popel 2015/12/11 12:29 popel 2015/12/11 11:16 popel 2015/12/11 11:14 popel 2015/12/11 11:12 popel 2015/12/11 11:09 popel 2015/12/11 11:06 popel 2015/12/11 10:31 popel 2015/12/11 10:13 popel 2015/12/10 18:41 popel 2015/12/09 15:04 popel 2015/12/08 21:32 popel 2015/12/08 21:31 popel 2015/12/08 17:52 popel created Go Next revision Both sides next revision
treex:api-implementation [2016/01/08 17:29] popel		treex:api-implementation [2016/01/08 19:03] popel
Line 150:		Line 150:
	=== SORTED-CHILDREN ===		=== 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 ===		=== SORTED-CHILDREN + ALL-NODES ===
Line 172:		Line 172:
-	===== Benchmark načítání CoNLL-U v Perlu =====	+	===== 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.		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.
Line 190:		Line 190:
-	* 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 se někde ztratily). Kdyby byly děti implementované spojákem místo pole (to mám stále v plánu), tak to bude rychlejší, 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.	+	* 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.
-	* Ušetřil jsem 10s, tedy víc než 7s. Volám přímo ''UD::Node->new(...)'' místo ''$root->create_child(...)''.	+	* Vypuštěním testování cyklů v CoNLL-U závislostech se ušetří necelá sekunda, což za to asi nestojí.
-	* Ještě víc by šlo ušetřit vypuštěním testování cyklů v CoNLL-U závislostech (1s) a optimalizací kódu set_parent bez volání této metody (další 2s).	+	* Optimalizací kódu set_parent bez volání této metody se jakoby ušetří 2.5s.
-	* Nyní se nejvíc času stráví samotným vytvářením uzlů (10.917s-0.844s). To musím ještě prozkoumat.	+	* 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 =====		===== Benchmark konstruktorů v Perlu =====

---

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