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