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

Question

Допустим, у меня есть машина, которая отправляет 4 бита каждую секунду, и я хочу увидеть, сколько раз определенная битовая сигнатура отправляется за какое-то время.

Мне дан входной список списков, которые содержат сообщения в битах, которые со временем меняются.

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

Редактировать новый пример:

Например, этот следующий набор данных будет представлять эти данные. С горизонтальной осью, являющейся позицией бита, и вертикальной осью, являющейся выборками во времени. Так что для следующего примера у меня есть 4 полных бита и 6 полных выборок.

a = [
    [0, 0, 1, 1],
    [0, 1, 1, 1],
    [1, 1, 1, 1],
    [1, 1, 1, 1],
    [0, 0, 0, 0],
    [1, 0, 1, 0]])

Для этого набора данных я пытаюсь подсчитать, сколько раз встречается определенная битовая строка, эта длина должна быть в состоянии варьироваться, но для этого примера, скажем, я делаю 2 бита за раз.

Таким образом, первая выборка [0,0,1,1] будет разбита на эту [00,01,11] и второй будет [01,11,11], а третий будет [11,11,11] и так далее. Составить список примерно так:

y = [
    [00,01,11],
    [01,11,11],
    [11,11,11],
    [11,11,11],
    [00,00,00],
    [10,01,10]]

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

Словарь хотел бы это

z = [
    {'00':2, '01':1, '11':2, '10':1}, 
    {'00':1, '01':2, '11':3},
    {'00':1, '11':4], '10':1}]

Найти количество легко, если есть список проанализированных элементов. Однако при получении необработанных данных в этот разобранный список у меня возникли некоторые проблемы. У меня есть реализация, но по сути это 3 для циклов, и она работает очень медленно на большом наборе данных. Конечно, есть лучший и более питонный способ обойти это?

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

UPDATE: Я смотрел вокруг на другие вещи и пришел к этому. Не уверен, что это лучшее решение.

import numpy as np
a = np.array([
    [0, 0, 1, 1],
    [0, 1, 1, 1],
    [1, 1, 1, 1]])

my_list = a.astype(str).tolist()


# How many elements each
# list should have
n = 2

# using list comprehension
final = [([''.join(c[i:(i) + n]) for i in range((len(c) + n) // n)]) for c in my_list]

final = [['00', '01', '11'], ['01', '11', '11'], ['11', '11', '11']]

ОБНОВЛЕНИЕ 2:

Я запустил следующие реализации и протестировал там скорости, и вот что я придумал.

Выполнение данных на небольшом примере из 4 битов и 4 выборок шириной 2.

x = [
    [0,0,1,1],
    [0,1,1,1],
    [1,1,1,1]]

• Моя реализация заняла 0,0003 секунды

• Реализация Kasrâmvd заняла 0,0002 секунды

• Реализация Криса заняла 0,0002 секунды

• Реализация Павла заняла 0,0243 секунды

Однако при работе с фактическим набором данных из 64 бит и 23 497 выборок с шириной 2. Я получил следующие результаты:

• Моя реализация заняла 1,5302 секунды

• Реализация Kasrâmvd заняла 0,3913 секунд

• Реализация Криса заняла 2,0802 секунды

• Реализация Павла заняла 0,0204 секунды

Answer 1

Если вы хотите провести геометрический или алгебраический анализ / решение, вы можете сделать следующее:

In [108]: x = np.array([[0,0,1,1],
     ...:       [0,1,1,1],
     ...:       [1,1,1,1]])
     ...:       

In [109]: 

In [109]: pairs = np.dstack((x[:, :-1], x[:, 1:]))

In [110]: x, y, z = pairs.shape

In [111]: uniques
Out[111]: 
array([[0, 0],
       [0, 1],
       [1, 1]])

In [112]: uniques = np.unique(pairs.reshape(x*y, z), axis=0)

# None: 3d broadcasting is not recommended in any situation, please read doc for more details,
In [113]: R = (uniques[:,None][:,None,:] == pairs).all(3).sum(-1)

In [114]: R
Out[114]: 
array([[1, 0, 0],
       [1, 1, 0],
       [1, 2, 3]])

Столбцы матрицы R обозначают количество каждой уникальной пары в uniques объекте вкаждая строка вашего исходного массива.

Затем вы можете получить объект Python, например, как вы хотите, следующим образом:

In [116]: [{tuple(i): j for i,j in zip(uniques, i) if j} for i in R.T]
Out[116]: [{(0, 0): 1, (0, 1): 1, (1, 1): 1}, {(0, 1): 1, (1, 1): 2}, {(1, 1): 3}]

Answer 2

Вот подход, использующий свертку. Поскольку быстрая свертка зависит от БПФ и, следовательно, должна выполнять вычисления с плавающей точкой, у нас есть 52-битная мантисса и 53 - максимальная длина шаблона, с которой мы можем справиться.

import itertools as it
import numpy as np
import scipy.signal as ss

MAX_BITS = np.finfo(float).nmant + 1

def sliding_window(data, width, return_keys=True, return_dict=True, prune_empty=True):
    n, m = data.shape
    if width > MAX_BITS:
        raise ValueError(f"max window width is {MAX_BITS}")
    patterns = ss.convolve(data, 1<<np.arange(width)[None], 'valid', 'auto').astype(int)
    patterns += np.arange(m-width+1)*(1<<width)
    cnts = np.bincount(patterns.ravel(), None, (m-width+1)*(1<<width)).reshape(m-width+1,-1)
    if return_keys or return_dict:
        keys = np.array([*map("".join, it.product(*width*("01",)))], 'S')
        if return_dict:
            dt = np.dtype([('key', f'S{width}'), ('value', int)])
            aux = np.empty(cnts.shape, dt)
            aux['value'] = cnts
            aux['key'] = keys
            if prune_empty:
                i,j = np.where(cnts)
                return [*map(dict, np.split(aux[i,j],
                                            i.searchsorted(np.arange(1,m-width+1))))]
            return [*map(dict, aux.tolist())]
        return keys, cnts
    return cnts

example = np.random.randint(0, 2, (10,10))
print(example)
print(sliding_window(example,3))

Пример прогона:

[[0 1 1 1 0 1 1 1 1 1]
 [0 0 1 0 1 0 0 1 0 1]
 [0 0 1 0 1 1 1 0 1 1]
 [1 1 1 1 1 0 0 0 1 0]
 [0 0 0 0 1 1 1 0 0 0]
 [1 1 0 0 0 1 0 0 1 1]
 [0 1 1 1 0 1 1 1 1 1]
 [0 1 0 0 0 1 1 0 0 1]
 [1 0 1 1 0 1 1 0 1 0]
 [0 0 1 1 0 1 0 1 0 0]]
[{b'000': 1, b'001': 3, b'010': 1, b'011': 2, b'101': 1, b'110': 1, b'111': 1}, {b'000': 1, b'010': 2, b'011': 2, b'100': 2, b'111': 3}, {b'000': 2, b'001': 1, b'101': 2, b'110': 4, b'111': 1}, {b'001': 2, b'010': 1, b'011': 2, b'101': 4, b'110': 1}, {b'010': 2, b'011': 4, b'100': 2, b'111': 2}, {b'000': 1, b'001': 1, b'100': 1, b'101': 1, b'110': 4, b'111': 2}, {b'001': 2, b'010': 2, b'100': 2, b'101': 2, b'111': 2}, {b'000': 1, b'001': 1, b'010': 2, b'011': 2, b'100': 1, b'101': 1, b'111': 2}]

Answer 3

Это решение не объединяет биты, а дает их как кортежи (хотя это должно быть достаточно просто).

РЕДАКТИРОВАТЬ: сформированные строки битов по мере необходимости.

from collections import Counter

x = [[0,0,1,1],
      [0,1,1,1],
      [1,1,1,1]]



y = [[''.join(map(str, ref[j:j+2])) for j in range(len(x[0])-1)] \
     for ref in x]

for bit in y:
    d = Counter(bit)
    print(d)

Печать

Counter({'00': 1, '01': 1, '11': 1})
Counter({'11': 2, '01': 1})
Counter({'11': 3})

РЕДАКТИРОВАТЬ: Чтобы увеличить окно с 2 до 3, вы можете добавить это к своему коду:

window = 3
offset = window - 1

y = [[''.join(map(str, ref[j:j+window])) for j in range(len(x[0])-offset)] \
     for ref in x]