在内存和执行时间有限的情况下迭代大数组

Question

我在使用 Ruby 通过一些测试时遇到问题，这些测试使数组太大并且 return 出错。

Solution.rb: failed to allocate memory (NoMemoryError)

两次都没有通过

问题是关于安排会议的。该方法按顺序接收两个参数：一个矩阵，包含投资者可以在公司见面的所有第一天，以及一个矩阵，包含所有最后几天。

例如：

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

这表明第一位投资者将能够在 1..4 日之间找到自己，第二位投资者将能够在 5..10 日之间找到自己，最后一位投资者将在 10..10 日之间找到自己。[=24] =]

我需要 return 公司将服务的最大数量的投资者。在这种情况下，所有这些都可以参加，第 1 天第一个，第 5 天第二个，第 10 天最后一个。

到目前为止，代码运行正常，但在至少1000个投资者的一些隐藏测试中，出现了我之前提到的错误。

Ruby 中是否有处理此问题的最佳实践？

我当前的代码是：

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[i]..lastDay[i]).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[i]..lastDay[i]).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

据我所知使用 Lazy，我逃脱了 MemoryError，但我开始收到运行时错误：

Your code was not executed on time. Allowed time: 10s

我的代码是这样的：

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

而且它经历了很少有投资者的案例。我想过用multi-thread，代码变成了下面这样：

 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

不幸的是，它又回到了MemoryError。

Answer 1

这可以在不消耗比天数范围更多的内存的情况下完成。关键是 避免数组 并尽可能保持 Enumerators。

首先，如果范围列表非常大，则传入 Ranges. This both simplifies the method, and it allows it to be Lazy 的 Enumerable，而不是需要转换为范围的笨拙的数组对。它可以从文件中读取，从数据库或 API 中获取，或者由另一个惰性枚举器生成。这使您无需大数组。

这是一个使用范围数组的示例。

p count_meetings([(1..4), (5..10), (10..10)])

或者演示如何将您的 firstDay 和 lastDay 数组转换为范围惰性可枚举...

firstDays = [1,5,10]
lastDays = [4,10,10]
p count_meetings(
  firstDays.lazy.zip(lastDays).map { |first,last|
    (first..last)
  }
)

firstDays.lazy让后面的一切变得懒惰。 .zip(lastDays) 成对遍历两个数组：[1,4]、[5,10] 和 [10,10]。然后我们把它们变成范围。因为它很懒惰，所以只会根据需要映射它们。这避免了创建另一个大数组。

现在已经解决了，我们需要做的就是遍历每个范围并增加当天的出勤率。

def count_meetings(attendee_ranges)
  # Make a Hash whose default values are 0.
  daily_attendance = Hash.new(0)

  # For each attendee
  attendee_ranges.each { |range|
    # For each day they will attend, add one to the attendance for that day.
    range.each { |day| daily_attendance[day] += 1 }
  }
  
  # Get the day/attendance pair with the maximum value, and only return the value.
  daily_attendance.max[1]
end

内存增长受日期范围的限制。如果最早的与会者在第 1 天，最后的与会者在第 1000 天，daily_attendance 就是 1000 个条目，这对于会议来说是很长的时间。

既然你已经构建了整个哈希，为什么要浪费它呢？写一个 returns 全出勤率的函数，另一个提取最大出勤率的函数

def count_meeting_attendance(attendee_ranges)
  daily_attendance = Hash.new(0)

  attendee_ranges.each { |range|
    range.each { |day| daily_attendance[day] += 1 }
  }
  
  return daily_attendance
end

def max_meeting_attendance(*args)
  count_meeting_attendance(*args).max[1]
end

因为这是一个练习，你被那些靠不住的论点所困，我们可以做同样的事情，懒惰地将 firstDays 和 lastDays 压缩在一起，并将它们变成范围。

def count_meeting_attendance(firstDays, lastDays)
  attendee_ranges = firstDays.lazy.zip(lastDays).map { |first,last|
    (first..last)
  }

  daily_attendance = Hash.new(0)
  attendee_ranges.each { |range|
    range.each { |day| daily_attendance[day] += 1 }
  }
  
  return daily_attendance
end

在内存和执行时间有限的情况下迭代大数组

Iterating over big arrays with limited memory and time of execution

ruby

performance

testng

out-of-memory