java - 如何高效存储大型Java map ？

Question

我正在暴力破解一款游戏，我需要存储所有位置和结果的数据。数据的大小可能会达到数百 Gb。我考虑过 SQL，但我担心紧密循环中的查找可能会降低性能。程序将迭代可能的位置并返回获胜的 Action (如果已知)，如果已知所有 Action 都会失败则返回最长的失败序列并检查未知 Action 的结果。

存储大型 Map<Long,Long[]> positionIdToBestMoves 的最佳方式是什么？ ？我正在考虑 SQL 或数据序列化。

我想通过暴力破解 Java 中所有可行的棋步来破解小跳棋。持仓上限在1000亿左右。他们中的大多数都不合理(即比游戏开始时出现的更多)。大约 100 亿是一个合理的估计。每个Map<Long, Long[]> position map Long positionID至 Long whiteToMove和 Long blackToMove .正值表示位置获胜，应选择导致位置存储在值中的移动。负值 -n意味着头寸最多亏损 n移动。

搜索本身会有这样的递归:

//this is a stub

private Map<Long, Long[]> boardBook =...

//assuming that all winning positions are known
public Long nextMove(Long currentPos, int whiteOrBlack){
Set<Long> validMoves = calculateValidMoves(currentPos, whiteOrBlack);
boolean hasWinner = checkIfValidMoveIsKnownToWin(validMoves, whiteOrBlack);

if(hasWinner){  //there is a winning move - play it
    Long winningMove = getWinningMove(validMoves, whiteOrBlack);
    boardBook.get(currentPos)[whiteOrBlack] = winningMove ;    
    return winningMove ;
    }
boolean areAllPositionsKnown = checkIfAllPositionsKnown(validMoves, whiteOrBlack);
if(areAllPositionsKnown){  //all moves are losing.. choose longest struggle
    Long longestSequenceToDefeat = findPositionToLongestSequenceToDefeat(validMoves, whiteOrBlack);
    int numberOfStepsTodefeat = boardBook.get(longestSequenceToDefeat)[whiteOrBlack];
    boardBook.get(currentPos)[whiteOrBlack] = longestSequenceToDefeat ;
    return longestSequenceToDefeat;
    }

Set<Long> movesToCheck = getUntestedMoves(validMoves, whiteOrBlack);
Long longeststruggle;
int maxNumberOfMovesToDefeat =-1;
for(Long moveTocheck : movesToCheck){
    Long result = nextMove(moveToCheck, whiteOrBlack);
    if(result>0){ //just discovered a winning move
            boardBook.get(currentPos)[whiteOrBlack] = winningMove ;    
            return winningMove ;
        }else {
            int numOfMovesToDefeat = -1*boardBook.get(moveTocheck)[whiteOrBlack];
            if( numOfMovesToDefeat >maxNumberOfMovesToDefeat ){
                 maxNumberOfMovesToDefeat =numOfMovesToDefeat ; 
                 longeststruggle = moveTocheck;
                  }
         }
      }
boardBook.get(currentPos)[whiteOrBlack] = -1*maxNumberOfMovesToDefeat;
return  longeststruggle;
}

Answer 1

你可能想看看Chronicle .它是高度优化的键值存储，应该适合您的目的。

或者你可以自己写存储，但你仍然会在后台做一些像映射和内存映射文件这样的事情。