как искать в списке элементы с расстоянием ниже F до P, не ища весь список? - PullRequest
Новая
       4

как искать в списке элементы с расстоянием ниже F до P, не ища весь список?

2 голосов
/ 05 мая 2011


Я должен искать в списке структур для каждого элемента, XZPos которого ближе к Vector2 (или PointF) P. Список упорядочен по XZPos 'x и y. Это будет выглядеть примерно так: 

Item 1 (XZPos: 0,0)<br>Item 2 (XZPos: 0,1)<br>Item 3 (XZPos: 0,2)<br>...<br>Item 12 (XZPos: 1,0)<br>Item 13 (XZPos: 1,1)<br>Item 14 (XZPos: 1,2)<br>...<br>2.249.984 elements later<br>...<br>

Теперь у меня есть точка P (4,4), и я хочу получить список структур в приведенном выше списке каждого элемента ближе к P, чем 5,66f. Мой алгоритм ищет каждый элемент в списке следующим образом: 

        List<Node> res = new List<Node>();
        for (int i = 0; i < Map.Length; i++)
        {
            Vector2 xzpos = new Vector2(Map[i].X, Map[i].Z);//Map is the list containing 2.250.000 elements
            //neighbourlength = 5,66f in our example
            if ((xzpos - pos).Length() <= neighbourlength && xzpos != pos)//looking for every item except the item which is P itself, therefore checking whether "xzpos != pos"
            {
                res.Add(new Node() { XZPos = xzpos, /*Other fields*/ }); 
            }
        }
        return res.ToArray();

Моя проблема в том, что way занимает слишком много времени для заполнения, и теперь я ищу способ найти поля, которые я ищу, не просматривая весь список. 22 секунды для поиска - СЛИШКОМ ДОЛГО . Если бы кто-то мог помочь мне довести это до 1 или 2 секунд, это было бы очень хорошо.

Спасибо за помощь, Алекс

Ответы [ 4 ]

2 голосов
/ 05 мая 2011

Ваш список отсортирован, и вы можете использовать это, чтобы уменьшить проблемное пространство.Вместо поиска по всему списку ищите подмножество списка, которое охватывает значения x в пределах 5,66f, поскольку все, что дальше максимума по одной координате, будет дальше, чем вы хотите, независимо от того, какая другая координата.Затем, если вы сохраните начальные позиции каждого значения в списке (т.е. в вашем примере элементы «0» начинаются с 1, а элементы «1» начинаются с 12), вы можете быстро перейти к той части списка, которая вам нужна.,Таким образом, вместо того, чтобы повторять пункты от 0 до 2 миллионов, вы можете вместо этого перебирать пункты с 175839 по 226835.

Пример: 

The List
1: (0,1)
2: (0,2)
3: (1,0)
4: (1,1)
5: (2,1)
6: (2,3)
7: (3,1)
8: (3,5)
9: (4,2)
10: (4,5)
11: (5,1)
12: (5,2)
13: (6,1)
14: (6,2)
15: (6,3)
16: (7,1) 
17: (7,2)   

Start Locations
(0,1)
(1,3)
(2,5)
(3,7)
(4,9)
(5,11)
(6,13)
(7,16)

Если у меня есть точка (3,5)Я хочу найти в списке точки в пределах 2, мне нужно только пройтись по точкам, где x находится между 1 и 5. Поэтому я смотрю на свои начальные местоположения и вижу, что 1 начинается с позиции 3 в списке, и5 заканчивается в положении (13 - 1).Таким образом, вместо итерации от 1 до 17, мне нужно только итерировать от 3 до 12. Если диапазон значений в ваших данных большой, но расстояние для проверки короткое, это значительно сократит количество записей, которые необходимо перебрать,

1 голос
/ 07 мая 2011

Для приведенного ниже решения есть несколько предположений.Эти предположения не указаны в вашем вопросе, и решение может потребовать корректировки.Если предположения верны, это решение очень быстро, но требует, чтобы вы сохранили данные в другой структуре.Однако, если вы можете изменить структуру, это будет выглядеть для каждой действительной точки в (почти) постоянном времени.То есть время, необходимое для нахождения M действительных точек в наборе, содержащем в общей сложности M точек, зависит только от N.

Допущения следующие:

  • Для значенийX и Y
  • В списке нет повторяющихся точек

`private IEnumerable> GetPointsByDistance (int xOrigin, int yOrigin, double maxDistance) {

                    var maxDist = (int) Math.Floor(maxDistance);
                    //Find the lowest possible value for X
                    var minX = Math.Min(0, xOrigin - maxDist);
                    //Find the highest possible value for X
                    var maxX = Math.Min(MaxX, xOrigin + maxDist);
                    for (var x = minX; x <= maxX; ++x){
                        //Get the possible values for Y with the current X
                        var ys = points[x];
                        if (ys.Length > 0){
                            //Calculate the max delta for Y
                            var maxYDist =(int)Math.Floor(Math.Sqrt(maxDistance*maxDistance - x*x));
                            //Find the lowest possible Y for the current X
                            var minY = Math.Min(0, yOrigin - maxYDist);
                            //Find the highest possible Y for the current X
                            var maxY = Math.Min(ys.Length, yOrigin + maxYDist);
                            for (var y = minY; y <= maxY; ++y){
                                //The value in the array will be true if a point with the combination (x,y,) exists
                                if (ys[y]){
                                    yield return new KeyValuePair<int, int>(x, y);
                                }
                            }
                        }
                    }
                }`

Theвнутреннее представление точки в этом коде bool[][].Значение будет истинным, если индексы двух массивов - это точки, включенные в набор.Например, баллы [0] [1] будут истинными, если в наборе было шесть баллов, которые вы включили в сообщение, а баллы [0] [3] были бы ложными.

Если предположения не выполненыта же самая идея может все еще использоваться, но потребует настройки.Если вы опубликуете, какими должны быть предположения, я обновлю ответ на вопрос.

Предположение, которое не должно выполняться, состоит в том, что точки близки к последовательным.Если это не так, это будет довольно жадным, когда дело доходит до памяти.Изменения могут быть сделаны, если точки не (близки) к последовательным, и снова опубликуйте инварианты, если мои предположения неверны, и я обновлю.

0 голосов
/ 05 мая 2011

Эта проблема связана с этим:

http://en.wikipedia.org/wiki/Nearest_neighbor_search

Найдите сублинейные решения.

Также взгляните на этот вопрос

какая структура данных подходит для запроса «всех точек на расстоянии d от точки p»

0 голосов
/ 05 мая 2011

Понятия не имею, что делает ваш оригинальный код.Я вижу, что вы определили x и y и никогда не используете их, и вы ссылаетесь на pos, но это не определено.Итак, вместо этого я собираюсь взять словесное описание проблемы, которую вы пытаетесь решить

Теперь у меня есть точка P (4,4), и я хочу получить список структур в приведенном выше списке каждого элементаближе к P, чем 5,66f.

и решите его.Это легко: 

var nearbyNeighbors = Map.Where(
    point => (point.X - 4) * (point.X - 4) +
             (point.Z - 4) * (point.Z - 4) <
             5.66f * 5.66f
    );

foreach(var nearbyNeighbor in nearbyNeighbors) {
    // do something with nearbyNeighbor
}

Здесь я предполагаю, что вы используете стандартную евклидову норму.

Чтобы использовать тот факт, что коллекция отсортирована по лексикографическому признаку:

Двоичный поиск до |point.X - 4| >= 5.66.Это разбивает список на два смежных подсписка.Выкиньте список с помощью |point.X - 4| >= 5.66.От оставшегося подсписка бинарный поиск до |point.Y - 4| >= 5.66 Это разбивает оставшийся подсписок на два смежных подсписка.Выкиньте подсписок с |point.Y - 4| >= 5.66.Затем выполните линейный поиск по оставшемуся подсписку.

...