17 Feb
2018
17 Feb
'18
5:49 a.m.
On Fri, 16 Feb 2018 14:28:35 -0800 Larry McVoy <lm(a)mcvoy.com> wrote:
On Fri, Feb 16, 2018 at 02:05:09PM -0800, Bakul Shah
wrote:
By issuing this challenge you automatically "win" as no one is
going to take up your challenge and spend the kind of time
that was needed to optimize GNU grep. Very clever of you! But
if you are serious, it is only fair that both sides start with
a clean slate.
Here's a somewhat related problem: Consider trees with zero or
more integers as leaves. For example, ((1 2)3(4 (5 () 6))).
A file contains 0 or more such trees. Write a tree-grep to
find and print trees with matching fringes. For example:
.*3.*5.* matches the above tree
.*(3).* doesn't as there is no subtree with 3 as its sole leaf
.*(.*2)[2,3].* also matches
.*(.*2.+).* doesn't as 2 is the last leaf and we want at least one more
.*(4#(.*().*).*).* matches -- (4...) contains (.*().*) 0 or more levels down.
. is any, * is 0 or more, + is 1 or more, # is like ** in zsh.
[...] is used to specify alternatives. e.g {0-5,11-23, 99-}.
Assume unsigned ints.
#(5.*) says there is some subtree with 5 as the first leaf.
Syntax needs to be refined to be able to exactly specify
the shape one wants.
For extra credit also generate a tree-sed!
If you want to do more of an apples to apples comparison, you
should pick a brand new problem not known to be solved in
either C or Lisp so that both sides start at the same point!
Nope. It's my challenge and it stands as I stated it. People said
I was wrong when I said Lisp was perceived as slow. I picked a
perfectly reasonable example of a common problem (text processing),
gave a benchmark, gave a pointer to how the C program was made fast,
and asked for a lisp program that even comes close. I'm more than willing to be wrong, that's
how I learn. But the proof
here is to show up with a pure lisp grep that is fast as the C version.
I'm no lisp expert, not by any stretch, but I've never seen a lisp
program that out performed a well written C program.
http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html
Has a comparison of several languages used for implementing
raytracing. Harrop's graph is weird but for 32bit word
machines Stalin comes close to g++ results.