Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 22.07.2009, 21:54
Аватар для Shasoft
Профессор
Отправить личное сообщение для Shasoft Посмотреть профиль Найти все сообщения от Shasoft
 
Регистрация: 03.03.2009
Сообщений: 156

Быстрый поиск объектов
Есть такая задача:
Множество объектов. Каждый объект имеет числовой ключ (вещественный).
Нужна функция, которая позволяет определить по заданному числовому значению список объектов, ключ которых больше/меньше заданного числа.
Самое простое, что приходит в голову, это, конечно, взять массив объектов и отсортировать по ключу. Тогда очень просто найти нужные объекты. Но дело в том, что объекты добавляются не все сразу, а по одному. Т.е. при вставке нового объекта нужно изменять массив. А это операция вроде не самая быстрая (по крайней мере для того же С++).

Ещё есть идея с бинарными деревьями. Но прежде чем копать, рушеил поинтересоваться у спецов javascript: может есть какие-то библиотеки для решения такой задачи? Или может вставка нового элемента в середину массива на javascript операция быстрая?

P.S. Количество объектов теоретически от 0 до много. Это решение буду прикручивать к google и яндекс map. И каждый объект - это метка на карте. К примеру пользователь может добавить на карту ВСЕ дома города Москвы. С учетом наличия около 4500 улиц количество домов может быть весьма приличным.
Ответить с цитированием
  #2 (permalink)  
Старый 22.07.2009, 22:12
Профессор
Отправить личное сообщение для Dmitry A. Soshnikov Посмотреть профиль Найти все сообщения от Dmitry A. Soshnikov
 
Регистрация: 25.02.2008
Сообщений: 707

Сообщение от Shasoft
Или может вставка нового элемента в середину массива на javascript операция быстрая?
Зависит от массива, потестируйте на вашем случае.
__________________
Тонкости ECMAScript
Ответить с цитированием
  #3 (permalink)  
Старый 22.07.2009, 22:30
Аватар для Shasoft
Профессор
Отправить личное сообщение для Shasoft Посмотреть профиль Найти все сообщения от Shasoft
 
Регистрация: 03.03.2009
Сообщений: 156

Сообщение от Dmitry A. Soshnikov Посмотреть сообщение
Зависит от массива, потестируйте на вашем случае.
Тестировать нужно на IE, FF, Opera (как минимум), потому и спрашиваю у гуру, чтобы время съэкономить. Размер массива в 50-150 тысяч объектов меня почему-то сразу наводит на мысль, что будет тормозить.
Хотя, на таких объемах при добавлении по одному объекту наверное всё-равно будет тормозить. Так то по-любому нужно будет делать пакетное добавление.
Ответить с цитированием
  #4 (permalink)  
Старый 23.07.2009, 09:54
Аватар для Shasoft
Профессор
Отправить личное сообщение для Shasoft Посмотреть профиль Найти все сообщения от Shasoft
 
Регистрация: 03.03.2009
Сообщений: 156

Как показали тесты никаких хитрых алгоритмов не требуется, так как скорость прогонки проверки в цикле достаточно большая. Такой код:
//------------------------------------
 id = "init";
 console.time(id);
 var arr = new Array(100000);
 for(var i=0;i<arr.length;i++)
  arr[i] = Math.random()*100;
 console.timeEnd(id);
 //------------------------------------
 id = "if/else";
 console.time(id);
 for(var i=0;i<arr.length;i++)
  if(arr[i]>0)
//   for(var j=0;j<10;j++)
    arr[i] += 1;
 console.timeEnd(id);

Время выполнения:
Код:
init: 80ms 
if/else: 41ms
Ответить с цитированием
  #5 (permalink)  
Старый 23.07.2009, 15:48
Аватар для x-yuri
Отправить личное сообщение для x-yuri Посмотреть профиль Найти все сообщения от x-yuri
 
Регистрация: 27.12.2008
Сообщений: 4,201

Сообщение от Shasoft
Нужна функция, которая позволяет определить по заданному числовому значению список объектов, ключ которых больше/меньше заданного числа.
если индексы без пропусков, то slice
Ответить с цитированием
  #6 (permalink)  
Старый 24.07.2009, 13:48
Аватар для Shasoft
Профессор
Отправить личное сообщение для Shasoft Посмотреть профиль Найти все сообщения от Shasoft
 
Регистрация: 03.03.2009
Сообщений: 156

Решение найдено. Никакой вставки вообще делать не буду, так как простой перебор дает приличную скорость. При этом скорость добавления вообще супер-пупер-быстрая (просто push в конец массива)

Хотя, был удивлен тем, что конструкция вида
for(var i=0;i<arr.length;i++)

работает быстрее
for(var i in arr)

Почему-то всегда считал, что in быстрее цикла работает. Но при тесте в FF получил 50ms против 125ms
Ответить с цитированием
  #7 (permalink)  
Старый 24.07.2009, 14:41
Новичок на форуме
Отправить личное сообщение для Kolyaj Посмотреть профиль Найти все сообщения от Kolyaj
 
Регистрация: 19.02.2008
Сообщений: 9,177

Это в принципе объяснимо, for-in перебирает все свойства объекта (у массивов много других свойств, в том числе методы) и проверяет у них свойство enumerable, в то время как for сразу берет только нужные. Ну это чисто интуитивно.
Ответить с цитированием
  #8 (permalink)  
Старый 30.07.2009, 05:28
Аспирант
Отправить личное сообщение для hp5741 Посмотреть профиль Найти все сообщения от hp5741
 
Регистрация: 22.04.2009
Сообщений: 34

...
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск на странице no_name jQuery 4 07.09.2010 13:26
Динамическая обработка - поиск по 2 и более символов bavin Я не знаю javascript 1 26.05.2009 18:02
ООП: как создавать наследника от встроенных объектов? Langalier Общие вопросы Javascript 17 02.02.2009 17:07
Поиск в массиве через JavaScript Noran Общие вопросы Javascript 0 10.08.2008 17:31
Как определить включен ли поддержака объектов ActoveX feodul Events/DOM/Window 5 02.06.2008 12:04