3

I currently have an ArrayList holding objects of a class I have created, I then parse through the ArrayList in a for loop searching and comparing some data from the ArrayList and some global variables that are loaded else where, however this ArrayList is constantly growing and will eventually have about 115 elements to it towards the end, which then takes a very long time to search through, the function that does this is also called once for every line I read from a text file and the text file will usually be around 400-500 lines long so as you can tell it is very slow process even when testing on small files. Is there a way to speed this up by maybe using another collection instead of an ArrayList, my reasoning for using the ArrayList is I have to know what index it is on when it finds a match.

Here is the class: 

private ArrayList<PanelData> panelArray = new ArrayList<PanelData>(1);

    public class PanelData {
        String dev = "";
        String inst = "";
        double tempStart = 0.0;
        double tempEnd = 0.0;
    }

Function:

public void panelTimeHandler (double timeStart, double timeEnd) throws SQLException {   
        PanelData temps = new PanelData();
        temps.dev = devIDStr;
        temps.inst = instanceStr;
        temps.tempStart = timeStart;
        temps.tempEnd = timeEnd;
        boolean flag = false;

        if(!flag)
        {
            panelArray.add(temps);
            flag = true;
        }

        for(int i = 0; i < panelArray.size(); ++i ) {
            if(panelArray.get(i).dev.equals(devIDStr) && panelArray.get(i).inst.equals(instanceStr)) {
                if(panelArray.get(i).tempStart <= timeStart  && panelArray.get(i).tempEnd >= timeEnd ) {
                    //Do Nothing
                }
                else 
                {
                    temps.dev = devIDStr;
                    temps.inst = instanceStr;
                    temps.tempStart = timeStart;
                    temps.tempEnd = timeEnd;
                    insert();
                    panelArray.set(i, temps);
                }
            }
            else
            {
                temps.dev = devIDStr;
                temps.inst = instanceStr;
                temps.tempStart = timeStart;
                temps.tempEnd = timeEnd;
                panelArray.add(temps);
                insert();
            }
        }
    }

If there is something more you would like to see just ask, thanks. Beef.

Update: Added insert() function

private void insert() throws SQLException
{
    stmt = conn.createStatement();  

    String sqlStm = "update ARRAY_BAC_SCH_Schedule set SCHEDULE_TIME = {t '" + finalEnd + "'} WHERE SCHEDULE_TIME >=  {t '" + finalStart + "'} AND" +
        " SCHEDULE_TIME <=  {t '" + finalEnd + "'} AND VALUE_ENUM = 0 AND DEV_ID = " + devIDStr + " and INSTANCE = " + instanceStr;
    int updateSuccess = stmt.executeUpdate(sqlStm);

    if (updateSuccess < 1)
    {   
        sqlStm = "insert into ARRAY_BAC_SCH_Schedule (SITE_ID, DEV_ID, INSTANCE, DAY, SCHEDULE_TIME, VALUE_ENUM, Value_Type) " +
                " values (1, " + devIDStr + ", " + instanceStr + ", " + day + ", {t '" + finalStart + "'}, 1, 'Unsupported')";
        stmt.executeUpdate(sqlStm);
        sqlStm = "insert into ARRAY_BAC_SCH_Schedule (SITE_ID, DEV_ID, INSTANCE, DAY, SCHEDULE_TIME, VALUE_ENUM, Value_Type) " +
                " values (1," + devIDStr + ", " + instanceStr + ", " + day + ", {t '" + finalEnd + "'}, 0, 'Unsupported')";
        stmt.executeUpdate(sqlStm);
    }
    if(stmt!=null)
        stmt.close();
}

Update:

Thank you to Matteo, I realized I was adding to the array even if I didnt find a match till the 10th element it would then added to the array the first 9 times which created many extra elements in the array, which was why it was so slow, I added some breaks and did a little tweaking in the function, and it improved the performance a lot. Thanks for all the input

Improve this question
9
  • Are you sure that this code works? If you have three elements, and only the second one matches your devIDStr and instanceStr, it seems to me that your result have four elements, with the second and the last one pointing to the same object. Commented Sep 27, 2011 at 13:17
  • @Matteo Im actually not sure if the panelTimeHandler works as I am hoping for its too slow to find out, but I made a similar function in a different version of this program and it worked as planned so I figured once I get it running completely I can tweak it to work Commented Sep 27, 2011 at 13:27
  • the more I look at the code, the more I think it has some errors... if panelArray contains 3 elements, with the second matching devIDStr and instanceStr, but with the condition panelArray.get(i).tempStart <= timeStart && panelArray.get(i).tempEnd >= timeEnd false, what is the execution of the function? Since !flag is true, the first if is executed and the temps is added at the end of the list (hence there are 4 elements in the list). Then the for loop is executed 6 times... (next comment) Commented Sep 27, 2011 at 13:41
  • @Matteo well you did just point out one error I didnt notice, I never meant to declare flag in the function because I dont want it to be false every time the function is called, its only purpose is to know when its the first time that function is called Commented Sep 27, 2011 at 13:44
  • The first time the element does not match dev and inst, hence the last else is executed and tems is added at the end of the list (panelArray contains 5 elements). The second time the element match and the first else branch is taken: as result the ith element is re-set with temps (panelArray still contains 5 elements). The third time the element does not match, hence the temps is added another time at the end of the list (panelArray still contains 6 elements). The fourth, fith, and sixth time the element matches but nothing happens (the //Do nothing branch is taken). Commented Sep 27, 2011 at 13:46

5 Answers 5

Reset to default
3

you can use LinkedHashSet. It seems you add only elements to the end of the list, which is exactly what LinkedHashSet does as well, when inserting an element.
Note however, a LinkedHashSet will not allow duplicates, since it is a set.
Searching if an element exists will be O(1) using contains()

Using the LinkedHashSet will also allow you to keep track of where an element was added, and iterating it will be in order of insertion.

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

3 Comments

alright, thanks, I dont think I will have any duplicates because every object that goes into it will have a unique devIDStr and instanceStr
does LinkedHashSet grow as I add elements to it, can I declare its initial capacity as 1 and then let it grow as needed
@Beef: The LinkedHashSet is growing on the fly. the default constructor creates an empty LinkedHashSet of size 16, and when balance factor gets too high, it increases the set's size automatically.
1

What about using a hashmap?

I would create a small class for the key:

class Key {
  String dev, instr;

  // todo: implements equals & hashCode
}

and create the map:

Map<Key, PanelData> map = new HashMap...

then you can easily find the element you need by invoking map.get(new Key(...)).

Instead of creating a new class, you could also tweak the PanelData class, implementing methods equals & hashcode so that two classes are equal iff their dev and instr are equal. In this case, your map becomes:

Map<PanelData, PanelData> map ...

// to add:
map.put(temps, temps)

// to search:
PanelData elem = map.get(new PanelData(desiredDev, desiredInstr));
Improve this answer

2 Comments

Ok, you can use a separate list to iterate your elements in the correct order.... or just use a LinkedHashMap as you suggested! :)
@Matteo I considered using a HashMap however if that first if matches, I only want to compared the tempStart and tempEnd that were from the same element as used in the previous if and I wasnt sure how to access that specific element when using a HashMap, also using a HashMap I didnt know how to access specific data from the class.
1

Quite a few optimiztions here.

1) the call: panelArray.get(i) is used repeatedly. Declare a PanelData variable outside the loop, but initialize it only once, at the very begining of the loop:

PanelData pd = null;
for (int i = 0; i < panelArray.size(); ++i) {
    pd = panelArray.get(i);

    ...
}

2) If your dataset allows it, consider using a few maps to help speed look up times:

HashMap<String, PanelData> devToPanelDataMapping = new HashMap<String,PanelData>();
HashMap<String, PanelData> instToPanelDataMapping = new HashMap<String,PanelData>();

3) Consider hashing your strings into ints or longs since String.equals() is slow compared to (int == int)

4) If the ArrayList will be read only, perhaps a multithread solution may help. The thread that reads lines from the text file can hand out individual lines of data to different 'worker' threads.

Improve this answer

1 Comment

The key is composed by two strings... in this case, you are not allowing a PanelData with equal dev but different instr!
1

1) Create PanelArray with the max expected size + 10% when you first create it. List<PanelData> panelArray = new ArrayList<PanelData>(130) - this will prevent dynamic reallocations of the array which will save processing time.

2) What does insert() do? Odds are that is your resource hog.

Improve this answer

6 Comments

insert() is a function that performs an sql insert on a database with use of the global variables that get loaded from the text file, I dont expect it to be too fast cause I know the insert slows it down to some extent
ok, you're making a database insert inside a loop - classic resource hog case. Look into batching your statements rather than inserting single rows at a time.
my reasoning for doing it in a loop is because the global variables change each time a line is read from the text file and I have to perform an insert for each line with the new global variables
That doesn't change the fact that you can batch the operations till you are done processing the file, and then execute + commit all the inserts as one transaction outside of the loop.
I am going to update question and add my insert function in it
|
0

This problem might best be solved with a different data structure such as a HashMap or SortedSet.

In order to use a HashMap, you would need to define a class that can produce a hash code for the dev and inst string pairs. One solution is something like:

public class DevAndInstPair
{
    private String dev, inst;

    @Override
    public int hashCode() {
        return ((dev.hashCode() * 0x490aac18) ^ inst.hashCode());
    }

    @Override
    public boolean equals(Object o) {
        if (o == null || !(o instanceof DevAndInstPair)) {
            return false;
        }
        DevAndInstPair other = (DevAndInstPair) o;
        return (dev.equals(other.dev) && inst.equals(other.inst));
    }
}

You would then use HashMap<DevAndInstPair, PanelData> as the map type.

Alternatively, if you know that a certain character never appears in dev strings, then you can use that character as a delimiter separating the dev value from the inst value. Supposing that this character is a hyphen ('-'), the key values would be dest + '-' + inst and the key type of the map would be String.

To use SortedSet, you would either have PanelData implement Comparable<PanelData> or write a class implementing Comparator<PanelData>. Remember that the compare operation must be consistent with equals.

A SortedSet is somewhat trickier to use than a HashMap, but I personally think that it is the more elegant solution to this problem.

Improve this answer

2 Comments

SortedSet is not sorted according to insertion order [which seems what the OP wants]. and a HashMap is not sorted at all!
@amit: Maintaining insertion order and/or a sorted collection does not appear to be necessary. In the implementation of panelTimeHandler(), @Beef is searching through the ArrayList looking for PanelData instances having the same dev and inst strings. If all that Beef requires is the ability to look up PanelData instances by these two fields, then a HashMap and SortedSet are both suitable for the problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.