[DGD] A good bigmap

[Dread Quixadhal]

A mapping is probably implemented as a hash table in the driver?

If so, and if you can’t (for “reasons”) just arbitrarily increase the number of buckets used, you could perhaps implement your own hash table in LPC.  That would, effectively, make it has hash backed hash table.

If the driver version is O(1) (dynamic resizing), you could implement a O(log N) version simply and still maintain O(log N).  I hate math, so you might care about https://en.wikipedia.org/wiki/Hash_table for actual details.

The few places I needed such a thing in my DikuMUD, I just used the simplistic linked-list backed version, which is still fast enough for my purposes.  If you expect to have lots of collisions, you may want to research some of the variations to see what will spread things out the best for your use case.

Sent from Mail for Windows 10

From: Raymond Jennings
Sent: Wednesday, August 1, 2018 9:28 PM
To: All about Dworkin's Game Driver
Subject: [DGD] A good bigmap

Ok, so, I've been grappling with this for awhile.

What's a good way to make a general purpose "big mapping"?

My bigstructs have served well as a fallback, but they have weaknesses.

skotos's code appears to be special case.

basically, I need a way to, with O(log N) complexity and O(N) space,
store a mapping of arbitrary size.
____________________________________________
https://mail.dworkin.nl/mailman/listinfo/dgd