최적의 HashSet 초기화 (스칼라 | Java)

Question

나는 A.I. "Maze of Life"퍼즐을 해결할 수 있습니다. 상태를 HashSet에 저장하려고하면 모든 것이 느려집니다. 탐색 된 상태 집합없이 실행하는 것이 더 빠릅니다. 나는 상당히 노드 노드 (상태 저장)가 equals를 구현하고 hashCode 테스트가 HashSet 중복 상태를 추가하지 않는다는 것을 보여주는 것으로 확신한다. hashCode 함수를 재 작업해야 할 수도 있지만 느려지는 것은 HashSet 재진입 및 크기 조정입니다.

나는 매우 많은 수의 초기 용량 설정을 시도했습니다,하지만 매우 느린 여전히 : 여기,

class QuickQueue[T](capacity: Int) { 

val hashSet = new HashSet[T](capacity) 
val queue = new Queue[T] 
    //methods below 

더 많은 정보를 들면 :

val initCapacity = java.lang.Math.pow(initialGrid.width*initialGrid.height,3).intValue() 
val frontier = new QuickQueue[Node](initCapacity) 

여기에 빠른 큐 코드 해시 함수입니다. 에

override def hashCode(): Int = { 
    var sum = Math.pow(grid.goalCoords._1, grid.goalCoords._2).toInt 
    for (y <- 0 until grid.height) { 
    for (x <- 0 until grid.width) { 
     sum += Math.pow(grid((x, y)).doubleValue(), x.toDouble).toInt 
    } 
    sum += Math.pow(sum, y).toInt 
    } 
    return sum 
} 

어떤 제안을 설정하는 방법에 천천히 일을 실 거예요 HashSet : 나는 두 배열의 바이트 그리드 값 및 액세스 그것을 사용하여 튜플을 저장? 탐험 한 국가를 기억하는 방법에 대한 또 다른 제안입니까?

P. java.util.HashSet을 사용하고/

Answer 1

자 세트 O를 개시 위해 함께

override def hashCode(): Int = 

교체주세요 승 심지어 초기 용량 세트, 그것을 80초 VS < 7초 소요

override lazy val hashCode: Int = 

따라서 해시 코드에 액세스해야 할 때마다 (grid.height*grid.width) 부동 소수점 수를 계산하지 마십시오. 엄청난 양의 속도를 낼 것입니다.

그렇다면 가까운 해시 코드를 가진 가까운 셀에 의존하지 않으면 휠을 다시 발명하지 마십시오. scala.util.hashing.MurmurHash3.seqHash을 사용하거나 해시를 계산할 때 사용하십시오. 이렇게하면 해시를 20 배 정도 향상시킬 수 있습니다. (여전히 게으른 값을 유지하십시오.)

그런 다음 필요한 설정 작업의 오버 헤드 만 있습니다. 현재 0x0 그리드가 많지 않다면 math.pow를 기다리는 동안 압도적 인 대부분의 시간을 사용하여 값을 얼마나 크게했는지에 따라 결과를 얻을 수 있습니다 (그리고 모든 것이 Double.PositiveInfinity 또는 0.0이 될 위험이 있습니다. 해시 충돌을 일으켜서 상황을 더 늦추 게 만듭니다.)

Answer 2

다음은 모든 개체가 변경할 수 없다고 가정합니다. 이것은 해싱을 사용할 때 정당한 가정입니다.

또한 최적화를 적용하기 전에 코드를 프로파일해야합니다 (예 : JDK와 함께 제공되는 무료 jvisualvm 사용). 해시 코드를 계산 빠른 hashCode

에 대한

메모이 제이션은 일반적으로 병목 현상입니다. 해시 코드를 각 객체에 대해 한 번만 계산하고 결과를 저장하면 해시 코드 계산 비용을 최소로 (객체 생성시 한 번) 줄일 수 있습니다. 이를 달성하려면 def hashCode을 lazy val 또는 val으로 변환하십시오.equals을 계산

당신이 제거 hashCode의 비용을 일단 빠른 equals을 위해 인턴

는 문제가된다. equals은 수집 장 및 일반적으로 깊은 구조물에 특히 비쌉니다.

equals은 인턴으로 최소화 할 수 있습니다. 즉, 팩토리 메서드를 통해 클래스의 새 객체를 가져 오면 요청 된 새 객체가 이미 있는지 여부를 확인한 다음 기존 객체에 대한 참조를 반환합니다. 이 유형의 모든 객체가 이러한 방식으로 구성되었다고 주장하면 각 객체의 인스턴스가 하나만 있고 equals이 객체 ID와 동일해진다는 것을 알 수 있습니다. 이는 저렴한 참조 비교입니다 (Scala의 eq).