Re: Why does the order of down values come back?
- To: mathgroup at smc.vnet.net
- Subject: [mg124888] Re: Why does the order of down values come back?
- From: Leonid Shifrin <lshifr at gmail.com>
- Date: Sat, 11 Feb 2012 06:33:46 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <jgo0e9$a2k$1@smc.vnet.net>
Best I can tell, only the rules with non-patterns (no Pattern-s, no blanks, etc) are directly based on hash-tables. And, these are the only rules which ignore manual reordering of the relevant ...Values. Rules with patterns and / or blanks are most likely also hashed in some way for speed, but their order can be manually changed, and my impression was that they come in their original order indeed, when using Sort->False. I may be wrong however, did not do extensive checks on that. Cheers, Leonid On Thu, Feb 9, 2012 at 1:37 PM, Oleksandr Rasputinov < oleksandr_rasputinov at ymail.com> wrote: > A very good point. To tell the truth, the only time I've ever had to worry > about the order of DownValues is when there is some ambiguity in their > ordering, so I had never noticed the ordering based on position in the > hash table of those values for which the hash is sufficient to completely > specify the way in which they are applied. It would be interesting to know > to what extent the hash table (or tables, if multiple levels of hashing > are applied, as one might anticipate from the statements about ordering > based on specificity) is used in the resolution of more complicated > DownValues and at which point the process reduces to a sequential test for > applicability by pattern matching (i.e., when the ordering begins to > matter). Perhaps this can be determined by experiment? > > Best, > > O. R. > > On Wed, 08 Feb 2012 10:32:55 -0000, Leonid Shifrin <lshifr at gmail.com> > wrote: > > > A more precise statement would be that DownValues with Sort->False do not > > perform additional sorting, > > and presumably expose the content of the rules just as they are kept in > > the > > underlying hash-table. This does not however mean that they will come in > > the order they were entered - since generally hash-table (at least the > > one > > used to implement DownValues) does not guarantee you that. This happens > > to > > be true for a small number of key-value pairs, but not in general. Try, > > for > > example, this: > > > > f[x_] := f[x] = x; > > > > f /@ Range[100] > > > > and then inspect the DownValues of f. Here is one relevant discussion I > > am > > aware of: > > > > > http://stackoverflow.com/questions/7062268/what-sort-option-of-values-does/7063143#7063143 > > > > Cheers, > > Leonid > > > > > > > > On Tue, Feb 7, 2012 at 12:05 PM, Oleksandr Rasputinov < > > oleksandr_rasputinov at ymail.com> wrote: > > > >> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo.vitz at msa.hinet.net> > >> wrote: > >> > >> > In[]:= f[0] := 0;f[1] := 1;f[n_] := f[n - 1] + f[n - 2] > >> > > >> > In[]:= DownValues[f] > >> > Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, > >> > HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]} > >> > > >> > In[]:= DownValues[f] = Reverse[DownValues[f]] > >> > Out[]:= {HoldPattern[f[n_]] :> f[n - 1] + f[n - 2], HoldPattern[f[1]] > >> :> > >> > 1, HoldPattern[f[0]] :> 0} > >> > > >> > In[]:= DownValues[f] > >> > Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, > >> > HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]} > >> > > >> > ==================================================== > >> > My question is: > >> > > >> > Why does the order of down values comes back after reordering? > >> > > >> > Thanks. > >> > > >> > >> Because DownValues sorts its output by default. The actual downvalues > >> are > >> not, however, sorted; the order is as you set them. To see their actual > >> order, use the (undocumented) option: > >> > >> DownValues[f, Sort -> False] > >> > >