Блог

Главная - Вопросы по программированию - Алгоритм Java для отслеживания частей агрегированных значений

Алгоритм Java для отслеживания частей агрегированных значений

#java #algorithm #aggregate

#java #алгоритм #агрегат

Вопрос:

Моя программа оценивает сотни миллионов записей. Итак, вопрос памяти и производительности важен. Позволяет каждой записи иметь ключ — TicketID. Также запись имеет значение поля и имя_источника_поля. В source TicketID есть от 1 до многих (около 100) имя_источника. Мне нужно агрегировать только по TicketID — получить почти 1 миллион записей, но также должна быть возможность вычитать значения для указанного source_name — поэтому у меня есть трек, который вносит свой вклад.

Существуют ли какие-либо алгоритмы или структуры данных, которые позволяют решить эту проблему?

Комментарии:

1. Звучит как тяжелая работа, которую позволяет выполнять БД….

2. Почему бы вам не предложить алгоритм и не обсудить, какие методы имеют решающее значение для повышения скорости? Не существует такого понятия, как алгоритм, который не обменивает что-то на что-то другое, и из вашего описания существует лишь смутное представление о проблеме.

Ответ №1:

Я не могу полностью разобрать вопрос, поэтому я предполагаю:

  • «почти 1 миллион записей» означает, что существует почти 1 миллион уникальных ticketID полей.
  • «почти 100» разных source_name s в системе.
  • не все ticketId s имеют source_name s. У нас нет 100 миллионов ticketID source_name комбинаций x.
  • Вы хотите иметь возможность суммировать все ticketId s, но также и total by source_name .

С учетом этих предположений я бы использовал a Map of maps. Внешний Map имеет ключ source_name и значение внутреннего Map . Внутренний Map имеет ключ ticketId и кумулятивный value .

Таким образом, псевдокод будет выглядеть примерно так:

 Map<String, Map<Integer,Double>> valueMap =
    new HashMap<String, Map<Integer,Double>>();

while (...reading in and processing data...) {
    int ticketId = ...;
    String sourceName = ...;
    double entryValue = ...;

    Map<Integer,Double> sourceNameMap = valueMap.get(sourceName);
    Double value = sourceNameMap.get(ticketId);
    if (oldValue == null) {
        value = entryValue;
    } else {
        value  = entryValue;
    }
    sourceNameMap.put(ticketId, value);
}

Вы можете легко получить общее количество, сложив каждую из source_name карт. Вы также можете сохранить текущую сумму для каждого source_name , конечно, если это поможет. Если ваша система может выделить гигабайт для JVM, то она должна быть способна обрабатывать большое количество ticketID source_name пар x.

Вы можете рассмотреть возможность создания изменяемого внутреннего класса значений для экономии циклов GC:

 private static class MutableValue {
    double value;
    public MutableValue(double value) {
        this.value = value;
    }
    public void add(double value) {
        this.value  = value;
    }
}

Итак, вы можете сказать:

 MutableValue value = sourceNameMap.get(ticketId);
if (oldValue == null) {
    sourceNameMap.put(new MutableValue(entryValue));
} else {
    value.add(entryValue);
}

Если вы отредактируете свой вопрос, я отредактирую свой ответ на случай, если я сделал какие-то неправильные предположения.