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);
}
}
}
网友评论