游戏开发论坛

 找回密码
 立即注册
搜索
查看: 1976|回复: 5

好久没有过来逛了,发个代码

[复制链接]

187

主题

600

帖子

606

积分

高级会员

Rank: 4

积分
606
QQ
发表于 2006-4-5 23:43:00 | 显示全部楼层 |阅读模式
'从size里面随机挑选num的不重复的选择!
'生成的结果保存在data数组里面,分别对应生成的索引
'比方你想从0-99里面随机抽选出10个不重复的数,对应的调用为:
'Dim data() as Long,i as Long
'RndChoose 100,10,data()
'For i=0 to 9
'    Debug.Print i
'Next
'有没有谁有更好的算法呢?在速度和内存上要兼顾!!!敬请回贴
'By Boywhp

Private Sub RndChoose(size As Long, num As Long, data() As Long)
    Dim i As Long, j As Long, k As Long, l As Long, m As Long
    Debug.Assert size > num
    ReDim data(2 * num - 1)
   
    data(0) = Rnd * size - 0.5
    For i = 1 To num - 1
        j = Rnd * (size - i) - 0.5
        If j < data(0) Then’插入到首位置
            CopyMemory data(num), data(0), i * LenB(data(0))
            CopyMemory data(1), data(num), i * LenB(data(0))
            data(0) = j
        ElseIf j > data(i - 1) Then’插入到末尾
            data(i) = j + i
        Else '计算插入位置
            l = data(0) - 1
            For k = 1 To i - 1
                l = l + data(k) - data(k - 1) - 1
                If l >= j Then
                    m = data(k) + j - l - 1
                    CopyMemory data(num), data(k), (i - k) * LenB(data(0))
                    CopyMemory data(k + 1), data(num), (i - k) * LenB(data(0))
                    data(k) = m
                    Exit For
                End If
            Next
            If l < j Then’插入到末尾
                data(i) = j + i
            End If
        End If
    Next
End Sub

26

主题

537

帖子

537

积分

高级会员

Rank: 4

积分
537
发表于 2006-4-6 09:32:00 | 显示全部楼层

Re:好久没有过来逛了,发个代码

需要那么复杂吗?如果不能用Randomize和rnd直接得到不重复内容,至少可以用以下方法吧。

Private Sub RndChoose(size As Long, num As Long, data() As Long)
Dim Count As Integer
Dim n As Long
Dim b() As Boolean
ReDim b(size - 1)
Count = 0
While Count < num
    n = Int(Rnd * size)
    If b(n) = False Then
        b(n) = True
        data(Count) = n
        Count = Count + 1
    End If
Wend
End Sub

187

主题

600

帖子

606

积分

高级会员

Rank: 4

积分
606
QQ
 楼主| 发表于 2006-4-6 23:24:00 | 显示全部楼层

Re:好久没有过来逛了,发个代码

一般情况下Size远大于num
你这里考虑了size跟num很接近的情况吗?
越到后面产生的随机数越困难哦,因为If b(n) = False Then不成立的情况太多了
下一个朋友继续贴阿!!!上面的方法效率不行

187

主题

600

帖子

606

积分

高级会员

Rank: 4

积分
606
QQ
 楼主| 发表于 2006-4-6 23:27:00 | 显示全部楼层

Re:好久没有过来逛了,发个代码

我的意思是既要效率高 又要对系统资源要求小 哈哈
if size N大 则 “系统崩溃”的方法耗内存
if Size跟num相差很少 则 “系统崩溃”的方法效率不好

15

主题

2093

帖子

2093

积分

金牌会员

Rank: 6Rank: 6

积分
2093
发表于 2006-4-7 00:24:00 | 显示全部楼层

Re:好久没有过来逛了,发个代码

不理解为什么要 i * LenB(data(0))

直接 i*4 就可以了啊

26

主题

537

帖子

537

积分

高级会员

Rank: 4

积分
537
发表于 2006-4-7 10:35:00 | 显示全部楼层

Re:好久没有过来逛了,发个代码

size跟num很接近时,b(n) = False情况太多确实是我没考虑到,考虑再三,改成下面的算法吧。

Private Sub RndChoose(size As Long, num As Long, data() As Long)
Dim Count As Long
Dim n As Long
Dim i As Long
Dim b() As Long
ReDim b(size - 1)
For i = 0 To size - 1
    b(i) = i
Next i
Count = 0
While Count < num
    n = Int(Rnd * (size - 1 - Count))
    data(Count) = b(n)
    List1.AddItem data(Count)
    i = b(size - 1 - Count)
    b(size - 1 - Count) = b(n)
    b(n) = i
    Count = Count + 1
Wend
End Sub

提高效率和资源占用本就是矛盾的,我在意算法主要从提高效率角度出发,如果size大时连临时内存都不肯多分配的话(如移动开发),那么应该从根本上就避免产生从太大范围内产生随机数,比如解决方法可以先分段抽取,再随机排序抽取结果。但这不就是我所感兴趣的了。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作品发布|文章投稿|广告合作|关于本站|游戏开发论坛 ( 闽ICP备17032699号-3 )

GMT+8, 2026-1-24 04:08

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表