Notifications
Clear all
Feb 16, 2018 12:55 pm
what about a bit modified handmade binary search?
fn binarySearchLowerIndex arr val = (
local count = arr.count
local found = false
local index = 0
if count == 0 then ( index = 0; found = true )
else if val <= arr[1] then ( index = 0; found = true )
else if val >= arr[count] then ( index = count + 1; found = true )
else if count == 1 do (
if val > arr[1] then index = 2 else index = 0
found = true
)
if found then index else (
bounds = [ 1, arr.count, 0, 0 ]
while (bounds[2] - bounds[1]) > 1 and not found and not keyboard.escPressed do (
m = (bounds[1] + bounds[2]) / 2
if arr[m] == val do (
found = true
index = int m
)
if val >= arr[m] do bounds[1] = m
if val <= arr[m] do bounds[2] = m
)
if found then index else 1 + int bounds[1]
)
)
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
-- testing
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
(
gc();t1=timestamp();hf = heapfree
global arr = #()
for i=1 to 123 do (
val = random -42 42
j = amax 1 (binarySearchLowerIndex arr val)
insertItem val arr j
)
format "Time: %sec. Mem: %
" ((timestamp()-t1)/1000 as float) (hf-heapfree)
)
arr
Feb 16, 2018 12:55 pm
of course! there are many possible implementations of pure mxs b-search (some were posted in “Threads and Beads” thread on this forum) . But someone doesn’t want to think at all !!!
fn comp_fn a b = if (a < b) then -1 else if (a > b) then 1 else 0
fn b_search arr key comp_function =
(
local pivot, start = 1, stop = arr.count
local index = 0, result
while (result != 0 and start <= stop) do
(
pivot = (start + stop) / 2
result = comp_function key arr[pivot]
if (result == 0) then index = pivot
else if (result > 0) then start = pivot + 1
else stop = pivot - 1
)
if (index == 0 and result > 0) then pivot += 1
[index, pivot]
)
-- where index is found index, and pivot is the index where we can insert
arr = for k=1 to 100000 collect (random 0 10000000)
qsort arr comp_fn
v = b_search arr arr[999] comp_fn
(
gc()
t = timestamp()
h = heapfree
for k=1 to 1000 do
(
b_search arr arr[random 1 arr.count] comp_fn
)
format "time:% heap:%
" (timestamp() - t) (h - heapfree)
)
Feb 16, 2018 12:55 pm
i didn’t test it very well because i wrote it for 20 min
Page 2 / 2
Prev