代码之家 › 专栏 › 技术社区 › RAGHHURAAMM

SCALA:生成符合某些条件的Tuple2对象的列表

scala

-2

RAGHHURAAMM · 技术社区 · 7 年前

我想创造一个 list 属于 Tuple2 objects . 每元组 (a,b) 清单中应符合下列条件: a 和 b 两者都是完美的正方形, (b/30)<a<b 和 a>N 和 b>N ( N 甚至可以是 BigInt ) 我想写一个 scala function 产生 the List of Tuples 满足上述要求? 这是我的尝试..对于int和long都很好..但是对于BigInt,我面临着sqrt问题..下面是我的编码方法:

scala>  def genTups(N:Long) ={
     |  val x = for(s<- 1L to Math.sqrt(N).toLong) yield s*s;
     |  val y = x.combinations(2).map{ case Vector(a,b) => (a,b)}.toList
     |  y.filter(t=> (t._1*30/t._2)>=1)
     | }
genTups: (N: Long)List[(Long, Long)]

scala> genTups(30)
res32: List[(Long, Long)] = List((1,4), (1,9), (1,16), (1,25), (4,9), (4,16), (4,25), (9,16), (9,25), (16,25))

使用BigInt平方根算法对此进行了如下改进:

def genTups(N1:BigInt,N2:BigInt) ={
    def sqt(n:BigInt):BigInt = {
        var a = BigInt(1)
        var b = (n>>5)+BigInt(8)
        while((b-a) >= 0) {
         var mid:BigInt = (a+b)>>1
         if(mid*mid-n> 0) b = mid-1
         else a = mid+1
        }; a-1 }
      val x = for(s<- sqt(N1) to sqt(N2)) yield s*s;
      val y = x.combinations(2).map{ case Vector(a,b) => (a,b)}.toList
      y.filter(t=> (t._1*30/t._2)>=1)
  }

我很感谢你对我算法的改进。

2 回复 | 直到 7 年前

1

2

Tim 7 年前

你可以避免 sqrt 在你的算法中通过改变你的计算方式 x 对此:

  val x = (BigInt(1) to N).map(x => x*x).takeWhile(_ <= N)

最后的功能是:

def genTups(N: BigInt) = {
  val x = (BigInt(1) to N).map(x => x*x).takeWhile(_ <= N)
  val y = x.combinations(2).map { case Vector(a, b) if (a < b) => (a, b) }.toList
  y.filter(t => (t._1 * 30 / t._2) >= 1)
}

您还可以将其重新编写为单个操作链,如下所示:

def genTups(N: BigInt) =
  (BigInt(1) to N)
    .map(x => x * x)
    .takeWhile(_ <= N)
    .combinations(2)
    .map { case Vector(a, b) if a < b => (a, b) }
    .filter(t => (t._1 * 30 / t._2) >= 1)
    .toList

为了追求性能,我提出了这个递归版本,它看起来要快得多

def genTups(N1: BigInt, N2: BigInt) = {
  def sqt(n: BigInt): BigInt = {
    var a = BigInt(1)
    var b = (n >> 5) + BigInt(8)
    while ((b - a) >= 0) {
      var mid: BigInt = (a + b) >> 1
      if (mid * mid - n > 0) {
        b = mid - 1
      } else {
        a = mid + 1
      }
    }
    a - 1
  }

  @tailrec
  def loop(a: BigInt, rem: List[BigInt], res: List[(BigInt, BigInt)]): List[(BigInt, BigInt)] =
    rem match {
      case Nil => res
      case head :: tail =>
        val a30 = a * 30
        val thisRes = rem.takeWhile(_ <= a30).map(b => (a, b))

        loop(head, tail, thisRes.reverse ::: res)
    }

  val squares = (sqt(N1) to sqt(N2)).map(s => s * s).toList

  loop(squares.head, squares.tail, Nil).reverse
}

循环的每个递归都将给定值的所有匹配对相加 a . 结果是反向生成的,因为添加到长列表的前面要比添加到尾部快得多。

2

-1

Chaitanya 7 年前

首先创建一个函数来检查数字是否为完美正方形。

def squareRootOfPerfectSquare(a: Int): Option[Int] = {
  val sqrt = math.sqrt(a)
  if (sqrt % 1 == 0)
    Some(sqrt.toInt)
  else
    None
}

然后,创建另一个func,它将根据上述条件计算这个元组列表。

def generateTuples(n1:Int,n2:Int)={
  for{
    b <- 1 to n2;
    a <- 1 to n1 if(b>a && squareRootOfPerfectSquare(b).isDefined && squareRootOfPerfectSquare(a).isDefined)
  } yield ( (a,b) )
}

然后用参数调用函数 generateTuples(5,10) 你将得到一个输出

res0: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,4), (1,9), (4,9))

希望能有帮助!!!