Skip to content

Instantly share code, notes, and snippets.

@pager
Created December 24, 2009 23:25
Show Gist options
  • Save pager/263418 to your computer and use it in GitHub Desktop.
Save pager/263418 to your computer and use it in GitHub Desktop.
user system total real
pure functional 1.820000 0.000000 1.820000 ( 1.817629)
mutable discriminator 1.530000 0.000000 1.530000 ( 1.534346)
imperative 1.110000 0.020000 1.130000 ( 1.118294)
cursor/iterator 2.370000 0.000000 2.370000 ( 2.373262)
true enumerator 2.090000 0.000000 2.090000 ( 2.089513)
Loaded suite sequences_by
Started
.
Finished in 0.000497 seconds.
1 tests, 5 assertions, 0 failures, 0 errors
# Готовим тестовые данные
require 'enumerator'
class M < Struct.new(:id, :user_id); end
user_ids = [1,1,1,2,2,1,3,3,3,1]
MESSAGES = user_ids.enum_with_index.map { |uid, i| M.new(i+1, uid) }
ETHALON = [
[
M.new(1,1),
M.new(2,1),
M.new(3,1)
],
[
M.new(4,2),
M.new(5,2)
],
[
M.new(6,1)
],
[
M.new(7,3),
M.new(8,3),
M.new(9,3)
],
[
M.new(10,1)
]
]
# Enumerable#sequence_by. Чистая функциональщина
module Enumerable
def sequence_by
inject([nil, []]) do |(prev_discriminator, accumulator), val|
discriminator = block_given? ? yield(val) : val
if accumulator.last && prev_discriminator == discriminator
accumulator.last << val
else
accumulator << [val]
end
[discriminator, accumulator]
end.last
end
end
# Enumerable#sequence_by2. Последний дискриминатор в локальной переменной.
module Enumerable
def sequence_by2
prev_discriminator = nil
inject([]) do |accumulator, val|
discriminator = block_given? ? yield(val) : val
if accumulator.last && prev_discriminator == discriminator
accumulator.last << val
else
accumulator << [val]
end
prev_discriminator = discriminator
accumulator
end
end
end
# Императивное решение в лоб :-)
class Array
def sequence_by3
accumulator = [[at(0)]]
prev_discriminator = block_given? ? yield(at(0)) : at(0)
for i in 1...size
discriminator = block_given? ? yield(at(i)) : at(i)
if prev_discriminator == discriminator
accumulator.last << at(i)
else
accumulator << [at(i)]
end
prev_discriminator = discriminator
end
accumulator
end
end
# Cursor/Iterator, тоже решение в лоб
require 'iterator'
class Array
def sequence_by4
rv = []
prev_discriminator = nil
iterate do |cursor|
discriminator = block_given? ? yield(cursor.curr) : cursor.curr
if cursor.first? || prev_discriminator != discriminator
rv << [ cursor.curr ]
else
rv.last << cursor.curr
end
prev_discriminator = discriminator
end
rv
end
end
# True ruby way: настоящий Enumerator. Этот можно использовать с любым enumerable,
# и при этом не нужно хранить в памяти все данные.
module Enumerable
def each_sequence_by(callable = nil)
prev_discriminator = nil
last_sequence = inject(nil) do |accumulator, val|
discriminator = callable ? callable.call(val) : val
if accumulator && prev_discriminator == discriminator
accumulator << val
else
yield(accumulator) if accumulator
accumulator = [val]
end
prev_discriminator = discriminator
accumulator
end
yield last_sequence
end
end
# Test it
require 'test/unit'
class TestSequenceBy < Test::Unit::TestCase
def test_sequence_by
assert_equal ETHALON, MESSAGES.sequence_by { |m| m.user_id }
assert_equal ETHALON, MESSAGES.sequence_by2 { |m| m.user_id }
assert_equal ETHALON, MESSAGES.sequence_by3 { |m| m.user_id }
assert_equal ETHALON, MESSAGES.sequence_by4 { |m| m.user_id }
assert_equal ETHALON, MESSAGES.enum_for(:each_sequence_by, proc { |m| m.user_id }).map
end
end
# Benchmark it
require 'benchmark'
n = 50000
Benchmark.bm do |x|
x.report("pure functional ") do
n.times { MESSAGES.sequence_by { |m| m.user_id } }
end
x.report("mutable discriminator ") do
n.times { MESSAGES.sequence_by2 { |m| m.user_id } }
end
x.report("imperative ") do
n.times { MESSAGES.sequence_by3 { |m| m.user_id } }
end
x.report("cursor/iterator ") do
n.times { MESSAGES.sequence_by4 { |m| m.user_id } }
end
x.report("true enumerator ") do
n.times { MESSAGES.enum_for(:each_sequence_by, proc { |m| m.user_id }).map }
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment