Как применить замаскированный массив к очень большой JSON быстро

Question

Данные

В настоящее время я работаю с очень большими JSON файлами, отформатированными как таковые

{key: [1000+ * arrays of length 241],
 key2: [1000+ * arrays of length 241],
 (...repeat 5-8 times...)}

Данные структурированы таким образом, что n ый элемент в массиве каждого ключа принадлежит n -ому объекту. Думайте об этом как о каждой клавише, являющейся дескриптором, таким как «высота» или «давление». И поэтому, чтобы получить «высоту» и «давление» сущности, вы должны получить доступ к индексу сущностей n во всех массивах. Поэтому все массивы ключей имеют одинаковую длину Z

Как вы можете себе представить, работать с этим в целом - боль. Поэтому всякий раз, когда я выполняю какие-либо манипуляции с данными, я возвращаю замаскированный массив длины Z , заполненный 1 и 0. 1 означает, что данные в этом индексе в каждом ключе должны быть сохранены, а 0 означает, что они должны быть опущены)

---

Проблема

Как только все мои манипуляции с данными были выполнены, мне нужно применить маскированный массив к данным, чтобы вернуть копию исходных данных JSON, но где длина массива каждого ключа Z равна числу единиц в маскированном массиве (если элемент в массив с индексом n равен 0, тогда элемент в индексе n будет удален из всех массивов ключа json и наоборот)

---

Моя попытка

# mask: masked array
# d: data to apply the mask to
 def apply_mask(mask, d):
    keys = d.keys()
    print(keys)
    rem = [] #List of index to remove
    for i in range(len(mask)):
        if mask[i] == 0:
            rem.append(i) #Populate 'rem'

        for k in keys:
            d[k] = [elem for elem in d[k] if not d[k].index(elem) in rem]

    return d

Это работает как задумано, но требует много времени для таких больших JSON данных

---

Вопрос

Я надеюсь, что все выше было ясно и поможет вам понять мой вопрос:

Существует ли более оптимальный / более быстрый способ применения маскированного массива к данным, как показано выше?

Cheers

Answer 1

Проблема заключается в высоких алгоритмах c сложности кода. Можно разработать гораздо более быстрый алгоритм.

Пусть K будет количеством ключей в словаре d (ie. len(d)). Пусть Z будет размером маски (ie. len(mask)), который также является типичным размером значений массива в d (ie. len(d[key]) для любого key).

Алгоритмы c сложность исходного кода O(Z^3 * K). Это связано с тем, что rem является списком, а in rem выполняется за линейное время, а также потому, что d[k].index(elem) выполняет поиск elem за d[k] и за линейное время.

Решение, предложенное Finefoot быстрее. Действительно, сложность его кода составляет O(Z^2 * K) (поскольку del выполняется за линейное время в списках CPython).

Однако это возможно сделать расчет по линейному времени: O(K * Z). Вот как:

def apply_mask(mask, d):
    for key in d:
        d[key] = [e for i,e in enumerate(d[key]) if mask[i]!=0]
    return d

Этот код должен быть на несколько порядков быстрее.

PS: Я думаю, что первоначальный алгоритм неверен в отношении описания проблемы. Действительно, некоторые элементы, которые следует сохранить, могут быть удалены, поскольку rem не очищается между итерациями (и, таким образом, индексы накапливаются).

Answer 2

Это будет медленно, потому что

d[k] = [elem for elem in d[k] if not d[k].index(elem) in rem]

каждый раз полностью воссоздает внутренний список.

Поскольку вы уже модифицируете d на месте, вы можете просто удалите соответствующие элементы:

def apply_mask(mask, d):
    for i, keep in enumerate(mask):
        if not keep:
            for key in d:
                del d[key][i - len(mask)]
    return d

(используются отрицательные индексы i - len(mask), поскольку положительные индексы больше не работают, если список уже изменил свою длину из-за ранее удаленных элементов.)