Tom*_*Tom 10 language-agnostic algorithm data-structures
我在一个空间中有多达10,000个随机定位点,我需要能够在任何给定时间分辨出哪个光标最接近.要添加一些上下文,这些点采用矢量绘图的形式,因此用户可以不断快速地添加和删除它们,并且可能在画布空间中不平衡.
因此,我试图找到最有效的数据结构来存储和查询这些点.如果可能的话,我想让这个问题语言不可知.
更新问题后
使用两个红黑树或Skip_list地图.两者都是紧凑的自平衡数据结构,为搜索,插入和删除操作提供O(log n)时间.一个贴图将使用每个点的X坐标作为关键点,将点本身用作值,另一个将使用Y坐标作为关键点,将点本身用作值.
作为权衡,我建议最初将光标周围的搜索区域限制为正方形.为了完美匹配,方形边应该等于光标周围的"灵敏度圆"的直径.即如果你只对距离光标10个像素半径内的最近邻居感兴趣,那么方形边需要为20px. ,如果你是最近邻居,无论接近,你可以尝试通过评估相对于光标的楼层和天花板来动态找到边界.
然后从边界内的地图中检索两个点的子集,合并以仅包括两个子集内的点.
循环结果,计算每个点的接近度(dx ^ 2 + dy ^ 2,避免平方根,因为你对实际距离不感兴趣,只是接近),找到最近的邻居.
从接近图中取根平方来测量到最近邻居的距离,看它是否大于"灵敏度圆"的半径,如果是,则意味着圆内没有点.
我建议每种方法做一些基准测试; 通过优化可以轻松超越顶部.在我的适度硬件(Duo Core 2)上,在10K点内的最近邻居的天真单线程搜索重复了一千次,在Java中需要350毫秒.只要整个UI重新操作时间低于100毫秒,对于用户来说就会立即显现,记住即使是天真的搜索也可能会给你足够快的响应.
通用解决方案
最有效的数据结构取决于您计划使用的算法,时间空间权衡以及点的预期相对分布:
因此,评估数据结构是否真的不可能与算法隔离,而如果没有对任务约束和优先级的好主意,反过来很难评估.
Java实现示例
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
class Test
{
public static void main (String[] args)
{
Drawing naive = new NaiveDrawing();
Drawing skip = new SkipListDrawing();
long start;
start = System.currentTimeMillis();
testInsert(naive);
System.out.println("Naive insert: "+(System.currentTimeMillis() - start)+"ms");
start = System.currentTimeMillis();
testSearch(naive);
System.out.println("Naive search: "+(System.currentTimeMillis() - start)+"ms");
start = System.currentTimeMillis();
testInsert(skip);
System.out.println("Skip List insert: "+(System.currentTimeMillis() - start)+"ms");
start = System.currentTimeMillis();
testSearch(skip);
System.out.println("Skip List search: "+(System.currentTimeMillis() - start)+"ms");
}
public static void testInsert(Drawing d)
{
Random r = new Random();
for (int i=0;i<100000;i++)
d.addPoint(new Point(r.nextInt(4096),r.nextInt(2048)));
}
public static void testSearch(Drawing d)
{
Point cursor;
Random r = new Random();
for (int i=0;i<1000;i++)
{
cursor = new Point(r.nextInt(4096),r.nextInt(2048));
d.getNearestFrom(cursor,10);
}
}
}
// A simple point class
class Point
{
public Point (int x, int y)
{
this.x = x;
this.y = y;
}
public final int x,y;
public String toString()
{
return "["+x+","+y+"]";
}
}
// Interface will make the benchmarking easier
interface Drawing
{
void addPoint (Point p);
Set<Point> getNearestFrom (Point source,int radius);
}
class SkipListDrawing implements Drawing
{
// Helper class to store an index of point by a single coordinate
// Unlike standard Map it's capable of storing several points against the same coordinate, i.e.
// [10,15] [10,40] [10,49] all can be stored against X-coordinate and retrieved later
// This is achieved by storing a list of points against the key, as opposed to storing just a point.
private class Index
{
final private NavigableMap<Integer,List<Point>> index = new ConcurrentSkipListMap <Integer,List<Point>> ();
void add (Point p,int indexKey)
{
List<Point> list = index.get(indexKey);
if (list==null)
{
list = new ArrayList<Point>();
index.put(indexKey,list);
}
list.add(p);
}
HashSet<Point> get (int fromKey,int toKey)
{
final HashSet<Point> result = new HashSet<Point> ();
// Use NavigableMap.subMap to quickly retrieve all entries matching
// search boundaries, then flatten resulting lists of points into
// a single HashSet of points.
for (List<Point> s: index.subMap(fromKey,true,toKey,true).values())
for (Point p: s)
result.add(p);
return result;
}
}
// Store each point index by it's X and Y coordinate in two separate indices
final private Index xIndex = new Index();
final private Index yIndex = new Index();
public void addPoint (Point p)
{
xIndex.add(p,p.x);
yIndex.add(p,p.y);
}
public Set<Point> getNearestFrom (Point origin,int radius)
{
final Set<Point> searchSpace;
// search space is going to contain only the points that are within
// "sensitivity square". First get all points where X coordinate
// is within the given range.
searchSpace = xIndex.get(origin.x-radius,origin.x+radius);
// Then get all points where Y is within the range, and store
// within searchSpace the intersection of two sets, i.e. only
// points where both X and Y are within the range.
searchSpace.retainAll(yIndex.get(origin.y-radius,origin.y+radius));
// Loop through search space, calculate proximity to each point
// Don't take square root as it's expensive and really unneccessary
// at this stage.
//
// Keep track of nearest points list if there are several
// at the same distance.
int dist,dx,dy, minDist = Integer.MAX_VALUE;
Set<Point> nearest = new HashSet<Point>();
for (Point p: searchSpace)
{
dx=p.x-origin.x;
dy=p.y-origin.y;
dist=dx*dx+dy*dy;
if (dist<minDist)
{
minDist=dist;
nearest.clear();
nearest.add(p);
}
else if (dist==minDist)
{
nearest.add(p);
}
}
// Ok, now we have the list of nearest points, it might be empty.
// But let's check if they are still beyond the sensitivity radius:
// we search area we have evaluated was square with an side to
// the diameter of the actual circle. If points we've found are
// in the corners of the square area they might be outside the circle.
// Let's see what the distance is and if it greater than the radius
// then we don't have a single point within proximity boundaries.
if (Math.sqrt(minDist) > radius) nearest.clear();
return nearest;
}
}
// Naive approach: just loop through every point and see if it's nearest.
class NaiveDrawing implements Drawing
{
final private List<Point> points = new ArrayList<Point> ();
public void addPoint (Point p)
{
points.add(p);
}
public Set<Point> getNearestFrom (Point origin,int radius)
{
int prevDist = Integer.MAX_VALUE;
int dist;
Set<Point> nearest = Collections.emptySet();
for (Point p: points)
{
int dx = p.x-origin.x;
int dy = p.y-origin.y;
dist = dx * dx + dy * dy;
if (dist < prevDist)
{
prevDist = dist;
nearest = new HashSet<Point>();
nearest.add(p);
}
else if (dist==prevDist) nearest.add(p);
}
if (Math.sqrt(prevDist) > radius) nearest = Collections.emptySet();
return nearest;
}
}
我想建议创建一个Voronoi图和一个梯形图(基本上和我给这个问题的答案一样).该Voronoi图将分区多边形的空间.每个点都有一个多边形,描述最接近它的所有点.现在当你得到一个点的查询时,你需要找到它所在的多边形.这个问题称为点位置,可以通过构造梯形图来解决.
可以使用Fortune算法创建Voronoi图,该算法采用O(n log n)计算步骤并且花费O(n)空间. 本网站向您展示如何制作梯形地图以及如何查询它.你也可以在那里找到一些界限:
我的来源(上面的链接除外)是:计算几何:算法和应用程序,第六章和第七章.
在那里,您将找到有关这两种数据结构的详细信息(包括详细的证明).Google图书版仅包含您需要的部分内容,但其他链接应足以满足您的需求.如果你对这类东西感兴趣,那就买这本书(这是一本好书).