15赞

如果元素在数组中出现三次以上,则返回布尔值

作者：帆侮听我悄悄说星星 | 2023-09-09 17:14

如何解决《如果元素在数组中出现三次以上,则返回布尔值》经验，为你挑选了3个好方法。

我需要一个数组并返回true它是否包含三次或更多的元素.如果数组包含少于三次的元素,则需要返回false.我猜我需要使用这个count方法,但我不知道要放在我的块中.我写了以下代码:

def got_three?(array)
  array.count {|x|}
end

got_three? ([1, 2, 2, 2, 4, 5, 4, 6, 7])

有人可以帮忙吗？

1> Silvio Mayol..：

您可以使用#count,但是您还需要另一个原语,因为您要检查每个元素.在这种情况下,#any?就足够了.

def got_three?(array)
  array.any? { |y| array.count(y) >= 3 }
end

这将返回数组中出现的任何元素是否至少出现三次.

虽然这样可以工作,但你在三重对象之前为每个对象重复一次**至少**...如果三重对象是第三个,你将三次迭代数组......这似乎是一个有些浪费的解决方案.如果我一直在我的笔记本电脑上,我会提供更多的输入.

2> Myst..：

虽然我喜欢Silvio的答案,但它可能会多次迭代阵列.

根据数组的大小以及使用此方法的频率,它可能会损害性能 - 尤其是在用于服务器应用程序时,例如在Rails中.

以下可能不太可读,但应该更好:

def has_three?(array)
   h = (Thread.current[:_has_three_buffer] ||= Hash.new(0)).clear
   array.each do |i|
      h[i] += 1
      return true if h[i] >= 3
   end
   false
end

编辑

关于方法优化的快速解释.

速度:

该方法使用哈希来映射每个元素重复的次数.这允许更少的迭代.

该方法不再迭代数组一次,停止true响应可用的时刻.

此方法将读取阵列中至少3个元素.最多,此方法将遍历数组迭代一次.

内存和对象分配(开销):

创建一个Hash来映射数组是一个昂贵的开销,可以(并且应该)最小化.

开销是由与对象创建和初始化(包括初始内存分配)相关的性能价格引起的.

基准测试表明,当三重物体在阵列内更深时(即位于第三个位置之后),开销非常值得.

此方法为每个线程创建一个Hash,只要调用该方法,就会使用该Hash.这是一种比使用Mutex更好的方法,它可以提供线程安全性但防止并行并发(即使用JRuby时).

Hash使用Thread.current内存存储在当前线程中.

Hash:Thread.current[:_has_three_buffer] ||= Hash.new(0)将保留在线程的内存中,直到线程退出,这样就可以避免主要的开销,并用访问Hash的较小开销替换,并使用"清除"它的内存clear.

这Hash.new(0)意味着哈希将返回0而不是nil缺少元素.

更新的基准

基准测试不同的解决方案让我感到惊讶.Silvio的解决方案并不像我担心的那么慢,Jon的解决方案比我想象的要慢......

我也对解决方案使用的内存感到惊讶.我的方法使用了比我想象的更多的内存,但与Wand的方法相比,它仍然是优化的

以下是使用某些样本数组进行100,000次迭代的测量.

前两个基准测试是一个10项长的数组,其中三元组(对象出现三次)在开头(由于它的开销导致我的答案处于劣势)或者结束(某些答案由于迭代).

- 数组(10项):[1,1,1,2,3,4,5,6,7,8]

silvio 0.040000 0.000000 0.040000(0.043519)

myst 0.080000 0.000000 0.080000(0.074734)

jon 0.240000 0.010000 0.250000(0.252569)

魔杖0.260000 0.030000 0.290000(0.289101)

- 数组(10项):[8,7,6,5,4,3,2,1,1,1]

silvio 0.310000 0.000000 0.310000(0.313565)

myst 0.300000 0.000000 0.300000(0.298405)

jon 0.530000 0.010000 0.540000(0.534697)

魔杖0.310000 0.030000 0.340000(0.350704)

接下来,我测量了一个10项长阵列,其中三联体位于大约中间位置(从项目编号5开始).

我还回顾了100项迭代的10项长阵列评论的近似内存使用情况.内存审查包括用于基准测试和构建报告的内存,它在任何方面都不准确......但它可能显示了一些内容......

- 数组(10项):[1,2,3,4,5,5,5,8,9,10]

使用的内存(通过打印数组):4KB - 显示这是不准确的

silvio 0.200000 0.000000 0.200000(0.200012)

使用的内存(silvio):4KB

myst 0.210000 0.010000 0.220000(0.214936)

使用的内存(myst):5,944KB

jon 0.420000 0.000000 0.420000(0.422354)

使用的内存(jon):18,364KB

魔杖0.300000 0.030000 0.330000(0.342656)

使用的内存(魔杖):118,496KB(~118MB!)

正如您所看到的,在查看短数组(10个项目)时,差异非常小,可能不值得用于优化更长数组方法的内存.

接下来我做了同样的事情(中间的三重奏),有50个项目的长数组...这是迭代的差异真的出现的时候.也就是说,虽然我的答案使用了大约1.5秒,但Silvio的方法花费了大约7.5秒 - 大约慢了5倍.

- 数组(50项):[1 ... 47,50,50,50]

silvio 7.560000 0.010000 7.570000(7.570565)

myst 1.480000 0.010000 1.490000(1.487640)

jon 8.290000 0.020000 8.310000(8.316714)

魔杖1.550000 0.150000 1.700000(1.700455)

然而,Jon指出基准测试非常无菌,除了三元组之外没有重复的对象,所以接下来我用100个项目对数组进行基准测试,其中每个项目重复两次(除了三元组).三胞胎在中间.

这是Jon的开销(使用unique)显示它的优势.虽然乔恩的方法花了大约8.6秒,但西尔维奥的进近达到了大约14秒.魔杖和我都保持在个位数,我的答案是最快的 - 约1.2秒.

我还回顾了迭代和Benchmarking本身导致的大致内存增长......

一些解决方案使用了大量内存.也就是说,Wand的漂亮解决方案为100个长项目(100K迭代)构建了~0.5GB(!),而Jon的解决方案使用了~50MB,我的解决方案可以达到~5MB,而Silvio的解决方案似乎根本没有使用任何内存(这可能是一个小故障,显示内存测试有多么不准确).

同样,内存使用不准确.

- 数组(100项):[1..23,1..23,24,25,25,25,26..50,26..50]

使用的内存(通过打印数组):4KB - 显示这是不准确的

silvio 14.090000 0.010000 14.100000(14.100915)

使用的内存(silvio):0KB

myst 1.170000 0.010000 1.180000(1.182665)

使用的内存(myst):5,992KB

jon 8.570000 0.020000 8.590000(8.592982)

使用的内存(jon):51720KB

魔杖1.940000 0.160000 2.100000(2.093121)

使用的内存(魔杖):569,264KB(~569MB!)

基准代码:

require 'benchmark'

def silvio_got_three?(array)
  array.any? { |y| array.count(y) >= 3 }
end

def myst_has_three?(array)
   h = (Thread.current[:_has_three_buffer] ||= Hash.new(0)).clear
   # h = Hash.new(0)
   array.each do |i|
      h[i] += 1
      return true if h[i] >= 3
   end
   false
end

def jon_has_three?(array)
  array.uniq.any? { |x| array.count(x) >= 3 }
end

def wand_has_three?(array)
  array.group_by {|i| i }.any? {|_, v| v.size >= 3}
end

def get_total_memory_used
  `ps -o rss= -p #{Process.pid}`.to_i
end

# warm-up
myst_has_three? [0]

Benchmark.bm do |bm|
  a = [1,1,1] + (2..8).to_a
  repeat = 100_000
  GC.disable
  puts "Array (#{a.length} items): #{a.to_s}"
  bm.report('silvio') { repeat.times { silvio_got_three?(a) } }
  bm.report('myst') { repeat.times { myst_has_three?(a) } }
  bm.report('jon') { repeat.times { jon_has_three?(a) } }
  bm.report('wand') { repeat.times { wand_has_three?(a) } }
  a.reverse!
  puts "Array (#{a.length} items): #{a.to_s}"
  bm.report('silvio') { repeat.times { silvio_got_three?(a) } }
  bm.report('myst') { repeat.times { myst_has_three?(a) } }
  bm.report('jon') { repeat.times { jon_has_three?(a) } }
  bm.report('wand') { repeat.times { wand_has_three?(a) } }
  a = (1..4).to_a + [5,5,5] + (8..10).to_a
  mem = get_total_memory_used
  puts "Array (#{a.length} items): #{a.to_s}"
  puts "Memory used (by printing the Array): #{get_total_memory_used - mem}KB - showing this isn't accurate"
  mem = get_total_memory_used
  bm.report('silvio') { repeat.times { silvio_got_three?(a) } }
  puts "Memory used (silvio): #{get_total_memory_used - mem}KB"
  mem = get_total_memory_used
  bm.report('myst') { repeat.times { myst_has_three?(a) } }
  puts "Memory used (myst): #{get_total_memory_used - mem}KB"
  mem = get_total_memory_used
  bm.report('jon') { repeat.times { jon_has_three?(a) } }
  puts "Memory used (jon): #{get_total_memory_used - mem}KB"
  mem = get_total_memory_used
  bm.report('wand') { repeat.times { wand_has_three?(a) } }
  puts "Memory used (wand): #{get_total_memory_used - mem}KB"
  mem = get_total_memory_used 
  a = (1..47).to_a + [50,50,50]
  puts "Array (#{a.length} items): #{a.to_s}"
  bm.report('silvio') { repeat.times { silvio_got_three?(a) } }
  bm.report('myst') { repeat.times { myst_has_three?(a) } }
  bm.report('jon') { repeat.times { jon_has_three?(a) } }
  bm.report('wand') { repeat.times { wand_has_three?(a) } }
  a = (1..23).to_a*2 + [24,25,25,25] + (26..50).to_a*2
  mem = get_total_memory_used
  puts "Array (#{a.length} items): [1..23,1..23,24, 25,25,25, 26..50,26..50]"
  puts "Memory used (by printing the Array): #{get_total_memory_used - mem}KB - showing this isn't accurate"
  mem = get_total_memory_used
  bm.report('silvio') { repeat.times { silvio_got_three?(a) } }
  puts "Memory used (silvio): #{get_total_memory_used - mem}KB"
  mem = get_total_memory_used
  bm.report('myst') { repeat.times { myst_has_three?(a) } }
  puts "Memory used (myst): #{get_total_memory_used - mem}KB"
  mem = get_total_memory_used
  bm.report('jon') { repeat.times { jon_has_three?(a) } }
  puts "Memory used (jon): #{get_total_memory_used - mem}KB"
  mem = get_total_memory_used
  bm.report('wand') { repeat.times { wand_has_three?(a) } }
  puts "Memory used (wand): #{get_total_memory_used - mem}KB"
  mem = get_total_memory_used
  GC.start
end; nil

3> Jon..：

Silvio的回答是有效的,但正如Myst指出的那样,它将使用相同的参数多次迭代数组.

如果没有Myst解决方案的复杂性,这应该会更好一些:

def has_three?(array)
  array.uniq.any? { |x| array.count(x) >= 3 }
end

这种微小的差异意味着您只会为每个唯一元素迭代一次数组,而不是对每个重复元素运行额外的检查.

推荐阅读

程序员
从移动应用程序中的PCI-DSS开始？

如何解决《从移动应用程序中的PCI-DSS开始？》经验，为你挑选了0个好方法。 ... [详细]
程序员
如何强制PHP / Apache再使用一年？

如何解决《如何强制PHP/Apache再使用一年？》经验，为你挑选了0个好方法。 ... [详细]
程序员
iOS - 使用Autolayout为UILabel设置最大宽度

如何解决《iOS-使用Autolayout为UILabel设置最大宽度》经验，为你挑选了1个好方法。 ... [详细]
程序员
Visual Studio 2015 Update 1 xaml设计器未显示UWP

如何解决《VisualStudio2015Update1xaml设计器未显示UWP》经验，为你挑选了1个好方法。 ... [详细]
程序员
如何在spring boot中使用应用程序上下文获取bean

如何解决《如何在springboot中使用应用程序上下文获取bean》经验，为你挑选了3个好方法。 ... [详细]
程序员
如何获取jquery datepicker的当前活动实例

如何解决《如何获取jquerydatepicker的当前活动实例》经验，为你挑选了1个好方法。 ... [详细]
程序员
C#Anti-Debug方法OutputDebugString无法正常工作

如何解决《C#Anti-Debug方法OutputDebugString无法正常工作》经验，为你挑选了1个好方法。 ... [详细]
程序员
缺少"使用严格",即使它已经在文件顶部声明

如何解决《缺少"使用严格",即使它已经在文件顶部声明》经验，为你挑选了1个好方法。 ... [详细]
程序员
AngularJs:ng-如果反应太迟了

如何解决《AngularJs:ng-如果反应太迟了》经验，为你挑选了0个好方法。 ... [详细]
程序员
无法构建gem本机扩展-解决方案

如何解决《无法构建gem本机扩展-解决方案》经验，为你挑选了1个好方法。 ... [详细]
程序员
使用mongo计算所有文档中的数组出现次数

如何解决《使用mongo计算所有文档中的数组出现次数》经验，为你挑选了1个好方法。 ... [详细]
程序员
部署到Visual Studio中找不到的Android设备

如何解决《部署到VisualStudio中找不到的Android设备》经验，为你挑选了2个好方法。 ... [详细]
程序员
如何压缩我的git分支提交到相同的分支没有变基？

如何解决《如何压缩我的git分支提交到相同的分支没有变基？》经验，为你挑选了0个好方法。 ... [详细]
程序员
如何在android中的文本视图中添加动画

如何解决《如何在android中的文本视图中添加动画》经验，为你挑选了1个好方法。 ... [详细]
程序员
如何在Docker Registry v2中创建只读用户？

如何解决《如何在DockerRegistryv2中创建只读用户？》经验，为你挑选了0个好方法。 ... [详细]
程序员
使用服务器端加密上传到S3期间的数据完整性检查

如何解决《使用服务器端加密上传到S3期间的数据完整性检查》经验，为你挑选了0个好方法。 ... [详细]
程序员
Swift.org与开源swift项目的问题.错误:xcrun:错误:无法找到实用程序"launch-with-toolchain",而不是开发人员工具或PATH

如何解决《Swift.org与开源swift项目的问题.错误:xcrun:错误:无法找到实用程序"launch-with-toolchain",而不是开发人员工具或PATH》经验，为你挑选了1个好方法。 ... [详细]
程序员
SmtpClient无法发送; 雷鸟可以

如何解决《SmtpClient无法发送;雷鸟可以》经验，为你挑选了0个好方法。 ... [详细]
程序员
将Future [List [String]]转换为List [String]

如何解决《将Future[List[String]]转换为List[String]》经验，为你挑选了1个好方法。 ... [详细]
程序员
通过JsonConvert和自定义TypeConverter反序列化对象

如何解决《通过JsonConvert和自定义TypeConverter反序列化对象》经验，为你挑选了0个好方法。 ... [详细]

帆侮听我悄悄说星星

这个屌丝很懒，什么也没留下！

关注作者

Tags | 热门标签

RankList | 热门文章