On this page:
4.1 Random-access vs. Sequential-access lists
4.2 Frequency counting
4.3 Garden fence encryption

4 Benchmarks

 (require (planet dvanhorn/ralist:1:13/run-benchmarks))

Runs all of the benchmarks for this package.

4.1 Random-access vs. Sequential-access lists

 (require (planet dvanhorn/ralist:1:13/benchmarks/ra-list))

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

(run-ra-list-benchmark)  void?
Runs this benchmark.

4.2 Frequency counting

 (require (planet dvanhorn/ralist:1:13/benchmarks/freq-count))

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.

Runs this benchmark.

4.3 Garden fence encryption

 (require (planet dvanhorn/ralist:1:13/benchmarks/garden-fence))

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.

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

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


  > (encrypt "diesisteinklartext" 6)


  > (decrypt "dkinleiasertittxse" 6)


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.

Runs this benchmark.