LINUX.ORG.RU

Как я могу оптимизировать свою программу (O(~n^2))?

 , , ,


0

1

Добрый день (я нуб, на всякий случай дублирую, кто теги не смотрит).

Я навелосипедил код, который как мне кажется медленный, что пипец.
Хотя я могу заблуждаться и все сделал ок.

Есть некоторая асинхронная функция, которая тянет данные из файла xml, сам файл на удаленном сервере

Далее псевдокод


class MyClass1 {
    String name;
    String field2;
    String field3;
    String field4;
    String field5;
    String field6;
    String field7;
    String field8;
}

class MyClass2 {
    String field1;
    String field2;
    String field3;
    String field4;
    String field5;
    String field6;
    String field7;
    String field8;
    String field9;
    String field10;
}


func Map<String, List<MyClass2>> fetchData(List<MyClass1> myClass1) {

    Map<String, List<MyClass2>> fetchedDataMapList;

    for (elemFromMyclass1 in myClass1) {
        url = 'someUrl/${elemFromMyclass1.name}';

        responseBody = http.get(url);

        xmlData = responseBody.getDataFromXml;

        list<MyClass2> myClass2List;

        xmlData.forEach((elem) {
            myClass2List.add(
                field1 = elem.1;
                field2 = elem.2;
                field3 = elem.3;
                field4 = elem.4;
                field5 = elem.5;
                field6 = elem.6;
                field7 = elem.7;
                field8 = elem.8;
                field9 = elem.9;
                field10 = elem.10;
            );
        });

        fetchedDataMapList.addKeyValue(elemFromMyclass1.name, myClass2List);
    }

    return fetchedDataMapList;
}

Как можно оптимизировать функцию fetchData, чтобы она была чутка побыстрее?

PS. Прошу без срачей и без советов в духе - «бери мой user_lang и все сделаешь в 2 строчки с супер скоростью»

UPD. Пока читал комментарии других людей, осознал, что мне такая сложная структура данных не нужна, все можно сделать намного проще и получать необходимые данные по запросу из списка. Будет быстрее и эффективней, а также не будет расходоваться память на хранения всех данных.

Не знаю насчет правильности решения, но мне подходит.

★

Последнее исправление: ChuCha (всего исправлений: 2)
Ответ на: комментарий от anonymous

Не уверен, что в dart так можно сделать, но я погуглю. А чем это поможет, обясните пожалуйста?

UPD. В dart такое не провернуть

ChuCha ★
() автор топика
Последнее исправление: ChuCha (всего исправлений: 3)

Для начала обмажь код счётчиками и определи, что именно работает медленно.

Laz ★★★★★
()
Ответ на: комментарий от Crocodoom

Конечно, Flutter сейчас горяч как никогда.

anonymous
()

можно оптимизировать сетевой ввод-вывод, попросив сервер отдать всё одним запросом и в сжатом виде (gzip?).

К чему тут алгоритмическая сложность, я не понимаю.

Lrrr ★★★★★
()
Ответ на: комментарий от Laz

А вы могли бы чуть подробнее описать как это сделать или пожалуйста дайте ссылку на мануал(англ/рус) где это можно изучить и посмотреть пример?

ChuCha ★
() автор топика
Ответ на: комментарий от Lrrr

Любопытно, но я думаю, что так вряд ли, либо не сейчас. Чтобы понять на сколько моя функция тормозная, но как ее переписать, я не знаю.

ChuCha ★
() автор топика

ну скорее всего всё упирается в http-вызов. поэтому либо как-нибудь сделай паралельные запросы (https://stackoverflow.com/a/50028201), либо на сервере попробуй вернуть всё сразу.

потом взгляд цепляется за forEach, но не совсем понятно сколько там элементов, поэтому врядли оптимизируешь.

anonymous
()
Ответ на: комментарий от anonymous

Не знаю, это все один анонимус пишет или нет. Максимальное количество элементов в forEach 877, только что посмотрел. Варьируется от 200 - 877 Элементов в list - 92

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

За ссылку спасибо, почитаю

ChuCha ★
() автор топика
Последнее исправление: ChuCha (всего исправлений: 2)
Ответ на: комментарий от anonymous

Если честно, даже не представляю как это сделать, запрос заменить рандомом.

ChuCha ★
() автор топика

Параллелизовать. Если не хочешь менять сервер, то хотя бы сделай все запросы одновременно.

Как это в Дарте работает, я не знаю.

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

Окей, спасибо, погуглю на эту тему. MOPKOBKA

Спасибо, буду изучать.

ChuCha ★
() автор топика

Собственно, алгоритмов для разбора XML два, DOM и SAX, и реализуются они библиотекой парсера. Судя по коду, у тебя DOM-парсер.

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

hobbit ★★★★★
()
Ответ на: комментарий от hobbit

На самом деле, тут есть rule of thumb: сначала оптимизируем HTTP-запросы, потом обращения к БД (к данному случаю не относится), потом уже алгоритмы.

Кстати, а что не так с DOM-ом? Памяти жрёт больше, это да, но ТС не на память жалуется, а на скорость. А по скорости DOM от SAX отличается не сильно.

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

но ТС не на память жалуется, а на скорость.

Если записей реально много, первое быстро перейдёт во второе. :)

hobbit ★★★★★
()
Ответ на: комментарий от Miguel

Дом будет как минимум тратить время на создание внутренней структуры документа. Создание каждого объекта это всё равно выделение памяти.

ya-betmen ★★★★★
()
Ответ на: комментарий от ya-betmen

Да быть-то будет, но асимптотика будет всё равно линейная (при вменяемой организации всего этого дела). И та же линейная асимптотика, но со значительно большим множителем, будет для получения XMLя по сети. Соответственно, нефиг парсинг оптимизировать, это экономия на спичках будет.

Плохо станет, если разобранный DOM не влезет в память и начнётся свопинг. Вот тогда и правда, суши вёсла.

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

Ну то что тупить будет на сетевом запросе это слов нет.

ya-betmen ★★★★★
()
Ответ на: комментарий от hobbit

Использую готовую либу для обработки xml. Да, она работает с ДОМ, но есть вариант работать с потоками, будет типа SAX. За наводку спасибо, я этот вопрос поизучаю на досуге.

Я в принципе уже придумал, что делать, в топике описал.

ChuCha ★
() автор топика
Последнее исправление: ChuCha (всего исправлений: 2)

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

anonymous
()
Вы не можете добавлять комментарии в эту тему: топик перемещен в архив.