在包含范围内生成唯一随机数数组
我试图用Apple (iOS)编写一个函数，该函数将生成任意数量在给定的包含范围内的唯一随机数，比如0到10。因此，如果我说我希望在0到10之间有5个唯一的随机数，它将返回一个数组，其中包含7、10、2、3、0或7、10、2、8、0等。
我的这部分工作是：
// Returns an array of unique numbers
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: UInt32) -> [Int] {
var uniqueNumbers = [Int]()
while uniqueNumbers.count < numberOfRandoms {
let randomNumber = Int(arc4random_uniform(maxNum + 1)) + minNum
var found = false
for var index = 0; index < uniqueNumbers.count; ++index {
if uniqueNumbers[index] == randomNumber {
found = true
break
}
}
if found == false {
uniqueNumbers.append(randomNumber)
}
}
return uniqueNumbers
}
print(uniqueRandoms(5, minNum: 0, maxNum: 10))现在，我想增加一个黑名单的能力，在这个范围内，我不想。假设我仍然希望在0到10之间有5个唯一的随机数，但我不希望它包含8。
这个部分会导致一个没完没了的循环(当时的25%+或更多)，我不知道为什么？我现在拥有的是：
var blackListNum = 8
// Returns an array of unique numbers
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: UInt32, checkBlackList: Bool = false) -> [Int] {
var uniqueNumbers = [Int]()
while uniqueNumbers.count < numberOfRandoms {
let randomNumber = Int(arc4random_uniform(maxNum + 1)) + minNum
var found = false
for var index = 0; index < uniqueNumbers.count; ++index {
if checkBlackList == false {
if uniqueNumbers[index] == randomNumber {
found = true
break
}
} else {
if uniqueNumbers[index] == randomNumber || uniqueNumbers[index] == blackListNum {
found = true
break
}
}
}
if found == false {
uniqueNumbers.append(randomNumber)
}
}
return uniqueNumbers
}
print(uniqueRandoms(5, minNum: 0, maxNum: 10, checkBlackList: true))我知道我的功能远没有效率，因为我刚刚开始学习Swift，但是我想让它保持类似于我想要了解它是如何工作的。我不想简单地复制和粘贴别人的更有效的解决方案而不理解它。我刚刚学习了变量、常量、if、while、for等语句和其他基本知识，并希望能做到这一点。
回答 6
Stack Overflow用户
发布于 2015-09-25 02:24:54
你可以用一个集合来存储所有随机数，直到你达到了预期的随机数，这样你的生活就容易多了：
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: UInt32) -> [Int] {
var uniqueNumbers = Set<Int>()
while uniqueNumbers.count < numberOfRandoms {
uniqueNumbers.insert(Int(arc4random_uniform(maxNum + 1)) + minNum)
}
return uniqueNumbers.shuffled()
}
print(uniqueRandoms(numberOfRandoms: 5, minNum: 0, maxNum: 10))
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: UInt32, blackList: Int?) -> [Int] {
var uniqueNumbers = Set<Int>()
while uniqueNumbers.count < numberOfRandoms {
uniqueNumbers.insert(Int(arc4random_uniform(maxNum + 1)) + minNum)
}
if let blackList = blackList {
if uniqueNumbers.contains(blackList) {
while uniqueNumbers.count < numberOfRandoms+1 {
uniqueNumbers.insert(Int(arc4random_uniform(maxNum + 1)) + minNum)
}
uniqueNumbers.remove(blackList)
}
}
return uniqueNumbers.shuffled()
}
uniqueRandoms(numberOfRandoms: 3, minNum: 0, maxNum: 10, blackList: 8) // [0, 10, 7]Stack Overflow用户
发布于 2015-09-25 02:39:27
一种直接的方法是创建一个可以选择的数字数组，然后在选择这些数字时删除它们：
// create an array of 0 through 10
var nums = Array(0...10)
// remove the blacklist number
nums.removeAtIndex(nums.indexOf(8)!)
var randoms = [Int]()
for _ in 1...5 {
let index = Int(arc4random_uniform(UInt32(nums.count)))
randoms.append(nums[index])
nums.removeAtIndex(index)
}这种方法的优点是您只需要在数组中生成尽可能多的随机数。因为您要从每次仍然可用的数字中进行选择，所以您不必检查是否已经有了随机值。
Stack Overflow用户
发布于 2017-09-04 01:20:52
Swift 4.0中的解决方案和性能崩溃
最近，我发现自己需要一个解决这个问题的方法，但没有黑名单，我在这个页面上看到了答案，在this question上也看到了答案，但我担心的是，当可选择的数字集合非常大时，以及在选择大量数字时(例如，在整个库中选择超过50%的数字时)。
所以我尝试了几个解决方案。
第一种是随机选择一个数字的类型，检查这个数字以前是否已经选择过，或者选择另一个数字，或者将它添加到数字列表中。
func randomNumber(between lower: Int, and upper: Int) -> Int {
return Int(arc4random_uniform(UInt32(upper - lower))) + lower
}
func generateRandomUniqueNumbers1(forLowerBound lower: Int, andUpperBound upper:Int, andNumNumbers iterations: Int) -> [Int] {
guard iterations <= (upper - lower) else { return [] }
var numbers: [Int] = []
(0..<iterations).forEach { _ in
var nextNumber: Int
repeat {
nextNumber = randomNumber(between: lower, and: upper)
} while numbers.contains(nextNumber)
numbers.append(nextNumber)
}
return numbers
}第二种解决方案与瓦瓦玛提出的解决方案基本相同。首先加载所有可用数字的数组，随机选择一个，然后从可用数组中删除它，并将其添加到数字数组中。重复你想要的数字。
func generateRandomUniqueNumbers2(forLowerBound lower: Int, andUpperBound upper:Int, andNumNumbers iterations: Int) -> [Int] {
guard iterations <= (upper - lower) else { return [] }
var indices: [Int] = (lower..<upper).sorted()
var numbers: [Int] = []
(0..<iterations).forEach { _ in
let nextNumberIndex = randomNumber(between: 0, and: indices.count)
let nextNumber: Int = indices[nextNumberIndex]
indices.remove(at: nextNumberIndex)
numbers.append(nextNumber)
}
return numbers
}第三种解决方案是对第一种解决方案进行调整，以解决数组在其中查找元素的速度慢这一事实。通过将存储的数字数组更改为一个集合，该操作应该会更快。
func generateRandomUniqueNumbers3(forLowerBound lower: Int, andUpperBound upper:Int, andNumNumbers iterations: Int) -> [Int] {
guard iterations <= (upper - lower) else { return [] }
var numbers: Set<Int> = Set<Int>()
(0..<iterations).forEach { _ in
let beforeCount = numbers.count
repeat {
numbers.insert(randomNumber(between: lower, and: upper))
} while numbers.count == beforeCount
}
return numbers.map{ $0 }
}我很确定解决方案1会陷入困境，比如你有100个号码可供选择，而你想要90个唯一的数字。当你选择第80位号码时，你只有20%的机会选择一个还没有被选中的号码。如果你有5000个数字，而且你仍然想要其中的90%，那么它的比例就很差了。
我认为解决方案2会更好地处理它，但我不确定从一个大数组中删除这么多值会带来什么样的性能。
我不知道解决方案3该怎么做。大概是在中间的某个地方。
我建立了XCTest来衡量这两种算法在不同负载条件下的性能。有2个参数:种群和密度。人口是可以选择的数字总数，密度是我们想要抽取的人口中的百分比(即80的人口意味着从中选择80个数字，而密度为50%意味着我们要从80人口中随机选择40个唯一的数字)。
我对3个不同的种群(5,250和12,500)和密度值(10%，50%和90%)进行了9次测试。根据测试能够完成的速度或速度，我调整了我所执行的测试的迭代次数(从一次到多达2,500次)。
这些结果是：
解决方案1
(Population: 5; Density: 10%; Iterations: 2,500): 0.0056s
(Population: 250; Density: 10%; Iterations: 50) : 0.0046s
(Population: 12,500; Density: 10%; Iterations: 10) : 1.33s
(Population: 5; Density: 50%; Iterations: 2,500): 0.0131s
(Population: 250; Density: 50%; Iterations: 50) : 0.0912s
(Population: 12,500; Density: 50%; Iterations: 1) : 4.09s
(Population: 5; Density: 90%; Iterations: 2,500): 0.0309s
(Population: 250; Density: 90%; Iterations: 10) : 0.0993s
(Population: 12,500; Density: 90%; Iterations: 1) : 23s解决方案2
(Population: 5; Density: 10%; Iterations: 2,500): 0.0184s
(Population: 250; Density: 10%; Iterations: 50) : 0.0086s
(Population: 12,500; Density: 10%; Iterations: 10) : 0.103s
(Population: 5; Density: 50%; Iterations: 2,500): 0.0233s
(Population: 250; Density: 50%; Iterations: 50) : 0.0125s
(Population: 12,500; Density: 50%; Iterations: 1) : 0.0209s
(Population: 5; Density: 90%; Iterations: 2,500): 0.0242s
(Population: 250; Density: 90%; Iterations: 10) : 0.0046s
(Population: 12,500; Density: 90%; Iterations: 1) : 0.0278s解决方案3
(Population: 5; Density: 10%; Iterations: 2,500): 0.00672s
(Population: 250; Density: 10%; Iterations: 50) : 0.0024s
(Population: 12,500; Density: 10%; Iterations: 10) : 0.0148s
(Population: 5; Density: 50%; Iterations: 2,500): 0.0134s
(Population: 250; Density: 50%; Iterations: 50) : 0.00769s
(Population: 12,500; Density: 50%; Iterations: 1) : 0.00789s
(Population: 5; Density: 90%; Iterations: 2,500): 0.0209s
(Population: 250; Density: 90%; Iterations: 10) : 0.00397s
(Population: 12,500; Density: 90%; Iterations: 1) : 0.0163s比较
(Case 1): Solution 1 is fastest; then 3; then 2
(Case 2): Solution 3 is fastest; then 1; then 2
(Case 3): Solution 3 is fastest; then 2; then 3
(Case 4): Solution 1 is fastest; then 3; then 2
(Case 5): Solution 3 is fastest; then 2; then 1
(Case 6): Solution 3 is fastest; then 2; then 1
(Case 7): Solution 3 is fastest; then 2; then 1
(Case 8): Solution 3 is fastest; then 2; then 1
(Case 9): Solution 3 is fastest; then 2; then 1结论
正如我从第一个解决方案中所怀疑的，它确实陷入了大量的人口和高密度的泥潭中。当你没有那么多的人口或者你只选择两个数字的时候，它仍然是非常快速的，但是在这些条件下，所有的解决方案都是非常快速的。即使解决方案1比方案2或方案3能更快地从250个人口中选择25个随机数，实时差异也是相当小的。
但是，需要指出的是，如果您希望从一个非常大的群体中获得很少的唯一数字(即:从12,500人池中获得2个唯一数字)，那么解决方案1是最快的，比解决方案3快77%，而且两者都比解决方案2快几个数量级。对于我的具体情况，这与我几乎所有时候都要做的事情更接近，所以我可能会做出一个特定的函数，使用解决方案1来具体地从大量的数据池中选择两个唯一的数字。
总的来说，解决方案3非常接近于一个全面的最佳算法.但是对于大型数据集，请根据您计划使用它们的目的来考虑这些解决方案中的每一个。
https://stackoverflow.com/questions/32773593
复制相似问题
腾讯云开发者
