Skip to content

Instantly share code, notes, and snippets.

@sdogruyol
Created January 11, 2017 13:01
Show Gist options
  • Save sdogruyol/968802c00924528a0b37a73f4f3b4022 to your computer and use it in GitHub Desktop.
Save sdogruyol/968802c00924528a0b37a73f4f3b4022 to your computer and use it in GitHub Desktop.
require "benchmark"
require "colorize"
require "http"
require "spec/dsl"
class String
private PRIME_RK = 2097169u32
def index_old(search : String, offset = 0)
offset += size if offset < 0
return nil if offset < 0
end_pos = bytesize - search.bytesize
reader = Char::Reader.new(self)
reader.each_with_index do |char, i|
if reader.pos <= end_pos
if i >= offset && (to_unsafe + reader.pos).memcmp(search.to_unsafe, search.bytesize) == 0
return i
end
else
break
end
end
end
def index_rabin_karp(search : String, offset = 0)
offset += size if offset < 0
return nil if offset < 0
return size < offset ? nil : offset if search.empty?
# Rabin-Karp algorithm
# https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
# calculate a rolling hash of search string (needle)
search_hash = 0u32
search.each_byte do |b|
search_hash = search_hash * PRIME_RK + b
end
pow = PRIME_RK ** search.bytesize
# Find start index with offset
char_index = 0
pointer = to_unsafe
end_pointer = pointer + bytesize
while char_index < offset && pointer < end_pointer
byte = pointer.value
if byte < 0x80
pointer += 1
elsif byte < 0xe0
pointer += 2
elsif byte < 0xf0
pointer += 3
else
pointer += 4
end
char_index += 1
end
head_pointer = pointer
# calculate a rolling hash of this text (heystack)
hash = 0u32
hash_end_pointer = pointer + search.bytesize
return if hash_end_pointer > end_pointer
while pointer < hash_end_pointer
hash = hash * PRIME_RK + pointer.value
pointer += 1
end
while true
# check hash equality and real string equality
if hash == search_hash && head_pointer.memcmp(search.to_unsafe, search.bytesize) == 0
return char_index
end
return if pointer >= end_pointer
byte = head_pointer.value
char_index += 1 if (byte & 0x80) == 0 || (byte & 0x40) != 0
# update a rolling hash of this text (heystack)
hash = hash * PRIME_RK + pointer.value - pow * byte
head_pointer += 1
pointer += 1
end
nil
end
end
unless File.exists?("mems.txt")
print "Downloading mems.txt (The Memoirs of Sherlock Holmes)...".colorize(:red)
File.open("mems.txt", "w") do |f|
HTTP::Client.get("https://sherlock-holm.es/stories/plain-text/mems.txt") do |response|
IO.copy response.body_io, f
end
end
puts " done".colorize(:green)
end
source = File.read("mems.txt")
short_source = <<-SHORT
Crystal is great, i love Crystal.
Lorem dolor sip amet, Crystal is great
SHORT
target = "crystal"
n = source.index(target)
short_n = short_source.index(target)
Benchmark.ips do |x|
x.report("index_old") { source.index_old(target).should eq n }
x.report("index_rabin_karp") { source.index_rabin_karp(target).should eq n }
x.report("index_short") { short_source.index_old(target).should eq short_n }
x.report("index_short_rabin_karp") { short_source.index_rabin_karp(target).should eq short_n }
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment