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 ruby, dagmethode | 1 reactie
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 ruby, english | geen reacties
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 ruby, english, daily_method | geen reacties
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 ruby, dagmethode | 3 reacties
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 ruby, english, daily_method | geen reacties
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 ruby, dagmethode | 2 reacties
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 ruby, english, daily_method | 1 reactie
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 ruby, ruby on rails, dagmethode | 2 reacties
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 ruby, english, daily_method | geen reacties
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 ruby, dagmethode | geen reacties
