最優搜索在給定區域（web服務）

我有一種算法&性能問題與Java解決2D點。我收集了大量的2D點（假設其中大約有10萬個點）。我想獲得一組在搜索點SP（X_sp，Y_sp）周圍給定區域中的那些，以便我想獲得滿足條件的點P（xy）：最優搜索在給定區域（web服務）

x是X_sp之間 - constValue和X_sp + constValue和Y是Y_sp之間 - constValue和Y_sp + constValue

爲了讓您的數字關係的想法，constValue會像2,5或10，和X，Y將範圍在0到1000之間。它意味着是一個web服務，因此必須考慮到同時搜索許多不同點的可能性。

由於這些固定點（不改變由於計算或東西），我認爲這將是最佳的，提供由X和另外一個分類對象之一名單，而是由Y.排序，那我就首先獲取X範圍內的點，然後使用引用從另一個列表中獲取這些點的集合（按Y排序）。然後，我將通過Y縮小這個選擇範圍，並在結果中獲得特定區域中的點。

我不知道Java的由內而外的，所以我想和你商量最優化的方法。我應該使用哪些對象來存儲排序的點，以便快速搜索範圍內的對象？或者，也許我必須爲此任務實現我的自定義算法？另外，在存儲數據庫中的點時，SQL查詢是否足夠快以提供結果？或者，也許NoSQL dbs對此更好？

我要履行我自己的測試，但我正在尋找一個首發人選。

來源

2017-10-10 przemulala

這太寬泛了。 – tnw

除非您對此問題的嘗試解決方案有具體問題，否則此問題不適合SO。這不是免費的編碼服務。 –

你在那裏有一個問題陳述。首先找到一個優化的算法來完成任務，然後如果您需要幫助優化您的代碼，請到這裏。 – digidude

我可能會使用一個TreeMap<Integer, TreeSet<Integer>>，其中關鍵的地圖是x協調和各x座標，你有y座標列表。然後，您可以使用floorEntry和ceilingEntry來查找在您的範圍內的x座標。然後，每TreeSet<Integer>組你，你可以使用ceiling和能得到相應的條目。

當然，這只是給你你的盒子（四角）的邊界的座標。但TreeSet也有一個subset，它會給你一個值的範圍。你將不得不使用這兩次;一次的x座標列表（你可以使用地圖的keySet方法按鍵）是你的範圍之內，然後爲每個x協調，是y座標的範圍之內。因此，僞代碼將是排序是這樣的：

List<Point> result = new ArrayList<>(); 
int lowerX = points.ceilingKey(x - c); 
int upperX = points.floorKey(x + c); 
for each x coordinate in points.entrySet().subset(lowerX, upperX) 
    TreeSet<Integer> yCoordinates = points.get(x); 
    lowerY = yCoordinates.ceiling(y - c); 
    upperY = yCoordinates.ceiling(y + c); 

    for each y coordinate in yCoordinates.subset(lowerY, upperY) 
     result.add(new Point(x, y))

我沒有測試過這一點，所以有可能是一些錯誤或什麼我已經錯過了。讓我知道，我會糾正答案。

的floor和ceiling電話是log(n)我相信 - 這是你得到的性能優勢，因爲如果你使用一個清單，這將是O(n)看這件事。

注：我不知道這是否是最高效的。 SO通常不是這樣一個開放式問題的地方，所以你可能在其他地方有更多的運氣。

來源

2017-10-10 15:24:55

最優搜索在給定區域（web服務）

回答

相關問題