Что нового

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

YOgen

Знающий
Сообщения
58
Репутация
5
Добрый день.
В наличии имеется один или сразу несколько диапазонов чисел, т.е.:
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

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

erlik

Продвинутый
Сообщения
317
Репутация
84
Вот накидал примерный вариант. Находит отсутствующие числа в указанном диапазоне 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

AutoIT Гуру
Сообщения
2,135
Репутация
465
Мой вариант:
Код:
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

YOgen

Знающий
Сообщения
58
Репутация
5
inververs,
Супер!!! Результат феноменальный!! :laugh:
Спасибо огромное!

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

WSWR

AutoIT Гуру
Сообщения
941
Репутация
363
Мне кажется, что при такой задаче можно использовать регулярные выражения.
Но вот нет ли ограничения на длину паттерна?
 

inververs

AutoIT Гуру
Сообщения
2,135
Репутация
465
WSWR
Как то сравнивал функции регулярных выражений, stringinstring, stringreplace в плане поиска и замены чего то, но быстрее оказалось разложить строку в массив и в цикле пройтись.
 
Верх