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
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.