What's new

Iterating over big arrays with limited memory and time of execution. Ruby

Fever

Active member
Staff member
I'm having trouble using Ruby to pass some tests that make the array too big and return an error. ** Solution.rb: failed to allocate memory (NoMemoryError) **

I have failed to pass it twice.

The problem is about scheduling meetings. Where the method receives two parameters that represent in order, a matrix with all the first days that investors can meet in the company and the second in the last days.

For example firstDay = [1,5,10] lastDay = [4,10,10]

This shows that the first investor will be able to find himself between the day 1..4, the second 5..10 and the last 10..10.

So, I need to return the largest number of investors that the company will serve. In this case, all of them can be attended to, the first on day 1, the second on day 5 and the last on day 10.

So far, the code works normally, but with some hidden tests with at least 1000 investors, the error I mentioned earlier appears.

Is there a best practice in Ruby to handle this?

My current code is:
def countMeetings(firstDay, lastDay)
GC::profiler.enable
GC::profiler.clear

first = firstDay.sort.first
last = lastDay.sort.last
available = []

#Construct the available days for meetings
firstDay.each_with_index do |d, i|
available.push((firstDay..lastDay).to_a)
end
available = available.flatten.uniq.sort
investors = {}
attended_day = []
attended_investor = []

#Construct a list of investor based in their first and last days
firstDay.each_index do |i|
investors[i+1] = (firstDay..lastDay).to_a
end

for day in available
investors.each do |key, value|
next if attended_investor.include?(key)
if value.include?(day)
next if attended_day.include?(day)
attended_day.push(day)
attended_investor.push(key)
end
end
end

attended_investor.size
end


Update:

Using "Lazy" as far as I could understand, I escaped MemoryError; therefore, start receiving a runtime error: Your code was not executed on time. Allowed time: 10s And my code look like this:

def countMeetings(firstDay, lastDay)

loop_size = firstDay.size
first = firstDay.sort.first
last = lastDay.sort.last

daily_attendance = {}

(first..last).each do |day|
for ind in 0...loop_size
(firstDay[ind]..lastDay[ind]).lazy.each do |investor_day|
next if daily_attendance.has_value?(ind)
if investor_day == day
daily_attendance[day] = ind
end
end
end
end

daily_attendance.size
end


And it went through the cases with few investors. So I thought about using multi-thread and the code became the following:

def countMeetings(firstDay, lastDay)

loop_size = firstDay.size
first = firstDay.sort.first
last = lastDay.sort.last
threads = []
daily_attendance = {}

(first..last).lazy.each_slice(25000) do |slice|
slice.each do |day|
threads << Thread.new do
for ind in 0...loop_size
(firstDay[ind]..lastDay[ind]).lazy.each do |investor_day|
next if daily_attendance.has_value?(ind)
if investor_day == day
daily_attendance[day] = ind
end
end
end
end
end
end
threads.each{|t| t.join}
daily_attendance.size
end


Unfortunately, it went back to the MemoryError. :(

Continue reading...
 
Top