CODEWITHSUNDEEP
rubyoptimizationlazy-evaluation
Mike H-R
Mike H-R

Reputation: 7815

Take the last element of a lazy enumerator

I have a function like this:

(0..Float::INFINITY).lazy.take_while {|n|(n**2+ 1*n+41).prime?}.force[-1]

I'm using this as an optimisation exercise. This works fine, but it has a memory order O(n) as it will create the entire array and then take the last element.

I am trying to get this without building the entire list, hence the lazy enumerator. I can't think of anything other than using a while loop.

(0..Float::INFINITY).lazy.take_while {|n|(n**2+ 1*n+41).prime?}.last.force

Is there a way to do this in space order O(1) rather than O(n) with enumerators?

EDIT: lazy isn't necessary here for the example to work, but I thought it might be more useful to reduce the space complexity of the function?

Upvotes: 4

Views: 710

Answers (2)

Kelvin
Kelvin

Reputation: 20857

Solution

Use inject to hold on to the current value instead of building an array.

(0..Float::INFINITY).lazy.take_while {|n|(n**2+ 1*n+41).prime?}.inject{|acc,n| n }

Note that you must use lazy otherwise inject will build an intermediate array.

Verifying

To see what happens if you don't use lazy, run the following after restarting ruby & running the non-lazy version. It will return arrays that "look like" the intermediate array.

ObjectSpace.enum_for(:each_object, Array).each_with_object([]) {|e, acc|
  acc << e if e.size == 40 and e.first == 0
}

The non-lazy version will return:

[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39]]

Re-doing the test with lazy will return an empty array.

Upvotes: 1

Cary Swoveland
Cary Swoveland

Reputation: 110675

If you just don't want to save the entire array:

(0..1.0/0).find {|n| !(n**2+n+41).prime?} - 1

1.0/0 is the same as Float::INFINITY. I used it in case you hadn't seen it. So far as I know, neither is preferable.

My first thought clearly was overkill:

def do_it
  e = (0..1.0/0).to_enum
  loop do
    n = e.peek
    return e.inspect unless (n**2+n+41).prime?
    e.next
  end
end

do_it

Upvotes: 2

Related Questions