Scala int значение символов String

Question

Я просто хочу суммировать цифры BigInt. Я могу сделать

scala> "1 2 3".split(" ").map(_.toInt).sum
res23: Int = 6

Итак, я попытался

scala> BigInt(123).toString().map(_.toInt).sum
res24: Int = 150

Это не работает, потому что отображает символы в значения Unicode.

Обе следующие работы работают, но есть ли более элегантный способ, чем использование статического метода Java или дополнительное преобразование toString?

BigInt(123).toString().map(Character.getNumericValue(_)).sum
BigInt(123).toString().map(_.toString.toInt).sum

(Я также сделал это, используя рекурсивную функцию, полностью обойдя строки, но меня интересует краткий 1-строчный).

Answer 1

Ух ты ... эти ответы повсюду! Вот, сделайте это:

BigInt(123).toString().map(_.asDigit).sum

Answer 2

Как насчет того, чтобы вообще не использовать строки?

def sumDigits(b:BigInt):BigInt = {
  if (b < 10) b else b%10 + sumDigits(b/10)
}

Answer 3

Это не короткий и, конечно, не эффективный, но это другой путь:

scala> Iterator.iterate(BigInt(123))(_/10).takeWhile(_>0).map(_%10).sum
res1: scala.math.BigInt = 6

(и вы, вероятно, хотите Int, который в любом случае быстрее, но требует .map(i=>(i%10).toInt).)

Проблема с этим методом (и простой рекурсией) состоит в том, что вам нужно вычислить столько делений, сколько цифр. (Вы можете использовать /%, чтобы ускорить процесс в 2 раза, но это все еще проблема.) Преобразование в строку происходит намного быстрее, потому что всех этих явных BigInt созданий можно избежать.

Если вы действительно хотите что-то, что работает быстро (не то, что вы просили, я знаю), вам нужен подход "разделяй и властвуй":

def fastDigitSum(b: BigInt): Int = {
  val bits = b.bitLength
  if (bits < 63) math.abs(b.toLong).toString.map(_-'0').sum
  else {
    val many = 256
    val zeros = math.ceil(bits*0.150515).toInt // constant is 0.5*log(2)/log(10)
    val root = (
      if (zeros<many) BigInt("1" + "0"*zeros)
      else {
        Iterator.iterate((BigInt("1"+"0"*many),many))(x => (x._1 * x._1, 2*x._2)).
          find(_._2 > zeros/2).get._1
      }
    )
    val (q,r) = b /% root
    fastDigitSum(q) + fastDigitSum(r)
  }
}

---

Редактировать: Если вы хотите действительно быстрых преобразований всех размеров, я изменил мою схему следующим образом. Есть некоторые не полностью функциональные биты, в основном из-за отсутствия метода takeTo. Это должно быть быстрее, чем все остальное во всех размерах (хотя он асимптотически увеличивает производительность fastDigitSum для очень больших BigInts).

Вероятно, будет работать лучше на 64-битных машинах, чем на 32.

При создании этой функции не пострадали строки.

object DigitSum {
  val memend = BigInt(10000000000000000L) :: BigInt(100000000) :: Nil

  def longSum(l: Long, sum: Int = 0): Int = {
    if (l==0) sum else longSum(l/10, sum + (l%10).toInt)
  }

  def bigSum(b: BigInt, memo: List[BigInt] = Nil): Int = {
    val bits = b.bitLength
    if (bits < 64) longSum(b.toLong)
    else {
      val mem = (
        if (memo.isEmpty) {
          val it = Iterator.iterate(memend.head)(x=>x*x).drop(1)
          var xs = memend
          while (xs.head.bitLength*4 <= bits) xs = it.next :: xs
          xs
        }
        else memo.dropWhile(_.bitLength > bits/2)
      )
      val (q,r) = b /% mem.head
      bigSum(q,memo) + bigSum(r,memo)
    }
  }
}

(Хорошо - в данный момент это похоже на код-гольф).

Answer 4

Это не ответ на вопрос, а тест скорости предложений. Я запускал тесты несколько раз, чтобы убедиться, что виртуальная машина прогрелась и результаты были согласованы: эти результаты являются репрезентативными и рассчитаны на 10000 итераций. См. Код для определения того, что представляют собой эти методы.

Для 10-значных BigInts

fastDigitSum: 0.020618047 seconds
stringSum:    0.023708908 seconds
stringSum2:   0.02940999 seconds
stringSum3:   0.021641507 seconds
division:     0.052856631 seconds

Для 50-значных BigInts

fastDigitSum: 0.183630732 seconds
stringSum:    0.110235062 seconds
stringSum2:   0.134900857 seconds
stringSum3:   0.096670394 seconds
division:     0.317359989 seconds

Для 100-значных BigInts

fastDigitSum: 0.427543476 seconds
stringSum:    0.228062302 seconds
stringSum2:   0.277711389 seconds
stringSum3:   0.20127497 seconds
division:     0.811950252 seconds

Для BigInts на 100 000 цифр (1 итерация)

fastDigitSum: 0.581872856 seconds
stringSum:    2.642719635 seconds
stringSum2:   2.629824347 seconds
stringSum3:   2.61327453 seconds
division:     30.089482042 seconds

Так что, похоже, BigInt(123).toString().map(_-'0').sum - победитель по скорости и краткости для меньших BigInts, но метод Рекса Керра хорош, если ваши BigInts огромны.

Код теста:

object Benchmark extends App{
  def fastDigitSum(b: BigInt): Int = {
    val bits = b.bitLength
    if (bits < 63) math.abs(b.toLong).toString.map(_-'0').sum
    else {
      val many = 256
      val zeros = math.ceil(bits*0.150515).toInt // constant is 0.5*log(2)/log(10)
      val root = (
        if (zeros<many) BigInt("1" + "0"*zeros)
        else {
          Iterator.iterate((BigInt("1"+"0"*many),many))(x => (x._1 * x._1, 2*x._2)).
            find(_._2 > zeros/2).get._1
        }
      )
      val (q,r) = b /% root
      fastDigitSum(q) + fastDigitSum(r)
    }
  }

  def stringSum(b: BigInt) = b.toString.map(_.getNumericValue).sum
  def stringSum2(b: BigInt) = b.toString.map(_.toString.toInt).sum
  def stringSum3(b: BigInt) = b.toString.map(_ - '0').sum

  def division(b: BigInt) = sumDig(b, 0)
  def sumDig(b: BigInt, sum: Int):Int = {
    if (b == 0) sum
    else sumDig(b / 10, sum + (b % 10).toInt)
  }

  def testMethod(f: BigInt => Int):Double = {
    val b = BigInt("12345678901234567890123456789012345678901234567890")
    val b2 = BigInt("1234567890")
    val b3 = BigInt("1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890")
    val t0 = System.nanoTime()
    var i = 0
    while(i < 10000){
      f(b3)
      i += 1
    }
    (System.nanoTime().toDouble - t0)/1e9
  }

  def runTest(){
    var i = 0
    while (i < 5) {
      println("fastDigitSum: " + testMethod ({fastDigitSum}) + " seconds")
      println("stringSum:    " + testMethod ({stringSum}) + " seconds")
      println("stringSum2:   " + testMethod ({stringSum2}) + " seconds")
      println("stringSum3:   " + testMethod ({stringSum3}) + " seconds")
      println("division:     " + testMethod ({division}) + " seconds")
      i += 1
    }
  }

  runTest()
}

Answer 5

Я не думаю, что это намного лучше, чем те, которые вы уже получили, но

BigInt(123).toString().split("").tail.map(_.toInt).sum

также работает.

Также

BigInt(123).toString().map(_.toInt - '0'.toInt).sum

исогласно комментарию Рекса Керра, это можно упростить до

BigInt(123).toString().map(_-'0').sum

Answer 6

Я только что заметил, что у класса RichChar есть метод getNumericValue, поэтому ответ будет

BigInt(123).toString().map(_.getNumericValue).sum