Scala int-Wert von String-Zeichen

Question

Ich möchte nur die Ziffern einer BigInt summieren. Ich kann

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

Also habe ich versucht

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

Das funktioniert nicht, weil die Zeichen auf ihre Unicode-Werte abgebildet werden.

Beide der folgenden Arbeit, aber gibt es einen eleganteren Weg als die Verwendung der statischen Java-Methode oder eine zusätzliche toString-Konvertierung?

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

(Ich habe es auch mit einer rekursiven Funktion gemacht, die Zeichenketten ganz umgeht, aber ich bin hier an einem knappen Einzeiler interessiert).

Answer 1

Wow... diese Antworten sind wirklich sehr unterschiedlich! Hier, mach das:

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

Answer 2

Wie wäre es, überhaupt keine Strings zu verwenden?

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

Answer 3

Das ist nicht kurz und sicherlich nicht effizient, aber es ist ein anderer Weg:

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

(und Sie wollen wahrscheinlich eine Int was ohnehin schneller ist, aber eine .map(i=>(i%10).toInt) .)

Das Problem bei dieser Methode (und der einfachen Rekursion) ist, dass man so viele Divisionen wie Ziffern berechnen muss. (Sie könnten verwenden /% um die Dinge um den Faktor 2 zu beschleunigen, aber das ist immer noch ein Problem). Die Konvertierung in eine Zeichenkette ist viel schneller, weil all diese expliziten BigInt Kreationen vermieden werden können.

Wenn Sie wirklich etwas wollen, das funktioniert schnell (nicht das, was Sie wollten, ich weiß), brauchen Sie einen Ansatz, bei dem Sie teilen und erobern:

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)
  }
}

---

Bearbeiten: Wenn Sie möchten wirklich schnelle Konvertierungen bei allen Größen, habe ich mein Schema wie folgt geändert. Es gibt einige nicht ganz funktionsfähige Bits, die hauptsächlich auf das Fehlen eines takeTo Methode. Dies sollte bei allen Größen schneller sein als alles andere (obwohl es asymptotisch zu fastDigitSum Leistung für sehr große BigInts).

Wahrscheinlich läuft es auf 64-Bit-Maschinen besser als auf 32-Bit-Maschinen.

Bei der Herstellung dieser Funktion wurden keine Saiten beschädigt.

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)
    }
  }
}

(Okay - das ist jetzt ein bisschen wie Code-Golf.)

Answer 4

Ich glaube nicht, dass sie viel besser ist als die, die Sie bereits haben, aber

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

funktioniert auch.

Auch

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

und gemäß Rex Kerrs Kommentar kann dies vereinfacht werden zu

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

Answer 5

Dies ist keine Antwort auf die Frage, sondern ein Geschwindigkeitstest der Vorschläge. Ich habe die Tests mehrmals durchgeführt, um sicherzustellen, dass die VM aufgewärmt war und die Ergebnisse konsistent waren: Diese Ergebnisse sind repräsentativ und beziehen sich auf 10000 Iterationen. Siehe Code für Definitionen dieser Methoden.

Für 10-stellige BigInts

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

Für 50-stellige BigInts

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

Für 100-stellige BigInts

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

Für 100.000-stellige BigInts (1 Iteration)

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

Es scheint also BigInt(123).toString().map(_-'0').sum ist der Gewinner für Geschwindigkeit und Prägnanz für kleinere BigInts, aber die Methode von Rex Kerr ist gut, wenn Ihre BigInts groß sind.

Benchmark-Code:

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()
}