How can I obtain the sorting order of the current key at once through the ordered_st type of ETS?

Questions / Help
,
1

When I use ETS of ordered-set type
I want to use ets: lookup/2 to query a key and also know its current sorting position
Similar to using ets: select_count/2, but select_count is too slow. Is there any good solution?

2

There are two different kinds of ordered_set: one without write_concurrency (AVL tree), and one with (CA-Tree). Neither one currently implements rank/order operation.

I can imagine repurposing BIT/Fenwick tree for this, but can’t imagine doing that in ETS with concurrent access.

1 Like
3

(╥﹏╥)
My current code is roughly like this
There are 100000 pieces of data in ETS
It takes approximately 10-50ms to complete
Is there a way to optimize it?

Ms = ets:fun2ms( fun(#ets_rank_atk_record{compare_tuple = C1} = R) when C1 >= CompareTuple->R end),
Rank = ets:select_count(?ETS_RANK_ATK, Ms),
4

What are you actually trying to do here? :sweat_smile:

5

What are you actually trying to do here?

My thoughts exactly. Knowing the position is pretty useless (there is ets:slot/2 but it’s not something I’d expect to see in normal code), and furthermore the position is invalidated if anything is inserted or deleted before the key in question.

Perhaps there is a use case, but if so I suspect a different data structure should be used.

2 Likes
6

I use points as a key to save in an ordered ETS, and I hope to
Can I obtain the ranking of my current points through my key
I don’t know if there’s a problem with doing this
If other options should be used, I would greatly appreciate it if you could let me know. Thank you

7

I use points as a key to save in an ordered ETS

If I understand you correctly, this means that you:

  1. Have a set table, T1, containing records with some unspecified key type.
  2. Have a second set table, T2, with integer keys being the positions of records in T1.

This is a really odd approach. First of all, you could just use the original T1 key to also index T2, there is no reason to take a detour over integer positions for Erlang ETS tables. Secondly the mapping from key to position is invalidated whenever keys are inserted in or deleted from T1, which means T2 would have to be rebuilt.

What are you actually trying to achieve here?

8

Thank you for your reply :face_in_clouds:
I don’t know if it’s a translation issue, which may have caused my description to be inaccurate,

My requirement is to create a ranking list of 100000 people with points, and the points data will change,

So my idea is to save the points as keys in order_cets,

But if I want to know the ranking of my current points, it seems difficult to quickly obtain it?

Or should I use other data structures? What should I do in Erlang?

9

The key value of an object can’t be changed.

2 Likes
10

Your approach has several flaws.

One is that, as @Maria-12648430 pointed out, you cannot change (via update_counter or update_element) the value in the key position of a record. So if you want to change the points value, you have to read the current record, delete it, then re-insert it with the updated value (or the other way round, first insert the updated and then delete the old).

Also, think of what would happen if two (or more) people have the same points value. Since you are using a set table here (ordered or not), there can only be 1 record per key. Ie, if you would try to insert a record with a point value that some other person already has, you would either be unable to do so (when using insert) or the person currently having the same number of points would be evicted (when using insert_new).

This won’t work, that is Rank will always be 0. The reason is that your match spec returns the record (... -> R) when C1 >= CompareTuple. However, the documentation says that a record is counted if the match spec returns true for it:

If the match specification returns true for an object, that object considered a match and is counted. For any other result from the match specification the object is not considered a match and is therefore not counted.

There is no general answer to this. It depends on the larger picture, and what operations are more important to be fast than whatever else. There will always be a tradeoff, for some things to be faster other things have to be slower, or more resource-hungry.

11

Thank you, I understand now :coffee: