redis存储空间复杂度和时间复杂度的平衡

// 精度范围（raterange）决定了数组大小
raterange = 10000      // 万分位 (0.0001)
raterange = 100000     // 十万分位 (0.00001)
raterange = 1000000    // 百万分位 (0.000001)

raterange = 10000
awardcount = 100
slotsperaward = 100  // 每个奖品100个槽位

内存占用 = 10000 × 4 bytes = 40 kb
✅ 可接受

raterange = 100000
awardcount = 100
slotsperaward = 1000  // 每个奖品1000个槽位

内存占用 = 100000 × 4 bytes = 400 kb
✅ 可接受，但增长明显

raterange = 1000000
awardcount = 100
slotsperaward = 10000  // 每个奖品10000个槽位

内存占用 = 1000000 × 4 bytes = 4 mb
⚠️ 开始需要注意

raterange = 100000
awardcount = 1000
slotsperaward = 100  // 每个奖品100个槽位

内存占用 = 100000 × 4 bytes = 400 kb
✅ 可接受

raterange = 1000000
awardcount = 1000
slotsperaward = 1000  // 每个奖品1000个槽位

内存占用 = 1000000 × 4 bytes = 4 mb
⚠️ 内存占用较大

// 存储随机数到奖品的映射
int[] awardmappingarray = new int[raterange];  // 固定大小数组

// 例如：raterange = 1000000
// 内存 = 1000000 × 4 bytes = 4 mb

// 存储奖品信息和前缀和
list<strategyawardentity> awards = new arraylist<>();  // 奖品列表
double[] prefixsums = new double[awardcount];          // 前缀和数组

// 例如：awardcount = 1000
// 内存 = 1000 × (award对象大小 + 8 bytes) ≈ 100 kb

raterange >> awardcount 时，o(logn) 更节省内存
raterange ≈ awardcount 时，两者内存相近

/**
 * o(1)抽奖算法 - 预热时生成固定大小数组
 * 优点：查询时间o(1)
 * 缺点：内存占用与raterange成正比
 */
public integer rafflestrategyo1(long strategyid, 
        list<strategyawardentity> strategyawardentities) {
    
    // 1. 获取精度范围
    bigdecimal minawardrate = minawardrate(strategyawardentities);
    int raterange = convert(minawardrate);  // 例如：10000, 100000, 1000000
    
    // 2. 分配数组（内存占用 = raterange × 4 bytes）
    int[] strategyawardraterandom = new int[raterange];
    
    // 3. 填充数组
    int currentindex = 0;
    for (strategyawardentity award : strategyawardentities) {
        // 计算该奖品应该占用的槽位数
        int awardslots = (int) (award.getawardrate() * raterange);
        
        // 填充槽位
        for (int i = 0; i < awardslots; i++) {
            if (currentindex >= raterange) break;
            strategyawardawardraterandom[currentindex++] = award.getawardid();
        }
    }
    
    // 4. 随机打乱（消除初始顺序偏差）
    shuffle(strategyawardawardraterandom);
    
    // 5. 抽奖（o(1)时间复杂度）
    int randomindex = threadlocalrandom.current().nextint(raterange);
    return strategyawardawardraterandom[randomindex];
}

/**
 * o(logn)抽奖算法 - 实时计算前缀和
 * 优点：内存占用与awardcount成正比，与raterange无关
 * 缺点：查询时间o(logn)，需要每次计算
 */
public integer rafflestrategylogn(long strategyid, 
        list<strategyawardentity> strategyawardentities) {
    
    // 1. 计算最小精度（用于确定随机数范围）
    bigdecimal minawardrate = minawardrate(strategyawardentities);
    int raterange = convert(minawardrate);  // 例如：100000, 1000000
    
    // 2. 构建前缀和数组（内存占用 = 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. 生成随机数
    int randomvalue = threadlocalrandom.current().nextint(raterange);
    double randomrate = (double) randomvalue / raterange;
    
    // 4. 二分查找（o(logn)时间复杂度）
    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();
}

/**
 * 综合考虑槽位数和内存占用的算法选择
 */
public integer rafflestrategy(long strategyid, 
        list<strategyawardentity> strategyawardentities) {
    
    // 1. 计算精度范围
    bigdecimal minawardrate = minawardrate(strategyawardentities);
    int raterange = convert(minawardrate);  // 10000, 100000, 1000000...
    
    int awardcount = strategyawardentities.size();
    int slotsperaward = raterange / awardcount;
    
    // 2. 计算内存占用
    long o1memorybytes = (long) raterange * 4;  // o(1)数组内存
    long lognmemorybytes = (long) awardcount * 40;  // o(logn)奖品对象内存估算
    
    // 3. 算法选择条件
    // 条件1：槽位数 >= 10（保证公平性）
    // 条件2：内存占用可接受（o(1)算法不超过10mb）
    if (slotsperaward >= 10 && o1memorybytes <= 10 * 1024 * 1024) {
        // 使用o(1)算法
        return rafflestrategyo1(strategyid, strategyawardentities);
    } else {
        // 使用o(logn)算法
        return rafflestrategylogn(strategyid, strategyawardentities);
    }
}

/**
 * 内存优化：如果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压缩存储
 * 例如：[a,a,a,b,b,c,c,c,c] → [(a,3), (b,2), (c,4)]
 */
class compressedarray {
    int[] awardids;     // 奖品id数组（去重后的）
    int[] runlengths;   // 每个奖品连续出现的次数
    
    // 随机抽奖
    public int raffle() {
        // 1. 计算总长度
        int totallength = arrays.stream(runlengths).sum();
        
        // 2. 生成随机位置
        int randomposition = threadlocalrandom.current().nextint(totallength);
        
        // 3. 查找对应的奖品
        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];
    }
}

/**
 * 分级缓存策略：根据访问频率选择不同的存储方式
 */
public class tieredstrategycache {
    
    // 热数据：高频访问的奖品，使用o(1)数组
    private int[] hotawardsarray;
    
    // 冷数据：低频访问的奖品，使用o(logn)列表
    private list<strategyawardentity> coldawardslist;
    
    // 访问统计
    private map<long, atomicinteger> accesscountmap = new concurrenthashmap<>();
    
    // 定期调整热冷数据
    public void rebalance() {
        // 统计访问频率
        map<long, integer> sortedawards = accesscountmap.entryset().stream()
            .sorted(map.entry.comparingbyvalue())
            .limit(100)  // 取访问最多的100个奖品
            .collect(collectors.tomap(
                map.entry::getkey,
                map.entry::getvalue,
                (e1, e2) -> e1,
                linkedhashmap::new
            ));
        
        // 将高频奖品放入热数据
        rebuildhotawardsarray(sortedawards.keyset());
    }
}

/**
 * 懒加载策略：只有首次访问时才加载数据
 */
public class lazystrategycache {
    
    private volatile int[] cachedarray = null;
    private volatile list<strategyawardentity> cachedawards = null;
    
    // 懒加载o(1)数组
    public int[] geto1array(list<strategyawardentity> awards) {
        if (cachedarray == null) {
            synchronized (this) {
                if (cachedarray == null) {
                    // 只在首次访问时计算
                    cachedarray = buildstrategyarray(awards);
                }
            }
        }
        return cachedarray;
    }
    
    // 懒加载o(logn)列表
    public list<strategyawardentity> getawardslist() {
        if (cachedawards == null) {
            synchronized (this) {
                if (cachedawards == null) {
                    cachedawards = loadawardsfromdb();
                }
            }
        }
        return cachedawards;
    }
}