MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: why does DownValues not return all downvalues for a

  • To: mathgroup at smc.vnet.net
  • Subject: [mg99398] Re: [mg99369] why does DownValues not return all downvalues for a
  • From: Leonid Shifrin <lshifr at gmail.com>
  • Date: Tue, 5 May 2009 05:39:08 -0400 (EDT)
  • References: <200905040959.FAA22619@smc.vnet.net>

Hi Michael,

In your example, you should use SubValues - these are responsible for the
types of definitions you explored last.

In[1] = g["x"]["y"] = 1;

In[2] = SubValues[g]

Out[2] = {HoldPattern[g["x"]["y"]] :> 1}

SubValues are used when the head is not atomic but a normal expression
itself (contains square brackets). The good news is that there are only 6
types of ..Values: DownValues,UpValues,SubValues,OwnValues, NValues,
FormatValues (also DefaultValues in principle), so no more surprises like
this.

As to hash-table business, I have the following comment: if you have a large
number of pairs, lists of rules optimized with Dispatch may be (much) more
efficient than DownValues or SubValues - based hashes. It all depends on
your situation: if you don't need to frequently add new pairs/remove old
ones, then, for large number of pairs, you can get about 100 speed-up for
your keys function. Illustration:

In[1] =
Clear[y];
StringKeys[y_] := DownValues[y] /. {(_[y[str_String]] :> _) :> str};
words = DictionaryLookup["*"];
(y[#1] = #2) & @@@ Transpose[{words, Range[Length[words]]}];


In[2] = StringKeys@y // Length // Timing

Out[2] = {2.253, 92518}

Now with dispatched rules:

In[3] = z = Dispatch[Thread[Rule[words, Range[Length[words]]]]];

In[4] = z[[1, All, 1]] // Length // Timing

Out[4] = {0.03, 92518}

In[5] = z[[1, All, 1]] === StringKeys@y

Out[5]  = True

The application of dispatched rules is also about twice faster (on v6
anyway):

In[6] = y /@ words; // Timing

Out[6] = {0.681, Null}

In[7] = words /. z; // Timing

Out[7] = {0.28, Null}

Of course, with Dispatch you lose the flexibility of adding/removing pairs
after the hash is formed - at least, I don't know how to do that efficiently
with Dispatch - so it may be a good option for a hash whose content you know
beforehand. But then again, in such case you probably could just as well
keep keys in some array (list) or whatever. Perhaps, if speed is the
question, and if the problem permits, a kind of hybrid (nested) hash could
be implemented, with DownValue-based hash pointing to Dispatch - based
sub-hashes (or combine them in some other way, for example maintain a small
DownValue-based hash for new pairs and periodically re-hash Dispatched-based
one, or whatever).


Regards,
Leonid


On Mon, May 4, 2009 at 2:59 AM, Michael <michael2718 at gmail.com> wrote:

> I'm trying to get the functionality of "associative arrays" or "alist"
> or "hash tables"  to work in Mathematica.  However I'm seeing a quirk
> and I wonder if anybody can explain what is going on or suggest a
> better approach?
>
> I can define a simple associate array like so:
> f["red"]=1;
> f["blue"]=2;
> ...
> If all my parameters are strings, then I can find the "keys" to my
> alist with the following function:
> StringKeys[y_] := DownValues[y] /. {( _[y[str_String]] :> _) -> str};
> SetAttributes[StringKeys, HoldFirst];
>
> In[141]:= StringKeys[f]
>
> Out[141]= {"blue", "red"}
>
> However, if I try to define a more complex alist, I cannot find any
> way to retrieve the definition!
>
> In[142]:= g["x"]["y"] = 1;
>
> In[143]:=  DownValues[g]
>
> Out[143]= {}
>
> In[144]:= UpValues[g]
>
> Out[144]= {}
>
>
> Any ideas?
>
> Thanks,
>
> Michael
>
>


  • Prev by Date: Re: problems with DSolve
  • Next by Date: Re: Re: Bug with Hypergeometric2F1?
  • Previous by thread: Re: why does DownValues not return all downvalues for a
  • Next by thread: Re: why does DownValues not return all downvalues for a symbol?