From: Robert Klemme <shortcutter@...>
Date: 2007-09-18T04:45:12+09:00
Subject: Re: Modifying a hash key

On 17.09.2007 20:19, Alex Shulgin wrote:
> On Sep 17, 12:53 pm, "Robert Klemme" <shortcut...@googlemail.com>
> wrote:
>>> So the real answer to my question (what is the reason for hash to
>>> store it's keys by reference?) might be: trading rule of a thumb for
>>> speed and memory?
>> No, the reason is that you can only store by reference in Ruby (there
>> are some internal optimizations for Fixnum and the like but the code
>> still basically behaves the same).
> 
> Yes, but hash implementation could make a copy of the key when it
> inserts new elements.  Of course, this will slow down the code in
> significant part of programs, so there is the trade-off I've talked
> about. :-)

That's the exact reason why this optimization was choosen for Strings only.

>>> state={}
>>> prefix=[]
>>> while $stdin.eof?
>> Are you serious about the line above?  I'd rather have expected "until" there.
> 
> Sorry, of course not.  It was pulled off the top of my head, since no
> real code was at hand (I've posted that from work, and the Ruby code
> is something I keep at home (-: ).
> 
>> I'd do this, note all the freezing in order to make errors with
>> changing keys obvious.
>>
>> state = Hash.new {|h,k| h[k]=[]}
>> prefix = [].freeze
>>
>> ARGF.each do |line|
>>   line.scan /\w+/ do |word|
>>     state[prefix] << word.freeze
>>     (prefix += [word]).freeze
>>     # or: prefix = (prefix.dup << word).freeze
>>   end
>> end
> 
> Uh-oh...  this freeze stuff seems overly complicated to me.

Well, it's not necessary - I just put it there in order to find bugs.

>> Btw, there's probably a more efficient way of storing this if you
>> introduce a specialized class for prefix chaining.  Probably like
>> this:
>>
>> Prefix = Struct.new :word, :previous
>>
>>>   w=...  # read a word
>>>   state[prefix] << w
>>>   ...
>>>   prefix << w   # <-- Bang!  The hash key is changed... :-)
>> You can #dup the prefix or use +:
>> prefix += [w]
> 
> My real code is as follows:
> 
> require 'scanf'
> 
> NPREFIX = 2
> 
> $nwords = ARGV[0] ? ARGV[0].to_i() : 1000
> 
> #
> # acquire knowledge
> #
> state = {}
> prefix = []
> while not $stdin.eof? do
>   #  w, = scanf("%s")
>   words = $stdin.gets().scan(/[^\s]+/)
>   words.each do |w|
>     suf = state[prefix]
>     if not suf
>       suf = state[prefix.clone()] = []
>     end
>     suf << w
>     if prefix.length >= NPREFIX
>       prefix.shift
>     end
>     prefix << w
>   end
> end
> state[prefix] = []
> 
> #
> # generate pseudo-text
> #
> prefix = []
> count = 0
> while count < $nwords do
>   suf = state[prefix]
>   if suf.empty?
>     break
>   end
>   w = suf[rand(suf.length)]
>   print w + " "
>   if prefix.length >= NPREFIX
>     prefix.shift
>   end
>   prefix << w
>   count += 1
> end
> 
> puts

You find my code "overly complicated"?  Amazing...

Cheers

	robert