[mercury-users] Converting large tables from prolog

[Richard Tucker]

At 04:39 AM 11/26/99 +1100, Fergus Henderson wrote:
>
>It would be interesting to examine that in the profiler to see
>where the time is being spent.
>
>How exactly are you constructing the map?  Are you inserting each
>element at a time?  That would be O(N * log(N)).  It could be more
>efficient to first store all the elements in a list, which is O(N), and
>then use map__from_sorted_list to convert the already-sorted list
>into map, which can also be done in O(N), although currently it
>isn't.  Converting a sorted list into a map would be O(N) if
>map__from_sorted_list were implemented with an O(N) algorithm,
>like binary_tree__from_sorted_assoc_list is, but the current naive
>implementation is O(N * log(N)).  It would be great if someone were
>to fix this and send us the patch.
>
>But I suspect it is probably more likely that the overhead
>may be related to the I/O code and the RTTI and dynamic typing
>inside io__read, rather than to actually inserting stuff
>in the map.
>

I'm constructing the map in the inefficient, one-element-at-a-time way.
But I think your suspicions as to where the overhead is are correct --
profiling system+user time shows that 92% of time is spent in io:read/4,
and only 7% in map:det_insert.

Ralph, James and you all suggested using fact table, so I'll try that.
My 'tag' type only has constructors of arity zero anyway, so it's rather
easy to convert to int.

Thanks,

Richard/

--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------