daily pastebin goal
5%
SHARE
TWEET

Untitled

a guest Aug 20th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public List<E> getNElements(List<E> list, Integer n) {
  2.     List<E> rtn = null;
  3.  
  4.     if (list != null && n != null && n > 0) {
  5.         int lSize = list.size();
  6.         if (lSize > n) {
  7.             rtn = new ArrayList<E>(n);
  8.             E[] es = (E[]) list.toArray();
  9.             //Knuth-Fisher-Yates shuffle algorithm
  10.             for (int i = es.length - 1; i > es.length - n - 1; i--) {
  11.                 int iRand = rand.nextInt(i + 1);
  12.                 E eRand = es[iRand];
  13.                 es[iRand] = es[i];
  14.                 //This is not necessary here as we do not really need the final shuffle result.
  15.                 //es[i] = eRand;
  16.                 rtn.add(eRand);
  17.             }
  18.  
  19.         } else if (lSize == n) {
  20.             rtn = new ArrayList<E>(n);
  21.             rtn.addAll(list);
  22.         } else {
  23.             log("list.size < nSub! ", lSize, n);
  24.         }
  25.     }
  26.  
  27.     return rtn;
  28. }
  29.    
  30. public List<E> getNElementsBitSet(List<E> list, int n) {
  31.         List<E> rtn = new ArrayList<E>(n);
  32.         int[] ids = genNBitSet(n, 0, list.size());
  33.         for (int i = 0; i < ids.length; i++) {
  34.             rtn.add(list.get(ids[i]));
  35.         }
  36.         return rtn;
  37.     }
  38.    
  39. E[] r = new E[k]; //not really, cannot create an array of generic type, but just pseudo code
  40. int i = 0;
  41. for (E e : list) {
  42.    //assign first k elements:
  43.    if (i < k) { r[i++] = e; continue; }
  44.    //add current element with decreasing probability:
  45.    j = random(i++) + 1; //a number from 1 to i inclusive
  46.    if (j <= k) r[j] = e;
  47. }
  48. return r;
  49.    
  50. for i = 0 to N-1
  51.     if random(N-i) < k
  52.         add item[i] to the result
  53.         k -= 1
  54.     end
  55. end
  56.    
  57. Random r = new Random();
  58. Set<Integer> s = new HashSet<Integer>();
  59. for (int j = m - n; j < m; j++) {
  60.     int t = r.nextInt(j);
  61.     s.add(s.contains(t) ? j : t);
  62. }
  63.    
  64. import java.util.ArrayList;
  65. import java.util.Collections;
  66. import java.util.List;
  67. import java.util.Map;
  68. import java.util.Map.Entry;
  69. import java.util.Random;
  70. import java.util.TreeMap;
  71.  
  72. public class ReservoirSampling
  73. {
  74.     public static void main(String[] args)
  75.     {
  76.         example();
  77.         //test();
  78.     }
  79.  
  80.     private static void test()
  81.     {
  82.         List<String> list = new ArrayList<String>();
  83.         list.add("A");
  84.         list.add("B");
  85.         list.add("C");
  86.         list.add("D");
  87.         list.add("E");
  88.         int size = 2;
  89.  
  90.         int runs = 100000;
  91.         Map<String, Integer> counts = new TreeMap<String, Integer>();
  92.         for (int i=0; i<runs; i++)
  93.         {
  94.             List<String> sample = sample(list, size);
  95.             String s = createString(sample);
  96.             Integer count = counts.get(s);
  97.             if (count == null)
  98.             {
  99.                 count = 0;
  100.             }
  101.             counts.put(s, count+1);
  102.         }
  103.         for (Entry<String, Integer> entry : counts.entrySet())
  104.         {
  105.             System.out.println(entry.getKey()+" : "+entry.getValue());
  106.         }
  107.     }
  108.  
  109.     private static String createString(List<String> list)
  110.     {
  111.         Collections.sort(list);
  112.         StringBuilder sb = new StringBuilder();
  113.         for (String s : list)
  114.         {
  115.             sb.append(s);
  116.         }
  117.         return sb.toString();
  118.     }
  119.  
  120.     private static void example()
  121.     {
  122.         List<String> list = new ArrayList<String>();
  123.         for (int i=0; i<26; i++)
  124.         {
  125.             list.add(String.valueOf((char)('A'+i)));
  126.         }
  127.  
  128.         for (int i=1; i<=26; i++)
  129.         {
  130.             printExample(list, i);
  131.         }
  132.     }
  133.     private static <T> void printExample(List<T> list, int size)
  134.     {
  135.         System.out.printf("%3d elements: "+sample(list, size)+"n", size);
  136.     }
  137.  
  138.     private static final Random random = new Random(0);
  139.     private static <T> List<T> sample(List<T> list, int size)
  140.     {
  141.         List<T> result = new ArrayList<T>(Collections.nCopies(size, (T) null));
  142.         int i = 0;
  143.         for (T element : list)
  144.         {
  145.             if (i < size)
  146.             {
  147.                 result.set(i, element);
  148.                 i++;
  149.                 continue;
  150.             }
  151.             i++;
  152.             int j = random.nextInt(i);
  153.             if (j < size)
  154.             {
  155.                 result.set(j, element);
  156.             }
  157.         }
  158.         return result;
  159.     }
  160.  
  161. }
  162.    
  163. choose random number from 0 to 99, lets say 42, and add it to result.
  164. choose random number from 0 to 98, lets say 39, and add it to result.
  165. choose random number from 0 to 97, lets say 41, but since 41 is bigger or equal than 39, increment it by 1, so you have 42, but that is bigger then equal than 42, so you have 43.
  166. ...
  167.    
  168. public static <T> List<T> getNRandomElements(int n, List<T> list) {
  169.     List<T> subList = new ArrayList<>(n);
  170.     int[] ids = generateUniformBitmap(n, list.size());
  171.     for (int id : ids) {
  172.         subList.add(list.get(id));
  173.     }
  174.     return subList;
  175. }
  176.  
  177. // https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2013/08/14/java/UniformDistinct.java
  178. private static int[] generateUniformBitmap(int num, int max) {
  179.     if (num > max) {
  180.         DebugUtil.e("Can't generate n ints");
  181.     }
  182.     int[] ans = new int[num];
  183.     if (num == max) {
  184.         for (int k = 0; k < num; ++k) {
  185.             ans[k] = k;
  186.         }
  187.         return ans;
  188.     }
  189.     BitSet bs = new BitSet(max);
  190.     int cardinality = 0;
  191.     Random random = new Random();
  192.     while (cardinality < num) {
  193.         int v = random.nextInt(max);
  194.         if (!bs.get(v)) {
  195.             bs.set(v);
  196.             cardinality += 1;
  197.         }
  198.     }
  199.     int pos = 0;
  200.     for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
  201.         ans[pos] = i;
  202.         pos += 1;
  203.     }
  204.     return ans;
  205. }
  206.    
  207. public static <T> List<T> getNRandomShuffledElements(int n, List<T> list) {
  208.     List<T> randomElements = getNRandomElements(n, list);
  209.     Collections.shuffle(randomElements);
  210.     return randomElements;
  211. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top