时间戳

首页 > 解决方案 > 迭代具有有限内存和执行时间的大数组

ruby - 迭代具有有限内存和执行时间的大数组

问题描述

我在使用 Ruby 来通过一些使数组太大并返回错误的测试时遇到问题。

Solution.rb: failed to allocate memory (NoMemoryError)

我两次都没有通过。

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

例如：

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

这表明第一个投资者将能够在天之间找到自己1..4，第二个在天和5..10最后一个之间10..10。

我需要回报公司将服务的最大数量的投资者。在这种情况下，所有这些都可以参加，第 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

它在少数投资者的情况下经历了这些案件。我想过使用多线程，代码变成了以下：

 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.

标签： rubyperformancetestngout-of-memory

解决方案

这可以在不消耗超过天数范围的内存的情况下完成。关键是避免使用数组并尽可能将事物保留为枚举器。

首先，不是需要转换为 Ranges 的尴尬的 Arrays 对，而是传入一个Ranges的 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]。然后我们把它们变成 Ranges。因为它很懒，它只会根据需要映射它们。这避免了制作另一个大数组。

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

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 个条目，这对于会议来说是很长的时间。

既然你已经构建了整个哈希，为什么要浪费它呢？编写一个返回完整出勤率的函数，以及另一个提取最大值的函数。

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把它们变成 Ranges。

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

推荐阅读