[Массивы] Поиск отсутствующих чисел в определенном диапазоне

[YOgen]

Добрый день.
В наличии имеется один или сразу несколько диапазонов чисел, т.е.:
1 вариант: от 1 до 10.000;
2 вариант: от 1 до 7.000, и от 15.000 до 20.000.
И есть массив используемых чисел.
Есть ли возможность быстрее чем в приведенном решении найти в диапазоне(ах) числа, которые отсутствуют в массиве используемых чисел?

В приведенном примере на моей машине (WinXP, 3.0 Ghz) поиск длится примерно 21 сек., хотя значений немного (есть диапазоны по 60.000 чисел и массивы используемых дел по 40.000).

#include <Array.au3>

Opt("TrayIconDebug", 1)

Global $aRanges[2][2] = [[1, 7000], [15001, 20000]] ; 2 диапазона чисел

Global $aNumbers[7000] ; массив используемых чисел
For $i = 0 To UBound($aNumbers) - 1
	$aNumbers[$i] = Random(1, 30000, 1)
Next

$hTimer = TimerInit()

Local $iRows = 0, $iCounter = 0
Local $aRangeFull[1]
For $i = 0 To UBound($aRanges) - 1
	$iRows += $aRanges[$i][1] - $aRanges[$i][0] + 1
	ReDim $aRangeFull[$iRows]
	For $k = $aRanges[$i][0] To $aRanges[$i][1]
		$aRangeFull[$iCounter] = $k
		$iCounter += 1
	Next
Next
Local $sRangeFull = "|" & _ArrayToString($aRangeFull) & "|"
For $i = 0 To UBound($aNumbers) - 1
	If StringInStr($sRangeFull, "|" & $aNumbers[$i] & "|") Then
		ToolTip(Round(TimerDiff($hTimer) / 1000, 2))
		$sRangeFull = StringReplace($sRangeFull, "|" & $aNumbers[$i] & "|", "|")
	EndIf
Next
$sRangeFull = StringReplace(StringTrimRight(StringTrimLeft($sRangeFull, 1), 1), "|", @CRLF)
FileWriteLine("Result.txt", $sRangeFull) ; результат записывается в файл

 

[mef-t]

Есть.
Используемые Вами конструкции являются на самыми лучшими при работе с большими массивами данных.
Приношу извинения, что не привожу пример.
Думаю, в скором времени Вам его приведут более опытные форумчане.
Могу лишь посоветовать поискать темы оптимизации сортировки массивов. А так же темы оптимизации поиска уникальных элементов в массиве.
Эти темы помогут оптимизировать Ваш код.

 

[erlik]

Вот накидал примерный вариант. Находит отсутствующие числа в указанном диапазоне 1-30000.

Local $hFile = FileOpen(@ScriptDir  & "\Result.txt", 2)
Local $hFile2= FileOpen(@ScriptDir & "\Result2.txt",2)
Global $aNumbers[7000] ; массив используемых чисел
For $i = 0 To UBound($aNumbers) - 1
    $aNumbers[$i] = Random(1, 30000, 1)
	FileWriteLine($hFile, $aNumbers[$i] & @CR) ; пишем сюда просто для визуального сравнения
Next
 _ArraySort($aNumbers)
;_ArrayDisplay($aNumbers)
$hTimer = TimerInit()

For $i = 1 To 30000  ; крутим цикл по диапазону заданных чисел
    _ArrayBinarySearch($aNumbers, $i)
	If @error Then FileWriteLine($hFile2, $i & @CR) ; если ошибка - значит значение отсутствует в массиве
    Next
ConsoleWrite(TimerDiff($hTimer))
FileClose($hFile)
FileClose($hFile2)

 

[inververs]

Мой вариант:

Local $used_numbers[7000]
For $i = 0 To UBound($used_numbers) - 1
	$used_numbers[$i] = Random(1,30000,1)
Next

Local $randges = [[1,7000],[15001,20000]]

Local $hFile = FileOpen('result.txt',2)
For $i = 0 To UBound($randges) -1
	check_range($randges[$i][0],$randges[$i][1],$used_numbers,$hFile)
Next
FileClose($hFile)

Func check_range($min,$max, ByRef $numbers, ByRef $hFile)
	Local $range[$max - $min + 1]
	For $number In $numbers
		If $number < $min Or $number > $max Then ContinueLoop
		$range[$number - $min] = 1
	Next
	For $i = 0 To UBound($range) - 1
		If $range[$i] Then ContinueLoop
		FileWriteLine($hFile,$i + $min)
	Next
EndFunc

 

[YOgen]

inververs,
Супер!!! Результат феноменальный!! :laugh:
Спасибо огромное!

erlik,
Спасибо большое, тоже интересный вариант.

 

[WSWR]

Мне кажется, что при такой задаче можно использовать регулярные выражения.
Но вот нет ли ограничения на длину паттерна?

 

[inververs]

WSWR
Как то сравнивал функции регулярных выражений, stringinstring, stringreplace в плане поиска и замены чего то, но быстрее оказалось разложить строку в массив и в цикле пройтись.