This project implements the phone number encoding described by Lutz Prechelt in his article for the COMMUNICATIONS OF THE ACM (October 1999/Vol. 42, No. 10), Comparing Java vs. C/C++ Efficiency Differences to Interpersonal Differences, later re-used for a more extended paper, An empirical comparisonofC, C++, Java,Perl, Python, Rexx, and Tclfor asearch/string-processing program from March, 2000.
The same problem was later used by Ron Garret (aka Erann Gat) on Lisp as an alternative to Java, also from the year 2000.
The instructions given to participants of the latter study (which was slightly adapted from the original paper, and used to implement my own solution in this repository) can be found at flownet.com.
Peter Norvig, after finding out about the Lisp paper, wrote his own Lisp program to solve the problem.
His solution is included in this repository at src/lisp/main.lisp as a baseline for performance measurements (see benchmark.sh).
The solution I first came up with is in src/java/Main.java.
Later, I ported Norvig's Lisp solution to Java (src/java/Main2.java) and Rust (src/rust/phone_encoder/src/main.rs).
In order to be able to benchmark the programs, I created a few utilities in Java and Rust:
To run the benchmarks, a shell script, benchmark.sh, is used.
The benchmarks currently require the following tools:
rustc 1.53.0 (53cb7b09b 2021-06-17)).Run this command to compile the Java solutions:
$ javac src/java/*.java -d buildTo compile the utilities, run:
$ javac src/java/util/*.java -d buildCompile the Rust solution:
$ cd src/rust/phone_encoder
$ cargo build --releaseCompile the Benchmark runner:
$ cd src/rust/benchmark_runner
$ cargo build --releaseNo compilation is required.
$ java -cp build Main dictionary.txt input.txtFor all programs, you can use the smaller dictionary at tests/words.txt and input file tests/numbers.txt to print just a few results.
$ cp src/rust/phone_encoder/target/release/phone_encoder .
$ ./phone_encoder dictionary.txt input.txt$ sbcl --script src/lisp/main.lisp dictionary.txt input.txtTo verify that your program works correctly execute it with arguments dictionary.txt input.txt, piping its output
to a file, say prog_out.txt, then run:
$ diff -q <(sort prog_out.txt) <(sort output.txt)If diff exits with 0 and does not print anything, your program is good.
The benchmarks generate input files of different sizes by running my Java utility. If you want to try your solution with larger inputs, try this, for example, to generate 50,000 random phone numbers:
$ java -cp build/util util.GeneratePhoneNumbers 50000 > phones_50_000.txtTo partially check your solution works with the larger inputs (the checker cannot guarantee that the digit-substitution algorithm is perfectly correct), run my Java utility as follows:
$ java -cp build/util util.OutputChecker dictionary.txt program_output.txtI've published the benchmarks results on a Google Docs Spreadsheet.
To run it yourself, checkout this repository and run:
See the requirements above first.
./benchmark.shI don't currently intend to accept pull requests to this repository because I used the programs in this repository on an article I wrote on my website and I don't want it to become stale.
However, feel free to fork it and modify it as you see fit!
src/lang/ (e.g. src/lisp/main.lisp).Requirements section.echo "Compiling Rust sources" block.COMMANDS array.I've found the following other solutions to Prechelt's phone number encoding so far:
This repository includes also Dart and Julia solutions in the
dart and julia branches, respectively.