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

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);
            }
        }
    }

• link