高分求稀疏算法！ ( 积分: 100 )

Y

yangyang2008

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-14

• #1

从10000个从小到大排列数据中挑选1000个，要求所选数据在10000个数中尽可能均匀分布。
比如：1～10000，挑出来应该是10,20,30……10000。

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-14

• #2

function ShouldGet(Start, Range, Count, TestNum:Integer):Boolean;
var
n,m1,m2:Integer;
begin
Result:=false;
n:=TestNum-Start+1;
if n>Range then
begin
Result:=false;
exit;
end;
m:=n*Count mod Range;
Result:=(m=0);
if Result then
exit;
m2:=(n+1)*Count mod Range;
Result:=(m>m2) and (m2<>0);
//m2比m更加接近0，但不能等于0
end;

用法：
判断1-10000中均匀的取1000个数，20是否应该取： ShouldGet(1,10000,1000,20)
判断1-10中均匀的取3个数，3是否应该取： ShouldGet(1,10,3,3)
在循环中改变最后一个参数，就可以输出整个范围中有哪些数“可取”了。

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-14

• #3

均匀分布具体是指什么？能不能再详细说明一下

 

C

Corn3

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-15

• #4

佩服creation-zy的智慧。
不过我个人感觉只要这样：先算出这1000个数，相邻两数之间的间隔10，然后再从0开始，依次加10上去，10,20,30...。如果间隔不是整数，那么再round一下就可以了。

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-15

• #5

上面给出的函数并不适用于负数的情况，现进行修正：
function ShouldGet(Start, Range, Count, TestNum:LongWord):Boolean;
var
n,m,m2:LongWord;
begin
Result:=(TestNum>=Start) and (Range>0);
if not Result then
exit;
//若测试值小于开始值，或者Range为0，则退出，返回假
n:=TestNum-Start+1;
//规范化，将 TestNum 在 Start..(Start+Range-1) 内 变换为 n 在 1..Range 内
if n>Range then
begin
Result:=false;
exit;
end;
m:=n*Count mod Range;
Result:=(m=0);
//刚好对位的情况：例如： 30*1000 mod 10000 = 0
if Result then
exit;
m2:=(n+1)*Count mod Range;
//获取n之后的数字距离Range整数倍的距离
Result:=(m>m2) and (m2<>0);
//m2比m更加接近0，但不能等于0
end;

 

Y

yangyang2008

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-15

• #6

谢谢 creation-zy。可能是我的问题表述有误。
有10000个数，置于数组a[0..9999]中，数据不一定是整数。两个数据之间的差不是等值，即(a[n]-a[n-1])<>(a[n+1]-a[n])；现在要从中取出1000个数，这1000个数在Min(a[0..9999]和Max(a[0..9999]之间均匀分布。你的方法在连续整数中是可以的，但离散的非整数不行。

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-15

• #7

是这样啊... 这就回到AI_Player兄的问题上来了——什么叫做“均匀”？
比如现在有10个数：1,2,3,4,5,16,17,18,19,20 要从中均匀的取出4个数，怎么取？
4,5,16,20 ?
3,5,17,20 ?
......
如果没有一个规范的判定规则可依赖，恐怕是无法自动给出合理解的——因为不知道什
么是合理。

 

Y

yangyang2008

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-15

• #8

呵呵，就是取出来的数据进行排列后，两两之间的间隔达到最大。比如上题，该取1,5,16,20。

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-15

• #9

还是有问题啊——间隔总是你挤我，我占你的，对于上例： 1,5,16,20 和 1,2,19,20 的
间隔总和都是19，如果是这样的话，只要把两头占住了，中间随机取就是。
ps: 按照最后的说法，原贴中10000个取1000个，就不应该从10开始了，而是1...
我大致知道了楼主的意思，不过好像很难有什么一次成功的高效算法（除非这些数本来分
布就“足够均匀”——即考察任何一个长度为Range/Count的区间，其中都有数可取）。
可能需要考虑用物理模拟的方式来实现——在区间的两头各放一个Node，其中再随机撒剩
下的Node，每个Node之间都有“排斥力”——隔的近的会努力把对方挤开，隔的远的则会被
挤压而靠拢，如此经过若干次的迭代，最后就能得到一个足够“合理”的解，呵呵。[]

 

Y

yangyang2008

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-15

• #10

哈哈，总算明白我想要什么结果了。我原来有个笨思路:把数据从小到大排列，把间隔最小的数据去掉一个，多次循环，得到最终结果。只是效率太低。

 

C

cactus123456

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-16

• #11

我想就是领导来检查的时候,赶紧从一批乱数中抽点好看的数出来给领导看,但又不能太偏离主体,赫赫。从数学上来讲，是个离中趋势的计量，就是样本方差与总体方差尽可能的接近，理论上说，样本应该随机抽取，当样本数据个数很大时，n与n – 1很接近，从而样本方差与总体方差也很接近，如果你真的有10000个数据，取1/10，随机取样和你挑选已经结果是差不多的，你都不用排序，就random（10000）数组下标1000次就可以了，当然重复的抛掉。计算这组的方差。如此重复11次，算出各自方差，然后求平均，离平均值最近的那个样本，就是你要的：）这是有数学依据的，赫赫

 

C

cactus123456

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-16

• #12

如你的开题，1～10000，挑出来应该是10,20,30……10000
1，11，。。。9991也应该是正确的，也就是说样本不一定唯一，
当总体和样本都很大的时候比如1万，10万等等，更不必苛求样本的偏离度，只有更好，没有最好：）
另外，不知道你的数据源是什么，抽样为前应该看看总体的MIN,MAX，防止极值影响样本。
比如
1,2,3,4,5,100000000这样的数据