Автокэш

Я тут недавно получил комментарий от человека со странным ником, он сказал мне, что мой autocomplete конечно всем хорош, но имеет один существенный недостаток. Получив данные от сервера через AJAX, при уточнении критерия поиска он снова обращается к серверу, вместо того чтобы фильтровать уже полученные данные.

Приведу пример. Мы ищем города начинающиеся на ‘К’ и получаем от сервера ответ [‘кардуба’,’кардижопа’,’казупий’,’кипир’] :) При вводе второй буквы мы уже не обращаемся к серверу, а фильтруем то, что получили прошлый раз, например вторая буква ‘А’ тогда ‘КА’ = [‘кардуба’,’кардижопа’,’казупий’]. При вводе третьей буквы все повторяется ‘КАР’ = [‘кардуба’,’кардижопа’].

Я вижу два выхода из этой ситуации.

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

Второй способ полон геморроя и собственно его я и буду дальше описывать. Для его реализации понадобиться намного больше память, но намного меньше времени, я не могу сказать, что лучше память или время, но могу сказать, что второй способ хотя бы напряг мои мозги. Так вод вам понадобиться: вазелин офисный, пол литра, руки прямые, две штуки и терпение, много терпения, хотя нет, руки, пожалуй, должны сгибаться в локтях….

Итак что собственно делаем. Вводим первую букву ‘К’, получаем от сервера ответ и сохраняем в переменной cache в таком виде.


cache =  {
	'К':['кардуба','кардижопа','казупий','кипир']
};

Вводим вторую букву ‘А’, теперь у нас строка ‘КА’, выбираем все ключи нашего кэша и начиная с самого длинного начинаем искать вхождение ключа в строку, если находим берем массив-значение и фильтруем а потом сохраняем результат с новым ключом, в результате.


cache = {
	'К':['кардуба','кардижопа','казупий','кипир'],
	'КА':['кардуба','кардижопа','казупий']
};

Еще раз та же процедура вводим ‘Р’, строка ‘КАР’, берем ключи объекта, разворачиваем в обратном порядке (чтобы сначала шли самые длинные), и ищем их вхождение в строку, если нашлось то снова фильтруем и сохраняем.


cache = {
	'К':['кардуба','кардижопа','казупий','кипир'], 
	'КА':['кардуба','кардижопа','казупий'], 
	'КАР':['кардуба','кардижопа']
};

Как видите одни и те же города находятся в массиве много раз, это есть не очень экономно с точки зрения памяти но зато к ним очень быстро можно получить доступ. Реализация этого метода тоже весьма муторная и я был бы не против сильно её заоптимайзить но вот что-то никак…



var cache = {'':['кардуба','кардижопа','казупий','кипир','другой город','еще село']},
	mask = ['к','ка','кар'];
	
function check(mask){
	// пытаемся быстро выйти
	if (cache[mask])
		return cache[mask]; 
	
	// инициализируем переменные
	var map = [], array = [];
	
	// получаем массив ключей
	for(var item in cache)
		array.push(item);
	// разворачиваем самыми длинными вначало
	array = array.reverse();
	
	// ищем...
	for(var item in array)
		// если вхождение ключа в строку имеет нулевую позицию
		if(!mask.indexOf(array[item])){
			// фильтруем
			for(var word in cache[array[item]])
				// если вхождение строки в элемент иммеет нулевую позицию
				if (!cache[array[item]][word].indexOf(mask))
					// сохраняем
					map.push(cache[array[item]][word]);
			break;
		}
	alert(map);
	cache[mask] = map
}

for (m in mask)
	check(mask[m]);
	

Вот такой вот алгоритм получился… Но это все было бы очень хорошо если бы наш бэкэнд (я имею ввиду сайт Киевстара) не возвращал только первых 500 найденных записей на каждый запрос, то есть если всего найдено 700 записей, то будут показаны только 500, причем первых найденных базой а не первых в алфавитном порядке.

Такое кэширование я конечно включу в следующий релиз autocomplete, но применять его сам вряд ли буду.