Что нового

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

kzru_hunter

Осваивающий
Сообщения
144
Репутация
49
Вообщем, задан упорядоченный массив. Значения могут быть разные.
Код:
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

Эволюция
Сообщения
295
Репутация
63
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)
 
Автор
K

kzru_hunter

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

Sp01LeR

Знающий
Сообщения
45
Репутация
12
kzru_hunter сказал(а):
Сортировку нельзя применять.

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

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

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

Kalisnik

Эволюция
Сообщения
295
Репутация
63
kzru_hunter
Либо использовать многомерный массив, что по сути будет повторять древовидность базы данных.
 
Автор
K

kzru_hunter

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

gregaz

AutoIT Гуру
Сообщения
1,166
Репутация
299
Предлагаю такой алгоритм.
Работает на удивление быстро. Если не использовать _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

Сидра
Сообщения
651
Репутация
158
Код:
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
 
Автор
K

kzru_hunter

Осваивающий
Сообщения
144
Репутация
49
gregaz 300мс - слишком долго. Надо, чтобы на поиск уходило < 1мс.
SyDr Спасибо, но это метод деления пополам.

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

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

XpycT

Скриптер
Сообщения
380
Репутация
133
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
 
Автор
K

kzru_hunter

Осваивающий
Сообщения
144
Репутация
49
Вообщем, ладно. Сам как-нибудь разберусь, надеюсь на это.
 
Автор
K

kzru_hunter

Осваивающий
Сообщения
144
Репутация
49
Вроде сделал :smile: В этом примере идёт сравнение алгоритмов бинарного поиска, а также ручного. На удивление оказалось, что если перебирать все числа, то у ручного способа время выполнения всего лишь в ~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
 
Автор
K

kzru_hunter

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