Talk:Recaman's sequence: Difference between revisions
A funny optimization that affects half of the implementations of this task
m (added a scatter plot.) |
(A funny optimization that affects half of the implementations of this task) |
||
Line 407:
└──█──█────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
</pre>
== A funny optimization that affects half of the implementations of this task ==
Several implementations of this task are translations of the same algorithm ([[Recaman%27s_sequence#AWK|AWK]], [[Recaman%27s_sequence#Microsoft_Small_Basic|Microsoft Small Basic]], [[Recaman%27s_sequence#C|C]], [[Recaman%27s_sequence#C.2B.2B|C++]], [[Recaman%27s_sequence#C.23|C#]], [[Recaman%27s_sequence#Go|Go]], [[Recaman%27s_sequence#D|D]], [[Recaman%27s_sequence#Kotlin|Kotlin]], [[Recaman%27s_sequence#Java|Java]], [[Recaman%27s_sequence#Julia|Julia]], [[Recaman%27s_sequence#Lua|Lua]], [[Recaman%27s_sequence#Objeck|Objeck]], [[Recaman%27s_sequence#Phix|Phix]], [[Recaman%27s_sequence#PHP|PHP]], [[Recaman%27s_sequence#Visual_Basic_.NET|Visual Basic .NET]] and my own one ([[Recaman%27s_sequence#F.C5.8Drmul.C3.A6|Fōrmulæ]]), 16 at the moment of writing this comment). The reason is simple, the algorithm used is compact, fast and clear.
However, a further optimization can be done. In order to detect when the 0..1000 integers are generated, it uses a set or array (usually named "used1000", initially containing the zero element) in order to store the numbers <= 1000 that were already generated. It is unnecessary, the same can be performed with a scalar initialized as 1, and incremented every time a new integer is generated. It will never be added again (for the same integer), because it is prevented by the testing for the integer in a unique set or array (usually named "used").
Note that the "used1000" array (or set) is never used to retrieve an element in any position, or the existence of a given element. Instead, it is used solely to check its size.
This optimization affects the space, not the time performance, because it is better to have a scalar instead of an unused 1001-element set or array.
[[User:Laurence|Laurence]] ([[User talk:Laurence|talk]]) 19:10, 19 September 2019 (UTC)
| |||