¿Cómo puedo restar estas listas más rápido?

Quiero restar dos ArrayLists para poder tener al niño que no esté en la otra lista.

Lo hago de esta manera:

removeIDs=(ArrayList<Integer>) storedIDs.clone(); removeIDs.removeAll(downloadedIDs); downloadIDs=(ArrayList<Integer>) downloadedIDs.clone(); downloadIDs.removeAll(storedIDs); 

El problema es que ambas listas contienen 5000childs y toma casi 4 segundos en mi androidphone.

¿Hay una manera rápida de hacer esto? ¿Es el uso de conjuntos más rápido? (No tengo valores duplicados en las listas)

Desarrollar una aplicación para Android

Use HashSet en lugar de ArrayList a menos que necesite mantener el orden.

La eliminación de un elemento requiere una exploración de la Lista completa para implementaciones de lista, un HashSet por comparación es sólo el cálculo de un código hash y luego la identificación de un cubo objetivo.

Los juegos deben ser más rápidos. En este momento, es básicamente haciendo un bucle n ^ 2. Se realiza un bucle sobre cada elemento de los ID de eliminación y comprueba si ese identificador está en los ID descargados, lo que requiere buscar en toda la lista. Si los IDs descargados se almacenaban en algo más rápido para buscar, como un HashSet, esto sería mucho más rápido y se convertiría en un O (n) en lugar de O (n ^ 2). También podría haber algo más rápido en la API de colecciones, pero no lo sé.

Si necesita guardar un pedido, puede usar un LinkedHashSet en lugar de un HashSet normal, pero agregará algo de memoria oída y un poco de rendimiento para insertar / quitar elementos.

Estoy de acuerdo con la recomendación de HashSet a menos que los Integer IDs encajen en un rango relativamente pequeño. En ese caso, haría un benchmark utilizando cada uno de HashSet y BitSet, y de hecho usaré lo que sea más rápido para sus datos en su entorno.

En primer lugar, estoy dando mi disculpa por la larga respuesta. Si me equivoco en cualquier momento, siempre es bienvenido para corregirme. Aquí estoy comparando algunas opciones de resolver la solución

OPCIÓN 1 <ArrayList>:

En el código que utilizó el método ArrayList.removeAll permite buscar en el código de removeAll

El código fuente de removeAll

 public boolean removeAll(Collection<?> c) { return batchRemove(c, false); } 

Por lo que necesita saber qué está en el método batchRemove . Aquí está el enlace . La parte clave aquí si puedes ver

 for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; 

Ahora permite mirar en el método contains que es sólo un envoltorio de método indexOf . Enlace En el método indexOf existe una operación O (n). (Notando sólo una parte aquí)

  for (int i = 0; i < size; i++) if (elementData[i]==null) return i; 

Así que sobre todo es un

O (n ^ 2)

Operaciones en el removeAll

OPCIÓN 2 <HashSet>: anteriormente escribí algo aquí pero parece que estaba equivocado en algún momento para quitar esto. Mejor tomar la sugerencia de un experto sobre Hashset. No estoy seguro en su caso si hashmap será una solución mejor. Así que estoy proponiendo otra solución

OPCIÓN 3 <Mi Sugerencia Puede probar>:

Paso 1: si los datos están ordenados, entonces no hay necesidad de este paso otro tipo de la lista que se restará (segunda lista)

Paso 2: para cada elemento de la lista no ordenada ejecutar una búsqueda binaria en la segunda lista

Paso 3: si no se encontró ninguna coincidencia, almacenar en otra lista de resultados, pero si se encontró la coincidencia, entonces no añadir

Paso 4: la lista de resultados es su respuesta final

Costo de la opción 3:

Paso 1: si no está clasificado O(nlogn) tiempo

Paso 2: tiempo O(nlogn)

Paso 3: O(n) espacio

**

De modo que el tiempo O (nlogn) y el espacio O (n)

**

Si se requiere una lista, puede elegir una LinkedList . En su caso, como dijo @ Chris, la implementación de ArrayList moverá todos los elementos de cada eliminación.

Con LinkedList obtendrías un rendimiento mucho mejor para añadir / eliminar aleatoriamente. Vea este post .

  • ¿Por qué tantos GC_FOR_ALLOC en una aplicación sencilla?
  • Android Ver animación - bajo rendimiento en pantallas grandes
  • ListView vs LinearLayout
  • Android: Diferencia entre la herramienta traceview y systrace
  • Ionic: transiciones lentas en la aplicación android instalada
  • Android: rendimiento de gson
  • ¿Tiene Android (en ARM) los contadores de rendimiento de hardware?
  • Jackson JSON Parser rendimiento
  • ¿Hay alguna sobrecarga significativa en el uso de FragmentActivity sobre la actividad normal en Android?
  • Cambiar las pestañas es lento / Laggy - Uso de fragmentos
  • ¿Por qué Google utiliza Canvas en la vista de la lista de conversaciones de aplicaciones de Gmail?
  • FlipAndroid es un fan de Google para Android, Todo sobre Android Phones, Android Wear, Android Dev y Aplicaciones para Android Aplicaciones.