6
\$\begingroup\$

I just want to do some benchmarking of different programming languages. So here is a tip: You can use as many characters as you want. In the end there is only the time your program needed.

So, here is the Task:

Task

After searching for a good task that would require a lot of computation, I came up with the problem Is a word in a given Type-1 grammar?

For people not knowing what this is: Formal Grammar  Chomsky-Hierarchy

Maybe there is a better algorithm but I came only up with brute forcing.

So, write a code that brute forces the Grammars as fast as possible.

Rules

  • Parallel execution is allowed
  • Delete your cache after every tested word
  • Add your complete compiler command for optimized result
  • You can use any algorithm and language you want, as long as the job gets done.
  • Add to your answer what files are read/how to set the files that should be read.

I Guarantee

  • Input is always well formatted
  • Variables are always capital letters, Terminals always small ones
  • Words only consist of Terminals
  • No empty Word

Input

For equal footing we need to define what the input looks like. The input is a file. I write multiple grammars and words in one file. The structure can be described with following Pseudocode:

foreach(Grammar G) do
    write('{');
    foreach (Variable V in G) do
        write(T + ',');
    od
    deleteLast();
    write('}');
    linebreak();
    write('{');
    foreach (Terminal T in G) do
        write(V + ',');
    od
    deleteLast();
    write('}');
    linebreak();
    write('{');
    foreach(Production P in G) do
        write(P + ',');
    od
    write('}');
    linebreak;
    write(StartSymbol(G));
    linebreak;
    foreach(Word W for G) do
        write(W + ',');
    od
    deleteLast();
    linebreak;
od
deleteLastLinebreak();

An Example

Output

The output has to be put in a file as well. The formatting of the output does not matter. It should be recognizable which result belongs to which word.

An Example

Example

Here is an example written in C# by myself.

Main Class

Data Classes

Test System

The system the code will run on is following:

  • Arch Linux
  • RunTime you need (if available; Please add in answer)
  • Intel i7-4700MQ 3.4GHz
  • 16GB RAM

How do I test

After the code is compiled I'll run a bash script that runs your program a certain amount of times and calculates the average and median run time.

Good Luck and may the best code win.

My Benchmark: Not completed after 8-9 hours of runtime.

My Benchmark (after changing some words):

  • mean: 39.5157
  • median: 39.448687194

PS: Here is the originally planned input, which took ages with my program. Grammars are slightly changed in the new input and words are way shorter.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Will you test submissions on fixed or random input? In the former case, minimum runtime is usually the better/fairer metric than average. \$\endgroup\$ Jul 27, 2014 at 9:55
  • \$\begingroup\$ @MartinBüttner fixed, but I want to see what the average runtime is, because there is also other stuff running (OS for example). A minimum runtime test would be good if I'd have a dedicated machine for number crunching. Since I don't have one, the programs need to share the processor with other stuff, that varies in its needs... \$\endgroup\$
    – Armin
    Jul 27, 2014 at 10:00
  • 2
    \$\begingroup\$ That's exactly why I'd prefer minimum runtime. Any deviation from the minimum runtime is due to other stuff running. There is no variation in the amount of processor instructions that are carried out by each program, so any fluctuations in runtimes is due to other programs or the OS doing stuff in between. Hence, the closest you get to the true performance of the code is the minimum runtime. I don't think averaging is any fairer, because it only penalises programs where you happen to get an unrelated CPU spike during one of the runs. \$\endgroup\$ Jul 27, 2014 at 10:11
  • \$\begingroup\$ @MartinBüttner following problem: my C# code (sequential) is currently running. I've started 8 hours ago. You can't have a run without spikes from other programs. And there is no way for controlling how often they happen. So, if I take the minimum runtime I could have run a program which was only interrupted 10-200 times per run and another was 50-100 times interrupted. The average might balance this deviation. \$\endgroup\$
    – Armin
    Jul 27, 2014 at 10:17
  • \$\begingroup\$ Another option would be the median to mitigate the effects of outliers. \$\endgroup\$ Jul 27, 2014 at 10:48

1 Answer 1

1
\$\begingroup\$

As the code is rather long, it can be found here (Java 8): http://pastebin.com/Q5Buuqfx

How I did it:

Instead of brute-force creating the possible word combinations and then try to find a match I instead did the reverse and tried to collapse the target word to find the starting point. As a result the path the algorithm has to traverse is much less branched, and the words from the example can all be verified in about 35 ms (on my machine).

As a side-effect of the reverse-search I do not need the first two lines of each task (variables, terminals).

In addition I utilize the Java 8 streaming technology, which allows to easily activate parallel processing with just a single change in one line of code.

Usage: java Grammar <inputFile>

Edit: Did some code cleanup and further speed tests and it ironically turned out, that the algorithm is so fast, that setting up the parallel stream takes longer than the actual task. I now use a single-CPU stream() instead and the complete example input set is processed in ~35 ms on my machine instead of ~80 ms if I use parallelStream().

Edit2: Further testing reveals some strange effects with parallelStream and certain types of Collections. A TreeSet seems to work best in both single and parallel processing. I did some tests on your extended input set and it seems to work fine, except for the task with the looping rules (CD->DC,DC->CD). Detecting and removing those would cause the search to verify instantly.

\$\endgroup\$
1
  • \$\begingroup\$ I'll run it as soon as I get home. I just arrived at work. \$\endgroup\$
    – Armin
    Jul 28, 2014 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.