как ускорить поиск в ArrayList?

Question

В настоящее время у меня есть ArrayList, содержащий объекты созданного мною класса, затем я анализирую ArrayList в for loop, ища и сравнивая некоторые данные из ArrayList и некоторые глобальные variables, которые загружается в другое место, где, однако, этот ArrayList постоянно растет и в конце концов к концу будет иметь около 115 элементов, что затем займет очень много времени для поиска, функция, которая делает это, также вызывается один раз для каждой строки, которую я читаю из текстового файла и текстового файла обычно будет иметь длину около 400-500 строк, так что вы можете сказать, что это очень медленный процесс, даже при тестировании небольших файлов. Есть ли способ ускорить это, возможно, используя другой collection вместо ArrayList, поэтому я считаю необходимым использовать ArrayList, я должен знать, по какому индексу он находится, когда находит совпадение.

Вот класс:

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

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

Функция:

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();
            }
        }
    }

Если есть что-то еще, что вы хотели бы увидеть, просто спросите, спасибо. Говядина.

Обновление: добавлена ​​функция вставки ()

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();
}

Обновление:

Спасибо Matteo, я понял, что добавляю в массив, даже если не найду совпадения до 10-го элемента, он будет добавлен в массив первые 9 раз, что создало много дополнительных элементов в массиве, поэтому это было так медленно, я добавил несколько перерывов и немного изменил функцию, и это значительно улучшило производительность. Спасибо за все вклады

Answer 1

вы можете использовать LinkedHashSet .Кажется, вы добавляете только элементы в конец списка, что точно также делает LinkedHashSet при вставке элемента.
Обратите внимание, однако, что LinkedHashSet не допустит дублирования, так как это набор.
Поиск, если элемент существует, будет O (1) с использованием contains ()

Использование LinkedHashSet также позволит вам отслеживать, где был добавлен элемент, иитерация будет в порядке вставки.

Answer 2

1) Создайте PanelArray с максимальным ожидаемым размером + 10% при первом создании.List<PanelData> panelArray = new ArrayList<PanelData>(130) - это предотвратит динамическое перераспределение массива, что сэкономит время обработки.

2) Что делает insert()?Скорее всего, это ваш ресурс боров.

Answer 3

Здесь довольно много оптимизаций.

1) вызов: panelArray.get (i) используется многократно. Объявите переменную PanelData вне цикла, но инициализируйте ее только один раз, в самом начале цикла:

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

    ...
}

2) Если ваш набор данных позволяет это сделать, рассмотрите возможность использования нескольких карт, чтобы ускорить поиск:

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

3) Рассмотрите возможность хэширования ваших строк в целые или длинные, поскольку String.equals () медленнее по сравнению с (int == int)

4) Если ArrayList будет доступен только для чтения, возможно, многопоточное решение может помочь. Поток, считывающий строки из текстового файла, может передавать отдельные строки данных различным «рабочим» потокам.

Answer 4

Как насчет использования hashmap?

Я бы создал небольшой класс для ключа:

class Key {
  String dev, instr;

  // todo: implements equals & hashCode
}

и создал бы карту:

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

тогда вы можете легко найти нужный элемент, вызвав map.get(new Key(...)).

Вместо создания нового класса вы также можете настроить класс PanelData, реализуя методы equals & hashcode, чтобы два класса были равны, если их dev и instr равны.В этом случае ваша карта становится:

Map<PanelData, PanelData> map ...

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

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

Answer 5

Эту проблему лучше всего решить с помощью другой структуры данных, такой как HashMap или SortedSet.

Для использования HashMap, вам нужно определить класс, который может создавать хеш-код для пар строк dev и inst.Одним из решений является что-то вроде:

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));
    }
}

Затем вы будете использовать HashMap<DevAndInstPair, PanelData> в качестве типа карты.

В качестве альтернативы, если вы знаете, что определенный символ никогда не появляется в строках devзатем вы можете использовать этот символ в качестве разделителя, отделяющего значение dev от значения inst.Предполагая, что этот символ является дефисом ('-'), значения ключа будут dest + '-' + inst, а тип ключа карты будет String.

Чтобы использовать SortedSet, вы должны иметьPanelData реализовать Comparable<PanelData> или написать класс, реализующий Comparator<PanelData>.Помните, что операция сравнения должна быть совместима с equals.

A SortedSet несколько сложнее в использовании, чем HashMap, но я лично считаю, что это более элегантное решение этой проблемы.