Mapping with continguous ranges of keys

[Terry Reedy]

On 12/15/2016 4:30 PM, Thomas Nyberg wrote:
> On 12/15/2016 12:48 PM, Terry Reedy wrote:
>> On 12/15/2016 12:27 PM, Thomas Nyberg wrote:
>>>
>>> I haven't dealt with a data structure exactly like this, but it's
>>> basically a sparse array.
>>
>> A sparse array has at least half missing values.  This one has none on
>> the defined domain, but contiguous dupicates.
>>
>
> I'm sorry for devolving into semantics, but there certainly isn't a
> single definition of "sparse array" out there. For example, the
> definition in wikipedia (https://en.wikipedia.org/wiki/Sparse_array)
> doesn't agree with you:

I think it does ;-).

> "In computer science, a sparse array is an array in which most of the
> elements have the default value (usually 0 or null)."

Let's devolve to a memory-based language like C. An physical array 
consisting of sequential memory locations must have *some* bit pattern 
in every byte and hence in every multibyte block.  If I remember 
correctly, C malloc initialized bytes to all 0 bits, which is an int 
value of 0 also.  If there is no meaningful value, there must be a 
default value that means 'missing'.  0 may mean 'missing'. Null values 
are by definition non-values.  Python uses None as a Null.  If the 
example had been populated largely with Nones, I would have called it 
'sparse'.

 > Personally my usage of sparse arrays in scipy has _always_ had all
 > defined values it's just that the default value was 0. I never deal
 > with "missing" values.

Lucky you.  In statistics and analysis of real, experimental data, 
missing values are often a possibility.  They are always a nuisance, 
sometimes a major one.  When the data are represented by arrays,  rather 
than by some compacted form, some value has to be chosen to represent 
the absence of of data.

-- 
Terry Jan Reedy