[erlang-questions] Nested match specifications?

Patrik Nyblom pan@REDACTED
Wed Mar 6 10:37:16 CET 2013


Hi!
On 03/05/2013 05:21 PM, Diego Llarrull wrote:
> Ivan, Patrik:
>
> Thank you both for the swift replies! Both provided functions that 
> yield the desired results. The functions are:
>
>  (I) ets:match(table, {"Peter", [{"children", '$1'},'_'] }).         
>                 (Ivan's)
> (II) ets:select(xxx,ets:fun2ms(fun({"Peter",[{"children",Data}|_]}) -> 
> Data end)).   (Patrick's)
>
> (II) is effectively rendered to
>
> ets:select(xxx,[{{"Peter",{"children",'$1'}},[],['$1']}])
>
Well, it's rendered to
ets:select(xxx,[{{"Peter",[{"children",'$1'}|'_']},[],['$1']}])
i.e. it matches an arbitrary long list as long as the first element is a 
tuple of two elements having a first element of "children".

ets:fun2ms happens at compile time (parse transform), so it's no problem 
performance-wise.

However, designing the table so that you have lists with certain fields 
in known positions seems error prone, I think using lists:keyfind on the 
result would be a better idea.

If you worry about performance, the first thing you should do is to 
replace the list strings with binaries (UTF-8 binaries preferably). 
Matching a list means walking through the cons cells and is slightly 
heavier than matching a binary. Binaries are also more compact. You 
should also have tags like "children" as atoms, not lists. If the number 
of possible fields is known in advance (which it would be if you know 
the positions, or?) you could use tuples (or records) instead of lists. 
With records you also are able to avoid the lists:keyfind. It all 
depends on your application of course.
> which is pretty similar to Ivan's suggestion. My final question (and I 
> so promise) is: it appears to me that (I) performs better than (II) 
> because of the lack of need of a transformation function such as 
> ets:fun2ms(). However, I don't known for sure whether ets:match() 
> outperforms ets:select() or not. I'm about to run a series of tests on 
> big datasets to check this, but I imagine that there is already an 
> answer to this question.
>
> Once again, thank you very much.
>
> Diego
Cheers,
/Patrik
>
>
> El 05/03/13 11:34, Patrik Nyblom escribió:
>> Hi!
>> On 03/04/2013 08:58 PM, Diego Llarrull wrote:
>>> Hello everyone,
>>>
>>> I would like to insert in an ETS table a tuple with the following 
>>> type signature:
>>>
>>> /{string(), [{string(), [string()]}]}/
>>>
>>> As an example:
>>> /
>>> //{"Peter", [{"children", ["Bob", "Paul"]}, {"father", ["Mike"]}]}//
>>>
>>> /
>>> My question is the following: is it possible to solve, using match 
>>> specifications, nested queries like "Retrieve the name of Peter's 
>>> children" ?
>>>
>>> That is, a query where I would need to
>>>
>>> a) Fetch all ("the", since its a set) tuples of size 3 where "Peter" 
>>> is located in the first position (doable with MS)
>>> b) Let '$2' be the value in the second position of the tuple fetched 
>>> in a). Then, fetch the value corresponding to the key "children" in 
>>> '$2', if interpreted as a key-value list (i.e. lists:keyfind() 
>>> should work on '$2').
>>>
>>> If I understood correctly, lists:keyfind can't be used inside a 
>>> match specification because they only allow the BIFs described in 
>>> http://www.erlang.org/doc/apps/erts/match_spec.html. My question is: 
>>> is there any low-level mechanism to operate on lists inside match 
>>> specifications, or am I trying to push the boundaries of match 
>>> specifications?
>>>
>> Yes, you're trying to push the boundaries of match specifications :)
>>
>> You'll have to do a lists:keysearch/keyfind on the results of the 
>> ets:select (when you're back in proper Erlang code), only constant 
>> time BIF's can be added to the ms language, so it's unfortunately not 
>> even an option to add this particular function... Without a huge 
>> rewrite that is...
>>
>> So...
>>   [lists:keyfind("children",1,P) || P <- 
>> ets:select(xxx,ets:fun2ms(fun({"Peter",Data}) -> Data end))].
>> would be the solution. Except of course if the list has a particular 
>> order, or you instead use some record'ish data structure, so that you 
>> can match directly:
>>   ets:select(xxx,ets:fun2ms(fun({"Peter",[{"children",Data}|_]}) -> 
>> Data end)).
>> But looping over the list inside the ms is not possible.
>>> In case anyone wonders "Why not use Query Lists Comprehensions?" the 
>>> answer is: "Because of performance issues: in our platform, we need 
>>> to dynamically build QLCs based on the number of arguments that 
>>> arrive, which forces us to build them as strings and then use 
>>> qlc:string_to_handle() which is SLOW".
>>>
>>> Any help of insight will be greatly appreciated. Thank you very much 
>>> in advance.
>>>
>>> Diego Llarrull
>>>
>>>
>> Cheers,
>> /Patrik
>>>
>>>
>>>
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130306/1f3b72ad/attachment.htm>


More information about the erlang-questions mailing list