Optimize Memory Java String Array

Question

I was trying to solve one programming challenge :

First input is a list of connections which is made of pair of IPv4 address. Each IP has its own state which starts with false, each connection also has state which is made up by logical AND of state of its IPs

Second input is a toggle IPs list , these toggles the state of IP address ( false to true or true to false). For each toggle action , calculate the impact on connections which is defined as how many connections state changed due to change in one IP address.

I solved the above challenge by using below Java program, but I'm not sure if there could be any scope of improvement for memory consumption and run time. Please pardon my programming knowledge, I would appreciate any positive feedback to cover corener cases

public class NumberOfDevices {

    public static void main(String[] args) {
        String [][]connections ={{"192.167.0.0","192.167.0.1"},{"192.167.0.2","192.167.0.0"},{"192.167.0.0","192.167.0.3"}};
        String []toggleIps= {"192.167.0.1","192.167.0.0","192.167.0.2","192.167.0.0", "0.0.0.0"};
        int[] result = numberOfDevices(connections, toggleIps);
        
        for(int i:result) {
            System.out.print(i + " ");
        }
    }

    public static int[] numberOfDevices(String[][] connections, String [] toggleIps) {
        int count =0;
        int [] result = new int[toggleIps.length];
        if(connections.length>0) { // already a given contaraint that the length of toggle IPs is >=1


            Map<String,Ipv4Address> ip = new HashMap<>();
            for(int i=0; i<connections.length; i++) {
                Ipv4Address ip1, ip2;
                
                if(!ip.containsKey(connections[i][0])) {
                    ip.put(connections[i][0], new Ipv4Address(connections[i][0]));                  
                }
                if(!ip.containsKey(connections[i][1])) {
                    ip.put(connections[i][1], new Ipv4Address(connections[i][1]));                  
                }
                
                ip1=ip.get(connections[i][0]);
                ip2=ip.get(connections[i][1]);
                
                ip1.addConnection(ip2);
                ip2.addConnection(ip1);

            }
            
            for(int j=0; j<toggleIps.length; j++) {
                if(!ip.containsKey(toggleIps[j])) {
                    result[j]=0;
                }
                else {
                    Ipv4Address ipv4 = ip.get(toggleIps[j]);
                    ipv4.setState(!(ipv4.getState()));
                    for(Ipv4Address conn:ipv4.getConnections()) {                       
                        if(conn.getState()) {
                            result[j]++;
                        }                       
                    }
                }
            }
        }
        
        
        return result; 
    }

}

// class representing the IPv4 address , it has IP address, current state and the connections where its present
class Ipv4Address{
    String ipAddress;
    boolean state;
    List<Ipv4Address> connections;
    

    public Ipv4Address(String ipAddress) {
        this.ipAddress = ipAddress;
        this.state=false;
        connections= new ArrayList<>();
    }

    public boolean getState() {
        return this.state;
    }
    public void setState(boolean state) {
        this.state=state;
    }

    public void addConnection(Ipv4Address ipaddress) {
        this.connections.add(ipaddress);
    }
    public List<Ipv4Address> getConnections(){
        return this.connections;
    }

}

Answer 1

As you asked about memory and run-time impact, I'll focus on memory.

Memory

IPv4

You store a IPv4 address as String. In Java a String can be represented by a byte per character, so 192.167.0.1 becomes 11 bytes. Also a String is internally a reference, which also costs 8 bytes on 64 bit.

192.167.0.1 will therefore cost at least 11 + 8 = 19 bytes.

A IPv4 addres could be represented as an int (32 bit), because a IPv4 address consist of 4 bytes. This saves a lot of room.

See for example: https://stackoverflow.com/a/16642424/461499

List of connections

If you really want to squeeze, you could not initialize the list of connections (saving an empty ArrayList when there are no connections). Just create it on the fly in the setter and make the getter return Collections.emptyList() if the internal list is null

If the list of connections becomes really long, you might consider storing them in an special datastructure, for example as packed integer list.

Answer 2

Welcome to Stack Review, it seems me there is no much space for improvement, just some little tips:

class Ipv4Address {
    String ipAddress;
    boolean state;
    List<Ipv4Address> connections;
   
    //setters and getters
}

Probably you included your Ipv4Address class inside the NumberOfDevices class file but for a cleaner code better create a Ipv4Address class file separated. If you have defined setters and getters, you can encapsulate fields into the class using the private access modifier like below:

public class Ipv4Address {
    private String ipAddress;
    private boolean state;
    private List<Ipv4Address> connections;

    public Ipv4Address(String ipAddress) {
        this.ipAddress = ipAddress;
        this.state = false;
        this.connections = new ArrayList<>();
    }
    
    //getters and setters
}

No much to say about NumberOfDevices; in its numberOfDevices method you have the following code :

public static int[] numberOfDevices(String[][] connections, String [] toggleIps) {
    int count =0;
    int [] result = new int[toggleIps.length];
    if(connections.length>0) { // already a given contaraint that the length of toggle IPs is >=1
    
    
       Map<String,Ipv4Address> ip = new HashMap<>();
       for(int i=0; i<connections.length; i++) {
          Ipv4Address ip1, ip2;
                    
          if(!ip.containsKey(connections[i][0])) {
            ip.put(connections[i][0], new Ipv4Address(connections[i][0]));                  
          }
          if(!ip.containsKey(connections[i][1])) {
            ip.put(connections[i][1], new Ipv4Address(connections[i][1]));                  
          }
                    
          ip1=ip.get(connections[i][0]);
          ip2=ip.get(connections[i][1]);
                    
          ip1.addConnection(ip2);
          ip2.addConnection(ip1);
    
     }

      //other lines
}

You can rewrite this part of your method using a foreach construct like below:

public static int[] numberOfDevices(String[][] connections, String[] toggleIps) {
    int[] result = new int[toggleIps.length];

    if (connections.length == 0) { return result; }

    Map<String, Ipv4Address> map = new HashMap<>();

    for (String[] connection : connections) {

        for (String c : connection) {

            if (!map.containsKey(c)) {
                map.put(c, new Ipv4Address(c));
            }
        }

        Ipv4Address ip1 = map.get(connection[0]);
        Ipv4Address ip2 = map.get(connection[1]);
        ip1.addConnection(ip2);
        ip2.addConnection(ip1);
   }

   //other lines
}

Answer 3

As @dariosicily said, hide the members of the Ipv4Address class; since it's a bad habit to expose internal values directly, since you will lose control over your own data when the object is mutable. In your Ipv4Address class, the list connections is mutable, and can be edited from anywhere; even if you create a getter / setter.

When dealing with mutable objects, it always a good practice to return a new instance in the getter. Luckily, with the Java collections, you can use the java.util.Collections#unmodifiableList to return a list that is not editable.

    public List<Ipv4Address> getConnections() {
        return Collections.unmodifiableList(this.connections);
    }