文档章节

集合的最优子集划分

l
 laolin23
发布于 11/18 10:06
字数 3156
阅读 7
收藏 0

问题描述:如何将一个具有n个元素的集合N划分为k个子集N1…Nk,其中1≤k≤n,使得任意两个子集Ni∩Nj={∅},1<=i,j(i≠j)<=k,且N1∪...∪Nk=N,计算出每个子集的最优结果R1…Rk,使得F(R1…Rk)为最优的结果。

 

这个问题可以分成3步解决:

  1. 求出集合所有子集
  2. 求出所有子集N1…Nk组合
  3. 遍历子集的所有组合,求出最优的F(R1…Rk)值

 

问题一:子集表达

用二进制表达式来表达集合,0代表该位置的元素不存在,1代表该位置的元素存在,其中二进制从右边开始数第n位代表集合从左边开始数第n位,依次类推。

对于集合 {1, 2},表示如下

子集:{ } 没有元素 00

{1}  元素1位于集合中左边开始数第一位,那么用二进制表示就是从右边开始数第一位用1表示, 二进制表示为 01

{2} 元素2位于集合中左边开始数第二位,那么用二进制表示就是从右边开始数第二位用1表示, 二进制表示为 10

{1, 2}  元素1位于集合中左边开始数第一位,那么用二进制表示就是从右边开始数第一位用1表示 ,元素2位于集合中左边开始数第二位,那么用二进制表示就是从右边开始数第二位用1表示, 二进制表示为11  

从上面的规律可以看出子集的表示就是从 0…0 ~ 1…1 的表示,

转为数字就是0~2^n-1

根据子集的数值特点我们就可以定义一个长度为2^n的数组来表示子集的最优结果。数组的下标就是子集的二进制表示。

 

问题二:集合拆分

我们可以使用下面的方式来计算子集组合:

如集合{1,2,3}

当 k=1 时,那么只能划分为{1,2,3}

当 k=2 时,也就是需要划分成两个子集,可以划分为 {1, 2} {3} 或者 {1} {2, 3} 或者 {1, 3} {2}

当 k=3 时,需要划分成3个子集,{1} {2} {3}

注:其中1<=k<=n,当k=1或者k=n时,子集的划分都只有一种情况

其实每加一个元素,就是在原来的划分情况为新元素找到合适的位置放进去。

例如对于集合{1,2,3},现在我们加入第4个元素,值为4,那么应该怎么弄呢?

当 k = 1 时,我们只能找到{1,2,3}划分为1个子集的情况,然后将元素4插进去,得 {1,2,3,4}

当 k = 2时,我们有两种情况可以组成:

①找到{1,2,3}划分为k-1=1个元素的子集组合{1,2,3},然后元素4子集作为一个子集,即{1,2,3} {4}

②找到{1,2,3}划分为k=2个元素的子集组合, {1, 2} {3} 或者 {1} {2, 3} 或者 {1, 3} {2},然后逐个子集插入元素4,形成新的组合

对于{1,2} {3}   将元素4插入{1,2} => {1,2,4} {3}, 将元素插入{3} => {1,2} {3,4}

对于{1} {2,3}   将元素插入{1} => {1,4} {2,3} , 将元素插入{2,3} => {1} {2,3,4}

对于{1,3} {2} 将元素插入{1,3} => {1,3,4} {2},将元素插入{2} => {1,3} {2, 4}

当 k = 3时,步骤跟k=2时一样

当 k = 4时,步骤跟k=2时的①一样,由于{1,2,3}最多只有3个元素,所以步骤②不存在

设F(n, m)表示将一个各数为n的集合拆分成有m个子集表示的情况,其中1≤m≤n,

可以推导出F(n, m) = F(n-1, m-1) + m * F(n-1,m)

其中:F(n, 1) = 1, F(n, n) = 1

那么

 

问题三:求最优结果

自行定义F的计算方法即可。

 

下面是一个实现例子。

1、Strategy<T, R>

/**
 * 策略接口,该接口主要从集合中获取策略算法结果,T为元素类型,R为结果类型
 *
 * @param <T>
 * @param <R>
 */
public interface Strategy<T, R> {
	
	/**获取平均值**/
	Strategy<Integer, Integer> AVG = (datas) -> (int)datas.stream().mapToInt(e -> (e != null ? e.intValue() : 0)).average().getAsDouble();
	
	/**求最大值**/
	Strategy<Integer, Integer> MAX = (datas) -> datas.stream().max((e1, e2) -> e1.compareTo(e2)).get();
	
	/**
	 * 策略器的唯一ID表示,用于判断是否为相同的策略器
	 * @return
	 */
	default String getId() {
		return Integer.toBinaryString(this.hashCode());
	}
	
	/**
	 * 这里给定一个集合datas,计算该集合的策略值并返回
	 * @param datas
	 * @return
	 */
	R get(Collection<T> datas);
	
}

2、StrategyNode<T, R>

/**
 * 策略节点
 *
 * @param <T> 原始的数据来源类型
 * @param <R> 为该节点所有策略器Strategy返回的结果类型
 */
public class StrategyNode<T, R> {
	
	final T value;//集合中的原始元素
	
	final Set<Strategy<T, R>> strategies = new HashSet<>();//元素拥有的策略
	
	public StrategyNode(T value, Strategy<T, R>[] strategies) {
		Objects.requireNonNull(value);
		this.value = value;
		if (strategies != null && strategies.length > 0) {
			for (Strategy<T, R> st : strategies) {
				this.strategies.add(st);
			}
		}
	}
	
	/**
	 * 判断集合中元素是否满足某种策略,通过策略Id匹配
	 * @param strategy
	 * @return
	 */
	public boolean existStrategy(Strategy<T, R> strategy) {
		if (strategy != null && !this.strategies.isEmpty()) {
			for (Strategy<T, R> s : this.strategies) {
				if (s.getId().equals(strategy.getId())) {
					return true;
				}
			}
		}
		return false;
	}

}

3、StrategySelector<S extends Strategy<T, R>, T, R>

/**
 * 策略选择,从所有策略中选择最优的策略
 * @param <S>
 * @param <T>
 * @param <R>
 */
interface StrategySelector<S extends Strategy<T, R>, T, R> {

	/****/
	StrategySelector<Strategy<Integer, Integer>, Integer, Integer> MAX = (strategies, values) -> {
		Set<Strategy<Integer, Integer>> rtSet = new HashSet<>();
		Number rt = null;
		for (Strategy<Integer, Integer> st : strategies) {
			Integer r = st.get(values);
			if (r != null && (rt == null || r.intValue() >= rt.intValue())) {
				if (!r.equals(rt)) {
					rtSet.clear();
				}
				rt = r;
				rtSet.add(st);
			}
		}
		return rtSet;
	};

	/**
	 * 返回最优策略,如果有多个,返回多个
	 * 
	 * 给定集合values,并且共有的策略strategies,从strategies取出使得结果最优的strategies集合并返回
	 * 
	 * @param strategies 策略
	 * @param values 集合
	 * @return
	 */
	Set<S> get(Set<S> strategies, Collection<T> values);

}

4、StrategyCalculate<R, K>

/**
 * 对子集组合进行运算
 *
 * @param <R> 子集策略结果的集合元素
 * @param <K> 子集计算后得到的数据类型
 */
interface StrategyCalculate<R, K> {

	StrategyCalculate<Integer, Integer> SUM = (datas) -> datas.stream().mapToInt(e -> e != null ? e.intValue() : 0).sum();

	StrategyCalculate<Integer, Integer> AVG = (datas) -> (int) datas.stream().mapToDouble(e -> e != null ? e.doubleValue() : 0.0D).average().getAsDouble();

	StrategyCalculate<Integer, Integer> MAX = (datas) -> datas.stream().max((e1, e2) -> e1.compareTo(e2)).get();

	/**
	 * 获取最优答案
	 * 
	 * R 为集合N 通过 StrategySelector 选择最优的策略 Strategy 所计算出的值
	 * 这里是对每个子集的最优策略结果进行合并运算
	 * 
	 * @return
	 */
	K get(Collection<R> datas);

}

5、StrategyComparator<K>

/**
 * 组合结果比较器
 * @param <R>
 */
interface StrategyComparator<K> {
	
	StrategyComparator<Integer> GREAT = (r1, r2) -> r1.compareTo(r2) >= 0;
	
	/**
	 * K 为 StrategyCalculate 计算出的结果,这里对结果进行比较取优
	 * 判断k1 是否优于 k2
	 * @param k1
	 * @param k2
	 * @return
	 */
	boolean better(K k1, K k2);
	
}

6、SubSet<T, R>

/**
 * 表示子集
 *
 * @param <T>
 * @param <R>
 */
public class SubSet<T, R> {
	
	/**子集元素**/
	private List<T> elements;
	
	/**子集使用的策略算法**/
	private Set<Strategy<T, R>> strategies;
	
	/**子集的策略计算结果**/
	private R result;
	
	public SubSet(List<T> elements, Set<Strategy<T, R>> strategies, R result) {
		this.elements = elements;
		this.strategies = strategies;
		this.result = result;
	}

	public List<T> getElements() {
		return elements;
	}

	public void setElements(List<T> elements) {
		this.elements = elements;
	}

	public Set<Strategy<T, R>> getStrategies() {
		return strategies;
	}

	public void setStrategies(Set<Strategy<T, R>> strategies) {
		this.strategies = strategies;
	}

	public R getResult() {
		return result;
	}

	public void setResult(R result) {
		this.result = result;
	}
	
	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		builder.append("{");
		if (this.elements != null && !this.elements.isEmpty()) {
			for (int i = 0, len = this.elements.size(); i < len; ++i) {
				if (i != 0) {
					builder.append(", ");
				}
				builder.append(String.valueOf(this.elements.get(i)));
			}
		}
		builder.append("} = ").append(String.valueOf(this.result));
		return builder.toString();
	}

}

7、Plan<T, R, K>

/**
 * 表示子集的一种组合方案
 *
 * @param <T>
 * @param <R>
 * @param <K>
 */
public class Plan<T, R, K> {
	
	/**子集组合**/
	private List<SubSet<T, R>> subSets;
	
	/**子集组合的计算结果**/
	private K result;
	
	public Plan(List<SubSet<T, R>> subSets, K result) {
		this.subSets = subSets;
		this.result = result;
	}

	public List<SubSet<T, R>> getSubSets() {
		return subSets;
	}

	public void setSubSets(List<SubSet<T, R>> subSets) {
		this.subSets = subSets;
	}

	public K getResult() {
		return result;
	}

	public void setResult(K result) {
		this.result = result;
	}
	
	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		builder.append("[");
		if (this.subSets != null && !this.subSets.isEmpty()) {
			for (int i = 0, len = this.subSets.size(); i < len; ++i) {
				if (i != 0) {
					builder.append(", ");
				}
				builder.append(String.valueOf(this.subSets.get(i)));
			}
		}
		builder.append("] = ").append(String.valueOf(this.result));
		return builder.toString();
	}
	
}

8、Answer<T, R, K>

/**
 * 最优答案的组合
 *
 * @param <T>
 * @param <R>
 * @param <K>
 */
public class Answer<T, R, K> {
	
	/**最优结果**/
	private K result;
	
	/**最优的方案集合**/
	private List<Plan<T, R, K>> plans;
	
	public Answer(List<Plan<T, R, K>> plans, K result) {
		this.plans = plans;
		this.result = result;
	}

	public K getResult() {
		return result;
	}

	public void setResult(K result) {
		this.result = result;
	}

	public List<Plan<T, R, K>> getPlans() {
		return plans;
	}

	public void setPlans(List<Plan<T, R, K>> plans) {
		this.plans = plans;
	}
	
	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();
		builder.append("最优值:").append(String.valueOf(this.result)).append("\n");
		builder.append("最优方案个数:").append(this.plans == null ? 0 : this.plans.size()).append("\n");
		if (this.plans != null && !this.plans.isEmpty()) {
			this.plans.forEach(e -> builder.append(String.valueOf(e)));
		}
		return builder.toString();
	}
	
}

9、

/**
 * 集合划分求最优的算法构造器
 *
 * @param <N>
 * @param <T>
 * @param <R>
 * @param <K>
 */
public class SetSplitBuilder<N extends StrategyNode<T, R>, T, R, K> {
	
	static Logger logger = Logger.getLogger(SetSplitBuilder.class.getName());
	
	private static final Map<Integer, List<int[]>> cache = new HashMap<>();//子集组合缓存
	
	private static final int cache_size = 10;
	
	static {
		initCache();
	}
	
	private static void initCache() {
		for (int i = 1; i <= cache_size; ++i) {
			List<int[]> rows = new ArrayList<>(s(i));
			initCache(0, i, new int[0], rows);
			cache.put(i, rows);
		}
	}
	
	private static void initCache(int idx, int len, int[] subs, List<int[]> combs) {
		if (idx < len) {
			for (int j = 0; j < subs.length; ++j) {
				int[] newSubs = Arrays.copyOf(subs, subs.length);
				newSubs[j] = newSubs[j] | (1 << idx);
				initCache(idx + 1, len, newSubs, combs);
			}
			int[] newSubs = Arrays.copyOf(subs, subs.length + 1);
			newSubs[subs.length] = (1 << idx);
			initCache(idx + 1, len, newSubs, combs);
		} else {
			combs.add(Arrays.copyOf(subs, subs.length));
		}
	}
	
	/**
	 * n个元素的集合有多少种划分方法
	 * @param n
	 * @return
	 */
	private static int s(int n) {
		int sum = 0;
		for (int i = 1; i <= n; ++i) {
			sum += f(n, i);
		}
		return sum;
	}
	
	/**
	 * n个元素的集合划分成m个子集的个数
	 * @param n
	 * @param m
	 * @return
	 */
	private static int f(int n, int m) {
		if (m == 1 || n == m) {
			return 1;
		}
		
		int[][] mt = new int[n + 1][m + 1];
		for (int i = 0; i < mt.length; ++i) {
			mt[i][1] = 1;
		}
		for (int i = 1; i <= m; ++i) {
			mt[m][m] = 1;
		}
		
		for (int i = 2; i <= n; ++i) {
			for (int j = 2; j <= m; ++j) {
				mt[i][j] = mt[i - 1][j - 1] + mt[i - 1][j] * j;
			}
		}
		
		return mt[n][m];
	}
	
	private N[] values; 
	
	private Object[] subsetResults;//每个子集的最优结果
	
	private Object[] subsetResultStrategies;//每个子集对应的最优策略,可以有多个,用set表示
	
	private StrategySelector<Strategy<T, R>, T, R> strategySelector;
	
	private StrategyCalculate<R, K> strategyCalculate;
	
	private StrategyComparator<K> strategyComparator;
	
	private K result;
	
	private List<int[]> optimalSubsetCombs = new ArrayList<>();//子集最优组合
	
	List<Plan<T, R, K>> plans;
	
	public SetSplitBuilder(N[] values, StrategySelector<Strategy<T, R>, T, R> strategySelector, StrategyCalculate<R, K> strategyCalculate, StrategyComparator<K> strategyComparator) {
		Objects.requireNonNull(values);
		Objects.requireNonNull(strategySelector);
		Objects.requireNonNull(strategyCalculate);
		Objects.requireNonNull(strategyComparator);
		this.values = values;
		this.strategySelector = strategySelector;
		this.strategyCalculate = strategyCalculate;
		this.strategyComparator = strategyComparator;
	}

	public void setValues(N[] values) {
		Objects.requireNonNull(values);
		this.values = values;
	}

	public void setStrategySelector(StrategySelector<Strategy<T, R>, T, R> strategySelector) {
		Objects.requireNonNull(strategySelector);
		this.strategySelector = strategySelector;
	}

	public void setStrategyCalculate(StrategyCalculate<R, K> strategyCalculate) {
		Objects.requireNonNull(strategyCalculate);
		this.strategyCalculate = strategyCalculate;
	}

	public void setStrategyComparator(StrategyComparator<K> strategyComparator) {
		Objects.requireNonNull(strategyComparator);
		this.strategyComparator = strategyComparator;
	}
	
	/**
	 * 计算结果
	 */
	public void build() {
		logger.info("子集初始化开始----->");
		initSubsetResults();
		logger.info("子集初始化结束----->");
		
		logger.info("计算最优路径开始----->");
		calculate();
		logger.info("计算最优路径结束----->");
		
		logger.info("组装结果开始----->");
		packageResult();
		logger.info("组装结果结束----->");
	}
	
	public Answer<T, R, K> getAnswer() {
		return new Answer<>(this.plans, this.result);
	}
	
	/**
	 * 计算每个子集的最优策略
	 */
	private void initSubsetResults() {
		int len = 2 << this.values.length;
		this.subsetResults = new Object[len];
		this.subsetResultStrategies = new Object[len];
		
		for (int i = 0; i < len; ++i) {
			//int sub = i;//子集组合
			List<N> subNodes = new ArrayList<>(this.values.length);
			for (int j = 0; j < this.values.length; ++j) {
				if (((i >> j) & 1) == 1) {
					subNodes.add(this.values[j]);
				}
			}
			
			//获取最少的策略算法
			Set<Strategy<T, R>> nodesStrategies = null;
			for (N n : subNodes) {
				if (nodesStrategies == null || n.strategies.size() < nodesStrategies.size()) {
					nodesStrategies = n.strategies;
				}
			}
			
			//满足子集的策略
			Set<Strategy<T, R>> satisfiedStrategy = new HashSet<>();
			if (nodesStrategies != null && !nodesStrategies.isEmpty()) {
				boolean flag = true;
				for (Strategy<T, R> s : nodesStrategies) {
					for (N n : subNodes) {
						if (!n.existStrategy(s)) {
							flag = false;
							break;
						}
					}
					if (flag) {
						satisfiedStrategy.add(s);
					}
				}
			}
			
			//获取子集最优的策略集合
			Set<Strategy<T, R>> r = null;
			if (!satisfiedStrategy.isEmpty()) {
				r = this.strategySelector.get(satisfiedStrategy, subNodes.stream().map(e -> e.value).collect(Collectors.toList()));
			}
			this.subsetResults[i] = r != null && !r.isEmpty() ? r.iterator().next().get(subNodes.stream().map(e -> e.value).collect(Collectors.toList())) : null;
			this.subsetResultStrategies[i] = r;
		}
	}
	
	/**
	 * 计算最优路径
	 */
	private void calculate() {
		List<int[]> rows = cache.get(this.values.length);
		if (rows != null) {
			calculateByCache(rows);
		} else {
			calculate(0, this.values.length, new int[0]);
		}
	}
	
	private void calculateByCache(List<int[]> rows) {
		for (int[] subs : rows) {
			cacheCurrentOptimalResults(subs);
		}
	}
	
	private void calculate(int idx, int len, int[] subs) {
		if (idx < len) {
			for (int j = 0; j < subs.length; ++j) {
				int[] newSubs = Arrays.copyOf(subs, subs.length);
				newSubs[j] = newSubs[j] | (1 << idx);
				calculate(idx + 1, len, newSubs);
			}
			int[] newSubs = Arrays.copyOf(subs, subs.length + 1);
			newSubs[subs.length] = (1 << idx);
			calculate(idx + 1, len, newSubs);
		} else {
			cacheCurrentOptimalResults(subs);
		}
	}
	
	/**
	 * subs 为子集的组合结果
	 * 缓存当前最优结果
	 */
	@SuppressWarnings("unchecked")
	private void cacheCurrentOptimalResults(int[] subs) {
		//记录每个集合的策略结果
		List<R> datas = new ArrayList<>();
		for (Integer st : subs) {
			if (st != null) {
				R r = (R)this.subsetResults[st.intValue()];
				if (r != null) {
					datas.add(r);
				}
			}
		}
		
		K rt = this.strategyCalculate.get(datas);//获取子集计算结果
		if (this.result == null || this.strategyComparator.better(rt, this.result)) {
			if (!rt.equals(this.result)) {
				this.optimalSubsetCombs.clear();
			}
			this.optimalSubsetCombs.add(subs);
			this.result = rt;
		}
	}
	
	/**
	 * 组装结果
	 */
	@SuppressWarnings("unchecked")
	private void packageResult() {
		this.plans = new ArrayList<>(this.optimalSubsetCombs.size());
		for (int[] rows : this.optimalSubsetCombs) {
			List<SubSet<T, R>> subsets = new ArrayList<>(rows.length);
			for (int sub : rows) {
				subsets.add(new SubSet<T, R>(getSubSetValues(sub), (Set<Strategy<T, R>>)this.subsetResultStrategies[sub], (R)this.subsetResults[sub]));
			}
			this.plans.add(new Plan<T, R, K>(subsets, this.result));
		}
	}
	
	/**
	 * 获取子集中的元素集合
	 * @param sub
	 * @return
	 */
	private List<T> getSubSetValues(int sub) {
		List<T> values = new ArrayList<>();
		for (int i = 0; i < this.values.length; ++i) {
			if ((sub & (1 << i)) != 0) {
				values.add(this.values[i].value);
			}
		}
		return values;
	}
	
	
}

10、测试

public class Test {
	
	public static void main(String[] args) {
		
		for (int l = 1; l <= 10; ++l) {
			StrategyNode<Integer, Integer>[] nodes = new StrategyNode[l];
			for (int i = 0; i < nodes.length; ++i) {
				nodes[i] = new StrategyNode<Integer, Integer>(i + 1, Arrays.asList(Strategy.AVG, Strategy.MAX, Strategy.AVG, Strategy.MAX, Strategy.AVG, Strategy.MAX, Strategy.AVG, Strategy.MAX).toArray(new Strategy[0]));
			}
			SetSplitBuilder<StrategyNode<Integer,Integer>,Integer,Integer,Integer> strategyBuilder = 
					new SetSplitBuilder<>(nodes, StrategySelector.MAX, StrategyCalculate.AVG, StrategyComparator.GREAT);
			strategyBuilder.build();
			Answer<Integer,Integer,Integer> answer = strategyBuilder.getAnswer();
			System.out.println(answer.toString());
		}
		
	}

}

 

© 著作权归作者所有

共有 人打赏支持
l
粉丝 0
博文 23
码字总数 19178
作品 0
广州
程序员
私信 提问
【XSY2701】异或图 线性基 容斥原理

题目描述   定义两个图 与 的异或图为一个图 ,其中图 的每条边在 与 中出现次数和为 。   给你 个图,问你这 个图组成的集合有多少个子集的异或图为一个连通图。    题解   考虑枚举...

ez_yww
01/23
0
0
【理论】离散数学中的二元关系

这篇文章将了解到以下方面的知识 01 二元关系的定义 02 笛卡尔积定义 03 二元关系的表示方式 0301 二元关系是笛卡尔积的子集 0302 等价关系与集合上的划分一一对应 二元关系定义 由两个元素x...

needrunning
2017/12/14
0
0
bzoj4671: 异或图【容斥原理+线性基】

解题思路: 考虑容斥,枚举点的集合划分,强制两两集合间的点不连通,集合内的点任意连,若划分成m个集合,则最后至少有m个连通块。 而一个m的划分,在容斥时会被计算 次( 为第二类斯特林数)...

cdsszjj
01/07
0
0
算法|决策树算法究竟说的是什么?

作者简介 浩彬老撕,R语言中文社区特邀作者。 个人公众号:探数寻理 决策树算法概述

kmd8d5r
05/10
0
0
机器学习 西瓜书 Day14 特征选择与稀疏学习

p247 - p266 哈哈哈感觉今天看书的状态不错 看来有希望把欠的两天都补上呀 不多说了进入第11章 第11章 特征选择与稀疏学习 11.1 子集搜索与评价 从给定的特征集合中选择相关特征子集的过程,...

皇家马德里主教练齐达内
05/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周三乱弹 —— 有一天考拉麻麻拉肚子了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @瘟神灬念 :分享周汇洋的单曲《Man Srae(曼斯拉之舞)》:美滋滋。。。。 手机党少年们想听歌,请使劲儿戳(这里) 我听了一下 赶紧关了, ...

小小编辑
今天
44
5
oh-my-zsh 自定义

GitHub 地址 基于 oh-my-zsh 的自定义配置,增加了一些个人常用插件与皮肤。 采用的是 git submodule 来维护,包括 oh-my-zsh,之所以这么搞,主要是手头有多台 linux 需要维护, 每台机器、...

郁也风
今天
6
0
Docker安装踩坑:E_FAIL 0x80004005的解决

参考 菜鸟教程--Windows Docker 安装 http://www.runoob.com/docker/windows-docker-install.html 官方文档-Install Docker Toolbox on Windows https://docs.docker.com/toolbox/toolbox_in......

karma123
今天
6
0
js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
18
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部