4 ms·
Keep in mind that functional programming is inherently less efficient than a random access machine[1]: ... And it is not easy to create their equally efficient
by ambrop7 12y ago
Keep in mind that functional programming is inherently less efficient than a random access machine[1]:
... And it is not easy to create their equally efficient general-purpose immutable counterparts. For purely functional languages, the worst-case slowdown is logarithmic in the number of memory cells used, because mutable memory can be represented by a purely functional data structure with logarithmic access time (such as a balanced tree).
In this case I think you could use (a pair of?) balanced trees to keep a mapping between the graph and the FIbonnaci heap, as well as for any "mutable" state you need to keep per node.
[1] http://en.wikipedia.org/wiki/Functional_programming#Efficiency_issues http://en.wikipedia.org/wiki/Functional_programming#Efficien...
- colanderman 12y agoThe funny thing about that? There's no such thing as a random access machine. Everything's O(log n). Modern architectures don't even provide random access for more than a handful of kilobytes. Anything that doesn't fit in the L1 cache incurs access latency roughly proportional to the logarithm of its size.
- xyzzyz 12y agoFortunately, most functional languages (including Haskell) provide mutable random access arrays, so the slow-down is theoretical.
- acqq 12y agoBut then the code is not "pure" anymore and it even isn't different than the non-functional one.
- xyzzyz 12y agoThis just proves that "pure" in this sense is a useless concept.
- lvh 12y agoHow so? All I'm seeing is that some speedups aren't possible. It still seems like a useful concept, particularly since "faster" was never one of its promises (maybe "easier to parallellize", though.).
- lucian1900 12y agoInterestingly, in some cases it is actually faster. Modern hardware is peculiar in that respect.
- mijoharas 12y agoMy solution would be to make two changes. One to the fibbonacci heap and one to the graph that Dijkstra's is being used on. I would have the pointers in the Dijkstra's graph be pointers to a mutable data structure (we do this to make sure there is only one place that we need to update per node in the fibbonacci heap and to localize our mutability and keep it out of the rest of our code). I would then need to update the update code in the fibbonacci heap to take a general function which it will run on the nodes that are updated and which gets passed the original and updated nodes pointer. In the Dijkstra case you simply need to write a function which takes these pointers and has the mutable data structure and modifies it accordingly. Thus you have kept your generality, confined your mutability and solved your problem at the expense of one pointer indirection and an added callback function (and the associated documentation).
- Dewie 12y agoBut you can still provide a pure interface. If you implement Dijkstra in an imperative fashion, with lot's of mutations etc., as long as you don't have any external side effects (changing global variables or input variables) and return an immutable result, the function is pure for all practical purposes, even though it is implemented in an imperative fashion/style.
- carterschonwald 12y agoThe theoretical slow down only holds for a strict functional language. In a lazy evaluation strategy language the mutation that happens when a thunk is evaluated and replaced with the result makes the asymptotic claims invalid.
- pflanze 12y agoCan you show an example to support your claim (of the invalidity of the asymptotic claims with lazy evaluation)? Given that the lazy term is evaluated (and thus the mutation happening) only once, how does that enable one to avoid the log(n) slowdown of updating mappings?