Zobrazit příspěvky
Tato sekce Vám umožňuje zobrazit všechny příspěvky tohoto uživatele. Prosím uvědomte si, že můžete vidět příspěvky pouze z oblastí Vám přístupných.
Jen vyvracím nepravdivé tvrzení, že vyhledávání s maximální složitostí O(1) neexistujeV tom případě to děláte špatně, protože za předpokladu, že si tam můžete vnést libovolné omezující podmínky, existuje daleko jednodušší argument:.
def search(_,_), do: nil
Data ale musí splňovat nějaké předpokladyJe fajn, že víme, že existuje případ, o kterém se nebavíme, který má jiné vlastnosti
...Sorry, já nějak ztrácím přehled, co se snažíte dokázat.
V OOP není problém (velikostní, rychlostní ani přehlednostní) ke grafu držet navíc seznam hran či uzlů (dle každého soudruha).A v FP zas GC nemusí řešit kruhové závislosti, čili může být výrazně efektivnější. Takže co z toho plyne?
Sorry, tady jsem se upsal tím přepnutím z Pythonu, v Elixiru jsou tuples správně takhle:Kód: [Vybrat]a = ...
b = ...
nodes = [a,b]
edges = [(a,b),(b,a)]
[{a,b},{b,a}]
Nepoužívejte zde prosím anglický název pro seznam, je v tom pak bordel...Omlouvám se, došlo mi to až po odeslání příspěvku, že vlastně "list" taky něco znamená česky
)...a v těch seznamech budete hledat a spojovat je, ne? Tak tohle rychlé nebude. Připomíná to relační model. S jednoduchostí, přirozeností (OOP je grafové z podstaty) a elegancí objektového modelu si to nezadá.No a to právě není pravda, protože přesně to samé můžu říct opačně: aha, takže mám jenom odkazy v jednotlivých objektech. A pokud budu chtít počet všech hran, tak to budu celé procházet a značit si, kde už jsem byl?!
pokud je n počet vrcholů, tak seznam vrcholů projdu v čase n, vy také.
teď si asi v něčem nerozumíme, nebo nevím. Mluvili jsme o reprezentaci způsobem (Python):a = {}
b = {'peers': [a]}
a['peers'] = [b]
a = ...
b = ...
nodes = [a,b]
edges = [(a,b),(b,a)]
to je v praxi asi nejlepší reprezentace, ale některé algoritmy budou mít horší asymptotickou složitost.Ale vždyť jsem to psal: návštěva sousedů je pomalejší, ale vyvoření seznam všech vrcholů je rychlejší (nulová náročnost - už to mám rovnou). Záleží, co chci, a podle toho volím reprezentaci. Nerozumím, o čem se vlastně bavíme.
návštěva sousedních vrcholů je pomalejší. viz níže.
imperativní jazyky mají mutable hashmapy s časem přístupu n(1), odkazy bych v nich nepoužívalNeplést prosím střední a maximální časovou složitost. Vyhledávání s maximální složitostí (o té jsem psal) O(1) neexistuje. Optimální složitost pro nejhorší případ je O(log n).
opravdovou hashmapu byste musel kopírovat při každé změně, pokud má být immutable. Právě proto se v FP jazycích používají stromy.Nemusí. Runtime ví, jestli se do mapy zapisuje, a může klidně použít jakoukoli implementaci.
Funkcionalne programovanie je hlavne neintuitivne, preto sa netesi popularite. [...] Riesit veci cez definicie, listy a rekurzie, bez vedlajsich efektov to je dobre mentalne cvicenie, no na problemy z praxe je fp nesikovny nastroj.<pokus o humor>a to ještě nemluvíme o Prologu!</pokus o humor>
To neni tak docela pravda, staci jen vtipne "pretacet" pointery (menit misto, kde ten strom ma koren), rika se tomu zipper.Jo, já jsem myslel strom, kde ta struktura nese význam. Např. strom internetových domén - v kořeni mám '.', pod ním dítě 'cz', pod ním 'root'...
Je to podobne jako treba s GOTO. Dnesni jazyky GOTO neumoznuji, prestoze by to v nekterych situacich bylo efektivnejsi (treba obecne stavove automaty, rizeni vyjimek, atd.). Spoleha se misto toho na kompilator, ze z relativne cisteho strukturovaneho kodu vytvori efektivni spagety.To je moc pěkný přirovnání. A kruhem (
) se tak zpátky dostáváme k tomu, co už tady zaznělo - že zajímavé je, když v jazyce něco zakážu (protože mi to poskytuje nějakou garanci), ne když něco povolím. To je ta chyba v uvažování lidí, kteří si myslí, že když někam přidám map a fold, tak mi vznikne funkcionální jazyk...Napadá mě role rodič, potomek - jejich vzájemné spojení. Zaměstnanec-pracovní místo, ...Viz to, co už tady zaznělo - existují na to reprezentace bez cyklů. V něčem jsou možná míň efektivní, v něčem zase víc. Záleží na úplně konkrétním způsobu použití. Já neznám žádný use case, kde by absence cyklů vedla k nějakému úplně zásadnímu problému. Jednak existence cyklů v datech dost často sama o sobě ukazuje na problematický návrh (jakmile vidím cyklus, měl bych zpozornět), jednak ten cyklus prostě můžu reprezentovat všelijak jinak než přímými referencemi.
jak v takové reprezentaci efektivně najdete všechny hrany incidující s danným vrcholem, případně všechny sousední vrcholy?Každá reprezentace je efektivní pro nějaké použití a neefektivní pro jiné. Reprezentace, která by byla optimální pro každé myslitelné použití, typicky neexistuje.
%{vrchol1: [vrchol2, vrchol3], vrchol3: [vrchol4]}
Představoval jsem si reprezentaci grafu jako seznam vrcholů, kde každý vrchol odkazuje na seznam svých hran. Hrany odkazují zpět na vrcholy. V takové reprezentaci se cykly vyskytují. Přidat hranu, která vytváří cyklus nejde, protože můžete přidávat hrany jen do dosud nevytvořených vrcholů.Asi ne seznam hran, ale seznam vrcholů. Ano, to skutečně v FP pro obecný graf udělat nejde. Ale nevadí to, protože máme jiné možné reprezentace. A je otázka, jestli to, že to v ostatních jazycích jde, za to skutečně stojí. Plynou z toho totiž pak např. takové věci, jako že když chce Ruby udělat GC, musí zastavit celý svět. Velice nepříjemná vlastnost pro produkci...
Myslel jsem nějakou slovníkovou datovou strukturu. Ty jsou ve funkcionálních jazycích často implementované nějakým stromem a přístup má logaritmickou složitost. Imutabilní jsem myslel ve smyslu implementovatelné pomocí immutable n-tic. Ne neměnnou.Jinak normální slovník (hashmap) je třeba v Elixiru first class citizen, takže je implementovaný v runtimu nejefektivnějším možným způsobem - maximální složitost pro čtení i zápis je log(n).
Určetě je efektivnější,Určitě?
)když můžete při procházení grafu skočit rovnou na odkazovaný vrchol namísto hledání id v nějaké immutable datové struktuře reprezentující množinu vrcholů (asi strom?).K čemu propánajána strom? Mám dva listy - v jednom je seznam vrcholů, ve druhém seznam hran - tj dvojic (from,to). Právě proto, že jsou data imutabilní a identitu není potřeba řešit, můžu mít klidně v obou listech nejenom nějaká idéčka (nepřímé reference), ale i přímé reference, nebo klidně i "instance" samotné (protože nemají identitu, stejné hodnoty mají z definice tutéž identitu).
Při implementaci běžných grachových algoritmů se bez muttable datových struktur obejdete jen dost těžko.A proto jsou grafové algoritmy většinou ty příklady, na kterých se demonstruje rekurze
já bych to uznal, grafy jsou docela rozšířená věc a ve funkcionálním programování fakt napičuJá to uznat nemůžu, protože odpověď (odpovídající úrovni otázky) je až trapně jednoduchá: obecný graf se modeluje listem vrcholů a listem hran.
Vše co se popisuje obecnými grafy? Nemusí se přímo jednat o model z reálného světa.Které části "(jedině konkrétní příklad prosím)" jsi nerozuměl?
Nikdo přece nevyžaduje, aby všechny třídy byly v jednom stromu.Ne "všechny", to jsem nepsal, ale ty, které mají mít společné vlastnosti.
Supr, tak se k tomu začínáme posunovat: V runtime se nějakým způsobem udržují stavy. Od tohoto se můžeme odpíchnout.To klidně můžeme. Vy jste říkal, že něco nevíte, já se vám to snažím přiblížit, jak nejlíp umím. Odpíchněte se tedy k další otázce na to, co vám dál není jasné.
Chápu. Tím se objevuje další otázka, jak se modelují vzájemné závislosti (cykly) v datech.To je konečně opravdu zajímavá otázka (bez ironie). Museli bysme říct, co konkrétně bysme chtěli modelovat. Co v reálném světě má kruhové závislosti? (jedině konkrétní příklad prosím)
Zde pořád nějak nevidím tu výhodu FP od OOP (teď nemám na mysli optimalizaci a paralelizaci, ale model) - když potřebuju objekt immutable, udělám si ho, když ne, nic mě nenutí. Rozhoduju se dle použití.Jedna z výhod je nabíledni: pokud si můžu vybrat, potom o výsledku neexistuje žádná garance.
Myslím, že jste si na ony připomínky odpověděl sám - všechna použití, co jste uvedl, jsou použití seznamu (List), a proto budou mít též jeho vlastnosti - je-li něčeho řada a je třeba jí otočit pořadí, téměř jistě se bavíme o seznamu, který toto již dávno umí. Je-li třeba použít jiný než obecný seznam (a to je otázka!), vždy jej lze specializovat, případně (u vaší obavy) při různých speciálních vlastnostech složit a zvláštnosti doplnit. Ani trait na to není třeba (osobně bych to ani nedělal). List JE ubiquitous a obecný, není třeba jej implementovat opakovaně na mnoha místech pomocí sady funkcí, pod kterou stejně bude ležet nějaká datová struktura seznamu.Podstata je v tom, že když se programátor v záchvatu oop-vitosti rozhodne ten list uvnitř objektu skrýt, tak na něm ten reverse neudělám.
Možná jste zvolil nevhodný příklad, nebo vyrábíte problém, kde není. To je můj názor, neberte to jako boj.
Možná jo, i když za těch 30 let, co se motám kolem počítačů, už na žádné zázračné stříbrné kulky, co dokážou skolit každý problém jedinou ranou, fakt věřit nezačnu. Jednu nesnáz vyřeší, další dvě způsobí. Ale když už porovnávat a vylepšovat, tak pro boha ne s javským (nebo nedej bože dokonce C++kovým), ale se smalltalkovským pojetí OOP. Pak totiž třeba přijdeš na to, že všechny ty pseudoproblémy OOP jsou ve skutečnosti problémy Javy nebo C++ a jejich podtřídně-typového programování, ale ne samotného objektového programování, s nímž mají společnou vážně jen možnost odvozovat podtřídy.Naprostý souhlas, v tomhle nejsme v žádném sporu.
Root.cz (www.root.cz), informace nejen ze světa Linuxu. ISSN 1212-8309
Copyright © 1998 – 2023 Internet Info, s.r.o. Všechna práva vyhrazena. Powered by Linux.