[Математика] Алгоритм поиска позиции в упорядоченном массиве

[kzru_hunter]

Вообщем, задан упорядоченный массив. Значения могут быть разные.

Dim $OrderedArray[10000]
For $i=1 to 9999
	$OrderedArray[$i] = 10000 - $i
Next

В этот массив я хочу вставить значение, но так чтобы массив остался упорядоченным.
Для этого нужно найти позицию в массиве, в которую нужно вставить элемент с заданным значением. Причём, если в массиве уже есть несколько элементов с таким же значением, то элемент нужно вставить после всех этих элементов.

Поиск нужно производить с заданной позиции в массиве и с заданным направлением.

Примечание: в 70-90% случаев нужная позиция будет находится рядом с позицией, с которой будет производится поиск. Поэтому метод деления пополам оставлю на крайний случай.

Есть на примете алгоритм, но никак не получается его сделать полностью рабочим: к заданной позиции прибавляем или убавляем сначала 1, потом 2, 4, 8 и т.д. в зависимости от направления и сравниваем значения, пока не найдем нужную позицию.

Вот код, который никак не получается сделать полностью рабочим:

#include <array.au3>

Dim $OrderedArray[10000]
For $i=1 to 9999
	$OrderedArray[$i] = 10000 - $i
Next

ConsoleWrite("value = " & $i & ", pos = " & _FindPos(3000, 10000) & @CRLF)

Func _FindPos($points, $pos)
	$direction = False ; направление
	$step = 1  ; шаг
	$count = 0 ; количество проходов

	While 1
		If not $direction Then
			$pos -= $step

			If $pos > 1 Then
				If $OrderedArray[$pos] < $points Then
					$count += 1
					$step += $step
					ConsoleWrite("$pos = " & $pos & @CRLF)
					ContinueLoop
				Else
					If $step = 1 Then
						ConsoleWrite("$count = " & $count+1 & @CRLF)
						return $pos+1
					EndIf
					$direction = True
					$step = 1
				EndIf
			Else
				If $OrderedArray[$pos] >= $points Then
					$direction = True
					$step = 1
				Else
					ConsoleWrite("$count = " & $count+1 & @CRLF)
					return 1
				EndIf
			EndIf
		Else
			$pos += $step

			If $OrderedArray[$pos] >= $points Then
				$count += 1
				$step += $step
				ConsoleWrite("$pos = " & $pos & @CRLF)
				ContinueLoop
			Else
				If $step = 1 Then
					ConsoleWrite("$count = " & $count+1 & @CRLF)
					return $pos
				EndIf
				$direction = False
				$step = 1
			EndIf
		EndIf

		$count += 1
	WEnd
EndFunc

 

[Kalisnik]

kzru_hunter [?]

Причём, если в массиве уже есть несколько элементов с таким же значением, то элемент нужно вставить после всех этих элементов.

Не совсем понимаю. Если значения идентичны, то какая разница куда вставлять? Главное что бы массив остался упорядоченным? Если так, то...

#include <Array.au3>

Dim $OrderedArray[10]
For $i= 0 to 9
    $OrderedArray[$i] += $i
Next

_ArrayAdd($OrderedArray, Random(0, 9, 1))
_ArraySort($OrderedArray)

_ArrayDisplay($OrderedArray)

 

[kzru_hunter]

Вот пример массива:
[1] = 50
[2] = 40
[3] = 30
[4] = 20
[5] = 16
[6] = 15
[7] = 15
[8] = 10
[9] = 5
[10] = 2
Если нужно вставить число 14 или 15, то оно будет вставлено в позицию [8].
Но для этого нужно найти эту позицию с помощью алгоритма, а не перебора.
Сортировку нельзя применять.

 

[Sp01LeR]

Сортировку нельзя применять.

Почему? Если все дело в сортировке по убыванию, то функция _ArraySort() тоже поддерживает этот метод.

Но для этого нужно найти эту позицию с помощью алгоритма, а не перебора.

Алгоритм без перебора все равно не осуществим в данном случае - если массив действительно огромен, то лучше задействовать более гибкие средства чем массивы, - например, базу данных ...

 

[Kalisnik]

kzru_hunter
Либо использовать многомерный массив, что по сути будет повторять древовидность базы данных.

 

[kzru_hunter]

Мне вообще не нужно добавлять элемент в массив, я это отдельно по-другому сделаю. Мне нужно только найти то место, куда нужно вставить элемент с новым значением. Мне это нужно для ранговой системы. Другое не предлагать, нужен только рабочий алгоритм нахождения позиции.

 

[gregaz]

Предлагаю такой алгоритм.
Работает на удивление быстро. Если не использовать _ArrayDisplay , < 1 сек.

#include <Array.au3>

Dim $aArray[10001]
For $i=1 To 10000 
	$aArray[$i]=$i *50
Next

$sString=_ArrayToString($aArray,",")

$iInsert=20301
$iSearch=20301
Do 
	$iPos=StringInStr ($sString,"," & $iSearch & ",",0,-1)
	$iSearch+=1
Until $iPos <> 0
;MsgBox(0,$iPos,$sFragm)
$sFragm=StringLeft($sString,$iPos-1)
$aArray=StringSplit($sFragm,",")
;MsgBox(0,$aArray[0],$aArray[$aArray[0]]); Индекс массива и его значение , после которого надо вставлять $iInsert=2301

ConsoleWrite("Индекс массива :" & $aArray[0] & @LF)
ConsoleWrite("Последнее значение массива :" & $aArray[$aArray[0]] & @LF)

Надо конечно " причесывать"

 

[SyDr]

Dim $OrderedArray[10000]

For $i=1 to 9999
    $OrderedArray[$i] = 10000 - $i
Next

MsgBox(4096, Default, Find(16, $OrderedArray))



Func Find($Item, ByRef $Array)
	Local $nLeft = 0, $nRight = UBound($Array, 1) - 1

	While True
		If $nLeft = $nRight Then
			ExitLoop
		ElseIf $Item > $Array[Floor(($nLeft+$nRight) / 2)] Then
			$nRight = Floor(($nLeft+$nRight) / 2)
		ElseIf $Item < $Array[Floor(($nLeft+$nRight) / 2)] Then
			$nLeft = Ceiling(($nLeft+$nRight) / 2)
		Else
			$nLeft = Floor(($nLeft+$nRight)/ 2)
			$nRight = $nLeft
			ExitLoop
		EndIf
	WEnd

	While $Array[$nLeft] >= $Item
		$nLeft += 1
		If $nLeft = UBound($Array, 1) Then ExitLoop
	WEnd

	Return $nLeft
EndFunc

 

[kzru_hunter]

gregaz 300мс - слишком долго. Надо, чтобы на поиск уходило < 1мс.
SyDr Спасибо, но это метод деления пополам.

Вообщем, расскажу, что из себя представляет массив.
Индекс массива равен рангу игрока.
Значения каждого элемента массива - это количество очков каждого игрока. ID игрока не стал указывать, т.к. он не играет роли в этой проблеме.

Каждый раз какой-то игрок зарабатывает очки, а у других при этом они уменьшаются. В большинстве случаев, при зарабатывании очков ранг игрока может измениться, например, с 50 до 51 (т.е. на 1 вверх), но могут быть случаи, что ранг может сместиться с 10000 до 1000 (т.е. на 9000 вверх).
Вероятность того, что ранг сместится на 1 равна примерно 70-90% и эта вероятность убывает в зависимости от разницы между старым и новым рангом.

 

[XpycT]

kzru_hunter

#Region Includes
#include <Array.au3>
#EndRegion Includes
#NoTrayIcon


Dim $OrderedArray[10000]
For $i=1 to 9999
    $OrderedArray[$i] = 10000 - $i
Next

$iValue = 9980

ConsoleWrite("$iValue = " & $iValue & ", ValuePos = " & _FindPos($iValue, $OrderedArray) & @CRLF)

; _ArrayDisplay($OrderedArray)

Func _FindPos($_iSearchValue, ByRef $_aSearchArray)

    For $i = 1 To UBound($_aSearchArray) - 1
        If $_aSearchArray[$i] <= $_iSearchValue Then
            _ArrayInsert($_aSearchArray, $i, $_iSearchValue)

            Return $i
        EndIf
    Next

EndFunc

 

[kzru_hunter]

Вообщем, ладно. Сам как-нибудь разберусь, надеюсь на это.

 

[kzru_hunter]

Вроде сделал В этом примере идёт сравнение алгоритмов бинарного поиска, а также ручного. На удивление оказалось, что если перебирать все числа, то у ручного способа время выполнения всего лишь в ~1.1-1.2 раза хуже, чем у бинарного, хотя количество проходов в 2 раза больше (видимо функция Floor тормозит бинарный поиск).
Ну а если известна ближающая позиция, как в моем случае (когда нужно заново определить ранг игрока), то ручной способ окажется лучше бинарного и перебора.

#include <array.au3>

Dim $OrderedArray[10000]
For $i=1 to 9999
	$OrderedArray[$i] = (10000 - $i)*2
Next
;_ArrayDisplay($OrderedArray)

$begin = TimerInit()
For $i=-100 to 30000
	$pos = _FindNewUp($i, 9999)
	If $pos>1 And $pos<10000 ANd NOT ($OrderedArray[$pos] < $i And $OrderedArray[$pos-1] >= $i) Then ConsoleWrite("new, $i= " & $i & ", не совпало" & @CRLF)
Next
ConsoleWrite("new time = " & TimerDiff($begin) & @CRLF)


$begin = TimerInit()
For $i=-100 to 30000
	$pos = _FindBinary($i)
	If $pos>1 And $pos<10000 ANd NOT ($OrderedArray[$pos] < $i And $OrderedArray[$pos-1] >= $i) Then ConsoleWrite("binary, $i= " & $i & ", не совпало" & @CRLF)
Next
ConsoleWrite("binary time = " & TimerDiff($begin) & @CRLF)

Func _FindNewUp($points, $pos)
	$step = 1

	While $pos > 1 ANd $OrderedArray[$pos] < $points
		$step += $step
		$pos -= $step
	WEnd

	$pos += $step

	Do
		$step /= 2
		$pos -= $step

		If $pos > 0 Then
			If $OrderedArray[$pos] >= $points Then
				$pos += $step
			EndIf
		Else
			$pos += $step
		EndIf
	Until $step <= 1

	If $OrderedArray[$pos-1] < $points Then
		return $pos-1
	Else
		return $pos
	EndIf
EndFunc

Func _FindBinary($points)
	Local $l = 0, $u = 10000, $m = 0, $mm = 0
	While $u-$l>1
		$m = Floor( ($l+$u) / 2 )
		If $OrderedArray[$m] < $points Then
			$u = $m
		Else
			$l = $m
		EndIf
	WEnd

	If $OrderedArray[$m] < $points Then
		return $m
	Else
		return $m+1
	EndIf
EndFunc

 

[Yashied]

Вроде сделал...

< 1мс...

 

[kzru_hunter]

Yashied в примере перебираются значения -100 до 30000. В среднем на поиск каждого значения уходит 4.5сек/31000 = 0.14мс (в PAWN ~0.0005мс )
Ещё больше порадовало то, что если это переписать на PAWN(язык для CS 1.6, почти как и C++), то и там время поиска с помощью данного алгоритма всего лишь в ~1.1-1.2 раза хуже, чем с помощью бинарного поиска.