Date: Wed, 10 Feb 2021 08:54:03 -0700
> On Feb 10, 2021, at 8:32 AM, Ville Voutilainen <ville.voutilainen_at_[hidden]> wrote:
>
> On Wed, 10 Feb 2021 at 16:45, Jeff Garland
> <jeff_at_[hidden]> wrote:
>>> Right. But sparse vs. dense matrices are what I think about when I see
>>> a suggestion for a sparse list,
>>> and I don't see how this std::hive (yay, surreptitious sleight-of-hand
>>> in play, caveat emptor :P) is more
>>> sparse than a linked list, it seems *less* sparse because there are
>>> allocated-but-skipped slots in it.
>>
>> Ok — if I follow you’re saying a ’sparse matrix’ representation would have less storage per unit size than a ‘dense matrix’. Interesting.
>
> What do you mean "by unit size"? But, well, what I mean is below..
Yes, sorry - matrix dimensions. 2x2 sparse matrix (aka diagonal for example) maybe only requires 2 data slots while a ‘dense’ 2x2 has 4 of course.
>
>> Unfortunately the hexagonal slot pattern is burned into the image of a ‘hive’ — very ordered cells.
> That doesn't make it random-access from the point of view of how bees
> go from outside to cell $foo,
> or how they go from cell $foo to outside. There's tunnels and layers
> and storage structures, and no
> random access because, well, if a bee is looking for a cell that has
> $bar amount of honey in it,
> there's an access that needs to look at more cells than just going
> straight to the right one. Some of
> those cells are in a skip list. :P
The analogy is getting stronger :)
>
>> That’s fair. The thing is that the ‘fleeting nature’ of elements in a colony is much more like the ‘moving traffic’ that comes and goes than the buildings. Although, to be fair, the use case involves both kinds of elements — some mostly static and some that come and go quickly.
>>
>> I’m not strongly against ‘hive’ at this point, it’s better than ‘colony’ in my opinion. Just not sure it’s better than block_list or some other function describing variant.
>
> That does seem like an alternative that describes the structure more
> than it does describe the purpose. But, then again,
> that's somewhat consistent with what we've had before. But also
> somewhat inconsistent, an unordered_map is not
> a hash_keyed_list_of_buckets.
True, and that name wouldn’t help the user decide if they want to use it like ‘unordered’ does - it actually obscures the function. But, I’m actually starting to think that in this case ‘bucket_list’ might really be better — I was half joking when proposing, but ‘buckets’ have their own analogy here from the real world and from implementations of hashed containers. They are often partially empty. You put stuff in and out of them. In hash buckets you skip over empty slots in the traversal. Buckets get allocated/deallocated as a unit. And it’s pithy ;0
Jeff
>
> On Wed, 10 Feb 2021 at 16:45, Jeff Garland
> <jeff_at_[hidden]> wrote:
>>> Right. But sparse vs. dense matrices are what I think about when I see
>>> a suggestion for a sparse list,
>>> and I don't see how this std::hive (yay, surreptitious sleight-of-hand
>>> in play, caveat emptor :P) is more
>>> sparse than a linked list, it seems *less* sparse because there are
>>> allocated-but-skipped slots in it.
>>
>> Ok — if I follow you’re saying a ’sparse matrix’ representation would have less storage per unit size than a ‘dense matrix’. Interesting.
>
> What do you mean "by unit size"? But, well, what I mean is below..
Yes, sorry - matrix dimensions. 2x2 sparse matrix (aka diagonal for example) maybe only requires 2 data slots while a ‘dense’ 2x2 has 4 of course.
>
>> Unfortunately the hexagonal slot pattern is burned into the image of a ‘hive’ — very ordered cells.
> That doesn't make it random-access from the point of view of how bees
> go from outside to cell $foo,
> or how they go from cell $foo to outside. There's tunnels and layers
> and storage structures, and no
> random access because, well, if a bee is looking for a cell that has
> $bar amount of honey in it,
> there's an access that needs to look at more cells than just going
> straight to the right one. Some of
> those cells are in a skip list. :P
The analogy is getting stronger :)
>
>> That’s fair. The thing is that the ‘fleeting nature’ of elements in a colony is much more like the ‘moving traffic’ that comes and goes than the buildings. Although, to be fair, the use case involves both kinds of elements — some mostly static and some that come and go quickly.
>>
>> I’m not strongly against ‘hive’ at this point, it’s better than ‘colony’ in my opinion. Just not sure it’s better than block_list or some other function describing variant.
>
> That does seem like an alternative that describes the structure more
> than it does describe the purpose. But, then again,
> that's somewhat consistent with what we've had before. But also
> somewhat inconsistent, an unordered_map is not
> a hash_keyed_list_of_buckets.
True, and that name wouldn’t help the user decide if they want to use it like ‘unordered’ does - it actually obscures the function. But, I’m actually starting to think that in this case ‘bucket_list’ might really be better — I was half joking when proposing, but ‘buckets’ have their own analogy here from the real world and from implementations of hashed containers. They are often partially empty. You put stuff in and out of them. In hash buckets you skip over empty slots in the traversal. Buckets get allocated/deallocated as a unit. And it’s pithy ;0
Jeff
Received on 2021-02-10 09:54:10