// 精度范圍（rateRange）決定了數(shù)組大小
rateRange = 10000      // 萬(wàn)分位 (0.0001)
rateRange = 100000     // 十萬(wàn)分位 (0.00001)
rateRange = 1000000    // 百萬(wàn)分位 (0.000001)

rateRange = 10000
awardCount = 100
slotsPerAward = 100  // 每個(gè)獎(jiǎng)品100個(gè)槽位

內(nèi)存占用 = 10000 × 4 bytes = 40 KB
? 可接受

rateRange = 100000
awardCount = 100
slotsPerAward = 1000  // 每個(gè)獎(jiǎng)品1000個(gè)槽位

內(nèi)存占用 = 100000 × 4 bytes = 400 KB
? 可接受，但增長(zhǎng)明顯

rateRange = 1000000
awardCount = 100
slotsPerAward = 10000  // 每個(gè)獎(jiǎng)品10000個(gè)槽位

內(nèi)存占用 = 1000000 × 4 bytes = 4 MB
?? 開始需要注意

rateRange = 100000
awardCount = 1000
slotsPerAward = 100  // 每個(gè)獎(jiǎng)品100個(gè)槽位

內(nèi)存占用 = 100000 × 4 bytes = 400 KB
? 可接受

rateRange = 1000000
awardCount = 1000
slotsPerAward = 1000  // 每個(gè)獎(jiǎng)品1000個(gè)槽位

內(nèi)存占用 = 1000000 × 4 bytes = 4 MB
?? 內(nèi)存占用較大

// 存儲(chǔ)隨機(jī)數(shù)到獎(jiǎng)品的映射
int[] awardMappingArray = new int[rateRange];  // 固定大小數(shù)組

// 例如：rateRange = 1000000
// 內(nèi)存 = 1000000 × 4 bytes = 4 MB

// 存儲(chǔ)獎(jiǎng)品信息和前綴和
List<StrategyAwardEntity> awards = new ArrayList<>();  // 獎(jiǎng)品列表
double[] prefixSums = new double[awardCount];          // 前綴和數(shù)組

// 例如：awardCount = 1000
// 內(nèi)存 = 1000 × (award對(duì)象大小 + 8 bytes) ≈ 100 KB

rateRange >> awardCount 時(shí)，O(logn) 更節(jié)省內(nèi)存
rateRange ≈ awardCount 時(shí)，兩者內(nèi)存相近

/**
 * O(1)抽獎(jiǎng)算法 - 預(yù)熱時(shí)生成固定大小數(shù)組
 * 優(yōu)點(diǎn)：查詢時(shí)間O(1)
 * 缺點(diǎn)：內(nèi)存占用與rateRange成正比
 */
public Integer raffleStrategyO1(Long strategyId, 
        List<StrategyAwardEntity> strategyAwardEntities) {
    
    // 1. 獲取精度范圍
    BigDecimal minAwardRate = minAwardRate(strategyAwardEntities);
    int rateRange = convert(minAwardRate);  // 例如：10000, 100000, 1000000
    
    // 2. 分配數(shù)組（內(nèi)存占用 = rateRange × 4 bytes）
    int[] strategyAwardRateRandom = new int[rateRange];
    
    // 3. 填充數(shù)組
    int currentIndex = 0;
    for (StrategyAwardEntity award : strategyAwardEntities) {
        // 計(jì)算該獎(jiǎng)品應(yīng)該占用的槽位數(shù)
        int awardSlots = (int) (award.getAwardRate() * rateRange);
        
        // 填充槽位
        for (int i = 0; i < awardSlots; i++) {
            if (currentIndex >= rateRange) break;
            strategyAwardAwardRateRandom[currentIndex++] = award.getAwardId();
        }
    }
    
    // 4. 隨機(jī)打亂（消除初始順序偏差）
    shuffle(strategyAwardAwardRateRandom);
    
    // 5. 抽獎(jiǎng)（O(1)時(shí)間復(fù)雜度）
    int randomIndex = ThreadLocalRandom.current().nextInt(rateRange);
    return strategyAwardAwardRateRandom[randomIndex];
}

/**
 * O(logn)抽獎(jiǎng)算法 - 實(shí)時(shí)計(jì)算前綴和
 * 優(yōu)點(diǎn)：內(nèi)存占用與awardCount成正比，與rateRange無(wú)關(guān)
 * 缺點(diǎn)：查詢時(shí)間O(logn)，需要每次計(jì)算
 */
public Integer raffleStrategyLogn(Long strategyId, 
        List<StrategyAwardEntity> strategyAwardEntities) {
    
    // 1. 計(jì)算最小精度（用于確定隨機(jī)數(shù)范圍）
    BigDecimal minAwardRate = minAwardRate(strategyAwardEntities);
    int rateRange = convert(minAwardRate);  // 例如：100000, 1000000
    
    // 2. 構(gòu)建前綴和數(shù)組（內(nèi)存占用 = awardCount × 8 bytes）
    double[] awardRates = new double[strategyAwardEntities.size()];
    double[] prefixSums = new double[strategyAwardEntities.size()];
    
    for (int i = 0; i < strategyAwardEntities.size(); i++) {
        StrategyAwardEntity award = strategyAwardEntities.get(i);
        awardRates[i] = award.getAwardRate();
        
        if (i == 0) {
            prefixSums[i] = awardRates[i];
        } else {
            prefixSums[i] = prefixSums[i - 1] + awardRates[i];
        }
    }
    
    // 3. 生成隨機(jī)數(shù)
    int randomValue = ThreadLocalRandom.current().nextInt(rateRange);
    double randomRate = (double) randomValue / rateRange;
    
    // 4. 二分查找（O(logn)時(shí)間復(fù)雜度）
    int left = 0;
    int right = prefixSums.length - 1;
    
    while (left < right) {
        int mid = (left + right) / 2;
        if (prefixSums[mid] < randomRate) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return strategyAwardEntities.get(left).getAwardId();
}

/**
 * 綜合考慮槽位數(shù)和內(nèi)存占用的算法選擇
 */
public Integer raffleStrategy(Long strategyId, 
        List<StrategyAwardEntity> strategyAwardEntities) {
    
    // 1. 計(jì)算精度范圍
    BigDecimal minAwardRate = minAwardRate(strategyAwardEntities);
    int rateRange = convert(minAwardRate);  // 10000, 100000, 1000000...
    
    int awardCount = strategyAwardEntities.size();
    int slotsPerAward = rateRange / awardCount;
    
    // 2. 計(jì)算內(nèi)存占用
    long o1MemoryBytes = (long) rateRange * 4;  // O(1)數(shù)組內(nèi)存
    long lognMemoryBytes = (long) awardCount * 40;  // O(logn)獎(jiǎng)品對(duì)象內(nèi)存估算
    
    // 3. 算法選擇條件
    // 條件1：槽位數(shù) >= 10（保證公平性）
    // 條件2：內(nèi)存占用可接受（O(1)算法不超過(guò)10MB）
    if (slotsPerAward >= 10 && o1MemoryBytes <= 10 * 1024 * 1024) {
        // 使用O(1)算法
        return raffleStrategyO1(strategyId, strategyAwardEntities);
    } else {
        // 使用O(logn)算法
        return raffleStrategyLogn(strategyId, strategyAwardEntities);
    }
}

/**
 * 內(nèi)存優(yōu)化：如果rateRange非常大，使用壓縮算法
 */
public Integer raffleStrategyCompressed(Long strategyId, 
        List<StrategyAwardEntity> strategyAwardEntities) {
    
    BigDecimal minAwardRate = minAwardRate(strategyAwardEntities);
    int rateRange = convert(minAwardRate);
    
    // 如果rateRange > 1000000，使用Run-Length Encoding壓縮
    if (rateRange > 1000000) {
        return raffleStrategyCompressed(strategyId, strategyAwardEntities);
    }
    
    // 正常O(1)算法
    return raffleStrategyO1(strategyId, strategyAwardEntities);
}

/**
 * Run-Length Encoding壓縮存儲(chǔ)
 * 例如：[A,A,A,B,B,C,C,C,C] → [(A,3), (B,2), (C,4)]
 */
class CompressedArray {
    int[] awardIds;     // 獎(jiǎng)品ID數(shù)組（去重后的）
    int[] runLengths;   // 每個(gè)獎(jiǎng)品連續(xù)出現(xiàn)的次數(shù)
    
    // 隨機(jī)抽獎(jiǎng)
    public int raffle() {
        // 1. 計(jì)算總長(zhǎng)度
        int totalLength = Arrays.stream(runLengths).sum();
        
        // 2. 生成隨機(jī)位置
        int randomPosition = ThreadLocalRandom.current().nextInt(totalLength);
        
        // 3. 查找對(duì)應(yīng)的獎(jiǎng)品
        int currentPosition = 0;
        for (int i = 0; i < runLengths.length; i++) {
            currentPosition += runLengths[i];
            if (randomPosition < currentPosition) {
                return awardIds[i];
            }
        }
        
        return awardIds[awardIds.length - 1];
    }
}

/**
 * 分級(jí)緩存策略：根據(jù)訪問(wèn)頻率選擇不同的存儲(chǔ)方式
 */
public class TieredStrategyCache {
    
    // 熱數(shù)據(jù)：高頻訪問(wèn)的獎(jiǎng)品，使用O(1)數(shù)組
    private int[] hotAwardsArray;
    
    // 冷數(shù)據(jù)：低頻訪問(wèn)的獎(jiǎng)品，使用O(logn)列表
    private List<StrategyAwardEntity> coldAwardsList;
    
    // 訪問(wèn)統(tǒng)計(jì)
    private Map<Long, AtomicInteger> accessCountMap = new ConcurrentHashMap<>();
    
    // 定期調(diào)整熱冷數(shù)據(jù)
    public void rebalance() {
        // 統(tǒng)計(jì)訪問(wèn)頻率
        Map<Long, Integer> sortedAwards = accessCountMap.entrySet().stream()
            .sorted(Map.Entry.comparingByValue())
            .limit(100)  // 取訪問(wèn)最多的100個(gè)獎(jiǎng)品
            .collect(Collectors.toMap(
                Map.Entry::getKey,
                Map.Entry::getValue,
                (e1, e2) -> e1,
                LinkedHashMap::new
            ));
        
        // 將高頻獎(jiǎng)品放入熱數(shù)據(jù)
        rebuildHotAwardsArray(sortedAwards.keySet());
    }
}

/**
 * 懶加載策略：只有首次訪問(wèn)時(shí)才加載數(shù)據(jù)
 */
public class LazyStrategyCache {
    
    private volatile int[] cachedArray = null;
    private volatile List<StrategyAwardEntity> cachedAwards = null;
    
    // 懶加載O(1)數(shù)組
    public int[] getO1Array(List<StrategyAwardEntity> awards) {
        if (cachedArray == null) {
            synchronized (this) {
                if (cachedArray == null) {
                    // 只在首次訪問(wèn)時(shí)計(jì)算
                    cachedArray = buildStrategyArray(awards);
                }
            }
        }
        return cachedArray;
    }
    
    // 懶加載O(logn)列表
    public List<StrategyAwardEntity> getAwardsList() {
        if (cachedAwards == null) {
            synchronized (this) {
                if (cachedAwards == null) {
                    cachedAwards = loadAwardsFromDB();
                }
            }
        }
        return cachedAwards;
    }
}