Обычная практика, как бороться с целочисленными переполнениями? - PullRequest
Новая
       15

Обычная практика, как бороться с целочисленными переполнениями?

9 голосов
/ 26 марта 2012

Что является обычной практикой для работы с целочисленными переполнениями, такими как 999999 * 999999 (результат> Integer.MAX_VALUE) с точки зрения команды разработчиков ?

Можно просто сделать BigInt обязательным и запретить использование Integer, но разве это хорошая / плохая идея?

Ответы [ 4 ]

13 голосов
/ 26 марта 2012

Если крайне важно, чтобы целое число не переполнялось, вы можете определить свои собственные операции по переполнению, например ::10000 

def +?+(i: Int, j: Int) = {
  val ans = i.toLong + j.toLong
  if (ans < Int.MinValue || ans > Int.MaxValue) {
    throw new ArithmeticException("Int out of bounds")
  }
  ans.toInt
}

Вы можете использовать шаблон enrich-your-library, чтобы превратить его в операторы; если JVM удастся правильно выполнить анализ побега, вы не получите за это слишком много штрафа: 

class SafePlusInt(i: Int) {
  def +?+(j: Int) = { /* as before, except without i param */ }
}
implicit def int_can_be_safe(i: Int) = new SafePlusInt(i)

Например: 

scala> 1000000000 +?+ 1000000000
res0: Int = 2000000000

scala> 2000000000 +?+ 2000000000
java.lang.ArithmeticException: Int out of bounds
    at SafePlusInt.$plus$qmark$plus(<console>:12)
    ...

Если это не чрезвычайно важно, то в большинстве случаев стандартное модульное тестирование и обзоры кода должны решить проблему. Использование BigInt возможно, но замедлит вашу арифметику примерно в 100 раз и не поможет вам, когда вам придется использовать существующий метод, который принимает Int.

6 голосов
/ 26 марта 2012

Если вы используете Scala (и, как я полагаю, на основе тега), одним из наиболее общих решений является написание кода вашей библиотеки для класса scala.math.Integral: 

def naturals[A](implicit f: Integral[A]) =
  Stream.iterate(f.one)(f.plus(_, f.one))

Вы также можете использовать границы контекста и Integral.Implicits для лучшего синтаксиса: 

import scala.math.Integral.Implicits._

def squares[A: Integral] = naturals.map(n => n * n)

Теперь вы можете использовать эти методы с Int или Long или BigInt по мере необходимости, поскольку экземпляры Integral существуют для всех из них: 

scala> squares[Int].take(10).toList
res0: List[Int] = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)

scala> squares[Long].take(10).toList
res0: List[Long] = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)

scala> squares[BigInt].take(10).toList
res1: List[BigInt] = List(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)

Нет необходимости изменять код библиотеки: просто используйте Long или BigInt, где проблема переполнения, и Int в противном случае.

Вы заплатите некоторый штраф с точки зрения производительности, но щедрость и способность отложить решение Int -или- BigInt могут стоить этого.

5 голосов
/ 26 марта 2012

Наиболее распространенная практика , касающаяся целочисленных переполнений, заключается в том, что программисты должны знать, что проблема существует, отслеживать случаи, когда они могут возникнуть, и делать соответствующие проверки или перераспределять математические вычисления так,что переполнения не произойдет, например, a * (b / c), а не (a * b) / c.Если в проекте используется модульное тестирование, они будут включать случаи, чтобы попытаться вызвать переполнение.

Я никогда не работал и не видел код от команды, которая требовала чего-то большего, поэтому я скажу, что этого достаточно для почти всех программ.

Единственное встроенное приложение, которое я видел, что, честно говоря, монстру-спагетти, НУЖНО предотвратить переполнения, они сделали это, доказав, что переполнения не возможны в каждой строке, где выглядело, как будто они могут произойти.

4 голосов
/ 27 марта 2012

В дополнение к простой внимательности, как отмечает @mjfgates, есть несколько приемов, которые я всегда использую при работе с масштабируемыми десятичными (не с плавающей запятой) величинами реального мира.Это может не подходить для вашего конкретного приложения - заранее извиняюсь, если нет.

Во-первых, если используется несколько единиц измерения, значения всегда должны четко определять, какие они есть.Это может быть соглашение об именовании или использование отдельного класса для каждой единицы измерения.Я всегда просто использовал имена - суффикс для каждого имени переменной.Помимо устранения ошибок из-за путаницы в единицах , это побуждает задуматься о переполнении, поскольку менее вероятно, что показатели будут восприниматься как просто числа.

Во-вторых, мой самый частый источник переполненияОбычно проблема заключается в изменении масштаба - преобразовании одной меры в другую - когда для этого требуется много значащих цифр.Например, коэффициент преобразования из см в дюймы составляет 0,393700787402.Чтобы избежать переполнения и потери значащих цифр, необходимо соблюдать осторожность при умножении и делении в правильном порядке.Я давно этого не делал, но я верю, что вы хотите что-то вроде:

Добавить в Rational.scala , из Книги: 

  def rescale(i:Int) : Int = {
      (i * (numer/denom)) + (i/denom * (numer % denom))

Тогда вы получите результаты (сокращенно из теста specs2): 

  val InchesToCm = new Rational(1000000000,393700787)
  InchesToCm.rescale(393700787) must_== 1000000000
  InchesToCm.rescale(1) must_== 2

Это не округляет или не учитывает отрицательные коэффициенты масштабирования.Производственная реализация может захотеть выделить numer/denom и numer % denom.

...