Как эффективнее организовать алгоритм парсинга JSON в данном случае?

Question

[uniquepeero]

Приветствую. Выполнял тестовое задание по обработке JSON.

Задание

Вывести json в котором каждый элемент это:
- неудаленная новость из списка новостей из файла news.json.
- для каждой новости указано кол-во комментариев этой новости из файла comments.json
- для каждой новости указана дата и время последнего (самого свежего) комментария

В списоке новостей должны отсутствовать новости, дата публикации которых еще не наступила.
Даты в файле хранятся в формате ISO 8601(%Y-%m-%dT%H:%M:%S) и должны отдаваться в том же формате.

Формат ответа:

news: [
        {
            id: int,
            author:	str,
            publishedAt: str,
            image:	str,
            teaser: str,
            isDeleted: bool,
            lastComment: str,
            commentsCount: int
        }
    ]

Часть файла news.json

{
    "news": [
        {
            "author": "Cynthia Pruitt",
            "content": "Democra.",
            "id": 90,
            "image": "https://",
            "isDeleted": false,
            "publishedAt": "2019-02-23T00:33:00",
            "teaser": "Successful without."
        },
        {
            "author": "Lorraine Lewis",
            "content": "Finish doctor .",
            "id": 78,
            "image": "https://",
            "isDeleted": false,
            "publishedAt": "2019-03-05T14:54:33",
            "teaser": "It during "
        },
        {
            "author": "Michael Ramirez",
            "content": "Recent seat.",
            "id": 29,
            "image": "https://",
            "isDeleted": false,
            "publishedAt": "2019-03-18T19:48:47",
            "teaser": "Entire respond."
        },
        {
            "author": "Lisa Johnson",
            "content": "Simple wide ",
            "id": 60,
            "image": "https://www",
            "isDeleted": true,
            "publishedAt": "2019-03-06T02:26:43",
            "teaser": "Brother can window"
        },

        ...

     ]
}

Часть файла comments.json

{
    "comments": [
        {
            "comment": "Perhaps as .",
            "newsId": 5,
            "publishedAt": "2019-03-12T18:50:47",
            "user": "scott17"
        },
        {
            "comment": "Everybody ",
            "newsId": 64,
            "publishedAt": "2019-03-15T16:22:50",
            "user": "keithstanle"
        },
        {
            "comment": "Total Democrat .",
            "newsId": 23,
            "publishedAt": "2019-03-22T16:01:13",
            "user": "kathleendouglas"
        },
        {
            "comment": "Yes American.",
            "newsId": 33,
            "publishedAt": "2019-03-03T03:52:55",
            "user": "nicholasjohnson"
        },

        ...

    ]
}

Моё решение

# news = news.json
# comments = comments.json
def foo():
    good_news = []
    for news_item in news['news']:
        if datetime.now().isoformat() > news_item['publishedAt'] and not news_item['isDeleted']:
            news_id = news_item['id']
            comments_counter = 0
            last_comment = datetime.strptime('2000-01-01T00:00:00', '%Y-%m-%dT%H:%M:%S')

            for comment in comments['comments']:
                if comment['newsId'] == news_id:
                    comments_counter += 1
                    comment_time = datetime.strptime(comment['publishedAt'], '%Y-%m-%dT%H:%M:%S')
                    if comment_time > last_comment:
                        news_item['lastComment'] = comment['publishedAt']
                        last_comment = comment_time

            news_item['commentsCount'] = comments_counter
            good_news.append(news_item)    

    return {"news": good_news}

Код рабочий, только сделали замечание по поводу сложности алгоритма. "Цикл в цикле, можно сильно лучше. Общая сложность N*M, где N - кол-во новостей, M - кол-во комментариев"

Думал сначала парсить комментарии, собирая в словарь с ключами ID новостей, но там у меня вышел так же цикл в цикле N*M

Answer 1

[kn1ght_t]

"Думал сначала парсить комментарии, собирая в словарь с ключами ID новостей, но там у меня вышел так же цикл в цикле N*M"

почему? сначала парсим все комментарии в словарь
это M операций

потом идем по всем новостям - это N операций

итого N + M

где тут цикл в цикле?

Answer 2

[Вадим Шаталов]

При обработке массивов бэд практис фильтовать внутри цикла

for news_item in news['news']:
    if datetime.now().isoformat() > news_item['publishedAt'] and not news_item['isDeleted']:

замени на

news_filter = lambda i: datetime.now().isoformat() > i['publishedAt'] and not i['isDeleted']
for news_item in filter(news_filter, news['news']):
   ...

Так же и с внутренним циклом

Comments

[Владимир Олохтонов]

А какая разница-то с точки зрения производительности?
Или просто некрасиво?

[Вадим Шаталов]

Походу только читаемость как ни странно

import random

source_list = [random.randrange(1000) for _ in range(10_000_000)]

def one(source):
    counter = 0
    for i in source:
        if i < 20:
            counter += 1
    return counter

%time print(one(source_list))
200291
CPU times: user 468 ms, sys: 31.9 ms, total: 500 ms
Wall time: 508 ms

def two(source):
    counter = 0
    for i in filter(lambda x: x < 20, source):
        counter += 1
    return counter

%time print(two(source_list))
200291
CPU times: user 1.04 s, sys: 7.29 ms, total: 1.04 s
Wall time: 1.05 s

def three(source):
    list_filter = lambda x: x < 20
    counter = 0
    for i in filter(list_filter, source):
        counter += 1
    return counter

%time print(three(source_list))
200291
CPU times: user 1.1 s, sys: 11.5 ms, total: 1.12 s
Wall time: 1.12 s

def four(source):
    return sum((1 for i in source if i < 20))

%time print(four(source_list))
200291
CPU times: user 422 ms, sys: 9.24 ms, total: 431 ms
Wall time: 437 ms