[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki


[ Back to the navigation ]

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
treex:api [2015/12/13 13:55]
popel
treex:api [2015/12/14 18:12] (current)
popel
Line 17: Line 17:
 create_child create_child
 get_parent -> parent get_parent -> parent
-set_parent+set_parent (defaultně kontroluje, aby nevznikl cyklus)
 get_children get_children
 +
 +=== Word-order methods ===
 +precedes($another_node)
 +get_next_node -> next_node()
 +get_prev_node -> prev_node()
 +shift_after_node($reference_node, {without_children=>1})
 +shift_after_subtree($reference_node, {without_children=>1})
 +shift_before_node($reference_node, {without_children=>1})
 +shift_before_subtree($reference_node, {without_children=>1})
 +is_nonprojective($reference_node, {without_children=>1})
  
 === New methods === === New methods ===
Line 64: Line 74:
 update_aligned_nodes update_aligned_nodes
  
-===== Poznámky =====+===== Mají children/descendants/siblings vracet pole, či iterable? =====
  
-  * Současné ''get_children'' i ''get_descendants'' vrací pole, které se ale musí vždy znovu alokovat (je tedy mutable, ale změny tohoto pole neovlivní původní strom). To je z hlediska rychlosti neoptimální, lepší by bylo vracet iterátor, jak je Javě (collection) a Pythonu zvykem. +  * Současné ''get_children()'' i ''get_descendants()'' vrací pole, které se ale musí vždy znovu alokovat (je tedy mutable, ale změny tohoto pole neovlivní původní strom). To je z hlediska rychlosti neoptimální, lepší by bylo vracet iterable objekt, jak je Javě (collection) a Pythonu zvykem. 
-  * Pokud někdo bude to pole potřebovat (třeba proto, že chce strom měnit, ale toto pole má zůstat neměnné), tak to lze vždy snadno zařídit (v Pythonu ''list(node.children)''). Výhodou Javy a Pythonu (oproti Perlu) je, že jde iterovat for cyklem i přes collection/iterátor (a v Pythonu je ještě efektivnější list comprehension, protože to jede celé rychlostí céčkového kódu).+  * Pokud někdo bude to pole potřebovat (třeba proto, že chce strom měnit, ale toto pole má zůstat neměnné), tak to lze vždy snadno zařídit (v Pythonu ''list(node.children())''). Výhodou Javy a Pythonu (oproti Perlu) je, že jde iterovat for cyklem i přes collection/iterátor (a v Pythonu je ještě efektivnější list comprehension, protože to jede celé rychlostí céčkového kódu).
   * Další výhodou iterátorů je, že někdy nepotřebuji ani projít všechny prvky toho pole, ale hledám první prvek, který splní nějakou podmínku (short circuit).   * Další výhodou iterátorů je, že někdy nepotřebuji ani projít všechny prvky toho pole, ale hledám první prvek, který splní nějakou podmínku (short circuit).
 +  * Pokud by implementace měla ke každému uzlu v paměti alokované pole dětí a potomků (a sourozenců), tak by samozřejmě šlo vrátit přímo toto pole (a nebylo by to pomalejší než iterátory). Ale buď by se to pole mělo udělat immutable, nebo by se muselo zajistit, že se naopak správně upraví celý strom (v případě přidání uzlu do ''children'' či ''siblings'' si to lze představit, v případě ''descendants'' ne, protože není jasné, kam ten nový uzel zavěsit).
 +  * Na druhou stranu v některých implementacích bude potřeba při každém zavolání ''descendants()'' vytvořit nové pole (aby se setřídilo perlsortem/timsortem inplace, kvůli neprojektivitám, viz dále). To pole sice je taky iterable (a lze z něj snadno vyrobit iterátor), ale když uživatel zavolá ''potomci = list(node.descendants())'', tak naopak vytvoří zbytečnou kopii (protože v této implementaci už ''node.descendants()'' vrací nové pole).
 +
 +===== Mají children/descendants/siblings být metoda, či property? =====
 +  * Tohle je trochu Python-specific. Pokud by to bylo předpočítané, tak by to mohlo být property, tedy by se "ušetřilo" psaní prázdných závorek: ''potomci = node.descendants''.
 +  * Jenže asi budeme chtít přidávat parametry, a to u properties nejde. Takže z hlediska API jsem pro metody: ''potomci = node.descendants()''.
  
-   +===== Mají children/descendants/siblings vracet setříděné uzly? ===== 
 +  * Současné řešení vrací uzly v nedefinovaném pořadí (u descendant průchodem do hloubky, děti pak v pořadí vložení), takže když chci pořadí dle (povrchového) slovosledu, musím zavolat ''get_children({ordered=>1})''. To je dost nešikovné, protože na to člověk často zapomene, na většině vět to funguje (pořadí dle vložení se většinou shoduje se slovosledným), ale pak ne a těžko se to debugguje. 
 +  * V současných zdrojácích bloků Treexu je 909 volání ''get_descendants'' a 405 z nich je ''ordered'' (jak často se které volání používá teď neberu v potaz). Navíc 455 bloků používá ''process_[at]node'', která vyžaduje ''get_descendants({ordered=>1})''. U ''get_children'' je to ordered/vše=95/598 a u ''get_siblings'' 2/46. Závěr: setřídění uzlů je potřeba velmi často (byť někde mohlo být to ordered přidáno preventivně a vlastně to potřeba není, viz předchozí bod). 
 +  * Ve zdrojácích je 241 volání metod ''shift_(before|after)_(node|subtree)''. Část z toho je volání hned po přidání nového uzlu. Změna slovosledu je tedy častá. Mám ale pocit, že v typickém scénáři (t-analýza, překlad) se mění slovosled mnohem méně často, než jak často se přistupuje k setříděným dětem/potomkům (chtělo by to profiling pro přesná čísla). 
 +  * U ''children'' a ''siblings'' by rozumná implementace měla udržovat seznam pořád setříděný (teď se pokaždé volá ''sort''), takže by parametr ''ordered'' mohl z API zmizet. 
 +  * U ''descendants'' je situace složitější, protože u neprojektivních stromů nejde správné pořadí potomků získat průchodem do hloubky. Viz [[treex:api-implementation#setrideni-dle-ord|poznámky k implementaci setřídění]].

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