Java Biginteger, 마지막 숫자를 차단합니다

StackOverflow https://stackoverflow.com/questions/1144735

문제

상당히 쉬운, Biginteger 번호가 543 인 경우 마지막 숫자를 차단하여 54가되기를 원합니다.

이 작업을 수행하는 두 가지 쉬운 방법은 다음과 같습니다.

  1. 문자열을 사용하고, 서브 스트링을 받고, 새로운 값으로 새로운 biginteger를 만듭니다.
  2. BigIntegers를 사용하여 방법은 10 번으로 나누기 방법을 분할하십시오 (543 / 10 = 54.3 => 54)

문제는 내가 이것을 수행 할 것입니다 많이 물론 큰 정수가있는 경우.

내 추측은 끈으로 연주하는 것이 느려질 것이지만 다시 BigIntegers를 그다지 많이 사용하지 않았으며 "나누기"작업이 얼마나 비싼 지 모릅니다.

속도는 여기서 필수적입니다. 이것을 구현하는 가장 빠른 방법은 무엇입니까 (메모리는 문제가 없음)?

다른 솔루션도 환영합니다.

도움이 되었습니까?

해결책

10으로 나누는 것이 기판 작업을 사용하는 것보다 훨씬 빠릅니다. 다음 벤치 마크를 사용하면 약 161 배의 시간을 얻습니다 (비율은 비트 수에 비례합니다)

    long divTime = 0;
    long substrTime = 0;
    final int bitsCount = 1000;

    for (int i = 0; i < 1000; ++i) {
        long t1, t2;
        BigInteger random = new BigInteger(bitsCount, new Random());

        t1 = System.currentTimeMillis();
        random.divide(BigInteger.TEN);
        t2 = System.currentTimeMillis();
        divTime += (t2 - t1);

        t1 = System.currentTimeMillis();
        String str = random.toString();
        new BigInteger(str.substring(0, str.length() - 1));
        t2 = System.currentTimeMillis();
        substrTime += (t2 - t1);
    }

    System.out.println("Divide: " + divTime);
    System.out.println("Substr: " + substrTime);
    System.out.println("Ratio:  " + (substrTime / divTime));

다른 팁

10으로 나누는 것이 더 빨라질 가능성이 높습니다.

숫자 10이있는 BigInteger를 만들고 10으로 나누는 데 사용하는 경우,이를 수행하는 가장 빠른 방법이 될 것입니다. 그것은 매번 임시 새로운 Biginteger를 만드는 것을 능가합니다.

서브 스트링의 문제점은 본질적으로 매번 새 문자열을 만들고 있다는 것입니다. 문자열을 통해 반복되는 속도는 말할 것도없이 훨씬 느립니다.

가장 빠른 방법은 효율적인 내부 부문 구현으로 숫자를 10으로 나누는 것입니다. 그 작업의 내부는 무대 뒤에 있지만 숫자가 Base-2가 저장되기 때문에 확실히 사소한 일입니다.

가장 빠른 구현은 아마도 내부 표현이 기본 10을 사용하는 데이터 유형을 사용하는 것입니다. BCD. 그런 다음 10 명으로 분할은 단순히 마지막 바이트를 삭제하는 것을 의미합니다 (또는 올바른 방법으로 구현할 경우 인덱스를 증가/감소시키는 것조차도).

물론, 당신은 처음부터 필요한 모든 산술 및 기타 작업을 구현해야하므로 많은 작업을 수행해야합니다.

이 질문을하는 것은 아마도 시기상조 일 것입니다. 명백한 방법 (10으로 나누기)을 수행 한 다음 벤치마킹하고 필요한 경우 최적화하십시오. 문자열 표현으로 변환하면 뒤로가 훨씬 느려집니다.

Tostring ()만으로는 기판보다 느리게 느리게 될 수 있습니다.

여러 사람들이 10으로 나누는 것이 스트링으로 변환하고 서브 스트링을 취하는 것보다 빠를 것이라고 말했다. 이유를 이해하려면 BigInteger에서 String으로 변환하는 것과 관련된 계산에 대해 생각하고 그 반대도 마찬가지입니다. 예를 들어: 

/* simplified pseudo code for converting +ve numbers to strings */
StringBuffer sb = new StringBuffer(...);
while (number != 0) {
   digit = number % 10;
   sb.append((char)(digit + '0'));
   number = number / 10;
}
return sb.toString();

주목해야 할 중요한 점은 숫자에서 문자열로 변환하면 반복적으로 10으로 나누는 것입니다. 다른 방향으로 이동하려면 log10 (번호) 곱셈이 포함됩니다. 이것은 단일 분할보다 훨씬 더 많은 계산이라는 것이 명백해야합니다.

성능이 중요하다면 ... Java를 사용하지 마십시오

기계 코드 (예 : C 또는 C ++)로 컴파일하는 언어에서는 정수 분할이 더 빠릅니다. 문자열 작업은 메모리 할당을 사용하거나 사용할 수 있으므로 느립니다.

내 베팅은 Java에서 Divisions도 더 빠를 것이라는 점입니다. 그렇지 않으면 그들의 VM 구현은 정말 이상합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top