Ranges to deal with corner cases and "random access"

Brett Brett at gmail.com
Sat Oct 5 00:38:06 UTC 2019


Typically a lot of algorithms have corner cases such as 
referencing elements that end up out of bounds at the start or 
end (k-c or k+c).

Is there any way to handle such things easily without having to 
worry about the corners?

E.g., have it return a default value such as 0, or repeat the 
values or periodically extend it.


The idea is not to have to code for the corners like

if (k - 1 < 0) { return 0 }
return data[k-1]/(k+1);



Many algorithms need to reference other parts of the data by 
index and which that index may be out of bounds for some corner 
cases. The idea I'm wanting is to be able to unify the corner 
cases and a very simple way so they can be ignored and ranges can 
be used simply and properly to avoid these corners. This 
simplifies coding and having extra corner case algorithms that 
only deal with the corners yet are functionally identical.



The idea with history:

https://forum.dlang.org/thread/yfppxywqonzsdjpsjbta@forum.dlang.org

But the issue is that it retains the history which is wasteful.


I see no easy way to access other data elements in a unified way.

With ranges one has to recompute the values but for certain 
inputs such as already computed arrays this is not necessary. 
Having an optimal way to memorize exactly what is needed(no 
excess) and to 0, constant, or continuously extend data for 
corner cases would make using ranges, in many mathematical 
algorithms, very useful...

else in many of these cases they offer nothing over the long 
winded coding. Ideally the the range semantics can make it very 
efficient such as:

1. If no non-local access is used(other values) then no 
memorization takes place.  Else it memorizes only up to what is 
used with the option for recomputation or storage. If the input 
is an array then the values are already computed so it is not 
necessary to do anything.

2. The ability to extend data outside the "accessible" range in a 
common format. Generally there are 4 methods:
    Any values accessed outside the "range" are set
    a) Zero.
    b) The end point value(constant extend) = continuously extended
    c) By extrapolating from the "inside" values(linear, 
quadratic, etc) = differentially extended
    d) Periodic/wrapping. Uses the other side of the boundary.

    but a 5th is common which is specifically setting some values.

    For optimization usually an algorithm is split in two multiple 
parts that deal with the boundaries separately since it 
conditionals which are not needed inside the data set.

3. Ability to access already computed values with the same 
solutions above!

These generally will cover 99% of algorithms and unify them.


I imagine D has the ability to do this but I'm not sure how to 
make it all work with ranges.

If one can carry over compile time information then maybe the 
"history" can be references in the common range algorithms by 
extending, e.g:

someRange.zeroExtend.map!((a,k,r){ return a + a[k-1]*r*r[k-1]; })

Here a is a special element, it is wrapped to handle out of 
bounds access given an opIndex to return them(could even be used 
to assign). r is previously computed values. If [j] is out of 
bounds or not computed yet then it returns 0(rather than 
crashing).

Only 2 to 3 value needs to be "memorized", r and the previous(and 
they are overwritten each iteration). The a's do not need to be 
memorized if the source is an array, else we would need to 
memorize 1 value.


For example..

iota(-10,10).zeroExtend.setValues(0=>1,1=>1).map!((a,k,r)=>r + 
r[k-1]);

Would produce the Fibonacci sequence.

Now recurrence basically does this but is less general.

One of the things that have limited my use of ranges is precisely 
these issues. I find that if I can't deal with certain common 
issues easily with ranges then I just do things the old fashion 
way.

Most algorithms I have corner cases and I either have to deal 
with it either with ranges or loops... each one requires 
separation... with loops though sometimes I can make things 
efficient by some tricks(e.g., using goto).

If I can get ranges to do these things simply and naturally then 
I'm more likely to use them.











More information about the Digitalmars-d-learn mailing list