Как разбить массив на несколько меньших массивов на основе заданного критерия между соседями

Question

Mathematica имеет две очень полезные функции для группировки массива в список меньших массивов на основе заданных критериев: Split [] и SplitBy [], которые мне нужно эмулировать в коде Python3:

Split [list,test] рассматривает пары смежных элементов как идентичные, когда применение к ним функции "test" дает True,

SplitBy [list, f] разбивает список на подсписки, состоящие из последовательностей последовательных элементов, которыедать то же значение, когда применяется f .

Таким образом, если

a=[2,3,5,7,11,13,17,19,23,29]

Split [a, (# 2- # 1 <4) &] дает: </p>

[[2,3,5,7],[11,13],[17,19],[23],[29]]

и SplitBy [a, (Mod [#, 2] == 0) &] дает:

[[2],[3,5,7,11,13,17,19,23,29]]

На практике массив, который нужно разделить, может быть двухмернымТаблица и тестовые функции могут работать с элементами в отдельных столбцах.

Как это поведение эффективно закодировано в Python3?

Answer 1

У вас нет быстрого ответа на первую часть вашего вопроса, и lenik уже предлагает хорошее решение на основе zip, но SplitBy можно легко воспроизвести с помощью функции groupby itertoolsмодуль ( документ здесь ).

Осторожно, groupby будет вставлять разделитель (~ создавать новую группу) каждый раз при смене ключа. Поэтому, если вы хотите что-то вроде SplitBy, вам нужно сначала отсортировать его по ключевой функции.

В конце это даст вам что-то вроде этого:

>>> def split_by(l, func):
        groups = []
        sorted_l = sorted(l, key=func)
        for _, g in it.groupby(sorted_l, key=func):
            groups.append(list(g)) 
        return groups

>>> split_by([2,3,5,7,11,13,17,19,23,29], lambda x: x%2)                                                                                                                                                                     
[[2], [3, 5, 7, 11, 13, 17, 19, 23, 29]]

Oneверсия с использованием списка:

splited_by = [list(g) for _, g in it.groupby(sorted(l, key=func), key=func)]

Быстрый тест timeit на моем старом и сломанном ноутбуке:

• версия itertools

>>> %timeit split_by([2,3,5,7,11,13,17,19,23,29], lambda x: x%2) 8.42 µs ± 92.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

• zip-версия

>>> %timeit split_by([2,3,5,7,11,13,17,19,23,29], lambda x: x%2) 10.8 µs ± 53.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

• пробная версия

>>> %timeit split_by([2,3,5,7,11,13,17,19,23,29], lambda x: x%2) 12.6 µs ± 162 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Answer 2

Вот несколько возможных решений:

a) Использование встроенного в Python zip

def split(lst, test):
    res = []
    sublst = []

    for x, y in zip(lst, lst[1:]):
        sublst.append(x)
        if not test(x, y):
            res.append(sublst)
            sublst = []

    if len(lst) > 1:
        sublst.append(lst[-1])
        if not test(lst[-2], lst[-1]):
            res.append(sublst)
            sublst = []

    if sublst:
        res.append(sublst)

    return res


def split_by(lst, test):
    return split(lst, lambda x, y: test(x) == test(y))


if __name__ == '__main__':
    a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    print(split(a, lambda x, y: y - x < 4))
    print(split_by(a, lambda x: (x % 2) == 0))

b) цикла for с внутренней попыткой / исключением:

def split(lst, test):
    res = []
    sublst = []

    for i, x in enumerate(lst):
        try:
            y = lst[i + 1]
            sublst.append(x)
        except IndexError:
            x, y = lst[i - 1], lst[i]
            sublst.append(y)

        if not test(x, y):
            res.append(sublst)
            sublst = []

    if sublst:
        res.append(sublst)

    return res


def split_by(lst, test):
    return split(lst, lambda x, y: test(x) == test(y))


if __name__ == '__main__':
    a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    print(split(a, lambda x, y: y - x < 4))
    print(split_by(a, lambda x: (x % 2) == 0))

Вывод:

[[2, 3, 5, 7], [11, 13], [17, 19], [23], [29]]
[[2], [3, 5, 7, 11, 13, 17, 19, 23, 29]]