Shulou(Shulou.com)06/03 Report--

This article focuses on "how to use stack memory search to speed up subsets and algorithms". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to use stack memory search to speed up subsets and algorithms."

The so-called subset sum is to find its subset in an array so that the sum of the subset is equal to a fixed value.

In general, we use recursion plus backtracking to deal with it. The code is as follows (here we can only find a set of conditions that can be met)

Public class SubSet {private List list = new ArrayList (); / / used to store the elements in the subset of the fetch @ Getter private List res = new ArrayList (); / / to get the elements in the array list and public int getSum (List list) {int sum = 0; for (int I = 0 int I)

< list.size();i++) sum += list.get(i); return sum; }public void getSubSet(int[] A, int m, int step) {if (res.size() >

0) {return;} while (step

< A.length) {list.add(A[step]); if (getSum(list) == m) {if (getSum(res) == 0) {res.addAll(list); } } step++; getSubSet(A, m, step); list.remove(list.size() - 1); //回溯执行语句，删除列表最后一个元素 } }public static void main(String[] args) { SubSet test = new SubSet(); int[] A = new int[6]; for(int i = 0;i < 6;i++) { A[i] = i + 1; } test.getSubSet(A, 8, 0); System.out.println(test.getRes()); }} 运行结果 [1, 2, 5] 但是这个算法的时间复杂度非常高，是NP级别的。如果数据量比较大的时候，将很难完成运算。 现在我们用栈和哈希缓存来加速这个算法。主要是缓存计算结果，不用每次都去getSum中把list的和算一遍。其思想主要是记忆化搜索，可以参考本人这篇博客动态规划、回溯、贪心，分治 public class SubSet {private List list = new ArrayList(); //用于存放求取子集中的元素 @Getter private List res = new ArrayList(); private Deque deque = new ArrayDeque(); private Map map = new HashMap(); //求取数组列表中元素和 public int getSum(List list) {int sum = 0; for(int i = 0;i < list.size();i++) sum += list.get(i); return sum; }public void getSubSet(int[] A, int m, int step) {if (res.size() >

0) {return;} while (step

< A.length) {list.add(A[step]); if (!map.containsKey(deque.toString())) {int sum = getSum(list); deque.push(A[step]); map.put(deque.toString(),sum); if (sum == m) {if (getSum(res) == 0) {res.addAll(list); } } }else {int sum = map.get(deque.toString()) + A[step]; deque.push(A[step]); map.put(deque.toString(),sum); if (sum == m) {if (getSum(res) == 0) {res.addAll(list); } } } step++; getSubSet(A, m, step); list.remove(list.size() - 1); //回溯执行语句，删除列表最后一个元素 deque.pop(); } }public static void main(String[] args) { SubSet test = new SubSet(); int[] A = new int[6]; for(int i = 0;i < 6;i++) { A[i] = i + 1; } test.getSubSet(A, 8, 0); System.out.println(test.getRes()); }} 运算结果 [1, 2, 5] 但C#无法满足获取栈的值，只能获取栈的类型，如果我们用遍历的方式去获取栈的值又回到了以前NP级的时间复杂度，故直接使用数字来做哈希表的键。内容如下 using System;using System.Collections.Generic;using System.Collections;using System.Text.RegularExpressions;using System.Linq;using System.Text;using System.Threading.Tasks;namespace ConsoleApplication1{ class Program { private class Oranize { public List array = new List(); public List res = new List(); public Stack stack = new Stack(); public Hashtable table = new Hashtable(); public decimal index = 0; public decimal getSum(List list) { decimal sum = 0; for (int i = 0; i < list.Count; i++) { sum += list[i]; } return sum; } public String stackValue(Stack stack) { StringBuilder sb = new StringBuilder(); foreach (decimal s in stack) { sb.Append(s.ToString()); } return sb.ToString(); } public void org(decimal[] arr,decimal all, int step) { if (res.Count >

0) {return;} while (step

< arr.Length) { array.Add(arr[step]); if (!table.ContainsKey(index.ToString())) { decimal sum = getSum(array); stack.Push(index); table.Add(stack.Peek().ToString(), sum); if (sum == all) { if (getSum(res) == 0) { foreach (decimal a in array) { res.Add(a); } } } } else { decimal sum = 0; if (stack.Count >

0) {sum = Convert.ToDecimal (table [stack.Peek (). ToString ()]) + arr [step];} else {sum = Convert.ToDecimal (table ["0"]) + arr [step] } index++; stack.Push (index); if (table.ContainsKey (stack.Peek (). ToString ()) {table.Remove (stack.Peek (). ToString ()) } table.Add (stack.Peek (). ToString (), sum) If (sum = = all) {if (getSum (res) = = 0) {foreach (decimal an in array) { Res.Add (a) } step++; org (arr, all, step); array.RemoveAt (array.Count-1); stack.Pop () } static void Main (string [] args) {decimal [] A = new decimal [6]; for (int I = 0; I

< 6; i++) { A[i] = i + 1; } Oranize oranize = new Oranize(); oranize.org(A, 8, 0); foreach (decimal r in oranize.res) { Console.Write(r + ","); } Console.ReadLine(); } }} 这里我们可以看到如果使用stackValue来获取栈的各个值的字符串是不可取的，同样会非常慢。 由于C#本身的Hashtable在数据量大的情况下存在溢出风险，所以我们要重写哈希表。重写的哈希表的每个节点由红黑树组成，由于我们并不需要删除哈希表内的元素，所以就不写红黑树和哈希表的删除方法。 private class RedBlackTreeMap { private static bool RED = true; private static bool BLACK = false; private class Node { public String key; public decimal value; public Node left; public Node right; public bool color; public Node(String key,decimal value,Node left,Node right,bool color) { this.key = key; this.value = value; this.left = left; this.right = right; this.color = color; } public Node(String key): this(key, 0, null, null, RED) { } public Node(String key,decimal value): this(key, value, null, null, RED) { } } private Node root; private int size; public ISet keySet = new HashSet(); public RedBlackTreeMap() { root = null; size = 0; } private bool isRed(Node node) { if (node == null) { return BLACK; } return node.color; } private Node leftRotate(Node node) { Node ret = node.right; Node retLeft = ret.left; node.right = retLeft; ret.left = node; ret.color = node.color; node.color = RED; return ret; } private Node rightRotate(Node node) { Node ret = node.left; Node retRight = ret.right; node.left = retRight; ret.right = node; ret.color = node.color; node.color = RED; return ret; } private void flipColors(Node node) { node.color = RED; node.left.color = BLACK; node.right.color = BLACK; } public void add(String key,decimal value) { root = add(root, key, value); keySet.Add(key); } private Node add(Node node,String key,decimal value) { if (node == null) { size++; return new Node(key, value); } if (key.CompareTo(node.key) < 0) { node.left = add(node.left, key, value); }else if (key.CompareTo(node.key) >

0) {node.right = add (node.right, key, value);} else {node.value = value } if (isRed (node.right) & &! isRed (node.left)) {node = leftRotate (node);} if (isRed (node.left) & & isRed (node.left.left)) {node = rightRotate (node) } if (isRed (node.left) & & isRed (node.right)) {flipColors (node);} return node;} public bool contains (String key) {return getNode (root, key)! = null } public decimal get (String key) {Node node = getNode (root, key); return node = = null? 0: node.value;} public void set (String key,decimal value) {Node node = getNode (root, key) If (node = = null) {throw new ArgumentException (key + "does not exist");} node.value = value;} public int getSize () {return size } public bool isEmpty () {return size = = 0;} private Node getNode (Node node,String key) {if (node = = null) {return null } if (key.CompareTo (node.key) = = 0) {return node;} else if (key.CompareTo (node.key))

< 0) { return getNode(node.left, key); }else { return getNode(node.right, key); } } } private class HashFind { private int[] capacity = {53,97,193,389,769,1543,3079,6151,12289,24593, 49157,98317,196613,393241,786433,1572869,3145739, 6291469,12582917,25165843,50331653,100663319, 201326611,402653189,805306457,1610612741}; //容忍度上界 private static int upperTol = 10; //容忍度下届 private static int lowerTol = 2; private int capacityIndex = 0; private RedBlackTreeMap[] tables; private int M; private int size; public HashFind() { this.M = capacity[capacityIndex]; this.size = 0; tables = new RedBlackTreeMap[M]; for (int i = 0; i < M; i++) { tables[i] = new RedBlackTreeMap(); } } private int hash(String key) { return (key.GetHashCode() & 0x7fffffff) % M; } public void add(String key,decimal value) { RedBlackTreeMap map = tables[hash(key)]; if (map.contains(key)) { map.add(key, value); }else { map.add(key, value); size++; if (size >

= upperTol * M & & capacityIndex + 1

< capacity.Length) { capacityIndex++; resize(capacity[capacityIndex]); } } } public bool contains(String key) { int index = hash(key); return tables[index].contains(key); } public decimal get(String key) { int index = hash(key); return tables[index].get(key); } public void set(String key,decimal value) { int index = hash(key); RedBlackTreeMap map = tables[index]; if(!map.contains(key)) { throw new ArgumentException(key + "不存在"); } map.add(key, value); } public int getSize() { return size; } public bool isEmpty() { return size == 0; } private void resize(int newM) { RedBlackTreeMap[] newTables = new RedBlackTreeMap[newM]; for (int i = 0; i < newM; i++) { newTables[i] = new RedBlackTreeMap(); } int oldM = this.M; this.M = newM; for (int i = 0; i < oldM; i++) { RedBlackTreeMap map = tables[i]; foreach (String key in map.keySet) { int index = hash(key); newTables[index].add(key, map.get(key)); } } this.tables = newTables; } } private class Oranize { public List array = new List(); public List res = new List(); public Stack stack = new Stack(); public HashFind table = new HashFind(); public decimal index = 0; public decimal getSum(List list) { decimal sum = 0; for (int i = 0; i < list.Count; i++) { sum += list[i]; } return sum; } //public String stackValue(Stack stack) //{ // StringBuilder sb = new StringBuilder(); // foreach (decimal s in stack) // { // sb.Append(s.ToString()); // } // return sb.ToString(); //} public void org(decimal[] arr, decimal all, int step) { if (res.Count >

0) {return;} while (step

< arr.Length) { array.Add(arr[step]); if (!table.contains(index.ToString())) { decimal sum = getSum(array); stack.Push(index); table.add(stack.Peek().ToString(), sum); if (sum == all) { if (getSum(res) == 0) { foreach (decimal a in array) { res.Add(a); } } } } else { decimal sum = 0; if (stack.Count >

0) {sum = Convert.ToDecimal (table.get (stack.Peek (). ToString () + arr [step];} else {sum = Convert.ToDecimal (table.get ("0")) + arr [step] } index++; stack.Push (index); if (! table.contains (stack.Peek (). ToString () {table.add (stack.Peek (). ToString (), sum) } if (sum = = all) {if (getSum (res) = = 0) {foreach (decimal an in array) {res.Add (a) } step++; org (arr, all, step); array.RemoveAt (array.Count-1); stack.Pop () }

Although the algorithm is accelerated, whether it can be calculated still depends on the number of combinations of the sum of the elements of the array, for example, there are 1, 2, 3, 4, 1, 2, 2, 3, 1, 2, 3, 3, 3, 3, 3, 3, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 4, 4, 3, 4, 3, 4, 3, 4, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4, 3, 4

We can verify it by calculating the combination number algorithm, which is also a way of recursive plus memory search.

Public class Combine {private static Map map= new HashMap (); / * calculates the number of combinations of n elements taken out of m elements * @ param m * @ param n * @ return * / private static long comb (int mline int n) {String key= m + "," + n; if (n = 0) return 1; if (n = 1) return m If (n > m / 2) return comb (mmae mmurn); if (n > 1) {if (! map.containsKey (key)) map.put (key, comb (mmer1)) + comb (mmer1)); return map.get (key);} return-1;} public static void main (String [] args) {long total = 0; for (int I = 1; I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.