Project

General

Profile

Feature #16851

Updated by ana06 (Ana Maria Martinez Gomez) 3 months ago

I have implemented Linear Probing and Simple tabulation in Ruby: https://github.com/Ana06/ruby/compare/master...Ana06:tabulation https://github.com/Ana06/ruby/compare/master...Ana06:tabulation_project 

 I tested it using the following code: 
 https://github.com/Ana06/ruby-tabulation/blob/master/benchmark_tabulation.rb 
 It benchmarks the insertion of 600000 elements (by hashing their 64 bits ids) in an empty hash 100 times. Below are the times (in seconds) I got executing this code for different versions of the Ruby code: 

 - master (without Simple Tabulation): 29.68 
 - master with Linear Probing (without Simple Tabulation): 99.76 
 - master with Quadratic Probing (without Simple Tabulation): 29.97 
 - master with Simple Tabulation: 15.76 
 - master with Linear Probing and Simple Tabulation: 24.23 
 - **master with Quadratic Probing and Simple Tabulation: 13.73** 

 `master` refers to ruby 2.8.0dev: 
 (2020-05-07T16:22:38Z master 7ded8fd) [x86_64-linux]. 
 I tried with 8 x Intel i5-8265U. 

 Although this is just a proof prove of concept and not something that could be already use in production, I think it proves the potential of Simple Tabulation to improve current Ruby implementation. It may be worthwhile to explore this idea further. What do you think? 

 I did this as part of a project for my [Advanced Algorithms course](http://www.cs.columbia.edu/~andoni/advancedS20/index.html). For more details check the project report:  
 https://github.com/Ana06/ruby-tabulation/blob/master/latex/RubyTabulation_Project.pdf

Back