>Learning Git, And Should You Switch from SVN

>If you are just learning to use git, or you have been using it for a while without too much thinking, this introduction to Git principles provides a fantastic overview into the concepts behind git, using a very simple and natural examples.

Do you need to switch to git from svn? My personal take on this is as follows:

• If you have several developers far away with bad internet connection, then YES.
• If you have more than several developers (say hundreds) then YES.
• If your developers often work on long multi-day features, where they want to commit often, but commits may result in instability of their branch, then YES. Git allows much easier branching than SVN.
• If you want to leverage GitHub’s infrastructure for hosting your project privately or publicly, then YES.

To balance this and not to appear as I am advocating everyone to switch, here is the reverse:

• If you have a small team who works locally and uses a local SVN server then NO.
• If your team does not need branching, or prefers to check-in complete features instead of incremental check-ins then NO.
• If your team is used to SVN and there are no major issues, then NO.
• If your team is using SVN authorization module to create groups and grant them special access per subdirectory then NO. I am unaware of Git providing this level of access control.

The actual tutorial is here: http://www.eecs.harvard.edu/~cduan/technical/git/

 

>Integer Division with Modulus in Ruby, using Linear and Binary Search

>

I was recently chatting with someone about algorithms, and we were talking about efficient algorithm for implementing integer division with modulus, and how to make it efficient for large integers.

The following code snippet shows a class that implements two division methods, linear and binary. I wonder if there is a more elegant way to implement binary, please feel free to post to comments if there are. Also, any other faster methods are welcome.

# divide.rb
# Integer Divider Class that implements two algorithms for finding the 
# division result and modulus of two integers.
class IntegerDivider
  def self.linear n, d
     raise 'Cant divide by zero!' if (d == 0)
     multiplier = n * d = n)
     i -= 1 if (i*d > n)
     return multiplier * i, n - i*d, i
  end

  def self.binary n, d
     raise 'Cant divide by zero!' if (d == 0) 
     multiplier = n * d = n) 
     return multiplier * i, 0 if (i*d == n) 
     i /= 2; j = i; cnt = 0
     begin
       j /= 2; cnt += 1
       sign = ((i + j)*d > n) ? 0 : 1
       i = i + sign * j 
     end until (i*d  n) 
     return multiplier * i, n - i*d, cnt
  end
  
  def self.divide(how, numerator, denominator)
    before = Time.now.to_f
    (result, remainder, iterations) = self.send(how, numerator, denominator)
    after = Time.now.to_f
    puts "#{sprintf('%8.3f',(after - before)*1000)}ms #{how}" + 
         " (#{sprintf '%10d', iterations} iterations):  #{numerator} / " +
         " #{denominator} = #{result}, mod #{remainder}"
    return [result, remainder]
  end
end

[:linear, :binary].each do |method|
  ARGV.each do |numerator|
    IntegerDivider.divide(method, numerator.to_i, 3)    
  end
end

And some results of running it. Of course for large number like 100000000, binary search takes 24 iterations to get the answer, while linear … well 100000000. The total speed difference at such large number is big: 1524ms/0.012ms = 127,000.

> ruby divide.rb 10 100 1000 20000 100000000
   0.006ms linear (         3 iterations):  10 /  3 = 3, mod 1
   0.003ms binary (         1 iterations):  10 /  3 = 3, mod 1
   0.003ms linear (        33 iterations):  100 /  3 = 33, mod 1
   0.003ms binary (         5 iterations):  100 /  3 = 33, mod 1
   0.017ms linear (       333 iterations):  1000 /  3 = 333, mod 1
   0.004ms binary (         8 iterations):  1000 /  3 = 333, mod 1
   0.411ms linear (      6666 iterations):  20000 /  3 = 6666, mod 2
   0.006ms binary (        11 iterations):  20000 /  3 = 6666, mod 2
1524.712ms linear (  33333333 iterations):  100000000 /  3 = 33333333, mod 1
   0.012ms binary (        24 iterations):  100000000 /  3 = 33333333, mod 1