¿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 .

  • Efecto de trayectoria de trazo que hace la pantalla lenta
  • Rendimiento de procesamiento en android
  • Miles de insertos crudos de ORMLite que tardan varios minutos en Android
  • Rendimiento en tiempo real de la galería de lienzo de Android
  • Simula la memoria baja en el dispositivo real de Android
  • Manipulación de lienzo vs manipulación de elementos
  • Diseño complejo de Android lineal y relativo
  • Descomprimir archivos de una manera más rápida que usar java.util.zip en Android
  • LockCanvas () muy lento
  • Inicio y fin de solicitudes de registro HTTP desde WebView incorporado de Android
  • ¿Cuál es la mejor solución para un salto de barra de progreso indeterminado en ICS?
  • FlipAndroid es un fan de Google para Android, Todo sobre Android Phones, Android Wear, Android Dev y Aplicaciones para Android Aplicaciones.