How can I optimize search on array of String array?

Question

I have String arrays of arrays.

List<String[]> mainList = new ArrayList<String[]>();

String[] row1 = {"foo", "bar", "moo"}
String[] row2 = {"cocoa", "zoo", "milk", "coffee"}

mainList.add(row1);
mainList.add(row2);

Let's say I want to find an element "milk".

I could do with N^2.

for(int i=0, j=mainList.size(); i<j; i++) {
    for(int x=0, y=mainList.get(i).length(); x<y; x++) {
        String item = mainList.get(i)[x];

        if(item.equals("milk")) {
            return true; //found milk
        }
    }
}

I tried to make it faster by putting all elements as Map key.

//put all elements to map key
Map m = new HashMap<String, String>();
for(int i=0, j=mainList.size(); i<j; i++) {
    for(int x=0, y=mainList.get(i).length(); x<y; x++) {
        m.put(mainList.get(i)[x], "whatever");
    }
}

//now iterate and see if key "milk" is found
if(m.contains("milk")) { return true; }

But I figured this is still N^2 (i.e. for loop inside of for loop, as the number of rows added to mainList like row3['item1', 'item2', 'item3'], the iteration increments in N^2)

how can I optimize this without N^2 ?

Map m = new HashMap<String>(); This won't compile as a Map has two type parameters. Also, what makes you think this will be O(n^2)? — Jim Garrison
– Jim Garrison, Commented May 11, 2011 at 5:20

Brett Kail · Accepted Answer · 2011-05-11 05:22:27Z

3

Neither algorithm is N^2 since you visit the elements only once. However, the first algorithm, is O(N) for each lookup, but the second algorithm is O(N) to populate the map and O(1) for each subsequent lookup.

answered May 11, 2011 at 5:22

Brett Kail

34k2 gold badges88 silver badges93 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Meow Over a year ago

Oh, I assumed it was N^2 because for loop inside of for loop. I might be misunderstanding

Brett Kail Over a year ago

The loop bounds are different, so it can't be N^2. You could call it M*N with M=mainList.size() and N=max(length of any array in mainList), but the important part of algorithmic complexity is figuring out what your significant operation is. In this case, it's the number of comparisons, which has an upper bound of all elements in all arrays in all the lists (i.e., some number N). If your algorithm was instead trying to count the number of duplicates using for(mainList) for (array) for(mainList) for(array), that would be N^2.

Dimitar · Accepted Answer · 2011-05-11 05:24:27Z

2

If you know the key you are looking for a get operation for a hashmap is actually O(1)

source: http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

answered May 11, 2011 at 5:24

Dimitar

2,4122 gold badges20 silver badges28 bronze badges

Comments

James Jithin · Accepted Answer · 2011-05-11 05:28:37Z

2

Why can't be the code as below?

        String[] row1 = {"foo", "bar", "moo"};
        String[] row2 = {"cocoa", "zoo", "milk", "coffee"};

        HashMap<String, String> mainMap = new HashMap<String, String>();
        for(String s: row1) {
            mainMap.put(s, s);
        }

        for(String s: row2) {
            mainMap.put(s, s);
        }

        System.out.println(mainMap.get("milk") != null);

answered May 11, 2011 at 5:28

James Jithin

10.6k6 gold badges40 silver badges53 bronze badges

Comments

Brian Stinar · Accepted Answer · 2011-05-11 05:29:30Z

Bkail beat me to this answer, but mine might provide a little more insight (even though it is the same.)

I believe you might be a little unclear on your lookup time and your construction time.

For the first example you provided, I think you have a constant construction time (is allocating a static array constant in Java?). Then, your lookup time (for every lookup) is n (for n elements, not n*n). I can see how this could be a little bit confusing with your notation, as your n elements come in two rows.

However, for your second example, you are spending n on construction. Your actual lookup is O(1), like the other answers said.

So, the important thing to consider is what you are measuring. Asymptotic notation for the lookup is what you're interested in.

Good luck!

Collectives™ on Stack Overflow

How can I optimize search on array of String array?

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related