Summarize and say sequence: Difference between revisions

Content added Content deleted
(Changed the key of cache to a seq[char] which eliminates a "join" and improve performance by almost 50%.)
Line 2,902: Line 2,902:


=={{header|Nim}}==
=={{header|Nim}}==
A version which uses a cache to store the number of iterations and thus avoids to compute the sequence for each permutation. The version without cache ran in 19s. This version runs in less than 500ms.
A version which uses a cache to store the number of iterations and thus avoids to compute the sequence for each permutation. The version without cache runs in more than 9 seconds. This version runs in less than 300 ms.


<lang Nim>import algorithm, sequtils, sets, strutils, tables
<lang Nim>import algorithm, sequtils, sets, strutils, tables


var cache: Table[string, int] # Cache seed -> number of iterations.
var cache: Table[seq[char], int] # Maps key -> number of iterations.




Line 2,930: Line 2,930:
proc seqLength(seed: string): int =
proc seqLength(seed: string): int =
## Return the number of iterations for the given seed.
## Return the number of iterations for the given seed.
let seed = sorted(seed, Descending).join()
let key = sorted(seed, Descending)
if seed in cache: return cache[seed]
if key in cache: return cache[key]
result = toSeq(sequence($seed)).len
result = toSeq(sequence(seed)).len
cache[seed] = result
cache[key] = result




Retrieved from "https://rosettacode.org/wiki/Summarize_and_say_sequence"