logicchains / lpathbench Goto Github PK
View Code? Open in Web Editor NEWBenchmarks of the longest path problem in various languages
License: MIT License
Benchmarks of the longest path problem in various languages
License: MIT License
I'm looking at D's results on x86-64 and how they varied today between the runs (1894 1799 2214 1959) without (as far as I could tell) D's code or command line changing between these specific commits.
It might be beneficial to take either the best out of 10 runs, or the average of 10 runs to smooth out the differences and get more consistent results.
Hello, i need to find the longest path in a graph. I've found your code and i'm trying to implement something like it on my own. But i can't make it print what is the longest path. It only prints the weight.
Can you show me in your python code how you could print the longest path nodes?
I offer a version written in C for inclusion in the benchmark:
https://gist.github.com/nkurz/5e49ba0ddb04e23de03f
I've only tested on Haswell under Linux, but results are good when compiled with gcc-4.8 -O2:
// 8981 LANGUAGE C 623
// 8981 LANGUAGE C++/clang 734
// 8981 LANGUAGE C++/gcc 755
I have tested, but I think the implementation should continue to perform well with larger graph sizes.
Maybe? :P
The first version of the page I saw had a (slightly disappointing wrt. x86-64) result for OCaml-ARM which I don't see in the writeup anymore. Is it a simple omission or are there technical problems that prevents the results to be recomputed?
Are you interested in adding a Factor (http://factorcode.org/) implementation for the benchmark? I wrote one here: https://github.com/bjourne/playground-factor/blob/master/lpath/lpath.factor
rustc rs.rs -C opt-level=3 -C no-stack-check
rs.rs:24:49: 24:50 error: unexpected token: `]`
rs.rs:24 unsafe { mem::transmute(self.routes[]) }
BTW, I had to change --opt-level=3
to -C opt-level=3
in makefile
The writeup describes this problem as NP-complete, but it cannot be since it is not a decision problem. It is in fact NP-Hard. The introduction on Wikipedia to the problem covers this.
There's a much clear version of the Haskell implementation at http://lpaste.net/121012.
See the discussion at http://haskell.1045720.n5.nabble.com/Haskell-implementation-of-longest-path-algorithm-td5765786.html.
I thought I'd write a C implementation to compare to the C++. I decided to start blind rather than looking at the other implementations. Everything I did was taking much longer than your benchmarks, and I was consistently getting a higher number than your code.
Eventually I started printing intermediate values, and I noticed that your answer matched the number I got starting from starting from node 0, but I had been looking for the "longest node in the graph" as the text said. Since I was looping over every start point in keeping with the brute force theme, my runtimes were about 15x what I thought I'd achieve. Finally I looked at the source for some other implementations, and they seemed to be checking only from starts at node 0.
Is this correct, or am I doing something stupid? If correct, perhaps you could change the writeup to reflect this?
I'm not really sure if I'm missing something, but why are you using case
to pattern match on a boolean in the Haskell source, when all of those
case isVisited of
True -> ...
False -> ...
could be replaced by simple if isVisited then ... else ...
?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.