N个数中取走一个，如何知道取走的是哪个
本帖最后由 大绯狼 于 2010-6-26 15:45 编辑假设有N个数（N>1），随机从中取走一个，问如何知道取走的数是哪个，为了体现算法的优劣，请大家尽量把这个N设大。
由於希望這個程序具有通用性，現在暫定N=16 777 216（數組限制。。。。如果能用別的方法設置更多當然最好），隨機數為任意（絕對值應儘量大）。
請給出得出結果所需時間，當然，儘量少佔用內存會更好。
测试平台:E7400 4G au3版本3.3.5.6 win7 32BIT
测试结果：
水木子（2樓）：
1千万個數用时：90767
16 777 216個數未通过 内存溢出
3mile(12樓):
1千萬位用時：82788
16 777 216個數同樣杯具了，生成完A.TXT的時候使用778MB，生成B.TXT的時候內存溢出。
異或（13樓）：
1千万位用时：54768
16 777 216個數用時:93042 內存使用431MB 本帖最后由 水木子 于 2010-6-25 18:15 编辑
如果全是十进制数倒比较简单！
也可能是我没理解大虾出题的意思，管他的，重在参与吧！#include <Array.au3>
Local $avArray ;一万个数
For $i = 0 To UBound($avArray) - 1
$avArray[$i] = Random(1, 100, 1)
Next
$iStringa = _ArrayToString($avArray, '+')
;_ArrayDisplay($avArray, '原数组') ;原数组
_ArrayDelete($avArray, Random(0, UBound($avArray) - 1, 1)) ;从数组中随机删除一个元素
;_ArrayDisplay($avArray, '新数组') ;删除某元素后得到的新数组
$iStringb = _ArrayToString($avArray, '+')
MsgBox(0, '计算结果:', '刚刚被删除的数是' & Execute($iStringa) - Execute($iStringb)) 楼上思路太漂亮了。
计算总和！佩服 设
原数组为 arry1
取走一个的 为 arry2
取走的数 = sum （arry1）-sum（arry2）
对autoit 不是很熟，不知道这样行不行？
btw, 这样对 非 十进制的也有效吧。 不过只能对取走一个数的有效。 本帖最后由 大绯狼 于 2010-6-26 12:04 编辑
回复 1# 大绯狼
程序結構非常不錯，不過這個加減法運算效率不夠好，如果涉及到更多數字的話（比如1億個），效率就大打折扣了。
另：請給出可以計算下所需時間。 回复 5# 大绯狼
正如大侠所说，这样确实不好，正在寻思更好的方法。
1楼代码计算时间：2.601 需要具体问题具体分析，随机是数是否可以存在重复问题？
如里按问题里面生成一个N=16 777 216数据，试着将16 777 216随机填充完数据（可以重复数据）需要多长时间？如不重复需要多长时间？然后在数组再取数？
如果只是需要取随数，那么实时生成就可以了 RtlCompareMemory可以返回相同的字节的数量。
String1 = abcdefghi
String2 = abcdefgi
返回结果等于7，说明删除了原本在第(7÷1)+1位上的值。
KMP算法：http://matrix-67.spaces.live.com/blog/cns!420B543611BA4E21!672.entry 回复 8# pusofalse
PUSOFALSE老大這個欠妥啊
由於數不是連續的 僅知道刪除數的位置也是沒有辦法知道刪除數的值的。 我很傻很天真
#Include <date.au3>
$t1 = StringReplace(_NowTime(), ":", "")
$file1 = FileOpen("1.txt", 1)
If $file1 = -1 Then
Exit
EndIf
For $i = 1 To 10000
FileWriteLine($file1, $i)
Next
FileClose($file1)
$file2 = FileOpen("2.txt", 1)
If $file2 = -1 Then
Exit
EndIf
For $i = 1 To 10000
if $i = 999 then
else
FileWriteLine($file2, $i)
endif
Next
FileClose($file2)
$file3 = FileOpen("1.txt", 0)
$file4 = FileOpen("2.txt", 0)
If $file3 = -1 or $file4 = -1 Then
Exit
EndIf
While 1
$line3 = FileReadLine($file3)
$line4 = FileReadLine($file4)
If @error = -1 Then ExitLoop
if $line3 <> $line4 then
$line5 = $line3
$line3 = FileReadLine($file3)
endif
Wend
$t2 = StringReplace(_NowTime(), ":", "")
$t3 = $t2 - $t1
msgbox(0,"用时:" & $t3 & "秒","差异：" &$line5)
FileClose($file3)
FileClose($file4) 回复 10# xsjtxy
请使用随机数测试下 1千万个数，最好能给出时间。 来个另类的笨办法。#include <Array.au3>
Local $avArray ;一万个数
$begin = TimerInit()
For $i = 0 To UBound($avArray) - 1
$avArray[$i] = Random(1, 100, 1)
Next
$iStringa = _ArrayToString($avArray, @CRLF)
FileWrite("a.txt",$iStringa)
_ArrayDelete($avArray, Random(0, UBound($avArray) - 1, 1)) ;从数组中随机删除一个元素
$iStringb = _ArrayToString($avArray, @CRLF)
FileWrite("b.txt",$iStringb)
RunWait(@ComSpec & " /c " & "fc a.txt b.txt /a >1.txt",@ScriptDir,@SW_HIDE)
$aa=FileReadLine("1.txt",3)
If Not @error Then
FileDelete("a.txt")
FileDelete("b.txt")
FileDelete("1.txt")
EndIf
MsgBox(0,"用时"&TimerDiff($begin),$aa) 本帖最后由 大绯狼 于 2010-6-26 15:46 编辑
考慮到大家說的進制問題，參照水木子的代碼進行了改進，使用異或，這樣就不管什麽進制進制，浮點數，都能夠進行運算。因为是在位级别上操作，无论是整数还是浮点数，在这个算法看来，都是一堆位，处理起来没有什么差别。結構改進了下，不然我內存受不了。。。$difftime = TimerInit();計時開始
Dim $avArray ;16 777 216个数(數組限制)
$avArray =Random(1, 100000000, 1)
$s_befor = $avArray;初始化刪除前對比值
For $i = 1 To UBound($avArray) - 1
$avArray[$i] = Random(1, 100000000, 1);隨機產生一到一億中任意一個數
$s_befor = BitXOR($s_befor, $avArray[$i]);異或
Next
$avArray = 0;隨機刪除一個數
$s_after = $avArray;初始化刪除后對比值
For $i = 1 To UBound($avArray) - 1
$s_after = BitXOR($s_after, $avArray[$i]);異或
Next
MsgBox(0, '计算结果:', '刚刚被删除的数是'& BitXOR($s_befor, $s_after) & @CRLF & '用時' & TimerDiff($difftime)) 没想到比楼上几位算法更好的办法，如果不用数组而用字符串的函数来操作，虽然有可能会突破16777216的数目，可是效率太低了，没法用。 回复 9# 大绯狼
不是连续的啊，我只是举个例子说明RtlCompareMemory的返回结果。
String1 = "autoitx"
String2 = "autoit"
返回结果等于6，只有前6个字节是相同的。在输出时从String1中截取所删的值就好了。
String1 = "7498163025"
String2 = "749816325"
返回7，说明删除了原本在第8位上的数，为何无法知道删除数的值？从String1中截取第8位就是了。
String1 = "6A01B87C43419EFFD0"
String2 = "6AB87C43419EFFD0"
返回2，依此，只要用StringMid(String1, 3, 2)，就知道所删的值是01。
页:
[1]
2