algorithm - 从n 中选择k

  显示原文与译文双语对照的内容
0 0

我想选择 k 元素均匀随机的可能 n 没有选择相同数量的两倍。 有两种方法可以用于这里。

  1. 列出所有 n 可能性。 洗牌( 你不需要洗牌 n 数字只是其中 k 通过执行第一个 k 费舍尔耶茨的步骤) 。 选择第一个 k 。这里方法需要 O(k) 时间( 假设分配一个大小为 n的数组需要 O(1) 时间) 和 O(n) 空间。 如果 k 相对于 n 而言是很小的,这是个问题。
  2. 存储一组已经查看的元素。 从 [0, n-1] 随机选择一个数字。 元素在集合中,然后选择一个新数字。 这个方法占用 O(k) 空间。 run-time的分析稍微复杂一点。 如果 k = theta(n) run-time O(k*lg(k))=O(n*lg(n)) 是因为收集器 优惠券的问题。 如果 k 相对于 n 小,那么它需要比 O(k) 稍微多一点,因为选择相同的数字的探针( 尽管低) 。 这在空间方面比上面的解决方案好,但在run-time方面更糟糕。

我的问题:

是否有 O(k) 时间,O(k) 空间算法用于所有 kn

时间: 原作者:

0 0

使用 O(1) 哈希表,部分Fisher-Yates方法可以在O ( ) 时间和空间中运行。 诀窍是只在哈希表中存储数组的改变元素。

下面是一个简单的Java示例:


public static int[] getRandomSelection (int k, int n, Random rng) {
 if (k> n) throw new IllegalArgumentException(
"Cannot choose" + k +" elements out of" + n +"."
 );

 HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(2*k);
 int[] output = new int[k];

 for (int i = 0; i <k; i++) {
 int j = i + rng.nextInt(n - i);
 output[i] = (hash.containsKey(j)? hash.remove(j) : j);
 if (j> i) hash.put(j, (hash.containsKey(i)? hash.remove(i) : i));
 }
 return output;
}

这段代码分配一个hashmap的2 × k ( 这应该足以确保哈希表从不重复) 桶存储修改后的元素,就运行部分Fisher-Yates洗牌。

是 Ideone的快速测试;它从三个 30,000次中挑选两个元素,并计算每一对元素的选择次数。 对于一个无偏的无序,每个有序的对应该出现大约 5,000 ( & pm ;100左右) 次,除了两个元素都相等的情况。

原作者:
0 0

你可以使用以下算法( 使用javascript而不是伪代码):


var k = 3;
var n = [1,2,3,4,5,6];

//O(k) iterations
for(var i = 0, tmp; i <k; ++i) {

//Random index O(1)
 var index = Math.floor(Math.random() * (n.length - i));

//Output O(1)
 console.log(n[index]);

//Swap and lookup O(1)
 tmp = n[index];
 n[index] = n[n.length - i - 1];
 n[n.length - i - 1] = tmp;
}

简而言之,将选定的值与最后一个迭代示例中的最后一个项目和下一个迭代示例交换。 假定你的原始设置是完全唯一的。

存储是 O(n), 如果你想以集合的形式检索数字,只需引用来自n的最后一个k 条目。

原作者:
0 0

你的第二个方法平均不需要 θ ( k 日志k ) 时间,它需要大约n/( n-k+1 ) + n/( n-k+2 ) + 。 + n/n操作,小于k( n/( n-k ) )既然你有k项都小于n/( n-k ) 。 对于k <= n/2,平均需要 2 *k 操作。 对于k>/2,你可以选择一个大小为n-k的随机子集,并使用。 这是一个 O(k) 平均时间和空间算法。

...