эффективно оценить, если объект JavaScript содержит строку

Question

У меня есть следующий пример на стороне клиента объект:

var obj = { 
"locations": [ 
    [ 
     37.502917, 
     -122.501335 
    ], 
    [ 
     37.494473, 
     -122.499619 
    ], 
    [ 
     37.484394, 
     -122.455673 
    ] 
], 
"types": [ 
    [ 
     "type1" 
    ], 
    [ 
     "type2" 
    ], 
    [ 
     "type3" 
    ] 
    ] 
}; 

Местоположение может содержать до 50 значений. Запрос ajax возвращает набор новых местоположений, и мне нужно оценить, находятся ли они в пределах obj.locations. Каждое новое возвращается место является строкой, например:

var test = 37.502917 + ',' + -122.501335; 

Для каждого места я могу перебирать текущими и проверить, если он присутствует:

for(var i = 0; i < obj.locations.length; i++) { 
    if(obj.locations[i] == test){ 
     console.log('Found!'); 
    } 
} 

Есть ли более эффективный способ сделать это как итерация через объект для каждого нового местоположения кажется неэффективной?

---

EDIT: Мое решение:

Я решил взять объект местоположения и повернуть на строку, а затем оценить каждый из входящих строк:

var test = -121.60183 + ',' + 38.025783; 
var cords = [].concat([], obj.locations).toString(); 
if(cords.indexOf(test) !== -1) { 
    console.log('found! '); 
} 

Answer 1

Это, пожалуй, одна из самых старых проблем в информатике - что-то в этом роде.

Прежде всего, вы должны спросить себя, стоит ли беспокоиться. Возможно, потребуется 1 мс, чтобы найти местоположение с линейным поиском, но 0,5 мс с каким-то оптимизированным поиском. Так, это стоит того?

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

Другой подход - создать некую хэш-таблицу. Вы можете использовать для этого объекты JavaScript со свойствами как хэш-ключи. Самый простой подход - использовать в качестве ключа свойства lat+long, но теперь вы только что переключили проблему эффективности на эффективность поиска JS ключей в больших объектах.

Вы можете создать свой собственный подход, похожий на хэш, где все местоположения с одной и той же целой частью широты хранятся в виде массива под хешем 37. Тогда производительность определяется временем, затраченным на поиск хэш-ключа в таблице, а затем просматривая меньшее количество мест в своем массиве.

Продолжая, если производительность действительно является проблемой, вы можете построить какую-то древовидную структуру для оптимального поиска.В какой-то момент вам нужно начать торговать между стоимостью строительства и обновления дерева, а также экономией от поиска вещей с помощью дерева.

Answer 2

Это точно неэффективен , но если вам не придется иметь дело с тысячами этих объектов, он не повесит ваш браузер.

Однако вы можете индексировать местоположения в ассоциативном массиве, а затем использовать их для проверки наличия или отсутствия элемента.

Например, вы могли бы добавить объект locations_index к объекту, например:

 
var obj = { 
"locations": [ 
    [ 
     37.502917, 
     -122.501335 
    ], 
    [ 
     37.494473, 
     -122.499619 
    ], 
    [ 
     37.484394, 
     -122.455673 
    ] 
], 
"locations_index" : { 
    "37.502917,-122.501335" : true, 
    "37.494473,-122.499619" : true, 
    // ... 
}, 
"types": [ 
    [ 

Затем вы можете проверить, если он или нет в location_index с:

if (obj.locations_index["37.502917,-122.501335"]) { 
    // It's already there 
} else { 

Очевидно, вам нужно позаботиться о добавлении новых мест (и удалении тех, которые вы удаляете) из «реального» массива и «индекса».