美文网首页
模拟题 08 Knuth 一个公平的洗牌算法

模拟题 08 Knuth 一个公平的洗牌算法

作者: 格林哈 | 来源:发表于2020-11-18 10:45 被阅读0次

    1 公平的洗牌算法

    • 公平的理解

      • n个元素,排列可能性 n!, 公平的洗牌算法 应该等概率给出这n!个结果中的任意一个
      • Knuth 算法公平
        • 对于生成的排列,每一个元素都能等概率地出现在每一个位置
    • 实现

    
    import org.junit.Test;
    import javax.annotation.concurrent.NotThreadSafe;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Random;
    
    /**
     * Knuth class
     *
     * @date 2020-11-18
     */
    @NotThreadSafe
    public class Knuth {
    
    
        public static <T> List<T> knuth(List<T> dest, int toEvict ) {
            if(dest == null  || dest.size() == 0) {
                return null;
            }
            toEvict = Math.min(dest.size(), toEvict);
            Random random = new Random(System.currentTimeMillis());
            for(int i = 0; i < toEvict; i ++) {
                int next = i + random.nextInt(dest.size() - i);
                Collections.swap(dest,i,next);
    //          T t = dest.get(i);
                dest.remove(i);
            }
            return dest;
        }
    
    
        @Test
        public void testKnuth() {
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < 10; i ++ ) {
                list.add(i);
            }
            list = Collections.synchronizedList(list);
            list = knuth(list, 5);
            list.forEach((e)->{ System.out.print( " " + e); });
        }
    }
    
    • 应用场景 eureka服务下线 定时任务
    // AbstractInstanceRegistry
        public void evict(long additionalLeaseMs) {
            logger.debug("Running the evict task");
    
            if (!isLeaseExpirationEnabled()) {
                logger.debug("DS: lease expiration is currently disabled.");
                return;
            }
    
            // We collect first all expired items, to evict them in random order. For large eviction sets,
            // if we do not that, we might wipe out whole apps before self preservation kicks in. By randomizing it,
            // the impact should be evenly distributed across all applications.
            // 获得 所有过期的租约
            List<Lease<InstanceInfo>> expiredLeases = new ArrayList<>();
            for (Entry<String, Map<String, Lease<InstanceInfo>>> groupEntry : registry.entrySet()) {
                Map<String, Lease<InstanceInfo>> leaseMap = groupEntry.getValue();
                if (leaseMap != null) {
                    for (Entry<String, Lease<InstanceInfo>> leaseEntry : leaseMap.entrySet()) {
                        Lease<InstanceInfo> lease = leaseEntry.getValue();
                        if (lease.isExpired(additionalLeaseMs) && lease.getHolder() != null) {
                            expiredLeases.add(lease);
                        }
                    }
                }
            }
    
            // To compensate for GC pauses or drifting local time, we need to use current registry size as a base for
            // 为了补偿GC的暂停或本地时间的漂移,我们需要使用当前注册表大小作为基础
            // triggering self-preservation. Without that we would wipe out full registry.
            // 触发自我保护。否则,我们将清除完整的注册表。
            // 计算 最大允许清理租约数量
            int registrySize = (int) getLocalRegistrySize();
            // renewalPercentThreshold 自我保护阈值 默认 0.85
            int registrySizeThreshold = (int) (registrySize * serverConfig.getRenewalPercentThreshold());
            int evictionLimit = registrySize - registrySizeThreshold;
            //  计算 清理租约数量
            int toEvict = Math.min(expiredLeases.size(), evictionLimit);
            if (toEvict > 0) {
                logger.info("Evicting {} items (expired={}, evictionLimit={})", toEvict, expiredLeases.size(), evictionLimit);
                // 随机剔除过期节点
                // 如果我们不这样做,我们可能会在自我保护开始之前就彻底清除整个应用程序。通过将其随机化,
                // 影响应该均匀地分布在所有应用程序中。
                Random random = new Random(System.currentTimeMillis());
                for (int i = 0; i < toEvict; i++) {
                    // 选择一个随机项目(Knuth随机算法)
                    // Pick a random item (Knuth shuffle algorithm)
                    int next = i + random.nextInt(expiredLeases.size() - i);
                    Collections.swap(expiredLeases, i, next);
                    Lease<InstanceInfo> lease = expiredLeases.get(i);
    
                    String appName = lease.getHolder().getAppName();
                    String id = lease.getHolder().getId();
                    EXPIRED.increment();
                    logger.warn("DS: Registry: expired lease for {}/{}", appName, id);
                    internalCancel(appName, id, false);
                }
            }
        }
    
    

    相关文章

      网友评论

          本文标题:模拟题 08 Knuth 一个公平的洗牌算法

          本文链接:https://www.haomeiwen.com/subject/kloqiktx.html