Onze dagmethode #16: Array#bsearch

Geplaatst door Michiel de Mare di, 26 feb 2008 07:52:00 GMT

Zoeken in arrays is best langzaam. Gebruik liever een hash.

Maar als de array al gesorteerd is, kun je een binary search gebruiken. Die werkt door de array doormidden te delen, en vervolgens verder te zoeken in het linker of het rechter deel, net zolang totdat het element gevonden is of er nog maar een element over is..


class Array
  def bsearch(k)
    x,y = -1,size
    while y != x + 1 do
      m = (x + y) / 2
      if self[m] <= k
        x = m
      else
        y = m
      end
    end
    x >= 0 && self[x] == k && x
  end
end

Geplaatst in ,  | 1 reactie

A Hash Is A Function (Hash#to_proc)

Geplaatst door Michiel de Mare di, 26 feb 2008 00:42:00 GMT

Staring at the following code, I got an idea (inspired by Arc):

specialism_codes.map {|code| SPECIALISMS[code] }

Why do I have to create a block to map from a list of codes to a list of descriptions, when those codes and descriptions are all contained in a constant? Isn’t that what a Hash is, a mapping from a domain to a range? Isn’t that exactly the definition of a function in mathematics? Why then that block?

Anyway, I solved that pretty quickly:

class Hash
  def to_proc
    lambda {|x| self[x] }
  end
end

specialism_codes.map &SPECIALISMS

Geplaatst in ,  | geen reacties

Our Daily Method #15: Kernel#levenshtein

Geplaatst door Michiel de Mare ma, 25 feb 2008 08:00:00 GMT

Not in any way invented by us, but still extremely useful and not a part of the standard library: the Levenshtein Distance

What does it calculate? The number of characters to add, delete or switch to turn the first string into the second. Ideal for detecting typos.


# example: 
levenshtein('levenstine', 'levenshtein') # => 3
Or how about instead of a LIKE-clause? Not quite as fast (cough) but much more accurate.

# In the old days:
User.find(:all, 
    :conditions => ['name like ?', params[:name] + '%']])

# Now:
User.find(:all).
    sort_by {|u| levenshtein(params[:name], u.name)}.
    first

def levenshtein(s1, s2)
  d = {}
  (0..s1.size).each { |row| d[[row, 0]] = row }
  (0..s2.size).each { |col| d[[0, col]] = col }
  (1..s1.size).each do |i|
    (1..s2.size).each do |j|
      i1,j1 = i-1,j-1
      cost = s1[i1] != s2[j1] ? 1 : 0
      d[[i, j]] = [d[[i1, j1]] + cost,
                   d[[i1, j]] + 1,
                   d[[i, j1]] + 1].min
      if i1*j1 > 0 and s1[i1] == s2[j-2] and s1[i-2] == s2[j1]
        d[[i, j]] = [d[[i,j]] , d[[i-2, j-2]] + cost].min
      end
    end
  end
  d[[s1.size, s2.size]]
end

Geplaatst in , ,  | geen reacties

Onze dagmethode #15: Kernel#levenshtein

Geplaatst door Michiel de Mare ma, 25 feb 2008 08:00:00 GMT

Allerminst door ons verzonnen, maar toch vreselijk nuttig en geen onderdeel van de standaard-library: de Levenshteinafstand

Wat berekent het? Hoeveel karakters je moet toevoegen, weghalen of omwisselen om van de ene naar de andere string te gaan. Ideaal voor het detecteren van typefouten.


# example: 
levenshtein('levenssteen', 'levenshtein') # => 2
Of wat dacht je voor in plaats van je LIKE-clause? Niet zo snel misschien (uche uche) maar wel heel goed.

# Vroeger:
User.find(:all, 
    :conditions => ['name like ?', params[:name] + '%']])

# Nu:
User.find(:all).
    sort_by {|u| levenshtein(params[:name], u.name)}.
    first

def levenshtein(s1, s2)
  d = {}
  (0..s1.size).each { |row| d[[row, 0]] = row }
  (0..s2.size).each { |col| d[[0, col]] = col }
  (1..s1.size).each do |i|
    (1..s2.size).each do |j|
      i1,j1 = i-1,j-1
      cost = s1[i1] != s2[j1] ? 1 : 0
      d[[i, j]] = [d[[i1, j1]] + cost,
                   d[[i1, j]] + 1,
                   d[[i, j1]] + 1].min
      if i1*j1 > 0 and s1[i1] == s2[j-2] and s1[i-2] == s2[j1]
        d[[i, j]] = [d[[i,j]] , d[[i-2, j-2]] + cost].min
      end
    end
  end
  d[[s1.size, s2.size]]
end

Geplaatst in ,  | 3 reacties

Our Daily Method #14: Time#warp

Geplaatst door Remco van 't Veer vr, 22 feb 2008 08:00:00 GMT

Time travel can be very convenient but unfortunately it isn’t very easy. Reality won’t allow it but we can bend the Time class!


class Time
  def self.now_with_warping
    @warptime || now_without_warping
  end

  class << self
    alias_method :now_without_warping, :now
    alias_method :now, :now_with_warping
  end

  def warp
    self.class.instance_variable_set('@warptime', self)
    yield
  ensure
    self.class.instance_variable_set('@warptime', nil)
  end
end
Now we can travel back to “Unix Epoch”:

Time.at(0).warp do
  puts "The current time is: #{Time.now}" 
end
Or just before the end of time as we know it:

Time.at(2 ** 31 - 1).warp do
  Time.now + 1
end

What’s the use? It makes testing time dependent code very easy!

Geplaatst in , ,  | geen reacties

Onze dagmethode #14: Time#warp

Geplaatst door Remco van 't Veer vr, 22 feb 2008 08:00:00 GMT

Tijdreizen is verschrikkelijk handig maar jammer genoeg niet altijd even gemakkelijk. Als de realiteit het niet toestaat dan passen die gewoon aan!


class Time
  def self.now_with_warping
    @warptime || now_without_warping
  end

  class << self
    alias_method :now_without_warping, :now
    alias_method :now, :now_with_warping
  end

  def warp
    self.class.instance_variable_set('@warptime', self)
    yield
  ensure
    self.class.instance_variable_set('@warptime', nil)
  end
end
Hiermee kunnen we gemakkelijk terug naar “Unix Epoch”:

Time.at(0).warp do
  puts "The current time is: #{Time.now}" 
end
Of vlak voor het einde der tijden:

Time.at(2 ** 31 - 1).warp do
  Time.now + 1
end

Wat heb je er aan? Heel handig om tijds afhankelijke zaken te testen!

Geplaatst in ,  | 2 reacties

Our Daily Method #13: Object#mymethods

Geplaatst door Michiel de Mare do, 21 feb 2008 08:00:00 GMT

I always have an irb or rails console session open, and I love methods to see what an object is capable of, but it certainly returns an exceptional amount of unsorted crap, especially in Rails.

Therefore, mymethods:


class Object
  def mymethods
    (methods - Object.instance_methods).sort
  end
end

(1..2).methods.size # => 150
(1..2).mymethods.size # => 46

Geplaatst in , ,  | 1 reactie

Onze dagmethode #13: Object#mymethods

Geplaatst door Michiel de Mare do, 21 feb 2008 08:00:00 GMT

Ik heb altijd wel een irb of rails console openstaan, en ik ben dol op methods om te kijken wat een object allemaal kan, maar wat krijg je toch een ontiegelijke hoeveelheid troep terug, vooral in Rails.

Daarom dit:


class Object
  def mymethods
    (methods - Object.instance_methods).sort
  end
end

(1..2).methods.size # => 150
(1..2).mymethods.size # => 46

Geplaatst in , ,  | 2 reacties

Our Daily Method #12: Comparable#at_least

Geplaatst door Michiel de Mare wo, 20 feb 2008 08:00:00 GMT

It took me a while before I discovered the accepted Ruby idiom to find the bigger of two values. I expected a method in Kernel or perhaps in Comparable. Instead, the Ruby Way is to create an array and ask the maximum value in the array:


[x,y].max
Well, it’s certainly short, but I don’t like it, for three reasons:
  • You create an array to compare two integers? That has to be inefficient, right? Of course, worrying about efficiency is not The Ruby Way.
  • I don’t like the name. When I say max it feels as if I’m declaring an upper bound, a maximum, when in fact, I’m declaring a lower bound, a minimum.
  • By listing both values in the array, you’re placing them on equal footing, when often that’s not really the case. Often it’s more an afterthought: you’re saying: I want value foo (and by the way, it must be at least 7.25).
Hence, at_most and at_least:

total_time / total_tries.at_least(1)

Implementation too trivial to list.

Geplaatst in , ,  | geen reacties

Onze dagmethode #12: Comparable#at_least

Geplaatst door Michiel de Mare wo, 20 feb 2008 08:00:00 GMT

Het kostte me even voordat ik de algemeen aanvaarde manier om de grootste van twee waarden te bepalen had gevonden. Ik verwachtte een methode in Kernel of in Comparable. In plaats daarvan is de Ruby Manier om een array met beide waarden aan te maken en daaraan te vragen wat de hoogste waarde is.


[x,y].max
Nou, kort is het zeker, maar het staat me toch niet aan, om drie redenen:
  • Je maakt een array aan om twee ints te vergelijken? Dat moest haast wel vreselijk inefficiĆ«nt zijn, toch? Goed, ik weet dat je je als ervaren Rubyist niet druk hoort te maken om efficiĆ«ntie.
  • Ik vind de naam verwarrend. Wanneer ik max hoor denk ik aan een maximum. Ik denk aan maximaal. De maximumsnelheid in Nederland: [you.speed,120].min. Klopt niet.
  • Door twee waarden in de array op te nemen plaats je ze op gelijke voet, vaak ten onrechte. Vaak is de tweede waarde alleen een voetnoot. Je zegt: ik wil waarde size (en trouwens, die moet minstens 1.2 zijn.) Dat wordt niet uitgedrukt door [size, 1.2].max
Vandaar, at_most and at_least:

size.at_least(1.2)
seconds / attempts.at_least(1)

Implementatie te triviaal om te laten zien.

Geplaatst in ,  | geen reacties

Oudere artikelen: 1 2 3 4 5 ... 12