Map with ordered keys

A theoretical example

• The main data structure, a gb_tree with:
  [{0, %{user: :a}}, {1, %{user: b}}, {2, %{user: z}}, {3, %{user: a}}
• The index, a Map of lists with:
  %{a: [0, 3], b: [1], c: [2]

You then iterate over the gb_tree until you find something you want to delete/process; then, to find out which other entries you need to delete, you consult the index rather than iterating over all the entries.

Then, once you’ve finished processing that particular group of objects, you can continue iterating where you left of (gb_tree does provide a function for this.)

All that it’s left is to write the bookkeeping code necessarily to ensure the two structures remain consistent with each other for every write.

You may also consider indexing your objects on every write, based on the property that binds distinct groups of them together across the ordered data structure.

This will increment memory usage and make each individual write more expensive - but not much so, if the right data structures are leveraged (e.g. a gb_tree for the ordered bit and a Map of lists for indexing stuff.)

The coordinated management of the two data structures (the main one plus the index) can be kept behind an API to keep it simple to use and reason about.

1. Are the keys the order of requests, and it’s desired to process in FIFO order?

2. Does the list of matches also need to be returned in FIFO order?

Am I understanding it correctly like this:

If you have structure like this

objects = [1: a, 2: c, 3: x, 4: c, 5:c, 6: a, 7: d]

Your algorithm loops over each element, finds 1:a and searches for all a (6 in this case).
Delete 1 and 6 and send a message to some process?
And then repeat this for the remaining entries? Starting with 2: c?

Is this correct?

If it’s correct, then can’t you sort the objects by the items first and then do the other actions on them, so sorted like: `a: 1, 6 - c: 2, 4, 5 - x: 3 - d: 7]?

This brings the logarithmic complexity down from an O(n2) to an O(n log n) operation and should be much faster

Need to continually perform the following operation:

1. Iterate through the list of objects, (ordered by key (monotonically incrementing integer))
   1.1 for each object:
   1.1.1 Iterate again through the list of objects, make a list of objects which can be matched with the current object
2. delete the current object, delete the list of matched objects (both operations by key)
   2.1 send a message with the object and it’s matches to another system
   2.1 GOTO 1

Can you explain the problem a bit more? I’m not sure I understand how an map with ordered keys will help with this exactly. Maybe there are other data structures that would be suited better?

The BEAM languages and Rust are a natural pair – both emphasize safety and never actually crashing (in terms of an OS process).

I know what it is to be very busy and to have an eternally huge backlog. So definitely not excuses as you said, we just have only so much focused creative time per day.

But my recommendation stands for when you have the time. Rustler works very well.

Typical use case would be to match people looking to rent or let property by geographic area. Perform a periodic rollup across all users. Remove users who had already been matched. Have tried with ETS but was only able to process 80,000 per second. Personal challenge is to find a way to match 200,000.

Can you share the use case for an ordered map? I super curious!

Thanks @mpope some good points there. exor_filter/c_src/xor_filter_nif.c at master · mpope9/exor_filter · GitHub yeah good example of resource allocation/deallocation - at least it’s reasonably straightforward in BEAM compared to say for example writing a Java native extension. Good point about the dirty NIF.