[java] вопрос по алгоритмам

kill-still

Есть маппинг Map<String, String> такого типа:


categoryID  -> category 

rusName     -> name.lang.rus

engName     -> name.lang.eng

germanName  -> name.lang.de

cost        -> prices.rus.price

currencyRus -> prices.rus.currency

price       -> prices.eng.price

usaCurrency -> prices.eng.currency

И есть поток данных (каждый ряд является массивом значений). Привожу только один ряд:


categoryID rusName engName    germanName cost currencyRus price usaCurrency

2          ромашка Matricaria Kamillen   100  рублей      4     $

.........................

Из них надо создать древовидную структуру (например HashMap<String, Object>) и отдать её дальше:


category = 2

name

    lang

        rus = ромашка

        eng = Matricaria

        de = Kamillen

prices

    rus 

        price = 100

        currency = рублей

    eng 

        price = 4

        currency = $

Сделать надо это быстро, потому что структура большая и ветвистая, поток очень интенсивный.
Как бы я это сделал в другом языке программирования:
Создал бы структуру-заготовку без данных и массив, где индексом является номер элемента из массива значений (из потока данных а значением - смещение поля под это значение в структуре-заготовке относительно указателя на рут. При получении следующего ряда бы просто клонировал заготовку и итерируясь одновременно по массиву значений и смещений записывал текущее значение по адресу ссылка_на_клон+текущее_смещение.
В яве пока что написал "в лоб":


        Map<String, Object> root = new LinkedHashMap<String, Object>

        for (int i = 0; i < rowMeta.size; i++) {

            ValueMetaInterface valueMeta = rowMeta.getValueMeta(i);

            String name = mapping.get(valueMeta.getName;

            Object value = row[i];

            if (StringUtils.isNotBlank(name {

                if (name.contains("." {

                    String[] parts = name.split("\\.");

                    Map<String, Object> current = root;

                    for (int j = 0; j < parts.length; j++) {

                        String part = parts[j];

                        if (j < (parts.length - 1 {

                            Object next = current.get(part);

                            if (next == null) {

                                next = new LinkedHashMap<String, Object>

                                current.put(part, next);

                            }

                            current = (Map<String, Object>) next;

                        } else

                            current.put(part, value);

                    }

                } else

                    root.put(name, value);

            }

        }

        return root;

Не уверен, что стоит лезть ради этого в unsafe, пока вот сижу и думаю, как бы соптимизировать без этого. Но что-то под вечер пятницы не приходит ничего путнего в голову. Может вы посоветуете что-нибудь?

katrin2201

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

kill-still

какой свич? структура заранее неизвестна же. неизвестно даже количество элементов.

evgen5555

В примере приведен только один ряд. Как ты собираешься доказать, что его структура меняется?

kill-still

1) стрктура маппинга (который rusName -> name.lang.rus) меняется (задаётся в конфиге(нечто вроде проперти-файла) для разных джобов). но код должен работать для любого из них.
2) rowMeta тоже может меняться - порядок полей в row может меняться в зависимости от того, из какого потока пришёл ряд (в одном потоке всё статично). Но во всех потоках количество и набор одинаков.

evgen5555

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

kill-still

а) про сериализацию никто пока что ничего не говорил
б) что-то я выпил и не совсем вас понимаю. ты предлагаешь в этом алгоритме в том месте где current.put(part, value) запоминать current как значение к строковому ключу name?

Marinavo_0507

в какую сторону оптимизировать-то надо

katrin2201

Если количество правых частей типа "name.lang.rus" произвольно, и тебе прям надо максимально быстро это делать, за наносы, то как ты написал.
Если допустимы сотни наносов-микросы, то можно обойтись кешируемым фаст рефлекшеном от cglib.
Если микросы - то можно просто рефлекшеном.
Если кол-во правых частей фиксировано, то можно для каждого случая написать код просто.

kill-still

В сторону количества таких операций в секунду.

kill-still

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

Marinavo_0507

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

kill-still

Идея с сериализацией была фейловой. Во-первых, мы никак не можем передать, куда же писать значения. Во вторых даже просто сериализация болванки занимает время, намного больше, чем просто создание мапы. 
100 000 docs:

standard 720 ms

serialized 4188 ms

Если почитать доки по тому, как она реализована, то становится ясно, почему. Но она натолкнула меня на другую идею - глубокое клонирование. Создаём мапу, которая знает, куда в себя писать, пишем значения и тут же клонируем от неё объект. Сначала попробовал com.rits.cloning.Cloner, охренел от его "производительности", потом сам реализовал:
100 000 docs:

standard 723 ms

cloned, variant1 19953 ms

cloned, variant2 149 ms

В общем пока наверно так оставлю.

evgen5555

А ты какую сериализацию использовал? ObjectOutputStream что ли? :crazy:

kill-still

Да. А какой надо?
В любом случае, как ты собираешься переносить относительные ссылки?
Оставить комментарий
Имя или ник:
Комментарий: