비트 셋 을 왜 써 요?
1711 단어 Java
예 를 들 어 2000 만 숫자 중 소수 개 수 를 판단 하 는 프로그램 에서 가장 기본 적 인 소수 판단 코드 를 사용 하면:
package com;
public class Sus {
public static void main(String[] args) {
// TODO Auto-generated method stub
int n = 20000000;
long start = System.currentTimeMillis();
int count = 0;
boolean is = false;
for(int i = 2;i <= n;i++){
for(int j = 2; j <= Math.sqrt(i);j++){
if( i % j == 0){
is = true;
break;
}
}
if(!is){
count++;
}
is = false;
}
long end = System.currentTimeMillis();
System.out.println("count = "+count);
System.out.println((end-start)+" milliseconds");
}
}
count = 1270607
35153 milliseconds
만약 에 BitSet 비트 맵 이 제공 하 는'스위치'사상 을 바탕 으로 하 는 소수 판단 코드 를 사용한다 면:
package com;
import java.util.BitSet;
public class Sieve {
public static void main(String[] args){
int n = 20000000;
long start = System.currentTimeMillis();
BitSet b = new BitSet(n+1);
int count = 0;
int i;
for(i = 2; i <= n;i++){
b.set(i);
}
i = 2;
while(i*i <=n){
if(b.get(i)){
count++;
int k = 2 * i;
while(k <= n){
b.clear(k);
k +=i;
}
}
i++;
}
while(i <= n){
if(b.get(i)){
count++;
}
i++;
}
long end = System.currentTimeMillis();
System.out.println("count = " + count);
System.out.println((end-start) +" milliseconds");
}
}
실행 시간 은:
count = 1270607 248 milliseconds
같은 규모 의 데 이 터 는 둘 의 실행 효율 이 100 배 나 떨 어 지 는 것 을 볼 수 있 기 때문에 스위치 로 판단 할 수 있 는 프로그램 에 서 는 가능 한 한 BitSet 를 사용 해 야 한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
