N个数中取走一个，如何知道取走的是哪个

大绯狼

假设有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

水木子

如果全是十进制数倒比较简单！
也可能是我没理解大虾出题的意思，管他的，重在参与吧！

#include <Array.au3>
Local $avArray[10000] ;一万个数

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))

3mile

楼上思路太漂亮了。
计算总和！佩服

shypro2009

设
原数组为 arry1[N]
取走一个的 为 arry2[N-1]

取走的数 = sum （arry1[N]）-sum（arry2[N-1]）

对autoit 不是很熟，不知道这样行不行？

btw, 这样对 非 十进制的也有效吧。 不过只能对取走一个数的有效。

大绯狼

回复 1# 大绯狼

程序結構非常不錯，不過這個加減法運算效率不夠好，如果涉及到更多數字的話（比如1億個），效率就大打折扣了。

另：請給出可以計算下所需時間。

水木子

回复 5# 大绯狼

正如大侠所说，这样确实不好，正在寻思更好的方法。

1楼代码计算时间：2.601

auto

需要具体问题具体分析，随机是数是否可以存在重复问题？
如里按问题里面生成一个N=16 777 216数据，试着将16 777 216随机填充完数据（可以重复数据）需要多长时间？如不重复需要多长时间？然后在数组再取数？
如果只是需要取随数，那么实时生成就可以了

pusofalse

RtlCompareMemory可以返回相同的字节的数量。

String1 = abcdefghi
String2 = abcdefgi
返回结果等于7，说明删除了原本在第(7÷1)+1位上的值。

KMP算法：http://matrix-67.spaces.live.com ... 611BA4E21!672.entry

大绯狼

回复 8# pusofalse

PUSOFALSE老大這個欠妥啊
由於數不是連續的 僅知道刪除數的位置也是沒有辦法知道刪除數的值的。

xsjtxy

我很傻很天真
#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千万个数，最好能给出时间。

3mile

来个另类的笨办法。

#include <Array.au3>
Local $avArray[10000] ;一万个数

$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)

大绯狼

考慮到大家說的進制問題，參照水木子的代碼進行了改進，使用異或，這樣就不管什麽進制進制，浮點數，都能夠進行運算。因为是在位级别上操作，无论是整数还是浮点数，在这个算法看来，都是一堆位，处理起来没有什么差别。結構改進了下，不然我內存受不了。。。

$difftime = TimerInit();計時開始

Dim $avArray[16777216] ;16 777 216个数(數組限制)

$avArray[0] =Random(1, 100000000, 1)
$s_befor = $avArray[0];初始化刪除前對比值

For $i = 1 To UBound($avArray) - 1
        $avArray[$i] = Random(1, 100000000, 1);隨機產生一到一億中任意一個數
        $s_befor = BitXOR($s_befor, $avArray[$i]);異或
Next

$avArray[Random(0, UBound($avArray) - 1, 1)] = 0;隨機刪除一個數

$s_after = $avArray[0];初始化刪除后對比值
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))

C.L

没想到比楼上几位算法更好的办法，如果不用数组而用字符串的函数来操作，虽然有可能会突破16777216的数目，可是效率太低了，没法用。

pusofalse

回复 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。