Как наиболее быстро перебрать массив?

Question

[teertsneerg]

Имеется массив, например [1 , 3 , 10 , 11 , 18 , 5] , в данном массиве указаны координаты "плиток" на прямой.

Нужно составить "Дороги", разница в координатах между плитками должна быть не более X (для примера возьмём 2), все элементы используются только один раз. Все элементы из которых нельзя составить дорогу записывать в отдельный массив, идём строго по-порядку.

1) Проходим массив первый раз, с первого элемента и получаем дорогу 1,3,5 , эти элементы использовать больше нельзя, т.е. у нас остался массив [10 , 11 , 18]

2) Проходим оставшийся массив второй раз и получаем дорогу 10, 11, остался массив [18]

3) Проходим оставшийся массив третий раз и записываем 18 в отдельный массив.

Собственно сам вопрос: как лучше организовать подобный перебор массива (с наибольшей скоростью) , с удалением использованных элементов? Элементов, естественно, в разы больше, чем в примере.

Comments

[Евгений]

я бы не удалял элементы, а формировал новые массивы, удаление дорогая операция

[di]

отсортировать массив по возрастанию, в один проход собрать дороги

Answer 1

[Eduard07]

filter

Answer 2

[di]

Я бы примерно так накатал за 15 минут

arr = [1 , 3 , 10 , 11 , 18 , 5];
x = 2;

arr.sort((a,b) => a > b);

result = [];
currentResultIndex = 0;
result.push([]);
result[currentResultIndex].push(arr[0]);

for(let i in arr) {
  if(i == 0) {
    continue;
  }
  if(arr[i] - arr[i-1] > x) {
    currentResultIndex++;
    result.push([]);
  }
  result[currentResultIndex].push(arr[i]);
}

console.log(result);

Можно код подулучшить и соптимизировать, я в js не огонь.
В result массив с дорогами.

Answer 3

[mipfikus]

может поможет:
Все способы перебора массива в JavaScript

Answer 4

[Somewhere Intech]

function* routes(coords, limit){
	coords = coords.sort( (a,b) => a - b );
	for (let i = 1; i < coords.length; i++)
		if (coords[i] - coords[i-1] > limit){
			yield coords.splice(0, i);
			i = 1;
		}
	if (coords.length > 0) yield coords;
}

let arr = [1 , 3 , 10 , 11 , 18 , 5], x = 2;

for (let route of routes(arr,x))
	console.log(`Path found: ${route.join(', ')}`)