Улучшение пошагового прохождения массива в два раза (вложенный цикл в одном и том же массиве)

Question

У меня есть большой набор данных, который я хочу циклически просмотреть, чтобы определить различные статистические данные о наборе данных от момента времени «D1» до момента времени в будущем «D2». По сути, я хочу добавлять в базу данных каждый раз, когда разница между значениями больше 10. Например:

Datum[] data = x;
for( Datum d1 : data ){
    Datum[] tail = y; //From d1 up to 10 elements ahead
    for( Datum d2 : tail ){
        //Calculate difference
        if( (d2.val - d1.val) > 10 ){
            //Insert into database
        }
    }
}

У меня вопрос, есть ли лучший алгоритм / метод для этого? Поскольку 9 элементов из tail повторно используются в следующей итерации внешнего цикла, могу ли я как-то извлечь из этого пользу? Моя цель состояла в том, чтобы свести это к намного меньшему, чем (Big-O Notation) O (n ² ), но я не могу обернуть это вокруг. Обычно нахождение пары D1, D2, которая удовлетворяет критериям, означает, что следующий элемент D1 также будет иметь больше шансов на совпадение. Могу ли я использовать это в своих интересах?

Я пытаюсь сделать это настолько эффективным, насколько это возможно, потому что набор данных очень большой.

Answer 1

то, что у вас есть, это классический алгоритм строчной развертки, который представляет собой O (k * n) с k «перекрытием» или частью, на которую переходит внутренний цикл.в вашем случае это максимум 10, независимо от того, что п

Datum[] data = x;
for(int i=0;i<data.length;i++ ){
    Datum d1=data[i];
    Datum[] tail = y; //From d1 up to 10 elements ahead
    for(int j=i+1;j<Math.min(i+10,data.length);i++){
        d2 = data[j];
        //Calculate difference
        if( (d2.val - d1.val) > 10 ){
            //Insert into database

            break;//inner loop
        }
    }
}

Answer 2

Цикл for на основе индекса может работать намного лучше, чем итератор, поскольку вы можете напрямую индексировать исходный массив и избежать копирования в новый массив. У вас будет гораздо лучшая локальность памяти, меньше шансов на ложное совместное использование и т. Д.

Answer 3

Существует асимптотически более быстрый способ решения этой проблемы, но у меня есть серьезные сомнения относительно того, будет ли он работать быстрее на практике, потому что размер вашего окна (10) очень мал.Если вы хотите увеличить этот размер - который я назову k - чтобы он был больше, то вы можете рассмотреть возможность выбора подхода, подобного следующему.

Когда вы используете этот алгоритм, вам необходимоподдерживать окно из k элементов, которое поддерживает две операции:

1. Вставить новый элемент, исключая самый старый.
2. Возвращает все элементы больше некоторого значения.

Один из способов сделать это - сохранить все ваши элементы в структуре данных, объединяющей сбалансированное двоичное дерево поиска и очередь.Очередь содержит все k элементов, хранящихся в том порядке, в котором они появляются в исходной последовательности, и используется для того, чтобы мы могли вспомнить, какой элемент нужно удалить, когда нам нужно добавить новый элемент.Сбалансированный BST хранит копию каждого из этих элементов, хранящихся в отсортированном порядке.Это означает, что вы можете реализовать описанные выше операции следующим образом:

1. Вставить новый элемент, исключив самый старый: Добавить новый элемент в очередь и BST.Затем удалите очередь из очереди, чтобы получить самый старый элемент, затем удалите его из BST.Время выполнения: O (log k), поскольку в BST содержится k элементов.
2. Возвращает все элементы, превышающие некоторое значение: Используя BST, найдите самый маленький элемент, по крайней мере, такой же большой, какэто значение в O (log n) времени.Затем отсканируйте BST и перечислите все элементы, по крайней мере, такого размера, как этот элемент.Это занимает время O (z), где z - общее количество найденных совпадений.

В совокупности, если у вас есть n элементов и всего z пар, которые необходимо вставить в базу данных, этоалгоритм займет O (n log k + z) времени.Чтобы увидеть это, обратите внимание, что мы делаем всего n копий операции (1), которая занимает по O (log k) времени.Мы также делаем n копий операции (2), которая занимает O (n log k) времени, чтобы найти преемников, а затем O (z) общее время на всех итерациях, чтобы вывести список всех совпадающих пар.

Асимптотическая среда выполненияэтот алгоритм хорош по сравнению с алгоритмом O (nk), который вы первоначально разместили.Предполагая, что количество совпадений не является «действительно огромным» (скажем, порядка nk), это будет намного быстрее, если вы увеличите n и k.

Если значения, которые вы храните, являются целыми числамив небольшом диапазоне (скажем, 0–10 000) вы можете ускорить это еще больше, заменив сбалансированный BST структурой данных, оптимизированной для целых чисел, например, дерево Ван Эмде Боаса , которое уменьшает это до O(n log log k + z).Опять же, это только быстрее асимптотически , и если вы держите k постоянным на 10, это почти наверняка не стоит.

Надеюсь, это поможет!

Answer 4

На вашем месте, первое, что я хотел бы сделать, это профилировать типичный набор данных и выяснить, куда идет время.Это должно дать некоторые подсказки относительно того, куда следует направить ваши усилия по оптимизации.

Если предположить, что вычисление так же просто, как вычитание / сравнение, и массивы быстро доступны, тогда вы предложите оптимизировать сохранение в базе данных.должен быть следующим приоритетом.Например, написание текстового файла и использование массовой вставки может дать очень высокую производительность по сравнению с отдельными инструкциями вставки.Если вы придерживаетесь отдельных вставок и используете JDBC, то пакетные обновления будут очень полезны, поскольку они избегают задержек при обмене данными с базой данных.

Если это все еще не достаточно быстро, рассмотрите возможность разбиения массива на N разделов, и каждый раздел обрабатывается отдельным потоком.Это будет особенно эффективно, если обработка связана с процессором.

Наконец, ищите оптимизации на уровне кода, например избегайте итераторов с помощью индекса.Если количество элементов, записанных в базу данных, мало по сравнению с количеством итерированных элементов, то создание итератора может стать узким местом.

Если количество элементов больше 10, и, что важно, больше, чем может поместиться в кэш процессора, будет более эффективно разбивать сканирование на более мелкие блоки.Например, вместо того, чтобы сканировать 1000 элементов из data2, разбейте его на (скажем) 10 сканирований по 100, при этом каждое из 10 сканирований использует различное значение d1.Это похоже на то, как матричное умножение реализовано в блочном режиме и лучше использует кэши процессора.

Хотя вы используете два цикла, который обычно является алгоритмом O (N ^ 2), второй цикл имеет фиксированный размер - 10 элементов, так что это сводится к простому постоянному коэффициенту - вы делаете примерноФактор еще 10 работ.