在大量数字列表中搜索特定数字的效率

Question

我有以下代码，其中 eratosthenes(N) returns 一个从 1 到 N 的素数数组。我想要做的是从此列表中删除包含数字 0、2、 4、5、6、8。我的代码似乎效率低下且错误，因为它需要大约 20 秒（eratosthenes(N) 是瞬时的）才能达到 100,000，并且没有删除我想要的所有数字。有没有更好的、可扩展的解决方案来解决这个问题？

N = 1_000_000
primes = eratosthenes(N)

primes.each do |num|
  if ["0", "2", "4", "5", "6", "8"].any? { |digit| num.to_s.include?(digit) }
      primes.delete(num)
  end
end

Answer 1

我认为您正在寻找类似的东西：

primes.reject!{|num| num % 2 == 0}

Answer 2

你的方法的问题是每个 delete 重写数组，并且为每个删除的项目调用它，所以算法的复杂度是 O(n^2) 而不是 O(n)。

你应该这样做：

primes.reject!{|num| ["0", "2", "4", "5", "6", "8"].any? { |digit| num.to_s.include?(digit) }}

或者简单地说：

primes.reject!{|num| num.to_s[/[024568]/]}

这只是样式问题，但我会将所有内容放在一行中（注意此处 reject 中缺少 !）：

primes = eratosthenes(N).reject{|num| num.to_s[/[024568]/]}

在大量数字列表中搜索特定数字的效率

Efficiency of searching a large list of numbers for certain digits

ruby

performance

scalability