Cómo mejoro este algoritmo simple? - JavaScript

M

Me han dicho que debería usar lo menos posible los for loops clásicos pero no se me ocurre otra forma de hacer el ejercicio entonces. Creo que el codigo se explica bastante bien lo que quiero hacer, pero cualquier cosa me preguntáis. Gracias! :)


const arr = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 5, 8, 8]
const repeatedNums = []

for (let i = 0; i <= arr.length; i++) {
  for (let j = i + 1; j <= arr.length; j++) {
    if (arr[i] === arr[j]) {
      repeatedNums.push(arr[i])
    }
  }
}

console.log(repeatedNums) // [100, 500, 5, 8]

-Yepeto-

Puedes ordenar primero la lista de menar a mayor, empiezas por el primer elemento el for y si la posición siguiente es el mismo número tiene un repetido, si no, pasas al número siguiente. De esta forma, solo tienes que recorrer el array una vez.

2
B

Piensa lo que quieres hacer:

Saber si un elemento de un array se encuentra dentro de otro, seguro que hay una función para hacer lo que buscas...

themaz
const arr = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 5, 8, 8];
const repeatedNums = arr.filter(function(item, pos, self) {
    return self.indexOf(item) < pos;
});
console.log(repeatedNums);
2 respuestas
M

#4 Vale gracias, algo así buscaba, suponía que con el filter valía pero aún no controlo muy bien el tema callbacks... efectivamente funciona pero no he tenido algo presente, y es que solo tiene en cuenta los números que van seguidos, es decir, si vuelvo a repetir un número más tarde en el array, se añade el número repetido al segundo array. He pensado que junto a tu solución, usando un Set puedo solucionar ese problema, pero no sé si estaré complicando demasiado todo para esta "tontería"...

const arr = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 8, 5, 8, 8, 100, 130];
const repeatedNums = arr.filter(function (item, pos, self) {
  return self.indexOf(item) < pos;
});

const removedRepeatedNums = new Set();
for (let num of repeatedNums) {
  removedRepeatedNums.add(num)
}

console.log(Array.from(removedRepeatedNums)) // [100, 500, 5, 8, 130]
2 respuestas
AkA7

#5 Puedes hacer la operación del Set sin necesidad de iterar.

[...new Set(repeatedNums)].

De hecho si expresas o declaras repeatedNums como una función puedes reutilizarla para otros arrays.

const array = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 8, 5, 8, 8, 100, 130];
const repeatedNums = arr => arr.filter(function(item, pos, self) {
  return self.indexOf(item) < pos;
});

console.log(repeatedNums(array)) // Todos los duplicados
console.log([...new Set(repeatedNums(array))]); // Duplicados unicos
1 1 respuesta
B
const repeatedNums = arr.filter(function(item, pos, self) {
 return (pos===self.indexOf(item)) ? self.slice(pos+1).indexOf(item)!==-1 : false;
})

Repetidos únicos...

1 respuesta
B

Otra forma por aquí...

const input = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 8, 5, 8, 8, 100, 130];
const repeatedNums = []; 
for (let i=input.length-1; i>0; --i) {
    const cur_num = input[i]; // Almacenamos el valor de la lista ya que lo vamos a usar varias veces...
    if (cur_num === input[i-1] && repeatedNums.indexOf(cur_num) === -1) { // Si el numero anterior es igual al numero actual es que está repetido y es consecutivo, lo añadimos a la lista de repetidos si no existe ya
        repeatedNums.push(cur_num); 
        --i; // Como sabemos que el número anterior es igual pues nos lo saltamos
    } 
} 
1 respuesta
PaCoX

lo mas optimo

const arr = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 5, 8, 8]
const repeatedNums =[100,500,5,8]
console.log(repeatedNums)

:clown: al toque

19 1 respuesta
Camperito

#9 La gente se complica la vida , ahahahha

EnderFX
const arr = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 5, 8, 8]
const repeatedNums = arr.filter((el, i) => arr.lastIndexOf(el) !== i)
console.log(repeatedNums) // [100, 500, 5, 8]
S

Si te dicen que quites el doble for será por que el algoritmo es muy ineficiente, tiene un coste exponencial. #4, #5 #6, #7 y #8 Tienen el mismo problema.

Para encontrar los duplicados con un coste lineal necesitas usar un Set, introducir los elementos y comprobar si ya existen.

const arr = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 5, 8, 8];
const findDuplicates = arr => {
    const set = new Set();
    const duplicates = [];
    arr.forEach(item => {
        if (set.has(item)) {
            duplicates.push(item);
        }
        set.add(item);
    });
    return duplicates;
}
console.log(findDuplicates(arr));

PD: El #9 es insuperable.

2 2 respuestas
B

#12 https://jsben.ch/PH80M

1 respuesta
S

#13 Ese test esta usando una entrada de datos diferente al problema inicial. (el mismo numero 2k veces), por lo que no es representativo de nada.

Mira, cuando hay bastantes duplicados (a pares).

https://jsben.ch/FrW9A

Ni te cuento ya si desordenas la entrada. Esto es por que tu algoritmo tiene un coste exponencial O(n2), dentro de un loop hace otro por cada elemento de la entrada. Para tu entrada cocinada estaba encontrando el 666 todo el tiempo al inicio del segundo bucle y falsea el resultado.

1
B

Representativo? No hay condiciones iniciales definidas en la data, así que

B

#12 ¿de donde sacas que "has" es más optimo que "indexOf"?

Con un test de 100.000.000 de registros en chromium:
Test_Array.indexOf(): 62.173095703125 ms
Test_Set.has(): 2131.112060546875 ms

1 respuesta
S

#16
Un Set es una estructura de datos con búsqueda en tiempo constante a sus elementos O(1) mientras que un array tiene que comprobar uno por uno los elementos O(n).
No sé que test has hecho pero esta mal.

1 respuesta
B

#17
https://262.ecma-international.org/6.0/#sec-set.prototype.has
https://262.ecma-international.org/6.0/#sec-samevaluezero

1 respuesta
S

#18
Muy interesante, sin embargo Set está implementado usando hash tables. Por eso tiene tiempo constante de acceso.

Test:
https://jsben.ch/1MqCW

1 respuesta
B

#19 El test está incorrecto... le es más sencillo a "console.log" trabajar con booleanos que con Number.

1 respuesta
S

#20

No
https://jsben.ch/29gp4

1 respuesta
B

#21 Ya veo... debe ser por culpa de TurboFan que anda "trucando" los resultados :/

Mi test está incorrecto en el sentido que voy buscando el valor reduciendo la distancia... entonces en algunos casos le es más sencillo a indexOf. Tu test es el caso más duro pues siempre fuerzas a indexOf a recorrer todo, mientras que "has" tira de hash-table como bien has dicho.

¿Has comprobado añadiendo elementos?

** La cosa cambia si en tu test usamos 'lastIndexOf' jejeje

B

https://jsben.ch/SxR74

S

Ese algoritmo es mejor al anterior, pero sigue siendo peor que usar un Set. Ordenar un array tiene un coste medio de nlogn, peor que linear.
Si en la prueba te sale mejor es por que el dato de entrada está ordenado con anterioridad al test. Si lo desordenas un poco para que el sort tenga que trabajar veras que es más lento.

1 1 respuesta
B
const repeatedNums = new Int16Array(arr).sort().filter(function(item, pos, self)
      { return item === self[pos+1] && item !== self[pos-1]; }
);

Int16Array + random https://jsben.ch/zLOsT

desu

#24 si pero no, depende de varios factores

  • optimizas rendimiento, memoria o escalabilidad
  • tus datos que estructura tienen, analisis de datos, tipos de datos

hay casos en que el set sera peor incluso para entradas muy grandes

que implementacion/algoritmo de set vas a usar? has resuelto solo para integers positivos? cualquier valor de int32 o int64? o tambien para []byte? has pensado en paralelizar y usar un filtro probabilistico para detectar colisiones? que hardware estas asumiendo que tiene tu maquina?

si se admite margen de error en la resupesta del 0.000...% dependiendo del tama;o de N, el OP te lo resuelvo con 1 for que ni termina. eso si es rapido. checkeas hasta que tu % de acierto es superior a tu budget de error. return.

de hecho segun el caso de uso de ese algoritmo, si es algo para repetidos sobre caches (sets) no hacen falta ningun for, segun la distribucion te puedo ir sacando randoms del array. y esto es muy habitual en caches distribuidas en el mundo real. yo he implementado algo parecido.

sobre el utlimo caso en la universidad se ense;a con el tema de NP, no podemos resolverlo en tiempo polinomial pero si comprovarlo, generas soluciones rapido y las compruevas en P. si tu algoritmo es "suficientemente bueno" aproximaras una solucion buena en tiempo P de un NP. de vuelta al OP, si comprovar que 1 elemento esta repetido o no es gratis, suele ser un filtro, (lo dificil es devolver TODOS los repetidos) es mejor devolver 1 random de la lista y comprovarlo, 2 operaciones, que no tratar de ejecutar 1 operacion buena. mejor 2 malas rapido que 1 buena lento. "eventual consistency" y esas cosas.

2 respuestas
W0rd

comprovar

laZAr0

Es un fallo grosero, pero no te quedes con eso hombre.

Exor720

#26 No he entendido nada julio.

Soulscx

#26 no vas a encontrar un algoritmo mejor que el que ha planteado sarwaz de coste lineal. Una vez tengas el algoritmo si tienes 1000 procesadores, infinitos caches y suerte en la entrada de datos te dara la sensacion que tiene un coste menor, pero no es así.
Y todas tus propuestas no hacen más q complicar un problema muy sencillo de resolver.

1 respuesta