Mejorar la eficiencia de esta función de filtrado.

06 Aug, 2023 Programación 0

Tengo una matriz (potencialmente muy grande) de usuarios. Quiero eliminar un usuario específico de esta matriz si el usuario está contenido en ella. Aquí está mi código:

if users.contains(user) {
  users = users.filter { $0.id != user.id }
  count -= 1
  change -= 1
}

Al pensar en esto en términos de complejidad temporal y espacial, contains() es una operación de complejidad O(n), y filter() también es una operación de complejidad O(n).

Podría hacer lo siguiente:

for (index, user) in users.enumerated() {
  if user == userToRemove {
    users.remove(at: index)
    count -= 1
    change -= 1
  }
}

Pero aquí remove(at:) es una operación de complejidad O(n), al igual que el bucle for. Así que en ambos casos, tengo que recorrer toda la matriz dos veces.

Otra cosa que podría hacer es convertirla en un conjunto (Set) antes, pero eso perdería el orden.

¿Hay alguna manera de mejorar la eficiencia de esto para que solo tenga que recorrerla como máximo una vez?

davy.ai

August 6, 2023 at 3:44 am

Una forma de mejorar la eficiencia y potencialmente recorrer el array como máximo una vez es utilizar un diccionario o una tabla hash. En lugar de almacenar el array “users” tal como está, podrías convertirlo en un diccionario donde las claves sean los ids de los usuarios y los valores sean los propios usuarios. Esto se puede hacer con el inicializador Dictionary(uniqueKeysWithValues:) en Swift:

let usersDictionary = Dictionary(uniqueKeysWithValues: users.map { ($0.id, $0) })

Luego, para eliminar un usuario específico, simplemente puedes hacer:

if let removedUser = usersDictionary.removeValue(forKey: userToRemove.id) {
  users = Array(usersDictionary.values)
  count -= 1
  change -= 1
}

De esta forma, estás utilizando operaciones de tiempo constante para acceder y eliminar al usuario del diccionario (removeValue(forKey:) es O(1)), y luego conviertes los valores restantes de nuevo en un array. Sin embargo, ten en cuenta que convertir el diccionario a un array utilizando Array(usersDictionary.values) es una operación potencialmente O(n), ya que no se garantiza el orden de los valores.

Answer

davy.ai

August 6, 2023 at 3:44 am
Una forma de mejorar la eficiencia y potencialmente recorrer el array como máximo una vez es utilizar un diccionario o una tabla hash. En lugar de almacenar el array “users” tal como está, podrías convertirlo en un diccionario donde las claves sean los ids de los usuarios y los valores sean los propios usuarios. Esto se puede hacer con el inicializador Dictionary(uniqueKeysWithValues:) en Swift:
```
let usersDictionary = Dictionary(uniqueKeysWithValues: users.map { ($0.id, $0) })
```
Luego, para eliminar un usuario específico, simplemente puedes hacer:
```
if let removedUser = usersDictionary.removeValue(forKey: userToRemove.id) {
  users = Array(usersDictionary.values)
  count -= 1
  change -= 1
}
```
De esta forma, estás utilizando operaciones de tiempo constante para acceder y eliminar al usuario del diccionario (removeValue(forKey:) es O(1)), y luego conviertes los valores restantes de nuevo en un array. Sin embargo, ten en cuenta que convertir el diccionario a un array utilizando Array(usersDictionary.values) es una operación potencialmente O(n), ya que no se garantiza el orden de los valores.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Mejorar la eficiencia de esta función de filtrado.

Answer

davy.ai