Разбить массив по узким условиям и составить массив массивов, поиск лучшего решения

292

25 октября 2017, 07:11

Всем здравствуйте и добрый день.

Сегодня столкнулся с интересной задачей и хочу поделиться со знатоками, в поиске наиболее интересного варианта.

Задача следующая:

Получаем массив объектов с двумя ключами, время и значение. Необходимо составить из него многомерный массив, где массив второго уровня будет собран исходя из того, что время между индексами не больше чем N.

У меня вышел гомункул, время исполнения которого не составляет более ~0.07

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

const data = [ 
	{'time': '2017-10-18T12:42:04+03:00', 'id': 73}, 
	{'time': '2017-10-18T12:38:04+03:00', 'id': 86}, 
	{'time': '2017-10-18T12:45:04+03:00', 'id': 43}, 
	{'time': '2017-10-18T12:39:24+03:00', 'id': 92}, 
	{'time': '2017-10-18T12:37:04+03:00', 'id': 70}, 
	{'time': '2017-10-18T12:46:04+03:00', 'id': 123}, 
	{'time': '2017-10-18T12:36:53+03:00', 'id': 43}, 
	{'time': '2017-10-18T12:43:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T16:43:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T16:44:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T16:45:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T16:46:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T22:46:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T22:47:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T22:48:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T22:49:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T22:50:04+03:00', 'id': 64}, 
	{'time': '2017-10-18T12:40:04+03:00', 'id': 93}, 
	{'time': '2017-10-18T12:44:04+03:00', 'id': 63} 
]; 
 
console.time('time'); 
data.sort((a, b) => new Date(a.time).getTime() < new Date(b.time).getTime() ? -1 : 1) 
 
let sortedArrays = [] 
while (true) { 
   let arr = [] 
   arr.push(data[0]) 
   if (!data.length) { 
	 break 
   } else { 
	 for (let i = 1; i < data.length; i++) { 
	   const firstI = arr[0].time.slice(11, 13) * 60 + +arr[0].time.slice(14, 16) 
	   let nextI = data[i].time.slice(11, 13) * 60 + +data[i].time.slice(14, 16) 
	   if (firstI + i === nextI) { 
		 arr.push(data[i]) 
	   } else { 
		 break 
	   } 
	 } 
	 data.splice(0, arr.length) 
	 sortedArrays.push(arr) 
   } 
} 
console.timeEnd('time'); 
console.log(sortedArrays);

Answer 1

но хотелось бы увидеть мысли и решения других...

Не берусь сказать какие отличия есть по скорости выполнения от кода автора (по крайней мере, console.time показывает одинаковый порядок времени выполнения).

Алгоритм следующий:

на основе исходного массива строится новый с добавлением в каждый элемент поля, содержащего время записи в unix time
массив сортируется по полю времени unix
из отсортированного массива формируется новый массив в который последовательно добавляются массивы, содержащие записи, интервалы времени между которыми не превышают интервал N

последний массив является конечным и выводится

const data = [ 
	{ time: "2017-10-18T12:42:04+03:00", id: 73 }, 
	{ time: "2017-10-18T12:38:04+03:00", id: 86 }, 
	{ time: "2017-10-18T12:45:04+03:00", id: 43 }, 
	{ time: "2017-10-18T12:39:24+03:00", id: 92 }, 
	{ time: "2017-10-18T12:37:04+03:00", id: 70 }, 
	{ time: "2017-10-18T12:46:04+03:00", id: 123 }, 
	{ time: "2017-10-18T12:36:53+03:00", id: 43 }, 
	{ time: "2017-10-18T12:43:04+03:00", id: 64 }, 
	{ time: "2017-10-18T16:43:04+03:00", id: 64 }, 
	{ time: "2017-10-18T16:44:04+03:00", id: 64 }, 
	{ time: "2017-10-18T16:45:04+03:00", id: 64 }, 
	{ time: "2017-10-18T16:46:04+03:00", id: 64 }, 
	{ time: "2017-10-18T22:46:04+03:00", id: 64 }, 
	{ time: "2017-10-18T22:47:04+03:00", id: 64 }, 
	{ time: "2017-10-18T22:48:04+03:00", id: 64 }, 
	{ time: "2017-10-18T22:49:04+03:00", id: 64 }, 
	{ time: "2017-10-18T22:50:04+03:00", id: 64 }, 
	{ time: "2017-10-18T12:40:04+03:00", id: 93 }, 
	{ time: "2017-10-18T12:44:04+03:00", id: 63 }, 
]; 
 
console.time("time"); 
 
const N = 100000; 
let last = -9999999999999; 
const mdata = data 
	.map(e => { 
		return { time: e.time, utime: Date.parse(e.time), id: e.id }; 
	}) 
	.sort((a, b) => a.utime - b.utime) 
	.reduce((p, c) => { 
		if (c.utime - last > N) { 
			p.push([]); 
		} 
		p[p.length - 1].push({ 
			time: c.time, 
			id: c.id, 
		}); 
		last = c.utime; 
		return p; 
	}, []); 
 
console.timeEnd("time"); 
 
console.log(mdata);