<div dir="ltr">All,<div>I'm doing a conceptual exercise to evaluate the usage of ETS with secondary indices.</div><div><br></div><div>The exercise is really simple:</div><div><ol><li>There are elements which can belong to groups, in a m-to-n relationship (every element can belong to one or more groups).</li><li>Elements and groups can be created/deleted at will.</li><li>We need to find the groups an element belongs to.</li><li>We need to find the elements included into a group.</li><li>We need to not keep an element if it does not belong to a group, nor a group if it does not have elements in it (this is to avoid memory leaks since groups / elements get added / removed).</li></ol></div><div>All of these operations should be optimized as much as possible.</div><div><br></div><div><br></div><div>A. One possibility is to have 2 ETS tables of type <font face="monospace">set</font>, that contain the following terms:</div><div><br></div><div>1. table <font face="monospace">elements</font> with tuple format <font face="monospace">{Element, Groups}</font></div><div>2. table <font face="monospace">groups</font> with tuple format <font face="monospace">{Group, Elements}</font></div><div><br></div><div>Groups and Elements would be maps (so that finding an element of the map does not require traversing an array).</div><div><br></div><div>Adding an <font face="monospace">Element</font> to a <font face="monospace">Group</font> would mean:</div><div><ul><li>An insert in the table <font face="monospace">elements</font> where the <font face="monospace">Group</font> gets added to the <font face="monospace">Groups</font> map (bonus of using a map: no duplicates can be created).</li><li>An insert in the table <font face="monospace">groups</font> where the <font face="monospace">Element</font> gets added to the <font face="monospace">Elements</font> map.</li></ul><div>Retrieving the groups an element belongs to is simple as getting the <font face="monospace">Element</font> in the table <font face="monospace">elements</font>, the groups will be keys of the <font face="monospace">Groups</font> map.</div></div><div><div><div>Retrieving the elements a group contains to is simple as getting the <font face="monospace">Group</font> in the table <font face="monospace">groups</font>, the elements will be keys of the <font face="monospace">Elements</font> map.</div></div><div><br></div><div>Deleting is far from being optimized though. For instance, deleting an <font face="monospace">Element</font> means:</div><div><ul><li>Getting the <font face="monospace">Groups</font> it belongs to with a lookup in the table <font face="monospace">elements</font>.</li><li>For every <font face="monospace">Group</font> in the <font face="monospace">Groups</font> map, remove the <font face="monospace">Element</font> from the <font face="monospace">Elements</font> map.</li></ul><div>It becomes something like this:</div></div><div><font face="monospace"><br></font></div><div><font face="monospace">case ets:lookup(elements, Element) of<br>    [{Element, Groups}] -></font></div><div><font face="monospace">        ets:delete(elements, Element),<br>        lists:foreach(fun({Group}) -><br>            case ets:lookup(groups, Group) of<br>                [{Group, Elements}] -><br>                    case maps:remove(Element, Elements) of<br>                        Elements1 when map_size(Elements1) == 0 -><br>                            ets:delete(groups, Group);<br>                        Elements1 -><br>                            ets:insert(groups, {Group, Elements1})<br>                    end;<br>                _ -><br>                    ok<br>            end<br>        end, maps:keys(Groups))<br>    _ -><br>        ok<br>end.</font><br></div><div><br></div><div>Ouch. Same goes for groups. And this is to delete <b>one</b> element, imagine if bigger operations need to be made.</div><div><br></div><div><br></div><div>B. Another possibility would be to have 2 ETS tables of type <font face="monospace">bag</font>, that contain the following terms:</div><div><br></div><div><div>1. table <font face="monospace">elements</font> with tuple format <font face="monospace">{Element, Group}</font></div><div>2. table <font face="monospace">groups</font> with tuple format <font face="monospace">{Group, Element}</font></div></div><div><div><br></div><div>Adding an <font face="monospace">Element</font> to a <font face="monospace">Group</font> means:</div><div><ul><li>An insert in the table <font face="monospace">elements</font> of the tuple <font face="monospace">{Element, Group}</font>.</li><li>An insert in the table <font face="monospace">groups</font> of the tuple <font face="monospace">{Group, Element}</font>.</li></ul></div></div></div><div><div>Retrieving the groups an element belongs to requires an <font face="monospace">ets:match_object/2</font> or similar such as:</div><div><span style="font-family:monospace">ets:match_object(elements, {Element, _ = '_'}).</span><br></div><div><br></div><div><div>Retrieving the elements a group belongs to requires an <font face="monospace">ets:match_object/2</font> or similar such as:</div><div><span style="font-family:monospace">ets:match_object(groups, {Group, _ = '_'}).</span></div></div><div><br></div><div>So retrieving requires the traversing of a table, but it should be relatively quick, given that the match is done on the index itself.</div><div><br></div><div><div>Deleting is not particularly optimized though, because it requires the traversing of a table with elements that are not indexed. For instance, deleting an <font face="monospace">Element</font> would look something like:</div></div></div><div><font face="monospace">ets:match_delete(elements, {Element, _ = '_'}). %% fast, indexed<br></font></div><div><font face="monospace">ets:match_delete(groups, {_ = '_', Element}). %% not fast, table is being traversed.</font><br></div><div><br></div><div><br></div><div>What would <i>you</i> do? Any takers are welcome ^^_</div><div><br></div><div>Cheers,</div><div>r.</div><div><br></div><div><br></div></div>