Arti-Jack
@Arti-Jack

Как улучшить алгоритм?

Привет, задали одну задачу. Выглядит так:

Перевод

Дан CSV-файл с информацией о ряде сделок.
Файл содержит следующие столбцы:
1. ВРЕМЯ - время сделки в формате Часы:Минуты:Секунды.Миллисекунды
2. ЦЕНА - цена акции
3. РАЗМЕР - количество акции, выполненных в этой сделке.
4. БИРЖА - биржа, на которой происходила сделка
Для каждой биржи найдите минутное окно, в течение которого наибольшее количество сделок проведено на этой бирже.

Входные данные:
Входные данные содержат несколько строк. Их можно прочитать из standart i/o или из файла "trades.csv".
Каждая линия содержит информацию об одной сделке: ВРЕМЯ, ЦЕНА, РАЗМЕР, БИРЖА. Числа разделены запятой.
Строки отображаются в порядке возрастания ВРЕМЯ. ВРЕМЯ может повторяться.
Размер входных данных не превышает 5 Мбайт.
См. пример ниже, чтобы понять точный формат ввода.

Выходные данные:
Если ввод содержит информацию об k биржах, напечатайте k строк в std i/o.
Каждая строка должна содержать только число - максимальное количество сделок во время минутного окна.
Ответы для бирж должны быть отсортированы в лексикографическом порядке.


You are given a content of CSV-file with information about set of trades. It contains the following columns:
TIME - Timestamp of a trade in format Hour:Minute:Second.Millisecond
PRICE - Price of one share
SIZE - Count of shares executed in this trade
EXCHANGE - The exchange that executed this trade
For each exchange find the one minute-window during which the largest number of trades took place on this exchange.

Input format

Input contains several lines. You can read it from standart input or file “trades.csv”
Each line contains information about one trade: TIME, PRICE, SIZE and EXCHANGE. Numbers are separated by comma.
Lines are listed in ascending order of timestamps. Several lines can contain the same timestamp.
Size of input file does not exceed 5 MB.
See the example below to understand the exact input format.
Output format

If input contains information about k exchanges, print k lines to standart output.
Each line should contain the only number — maximum number of trades during one minute-window.
You should print answers for exchanges in lexicographical order of their names.

Ввод
09:30:01.034,36.99,100,V
09:30:55.000,37.08,205,V
09:30:55.554,36.90,54,V
09:30:55.556,36.91,99,D
09:31:01.033,36.94,100,D
09:31:01.034,36.95,900,V


Вывод
2
3


Notes

In the example four trades were executed on exchange “V” and two trades were executed on exchange “D”. Not all of the “V”-trades fit in one minute-window, so the answer for “V” is three.

Я написал следующее решение, которое в системе валится на 3-ем тесте. Похоже, алгоритм недостаточно эффективен. Требование такое, что он должен выполняться за O(n).

Вот снипет:
public class Test {

    private static Map<String, Date> timestamps = new HashMap<>();
    private static Set<String> exchanges = new HashSet<>();
    private static SimpleDateFormat dateFormat = new SimpleDateFormat("hh:mm:ss.SSS");
    private static Map<String, Integer> results = new HashMap<>();

    public static void main(String... args) throws ParseException, IOException {
        Scanner input = new Scanner(System.in);
        String dataRow;

        while (input.hasNextLine()) {
            dataRow = input.nextLine();
            if (dataRow.isEmpty()) {
                break;
            }
            String[] data = dataRow.split(",");
            String timestamp = data[0];
            String exchange = data[3];

            calculateExchanges(timestamp, exchange);
        }

        results.entrySet().forEach(System.out::println);
    }

    private static void calculateExchanges(String timestamp, String exchange) throws ParseException{
        if (!(exchanges.contains(exchange))) {
            results.put(exchange, 1);
            exchanges.add(exchange);
            Date endOfTransaction = dateFormat.parse(timestamp);
            timestamps.put(exchange, incrementMinutes(endOfTransaction, 1));
        } else {
            Date current = dateFormat.parse(timestamp);
            if (current.getTime() < timestamps.get(exchange).getTime()) {
                results.put(exchange, results.get(exchange) + 1);
            }
        }
    }

    private static Date incrementMinutes(Date date, int minutes) {
        Calendar calendar = Calendar.getInstance();
        calendar.setTime(date);
        calendar.add(Calendar.MINUTE, minutes);
        return calendar.getTime();
    }
}


Как можно улучшить алгоритм?
  • Вопрос задан
  • 205 просмотров
Пригласить эксперта
Ответы на вопрос 1
byxo-cyze
@byxo-cyze
Спасаю мир.
Я не умею описывать алгоритмы, но я попытался. Можно уменьшить кол-во map-ов, мне так удобнее.
Алгоритм

1. Создаем map, который содержит максмальное кол-во сделок в одну минуту. - result и map текущий результат - current_result.
Создаем map, который содержит первоначальное время. - times (изначальное 0)
2. Считываем одну строку, получаем time и exchange
3. Если times.time + 60 > time ( если первоначальное время в секундах + 60 меньше текущего времени),
тогда current_result.result++;
Иначе
result.result = max(result.result, current_result.result) ( определение макисмального результата)
times.time = time (текущее время становится первоначальным)
current_result.result = 1 (сейчас в минутном окне 1 сделка)
4. goto 2.
5. Вывести отсортированный result.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы