Re: Data structure challenge

[dragonchild]

I've been thinking about this. Obviously, this is do-able in C (and similar languages), as you have C-like pseudo-code in your challenge. But, other than sparse arrays¹, what would be practical benefit of this data structure be? If you add in a hashing function to map strings to your set of i, you still have the collision issue.

Are you considering this as a possible implementation of the arrays Perl's hashes use? It would seem kinda wasteful to add an indexing array just to avoid clearing and initializing in O(n) ...

---

¹ I say sparse arrays because in the 2-array method, U doesn't have to be the upper limit of all i. It simply has to be the upper limit of how many i you can have at one time. So, if you know you'll only ever have a max of 10 things, they could be in the set of 2**32, but you would only need 2 10-element arrays and a short as your C.

[Abigail-II]

But, other than sparse arrays1, what would be practical benefit of this data structure be?

Worst-case constant time operations, regardless of how many elements there are in the data structure.

If you add in a hashing function to map strings to your set of i, you still have the collision issue.

Well, yes. Don't do that then. ;-) As I said, it only 'works' if you know certain things about your set - in this case, you know you are only going to store non-negative integers not exceeding U.

Are you considering this as a possible implementation of the arrays Perl's hashes use?

No.

I say sparse arrays because in the 2-array method, U doesn't have to be the upper limit of all i. It simply has to be the upper limit of how many i you can have at one time. So, if you know you'll only ever have a max of 10 things, they could be in the set of 2**32, but you would only need 2 10-element arrays and a short as your C.

In the 2-array method I described, it's essential U is the upper limit of all i, because i is used as an index in the array A.

Abigail