CODEWITHSUNDEEP
javaarraysperformancetime
madhu_karnati
madhu_karnati

Reputation: 795

Mapping key values from arrays of values where time complexity matters

I have two arrays like this..

 Long key1= 1l;  Long key2= 2l;  Long key3= 3l;  Long key4= 4l;  
 Long key5= 2l;  Long key6= 3l;  Long key7= 1l;  Long key8= 2l;
 Long key9= 4l;

 MyObject ob1= new MyObject(1l);     MyObject ob2= new MyObject(3l);     MyObject ob3= new MyObject(2l);
 MyObject ob4= new MyObject(1l);     MyObject ob5= new MyObject(4l);     MyObject ob6= new MyObject(3l);
 MyObject ob7= new MyObject(4l);     MyObject ob8= new MyObject(2l);     MyObject ob9= new MyObject(1l);

 Long[] keys= new Long[]{key1,key2,key3,key4,key5,key5,key7,key8,key9};
 MyObject[] objects= new MyObject[]{ob1,ob2,ob3,ob4,ob5,ob6,ob7,ob8,ob9};

I want to map Objects with keys. So each key will have list of Objects associate with it.

(More or less my problem is like.. Map 'A' with "Apple, Axe, Aero" ; 'B' with "Box, Ball..etc")

I am successful by the way I am doing but the problem is time complexity it is more than O(n * n)(I am taking a key , comparing it with each objects key.).

Can someone help me to get this work with less than o(n * n) time complexity.For me Time complexity matters.

Using JDK 1.6.

   My Program:


 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;

 public class Bar 
   {
 Long key1= 1l;  Long key2= 2l;  Long key3= 3l;  Long key4= 4l;  
 Long key5= 2l;  Long key6= 3l;  Long key7= 1l;  Long key8= 2l;
 Long key9= 4l;

 MyObject ob1= new MyObject(1l);     MyObject ob2= new MyObject(3l);     MyObject ob3= new MyObject(2l);
 MyObject ob4= new MyObject(1l);     MyObject ob5= new MyObject(4l);     MyObject ob6= new MyObject(3l);
 MyObject ob7= new MyObject(4l);     MyObject ob8= new MyObject(2l);     MyObject ob9= new MyObject(1l);

 Long[] keys= new Long[]{key1,key2,key3,key4,key5,key5,key7,key8,key9};
 MyObject[] objects= new MyObject[]{ob1,ob2,ob3,ob4,ob5,ob6,ob7,ob8,ob9};


 public void mapper()
 {
    Map<Long, List<MyObject>> keyToObjectMap= new HashMap<Long,List<MyObject>>(); 

    for(int i=0;i<keys.length;i++)
    {
        for(MyObject object:objects)
        {
            if(keyToObjectMap.containsKey(keys[i]))
            {
                if(keys[i].equals(object.getKey()))
                {
                    List<MyObject> objs= keyToObjectMap.get(keys[i]);
                    if(!objs.contains(object))
                    {
                        objs.add(object);
                    }
                    keyToObjectMap.put(keys[i], objs);  
                }
            }
            else if(keys[i].equals(object.getKey())) 
            {
                List<MyObject> objs= new ArrayList<MyObject>();
                objs.add(object);
                keyToObjectMap.put(keys[i], objs);  
            }                   
        }
    }       
 }   

 public static void main(String[] args) 
 {
     Bar b= new Bar();
     b.mapper();
}

   }



 class MyObject
 {
Long key;
String desc="description";  

MyObject(Long key)
{
    this.key=key;
}

public Long getKey(){
    return key;
}
}

Upvotes: 0

Views: 50

Answers (2)

Peter Lawrey
Peter Lawrey

Reputation: 533660

You can do it in O(n) like this.

Map<Long, Set<MyObject>> keyToObjectMap = new HashMap<>();
for (MyObject o : objects) {
     Set<MyObject> set = ketToObjectMap.get(o.getKey());
     if (set == null)
         keyToObjectMap.put(o.getKey(), set = new HashSet<>());
     set.add(o);
}

In Java 8 you can do

Map<Long, Set<MyObject>> map = objects.stream()
                .collect(Collectors.groupingBy(MyObject::getKey, Collectors.toSet()));

Upvotes: 4

Dude
Dude

Reputation: 1

If search performance is so important, you should just use hash of hash instead of hash of list.

By the way it is not o(nn) since your outer hash has constant cost.

Upvotes: 0

Related Questions