Notifications
Clear all
Apr 08, 2016 10:53 pm
several years ago some “Mini-Challenges” were very popular on this forum. and I want to issue a new one for who might be interested.
there are N Points associated with a name and a value. Their values are in range. Let’s say from 0.0 to 1.0.
we need a function that returns for every specified value two closest Points from the list – lower and upper.
Example #1 – points:
#(#(“a”, 0.0), #(“b”, 0.3), #(“c”, 0.4), #(“d”, 0.7), #(“e”, 1.0))
Example #2 – points:
seed 0
for k=1 to 10000 collect #(bit.intashex (random 0x100000 0xFFFFFF) , random 0.0 1.0)
as usually the best will be that is faster and uses less memory
Enjoy!
22 Replies
Apr 08, 2016 10:53 pm
Here are my results, testing several different methods:
1) Brute force:
For each query, we iterate the entire list checking if each value is the closest upper/lower item to the query value. The resulting upper/lower items are then returned.
Results:
"Time per lookup: 0.032658 seconds" "Total time for 500.0 lookups: 16.329 seconds"
Code:
(
seed 0
arr = for k=1 to 10000 collect #(bit.intashex (random 0x100000 0xFFFFFF) , random 0.0 1.0)
fn findNearestUpperLower arr target=
(
distUpper = distLower = 100000; resultUpper = resultLower = undefined
for val in arr do
(
tmp = abs(val[2]-target)
if resultUpper == undefined or (tmp < distUpper and val[2] >= target) then
(
resultUpper = val
distUpper = tmp
)
if resultLower == undefined or (tmp < distLower and val[2] <= target) then
(
resultLower = val
distLower = tmp
)
)
#(resultLower, resultUpper)
)
ts = timestamp()
iterCount = 500.0
for j in 1 to iterCount do
(
findNearestUpperLower arr (random 0.0 1.0)
)
te = timestamp()
print ("Time per lookup: " + ((((te-ts)/1000.0)/iterCount) as string) + " seconds")
print ("Total time for " + iterCount as string + " lookups: " + ((te-ts)/1000.0) as string + " seconds")
true
)
2) Sorted brute force:
First we sort the list by value, then for each query we parse the entire list up until we reach a value in the list that is higher than the query value. From there we get our upper/lower items by grabbing adjacent list members to our current position.
Results:
"Time per lookup: 0.008448 seconds" "Total time for 500.0 lookups: 4.474 seconds"
Code:
(
seed 0
arr = for k=1 to 10000 collect #(bit.intashex (random 0x100000 0xFFFFFF) , random 0.0 1.0)
fn findNearestUpperLower arr target=
(
inx = 1
while (inx <= arr.count and arr[inx][2] < target) do
(
inx += 1
)
if (inx == 1) then
(
#(arr[1], arr[1])
)else if (inx == arr.count) then
(
#(arr[arr.count], arr[arr.count])
)else if (arr[inx][2] == target) then
(
#(arr[inx], arr[inx])
)else
(
#(arr[inx-1], arr[inx])
)
)
fn sortFn v1 v2 =
(
if (v1[2] > v2[2]) then 1 else if (v1[2] < v2[2]) then -1 else 0
)
tss = timestamp()
qsort arr sortFn
tsf = timestamp()
iterCount = 500.0
for j in 1 to iterCount do
(
(findNearestUpperLower arr (random 0.0 1.0) )
)
tef = timestamp()
tes = timestamp()
print ("Time per lookup: " + ((((tef-tsf)/1000.0)/iterCount) as string) + " seconds")
print ("Total time for " + iterCount as string + " lookups: " + ((tes-tss)/1000.0) as string + " seconds")
true
)
3) Sorted kdtree
First we sort our list by value, then construct a faux-kdtree (this kdtree code only allows 1-dimensional input objects, instead of n-dimensional objects) of the resulting array using maxscript-compiled C# code (based on a kdtree implementation written by [A Stark, September 2009]( http://forum.unity3d.com/threads/point-nearest-neighbour-search-class.29923/)). Then we do nearest-neighbor queries on the kdtree which returns an array index of the closest member in the list. From there we grab adjacent members to get upper/lower items.
Results:
"Time per lookup: 3.6e-005 seconds" "Total time for 500.0 lookups: 0.464 seconds" --includes c# compilation time
Code:
global classIter
global kdtree_classname
(
fn sortFn v1 v2 =
(
if (v1[2] > v2[2]) then 1 else if (v1[2] < v2[2]) then -1 else 0
)
seed 0
arr = for k=1 to 10000 collect #(bit.intashex (random 0x100000 0xFFFFFF) , random 0.0 1.0)
tss = timestamp()
qsort arr sortFn
arr2 = for v in arr collect v[2]
(
if (classIter == undefined) then classIter = 100
kdtree_classname = "kdtree_" + classIter as string
classIter += 1
if classof (dotnet.GetType kdtree_classname) != dotNetObject then
(
classStr = "
using System;
using System.Collections;
using System.Collections.Generic;
public class " + kdtree_classname + "
{
public " + kdtree_classname + "[] lr;
public float pivot;
public int pivotIndex;
public " + kdtree_classname + "() {
lr = new " + kdtree_classname + "[2];
}
public static " + kdtree_classname + " MakeFromPoints(params float[] points) {
int[] indices = Iota(points.Length);
return MakeFromPointsInner(0, 0, points.Length - 1, points, indices);
}
static " + kdtree_classname + " MakeFromPointsInner(
int depth,
int stIndex, int enIndex,
float[] points,
int[] inds
) {
" + kdtree_classname + " root = new " + kdtree_classname + "();
int splitPoint = FindPivotIndex(points, inds, stIndex, enIndex);
root.pivotIndex = inds[splitPoint];
root.pivot = points[root.pivotIndex];
int leftEndIndex = splitPoint - 1;
if (leftEndIndex >= stIndex) {
root.lr[0] = MakeFromPointsInner(depth + 1, stIndex, leftEndIndex, points, inds);
}
int rightStartIndex = splitPoint + 1;
if (rightStartIndex <= enIndex) {
root.lr[1] = MakeFromPointsInner(depth + 1, rightStartIndex, enIndex, points, inds);
}
return root;
}
static void SwapElements(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
static int FindSplitPoint(float[] points, int[] inds, int stIndex, int enIndex) {
float a = points[inds[stIndex]];
float b = points[inds[enIndex]];
int midIndex = (stIndex + enIndex) / 2;
float m = points[inds[midIndex]];
if (a > b) {
if (m > a) {
return stIndex;
}
if (b > m) {
return enIndex;
}
return midIndex;
} else {
if (a > m) {
return stIndex;
}
if (m > b) {
return enIndex;
}
return midIndex;
}
}
public static int FindPivotIndex(float[] points, int[] inds, int stIndex, int enIndex)
{
int splitPoint = FindSplitPoint(points, inds, stIndex, enIndex);
float pivot = points[inds[splitPoint]];
SwapElements(inds, stIndex, splitPoint);
int currPt = stIndex + 1;
int endPt = enIndex;
while (currPt <= endPt)
{
float curr = points[inds[currPt]];
if ((curr > pivot)) {
SwapElements(inds, currPt, endPt);
endPt--;
} else {
SwapElements(inds, currPt - 1, currPt);
currPt++;
}
}
return currPt - 1;
}
public static int[] Iota(int num) {
int[] result = new int[num];
for (int i = 0; i < num; i++) {
result[i] = i;
}
return result;
}
public int FindNearest(float pt)
{
float bestDist = 1000000000f;
int bestIndex = -1;
Search(pt, ref bestDist, ref bestIndex);
return bestIndex;
}
void Search(float pt, ref float bestSoFar, ref int bestIndex)
{
float myDist = Math.Abs(pivot - pt);
if (myDist < bestSoFar) {
bestSoFar = myDist;
bestIndex = pivotIndex;
}
float planeDist = pt - pivot;
int selector = planeDist <= 0 ? 0 : 1;
if (lr[selector] != null) {
lr[selector].Search(pt, ref bestSoFar, ref bestIndex);
}
selector = (selector + 1) % 2;
float PlaneDist = Math.Abs(planeDist);
if ((lr[selector] != null) && (bestSoFar > PlaneDist)) {
lr[selector].Search(pt, ref bestSoFar, ref bestIndex);
}
}
}
"
compilerParams = dotnetobject "System.CodeDom.Compiler.CompilerParameters"
dotnet.setlifetimecontrol compilerParams #dotnet
compilerParams.ReferencedAssemblies.Add("System.dll");
compilerParams.ReferencedAssemblies.Add("System.Windows.Forms.dll");
compilerParams.ReferencedAssemblies.Add("System.Drawing.dll");
compilerParams.ReferencedAssemblies.Add((getdir #maxroot) + @"Autodesk.Max.dll");
compilerParams.ReferencedAssemblies.Add((getdir #maxroot)+ @"ManagedServices.dll");
compilerParams.ReferencedAssemblies.Add((getdir #maxroot)+ @"MaxCustomControls.dll");
compilerParams.GenerateInMemory = on
csharpProvider = dotnetobject "Microsoft.CSharp.CSharpCodeProvider"
compilerResults = csharpProvider.CompileAssemblyFromSource compilerParams #(classStr)
dotnet.setlifetimecontrol compilerResults #dotnet
if (compilerResults.Errors.Count > 0 ) then
(
local errs = stringstream ""
for i = 0 to (compilerResults.Errors.Count-1) do
(
local err = compilerResults.Errors.Item[i]
format "Error:% Line:% Column:% %
" err.ErrorNumber err.Line err.Column err.ErrorText to:errs
)
format "%
" errs
undefined
)
)
)
dnArr = dotnet.ValueToDotNetObject arr2 (dotnetclass "System.Single[]")
kdtree = (dotnetclass kdtree_classname).MakeFromPoints dnArr
tsf = timestamp()
iterCount = 500.0
for j in 1 to iterCount do
(
findVal = (random 0.0 1.0)
closestInx = (kdtree.findNearest findVal) + 1
upperInx = -1
lowerInx = -1
if (arr[closestInx][2] == findVal) then
(
upperInx = closestInx
lowerInx = closestInx
)else if (arr[closestInx][2] > findVal) then
(
upperInx = closestInx
lowerInx = amax #(1, closestInx-1)
)else if (arr[closestInx][2] < findVal) then
(
lowerInx = closestInx
upperInx = amin #(arr.count, closestInx+1)
)
upperLower = #(arr[lowerInx], arr[upperInx])
)
tef = timestamp()
tes = timestamp()
print ("Time per lookup: " + ((((tef-tsf)/1000.0)/iterCount) as string) + " seconds")
print ("Total time for " + iterCount as string + " lookups: " + ((tes-tss)/1000.0) as string + " seconds")
true
)
4) Unsorted kdtree, run twice
For this method we build a kdtree without sorting the input array first, and instead run our nearest-neighbor search twice, using an input parameter to determine if we're looking for upper/lower items compared to our search value.
Results:
"Time per lookup: 4.8e-005 seconds" "Total time for 500.0 lookups: 0.224 seconds" --includes c# compilation time
Code:
global classIter
global kdtree_classname
(
fn sortFn v1 v2 =
(
if (v1[2] > v2[2]) then 1 else if (v1[2] < v2[2]) then -1 else 0
)
seed 0
arr = for k=1 to 10000 collect #(bit.intashex (random 0x100000 0xFFFFFF) , random 0.0 1.0)
tss = timestamp()
arr2 = for v in arr collect v[2]
(
if (classIter == undefined) then classIter = 100
kdtree_classname = "kdtree_" + classIter as string
classIter += 1
tcs = timestamp()
if classof (dotnet.GetType kdtree_classname) != dotNetObject then
(
classStr = "
using System;
using System.Collections;
using System.Collections.Generic;
public class " + kdtree_classname + "
{
public " + kdtree_classname + "[] lr;
public float pivot;
public int pivotIndex;
public " + kdtree_classname + "() {
lr = new " + kdtree_classname + "[2];
}
public static " + kdtree_classname + " MakeFromPoints(params float[] points) {
int[] indices = Iota(points.Length);
return MakeFromPointsInner(0, 0, points.Length - 1, points, indices);
}
static " + kdtree_classname + " MakeFromPointsInner(
int depth,
int stIndex, int enIndex,
float[] points,
int[] inds
) {
" + kdtree_classname + " root = new " + kdtree_classname + "();
int splitPoint = FindPivotIndex(points, inds, stIndex, enIndex);
root.pivotIndex = inds[splitPoint];
root.pivot = points[root.pivotIndex];
int leftEndIndex = splitPoint - 1;
if (leftEndIndex >= stIndex) {
root.lr[0] = MakeFromPointsInner(depth + 1, stIndex, leftEndIndex, points, inds);
}
int rightStartIndex = splitPoint + 1;
if (rightStartIndex <= enIndex) {
root.lr[1] = MakeFromPointsInner(depth + 1, rightStartIndex, enIndex, points, inds);
}
return root;
}
static void SwapElements(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
static int FindSplitPoint(float[] points, int[] inds, int stIndex, int enIndex) {
float a = points[inds[stIndex]];
float b = points[inds[enIndex]];
int midIndex = (stIndex + enIndex) / 2;
float m = points[inds[midIndex]];
if (a > b) {
if (m > a) {
return stIndex;
}
if (b > m) {
return enIndex;
}
return midIndex;
} else {
if (a > m) {
return stIndex;
}
if (m > b) {
return enIndex;
}
return midIndex;
}
}
public static int FindPivotIndex(float[] points, int[] inds, int stIndex, int enIndex)
{
int splitPoint = FindSplitPoint(points, inds, stIndex, enIndex);
float pivot = points[inds[splitPoint]];
SwapElements(inds, stIndex, splitPoint);
int currPt = stIndex + 1;
int endPt = enIndex;
while (currPt <= endPt)
{
float curr = points[inds[currPt]];
if ((curr > pivot)) {
SwapElements(inds, currPt, endPt);
endPt--;
} else {
SwapElements(inds, currPt - 1, currPt);
currPt++;
}
}
return currPt - 1;
}
public static int[] Iota(int num) {
int[] result = new int[num];
for (int i = 0; i < num; i++) {
result[i] = i;
}
return result;
}
public int FindNearest(float pt, int dir)
{
float bestDist = 1000000000f;
int bestIndex = -1;
int minIndex = -1;
int maxIndex = -1;
float minDist = 1000000000f;
float maxDist = 1000000000f;
Search(pt, ref bestDist, ref bestIndex, ref minDist, ref minIndex, ref maxDist, ref maxIndex, dir);
if (bestIndex == -1)
{
if (dir < 0)
{
return minIndex;
}else
{
return maxIndex;
}
}
return bestIndex;
}
void Search(float pt, ref float bestSoFar, ref int bestIndex, ref float minDist, ref int minIndex, ref float maxDist, ref int maxIndex, int dir)
{
float myDist = Math.Abs(pivot - pt);
if (myDist < maxDist)
{
maxDist = myDist;
maxIndex = pivotIndex;
}
if (myDist < minDist)
{
minDist = myDist;
minIndex = pivotIndex;
}
if (myDist < bestSoFar &&
((dir > 0 && pivot >= pt) || (dir < 0 && pivot <= pt))
)
{
bestSoFar = myDist;
bestIndex = pivotIndex;
}
float planeDist = pt - pivot;
int selector = planeDist <= 0 ? 0 : 1;
if (lr[selector] != null) {
lr[selector].Search(pt, ref bestSoFar, ref bestIndex, ref minDist, ref minIndex, ref maxDist, ref maxIndex, dir);
}
selector = (selector + 1) % 2;
float PlaneDist = Math.Abs(planeDist);
if ((lr[selector] != null) && (bestSoFar > PlaneDist)) {
lr[selector].Search(pt, ref bestSoFar, ref bestIndex, ref minDist, ref minIndex, ref maxDist, ref maxIndex, dir);
}
}
}
"
compilerParams = dotnetobject "System.CodeDom.Compiler.CompilerParameters"
dotnet.setlifetimecontrol compilerParams #dotnet
compilerParams.ReferencedAssemblies.Add("System.dll");
compilerParams.ReferencedAssemblies.Add("System.Windows.Forms.dll");
compilerParams.ReferencedAssemblies.Add("System.Drawing.dll");
compilerParams.ReferencedAssemblies.Add((getdir #maxroot) + @"Autodesk.Max.dll");
compilerParams.ReferencedAssemblies.Add((getdir #maxroot)+ @"ManagedServices.dll");
compilerParams.ReferencedAssemblies.Add((getdir #maxroot)+ @"MaxCustomControls.dll");
compilerParams.GenerateInMemory = on
csharpProvider = dotnetobject "Microsoft.CSharp.CSharpCodeProvider"
compilerResults = csharpProvider.CompileAssemblyFromSource compilerParams #(classStr)
dotnet.setlifetimecontrol compilerResults #dotnet
if (compilerResults.Errors.Count > 0 ) then
(
local errs = stringstream ""
for i = 0 to (compilerResults.Errors.Count-1) do
(
local err = compilerResults.Errors.Item[i]
format "Error:% Line:% Column:% %
" err.ErrorNumber err.Line err.Column err.ErrorText to:errs
)
format "%
" errs
undefined
)
)
)
tce = timestamp()
dnArr = dotnet.ValueToDotNetObject arr2 (dotnetclass "System.Single[]")
kdtree = (dotnetclass kdtree_classname).MakeFromPoints dnArr
tsf = timestamp()
iterCount = 500.0
for j in 1 to iterCount do
(
findVal = (random 0.0 1.0)
upperInx = (kdtree.findNearest findVal 1) + 1
lowerInx = (kdtree.findNearest findVal -1) + 1
upperLower = #(arr[lowerInx], arr[upperInx])
)
tef = timestamp()
tes = timestamp()
print ("Time per lookup: " + ((((tef-tsf)/1000.0)/iterCount) as string) + " seconds")
print ("Total time for " + iterCount as string + " lookups: " + ((tes-tss)/1000.0) as string + " seconds")
true
)
Conclusion:
An unsorted kdtree implementation which is run twice in order to find out upper/lower values is the fastest method amongst all of these, completing 500 queries in ~0.225 seconds. The compilation time for the C# kdtree code is ~.15 seconds, and there's some overhead in converting the maxscript array to a dotnet array, so the time for 500 queries for method #4 is actually ~0.025 seconds. I'd say that's pretty fast!
Not sure what the rules of this challenge are, but maybe Denis would consider using compiled C# to be cheating ;)...if so, it would be interesting to see how fast a maxscript implementation of the C# kdtree code would run in comparison....maybe someone else would like to try that. Also, I realize there are further micro-optimizations that could be done to the code for method #4, both in terms of speed and memory usage, but with its current performance already being so good in comparison to the brute force methods, I'm not worrying about trying to squeeze an extra millisecond or two out of it. There's also the possibility of modifying the nearest-neighbor search code to grab both the upper/lower values on the fly as it evaluates, instead of running it twice. That could potentially add a speed boost as well.
Apr 08, 2016 10:53 pm
I’d pick bsearch for that. Had to ramp up the iterCount a bit:
iterCount = 5000
seed 0
pts = for k=1 to 10000 collect #(bit.intashex (random 0x100000 0xFFFFFF) , random 0.0 1.0)
fn comp v1 v2 = 1e6 * (v1[2] - v2[2])
start = timeStamp()
qsort pts comp
for i = 1 to iterCount do
if bsearch #(0, random 0.0 1.0) pts comp index:&index != undefined then case of
(
(index <= 1) : dataPair lower:undefined upper:pts[index+1][2]
(index >= 10000-1) : dataPair lower:pts[index-1][2] upper:undefined
default : dataPair lower:pts[index-1][2] upper:pts[index+1][2]
)
else undefined
format "Total time for % lookups: % seconds
" iterCount ((timeStamp() - start)/1000.0)
Total time for 5000 lookups: 0.282 seconds
Apr 08, 2016 10:53 pm
I can’t figure out how you use bsearch for an item that, in most cases, is not in the input array.
I’m reading your code and can’t understand it.
Apr 08, 2016 10:53 pm
It will return undefined if it cannot find it and I’m testing for it (and as the goal was to return the lower and higher values and not the matching item, I’m only using the index variable). Rewrite it to print to listener instead to make it a bit more obvious if you will:
iterCount = 50
seed 0
pts = #(#("a", 0.0), #("b", 0.3), #("c", 0.4), #("d", 0.7), #("e", 1.0))
fn comp v1 v2 = 1e6 * (v1[2] - v2[2])
start = timeStamp()
qsort pts comp
for i = 1 to iterCount do
(
local rnd = random 0 10 * 0.1
format "searched item: %, " rnd
if bsearch #(0, rnd) pts comp index:&index != undefined then
(
case of
(
(index <= 1) : format "index: %, lower: undefined, upper: %
" index pts[index+1][2]
(index >= pts.count-1) : format "index: %, lower: %, upper: undefined
" index pts[index-1][2]
default : format "index: %, lower: %, upper: %
" index pts[index-1][2] pts[index+1][2]
)
)
else format "undefined
"
)
format "Total time for % lookups: % seconds
" iterCount ((timeStamp() - start)/1000.0)
Apr 08, 2016 10:53 pm
Perhaps it’s my MAX version (Design 2014). ‘Index’ is allways zero or undefined.
This is the output I get:
searched item: 0.2, undefined
searched item: 0.7, index: 0, lower: undefined, upper: 0.0
searched item: 0.2, undefined
searched item: 0.7, index: 0, lower: undefined, upper: 0.0
searched item: 0.3, index: 0, lower: undefined, upper: 0.0
searched item: 0.8, undefined
searched item: 0.1, undefined
searched item: 0.9, undefined
searched item: 0.4, index: 0, lower: undefined, upper: 0.0
searched item: 0.2, undefined
.
.
.
Apr 08, 2016 10:53 pm
Yep
Since 3ds Max 2015, if the optional by-reference keyword argument index: is specified, the index of the found item will be written into it.
Apr 08, 2016 10:53 pm
DenisT should give some bases to his challenge.
It’s not the same to code the function for several iterations than just for one value.
A first simple try for just one value:
(
fn sortFn v1 v2 =
(
if (v1[2] > v2[2]) then 1 else if (v1[2] < v2[2]) then -1 else 0
)
--seed 0
arr = for k=1 to 10000 collect #(bit.intashex (random 0x100000 0xFFFFFF) , random 0.0 1.0)
findVal = (random 0.0 1.0)
tss = timestamp()
theFindVal = #("000000", findVal)
append arr theFindVal
qsort arr sortFn
item = finditem arr theFindVal
tes = timestamp()
print ("Total time for lookup: " + ((tes-tss)/1000.0) as string + " seconds")
format "ValueToFind= %; Item= %; Previous= %; Next= %
" findVal item arr[item-1] arr[item+1]
OK
)
In my computer time varies from 0.118 to 0.135 seconds:
"Total time for lookup: 0.121 seconds"
ValueToFind= 0.817636; Item= 8193; Previous= #("30fbb8", 0.817552); Next= #("5cc623", 0.817765)
It’s obviously a bad idea to corrupt the original array as I do!!!
Apr 08, 2016 10:53 pm
first of all i want to say “Thanks!” to Swordslayer
he understood the problem very well and showed the most promising solution – the using of kdtree
i’ve started with ‘brute force’ algorithm as:
fn directSearchSides points t =
(
_lower = undefined
_upper = undefined
for p in points do
(
if p[2] <= t and (_lower == undefined or p[2] >= _lower[2]) do _lower = p
if p[2] >= t and (_upper == undefined or p[2] <= _upper[2]) do _upper = p
)
if _lower == undefined do _lower = _upper
if _upper == undefined do _upper = _lower
#(_lower, _upper)
)
after that i went to version that uses sorted list:
fn sortedSearchSides points t =
(
end = off
k = 1
while (end = k < points.count) and (points[k][2] < t) do k += 1
if end then
(
if k == 1 then #(points[k], points[k]) else #(points[k-1], points[k])
)
else
(
if points[k][2] <= t then #(points[k], points[k]) else #(points[k-1], points[k])
)
)
but both of them are very slow in comparison with rest of my code
(this code might be used as a test )
seed 0
num = 10000
points = for k=1 to num collect #(bit.intashex (random 0x100000 0xFFFFFF) , random 0.0 1.0)
fn sortByValue v1 v2 = (if v1[2] < v2[2] then -1 else if v1[2] > v2[2] then 1 else 0)
fn directSearchSides points t =
(
_lower = undefined
_upper = undefined
for p in points do
(
if p[2] <= t and (_lower == undefined or p[2] >= _lower[2]) do _lower = p
if p[2] >= t and (_upper == undefined or p[2] <= _upper[2]) do _upper = p
)
if _lower == undefined do _lower = _upper
if _upper == undefined do _upper = _lower
#(_lower, _upper)
)
fn sortedSearchSides points t =
(
end = off
k = 1
while (end = k < points.count) and (points[k][2] < t) do k += 1
if end then
(
if k == 1 then #(points[k], points[k]) else #(points[k-1], points[k])
)
else
(
if points[k][2] <= t then #(points[k], points[k]) else #(points[k-1], points[k])
)
)
fn quicksearchSides points t =
(
local count = points.count
local result = undefined
local s = 1, e = count, k = count/2
while result == undefined and not keyboard.escpressed do -- escape is not necessary of course if we do everything right :)
(
if (k == s) or (k == e) then result = #(points[k], points[k])
else
(
if points[k][2] >= t then
(
if points[k-1][2] <= t then result = #(points[k-1], points[k])
else
(
e = k
k = (s + e)/2
)
)
else
(
if points[k+1][2] >= t then result = #(points[k], points[k+1])
else
(
s = k
k = (s + e)/2
)
)
)
)
if result[1][2] == t then result[2] = result[1]
else if result[2][2] == t then result[1] = result[2]
result
)
(
count = 100
seed (timestamp())
_seed = random 1 1e9
v = undefined
t = undefined
t1 = timestamp()
m1 = heapfree
seed _seed
for k=1 to count do v = directSearchSides points (t = random 0.0 1.0)
format "% % >> time:% memory:%
" t v (timestamp() - t1) (m1 - heapfree)
pts = deepcopy points
t1 = timestamp()
m1 = heapfree
qsort pts sortByValue
seed _seed
for k=1 to count do v = sortedSearchSides pts (t = random 0.0 1.0)
format "% % >> time:% memory:%
" t v (timestamp() - t1) (m1 - heapfree)
)
after that i was messing with a kdtree. but using of kdtree was to much for my case where i usually do 1-1000 iterations for 10-100 item list
and finally i wrote my own quick-search – simple Bisection method:
fn quicksearchSides points t =
(
local count = points.count
local result = undefined
local s = 1, e = count, k = count/2
while result == undefined and not keyboard.escpressed do -- escape is not necessary of course if we do everything right :)
(
if (k == s) or (k == e) then result = #(points[k], points[k])
else
(
if points[k][2] >= t then
(
if points[k-1][2] <= t then result = #(points[k-1], points[k])
else
(
e = k
k = (s + e)/2
)
)
else
(
if points[k+1][2] >= t then result = #(points[k], points[k+1])
else
(
s = k
k = (s + e)/2
)
)
)
)
if result[1][2] == t then result[2] = result[1]
else if result[2][2] == t then result[1] = result[2]
result
)
Apr 08, 2016 10:53 pm
Apr 08, 2016 10:53 pm
so the final code for test might be:
seed 0
num = 1000
points = for k=1 to num collect #(bit.intashex (random 0x100000 0xFFFFFF) , random 0.0 1.0)
fn sortByValue v1 v2 = (if v1[2] < v2[2] then -1 else if v1[2] > v2[2] then 1 else 0)
fn directSearchSides points t =
(
_lower = undefined
_upper = undefined
for p in points do
(
if p[2] <= t and (_lower == undefined or p[2] >= _lower[2]) do _lower = p
if p[2] >= t and (_upper == undefined or p[2] <= _upper[2]) do _upper = p
)
if _lower == undefined do _lower = _upper
if _upper == undefined do _upper = _lower
#(_lower, _upper)
)
fn sortedSearchSides points t =
(
end = off
k = 1
while (end = k < points.count) and (points[k][2] < t) do k += 1
if end then
(
if k == 1 then #(points[k], points[k]) else #(points[k-1], points[k])
)
else
(
if points[k][2] <= t then #(points[k], points[k]) else #(points[k-1], points[k])
)
)
fn quicksearchSides points t =
(
local count = points.count
local result = undefined
local s = 1, e = count, k = count/2
while result == undefined and not keyboard.escpressed do -- escape is not necessary of course if we do everything right :)
(
if (k == s) or (k == e) then result = #(points[k], points[k])
else
(
if points[k][2] >= t then
(
if points[k-1][2] <= t then result = #(points[k-1], points[k])
else
(
e = k
k = (s + e)/2
)
)
else
(
if points[k+1][2] >= t then result = #(points[k], points[k+1])
else
(
s = k
k = (s + e)/2
)
)
)
)
if result[1][2] == t then result[2] = result[1]
else if result[2][2] == t then result[1] = result[2]
result
)
(
count = 1000
seed (timestamp())
_seed = random 1 1e9
v = undefined
t = undefined
t1 = timestamp()
m1 = heapfree
seed _seed
for k=1 to count do v = directSearchSides points (t = random 0.0 1.0)
format "% % >> time:% memory:%
" t v (timestamp() - t1) (m1 - heapfree)
pts = deepcopy points
t1 = timestamp()
m1 = heapfree
qsort pts sortByValue
seed _seed
for k=1 to count do v = sortedSearchSides pts (t = random 0.0 1.0)
format "% % >> time:% memory:%
" t v (timestamp() - t1) (m1 - heapfree)
pts = deepcopy points
t1 = timestamp()
m1 = heapfree
qsort pts sortByValue
seed _seed
for k=1 to count do v = quicksearchSides pts (t = random 0.0 1.0)
format "% % >> time:% memory:%
" t v (timestamp() - t1) (m1 - heapfree)
)
1000 search iterations in 1000 item list
(sorting is included in performance check time)
result for my machine is:
0.315485 #(#("e6c9ae", 0.315462), #("f1e146", 0.317611)) >> time:1627 memory:128120L
0.315485 #(#("e6c9ae", 0.315462), #("f1e146", 0.317611)) >> time:464 memory:128120L
0.315485 #(#("e6c9ae", 0.315462), #("f1e146", 0.317611)) >> time:46 memory:128120L
Apr 08, 2016 10:53 pm
It was ivansavich not me who you wanted to say thanks to. Anyway now I see I got it wrong, thought the values are supposed to be there. Bummer that maxscript bsearch doesn’t return negative indices For the sake of completeness, using the .net binarysearch instead – first the function to insert in the test code:
binSearch = (dotNetClass "System.Array").BinarySearch
fn bsearchSides points floats t =
(
local index = binSearch floats t
case of
(
(index == -1 OR index == -points.count) : #(points[abs index], points[abs index])
(index < 0) : #(points[abs index - 1], points[abs index])
(index == 0 OR index == points.count - 1) : #(points[index+1], points[index+1])
default : #(points[index], points[index+1])
)
)
the test part:
pts = deepcopy points
t1 = timestamp()
m1 = heapfree
qsort pts sortByValue
floats = dotNet.ValueToDotNetObject (for p in pts collect p[2]) (dotNetClass "System.Single[]")
seed _seed
for k=1 to count do v = bsearchSides pts floats (t = random 0.0 1.0)
format "% % >> time:% memory:%
" t v (timestamp() - t1) (m1 - heapfree)
and the complete results:
0.87801 #(#("d5fb79", 0.877217), #("df733a", 0.878474)) >> time:2006 memory:128136L
0.87801 #(#("d5fb79", 0.877217), #("df733a", 0.878474)) >> time:614 memory:108184L
0.87801 #(#("d5fb79", 0.877217), #("df733a", 0.878474)) >> time:44 memory:108208L
0.87801 #(#("d5fb79", 0.877217), #("df733a", 0.878474)) >> time:36 memory:108456L
Page 1 / 2
Next