CODEWITHSUNDEEP
swift
KhanKhuu
KhanKhuu

Reputation: 177

Better Way to Search an Array of Objects for a Value (Map)

I have a class called Room where I store information about a particular room in my home (its name, an image of it, etc). In my main ViewController, I create an array of Rooms and assign them some values. Later on, I want to search that array of Rooms for the room named "Study Room." I can use 

func findARoom(named room: String) -> Room {
    for i in 0..<rooms.count {
        if rooms[i].roomName == room {    
            return rooms[i]
        }
    }
}

but I think there is a better way. I want to be able to call the findARoom() function in the same way but not iterate through the entire array. I have used Maps in C++, where some linked values are hashed into the map and you can search for one of the values using the other value (e.g. find a phone number attached to someone's last name). Is there any way I can use a similar structure in Swift to find a Room object based on its roomName parameter?

Room.swift:

import UIKit

struct Room {
    var roomName: String
    var roomImage: UIImage
    var port: UInt16

    init(roomName: String, roomImage: UIImage, port: UInt16 = 1883) {
        self.roomName = roomName
        self.roomImage = roomImage
        self.port = port
    }
}

ViewController:

import UIKit

class MainViewController: UIViewController, UITableViewDelegate, UITableViewDataSource, RoomCellDelegate, MQTTModelDelegate {

    var server = [MQTTModel()]
    let cellId = "cellId"
    var rooms: [Room] = [Room]()
    var roomTableView = UITableView()

    override func viewDidLoad() {
        super.viewDidLoad()
        createRoomArray()
        findARoom(named: "Study Room")

    }

    // Setting up the array of rooms
    func createRoomArray() {
        rooms.append(Room(roomName: "Living Room", roomImage: UIImage(named: "Living_Room")!, port: 48712))
        rooms.append(Room(roomName: "Study Room", roomImage: UIImage(named: "Study_Room")!, port: 1883))
        rooms.append(Room(roomName: "Bedroom", roomImage: UIImage(named: "Bedroom")!, port: 1883))    
    }        

    func findARoom(named room: String) -> Room {
        for i in 0..<rooms.count {
            if rooms[i].roomName == room {    
                return rooms[i]
            }
        }
    }
}

Upvotes: 1

Views: 81

Answers (4)

Duncan C
Duncan C

Reputation: 131408

For most things, using array.first(where: { $0.name == "stringToMatch" } will be plenty fast.

I just did a quick benchmark, and running with optimization turned off on my now very low-end original iPad Air, with an array of 100,000 structs that contain a name field, first(where:) matched an item in around 0.026 seconds. You probably would not be able to see that amount of delay. (That's searching for an item that occurs at a random index in the array. Forcing the string to match the last element in the array slows first(where:) down to more like 0.047 seconds (≈1/20 of a second)

EDIT:

Here is the code I used to time first(where:):

    struct AStruct {
        var name: String
        var contents: String
    }
    
    func randomString(length: Int) -> String{
        var result = String()
        let chars = Array(UnicodeScalar("a").value ... UnicodeScalar("z").value) +
            Array(UnicodeScalar("A").value ... UnicodeScalar("Z").value)
        for _ in 1...length {
            result.append(String(UnicodeScalar(chars.randomElement()!)!))
        }
        return result
    }

    func searchTest() {
        var arrayOfStructs = [AStruct]()
        let arrayCount = 100_000
        for _ in 1...arrayCount {
            let name = randomString(length: 10)
            let contents = randomString(length: 20)
            arrayOfStructs.append(AStruct(name: name, contents: contents))
        }
        
        var averageTime: Double = 0
        let iterations = 20
        for _ in 1...20 {
            let aName = arrayOfStructs.randomElement()!.name
//            let aName = arrayOfStructs.last!.name //Force search to find the last item
            let start = Date().timeIntervalSinceReferenceDate
            let match = arrayOfStructs.first( where: {  $0.name == aName } )
            let elapsed = Date().timeIntervalSinceReferenceDate - start
            if match != nil {
                let elapsedString = String(format: "%0.12f", elapsed)
                print("found item in in an array of \(arrayOfStructs.count) items in \(elapsedString)")
            } else {
                print("Failed to find item after \(elapsed)")
            }
            averageTime += elapsed
        }
        averageTime /= Double(iterations)
        let averageTimeString = String(format: "%0.9f", averageTime)
        print("Average time = \(averageTimeString)")
    }

Upvotes: 2

Rob
Rob

Reputation: 437442

As has been pointed out, you can use first(where:), e.g.:

func findARoom(named room: String) -> Room? {
    return rooms.first { $0.roomName == room }
}

But you said:

I want to be able to call the findARoom() function in the same way but not iterate through the entire array.

Unfortunately, first(where:) does perform a for loop. Just look at the source code for that method. It’s still O(n), just like your own implementation.

If you were saying you just don’t want to have to write your own for loop, then first (or the like) is just a more concise way of writing the same thing, but realize that it is no more efficient than your approach.

If you really wanted to enjoy hashed performance, you could build a dictionary:

let rooms: [Room] = ...
let dictionary = Dictionary(grouping: rooms, by: { $0.roomName })

The resulting dictionary is a [String: [Room]].

Now, when you lookup a room in a this dictionary, you enjoy the hashed key performance:

if let room = dictionary["Study Room"]?.first { ... }

IMHO, this dictionary structure isn’t going to be worth it in an app like this, and first(where:) is a really nice, concise solution. But if you really don’t want it looping and truly need O(1) performance, you should know that first will not achieve that.

Upvotes: 2

Mayank K Rastogi
Mayank K Rastogi

Reputation: 604

If you want to be able to search for a Room without iterating through the entire array in O(1) time, you should consider using a Dictionary instead of an array, which is similar to Maps in C++.

Your ViewController code will need to be modified like this:

import UIKit

class MainViewController: UIViewController, UITableViewDelegate, UITableViewDataSource, RoomCellDelegate, MQTTModelDelegate {

    var server = [MQTTModel()]
    let cellId = "cellId"
    var rooms: [String: Room] = [String: Room]()  // Declare the dictionary
    var roomTableView = UITableView()

    override func viewDidLoad() {
        super.viewDidLoad()
        createRoomDictionary()
        findARoom(named: "Study Room")

    }

    // Setting up the dictionary of rooms
    func createRoomDictionary() {
        rooms["Living Room"] = Room(roomName: "Living Room", roomImage: UIImage(named: "Living_Room")!, port: 48712)
        rooms["Study Room"] = Room(roomName: "Study Room", roomImage: UIImage(named: "Study_Room")!, port: 1883)
        rooms["Bedroom"] = Room(roomName: "Bedroom", roomImage: UIImage(named: "Bedroom")!, port: 1883)
    }        

    func findARoom(named room: String) -> Room {
        return rooms[room]
    }
}

Upvotes: 1

Shehata Gamal
Shehata Gamal

Reputation: 100503

You can try

if let res = rooms.first(where:{ $0.roomName == "Study Room" }) {

}

Upvotes: 2

Related Questions