▼Ra  List:   Purely Functional Random-Access Lists
►4 Benchmarks
On this page:
4.1 Random-access vs. Sequential-access lists
run-ra-list-benchmark
4.2 Contracted vs. Uncontracted bindings
run-contract-benchmark
4.3 Frequency counting
run-freq-count-benchmark
4.4 Garden fence encryption
encrypt
decrypt
run-garden-fence-benchmark
  top  ← prev  up  next → 

4 Benchmarks

 (require data/ralist/run-benchmarks) package: ralist

Runs all of the benchmarks for this package.

4.1 Random-access vs. Sequential-access lists

 (require data/ralist/benchmarks/ra-list)
  package: ralist

This benchmark compares the performance of typical list operations for random and sequential lists.

procedure

(run-ra-list-benchmark) → void?

Runs this benchmark.

4.2 Contracted vs. Uncontracted bindings

 (require data/ralist/benchmarks/contract)
  package: ralist

This benchmark compares the performance of the contracted and uncontracted bindings.

procedure

(run-contract-benchmark) → void?

Runs this benchmark.

4.3 Frequency counting

 (require data/ralist/benchmarks/freq-count)
  package: ralist

This benchmark compares an number of imperative and functional solutions to the problem of counting the frequencies of each number in a given list of numbers.

See the thread starting here for discussion.

procedure

(run-freq-count-benchmark) → void?

Runs this benchmark.

4.4 Garden fence encryption

 (require data/ralist/benchmarks/garden-fence)
  package: ralist

This benchmark compares solutions to the problem of garden fence encryption.

Garden fence encryption works as follows: you are given a plain text message (String) and a key (Nat). You scramble the message by a process that depends on the given key, producing a cipher text message (String) of the same length as the given plain text message. The scrambled message can be de-scrambled to obtain the original message by an inverse process when it is given the same key.

procedure

(encrypt s k) → string?

  s : string?
  k : natural-number/c
Produce the cipher text of the given string using the given key.

procedure

(decrypt s k) → string?

  s : string?
  k : natural-number/c
Produce the plain text of the given string using the given key.

Examples:
> (encrypt "diesisteinklartext" 6)

"dkinleiasertittxse"

> (decrypt "dkinleiasertittxse" 6)

"diesisteinklartext"

The process of scrambling a message works in a zigzag form. The key gives the number of lines to the zigzag. So suppose we want to encrypt the message "diesisteinklartext" with the key 6. Imagine the characters of the string are arranged in a zigzag, or wave, or even fence-like pattern, where the height of the wave, or zigzagging fency thing is 6:

;;;; 1. d         k         = (d k)     = "dk"

;;;; 2.  i       n l        = (i n l)   = "inl"

;;;; 3.   e     i   a       = (e i a)   = "eia"

;;;; 4.    s   e     r   t  = (s e r t) = "sert"

;;;; 5.     i t       t x   = (i t t x) = "ittx"

;;;; 6.      s         e    = (s e)     = "se"

The characters are grouped by line, forming the lists above. The lists are appended in order to obtain the resulting cipher text: "dkinleiasertittxse".

The following solutions are included in the benchmark:

  • An imperative, vector-based algorithm.

  • A functional translation of the above using random-access lists.

  • A functional algorithm designed by output structure.

  • A combinator style algorithm.

  • A cyclic sequence algorithm.

See the thread starting here and here for discussion.

procedure

(run-garden-fence-benchmark) → void?

Runs this benchmark.

  top  ← prev  up  next →