Специалист по Data Science с уклоном в машинное зрение
Контакты

Достижения

Все достижения (28)

Наибольший вклад в теги

Все теги (188)

Лучшие ответы пользователя

Все ответы (498)
  • Как найти арифметическую прогрессию в списке?

    adugin
    @adugin Куратор тега Python
    import numpy as np
    from collections import deque
    from itertools import combinations
    
    # data = np.array([1487, 1847, 4817, 4871, 7481, 7841, 8147, 8741])
    
    np.random.seed(42)
    data = np.random.randint(0, 100000, 1000)
    data.sort()
    
    # Интуитивный подход (baseline), O(n^3)
    def find_evenly_spaced_v1(data):
        for a, b, c in combinations(data, 3):
            if b - a == c - b:
                yield a, b, c
                
    # Эмпирическая оптимизация, O(n^2)
    def find_evenly_spaced_v2(data):
        dataset = set(data)
        for a, c in combinations(data, 2):
            b, mod = divmod(a + c, 2)
            if (mod == 0) and (b in dataset):
                yield a, b, c
    
    # Векторный вариант
    def find_evenly_spaced_v3(data):
        grid = data.reshape(-1, 1) + data.reshape(1, -1)
        divs, mods = np.divmod(grid, 2)
        mask = np.tri(*grid.shape, -1, dtype='bool') & np.isin(divs, data) & ~ mods.astype('bool')
        for c, a in zip(*np.where(mask)):
            b = divs[a, c]
            a, c = data[[a, c]]
            yield a, b, c

    Измерения скорости для 1000 элементов:

    5d95912c852ea517827440.png
    Ответ написан
  • Задача на декомпрессию строки. Почему код проходит не все тесты?

    adugin
    @adugin Куратор тега Python
    К чему такие сложности
    import re
    
    def decode(encoded):
        def repl(m): return m.group(2) * int(m.group(1))
        reg = re.compile('\((\d+)(\w+)\)')
        while True:
            decoded = reg.sub(repl, encoded)
            if decoded == encoded:
                return decoded
            encoded = decoded 
            
    assert decode('(2(3ac)a)') == 'acacacaacacaca'
    assert decode('(3(2aba))') == 'abaabaabaabaabaaba'
    assert decode('(3a)') == 'aaa'  # уменьшение длины
    Ответ написан
  • Как ускорить перемножение матриц в numpy?

    adugin
    @adugin Куратор тега Python
    Не нужно этого делать.

    Во-первых, следует учитывать важность row-major и column-major order в этой операции:
    5da1a98421c64984085602.png

    Во-вторых, переход от int32 к float32 (или float64) даёт радикальное ускорение за счёт BLAS:
    5da1c7d110982244427246.png

    BLAS уже используется в numpy "под капотом" (по крайней мере, в дистрибутиве Anaconda), поэтому не следует явным образом вызывать эти функции вручную - как показано выше, это будет медленее.

    5da1bf09df2f7466403215.png
    P.S. Теория вкратце:
    Performance Tips of NumPy ndarray
    Understanding the internals of NumPy to avoid unne...
    Ответ написан
    Комментировать
  • Что нужно сделать во втоорой части задания?

    adugin
    @adugin Куратор тега Python
    Подозреваю, речь о том, чтобы взять из матрицы случайную строку или столбец в виде слова:
    5dd8e6a0e9166100858750.png

    Ответ написан
    2 комментария
  • Как найти самый большой подмассив отрицалильных чисел в 2Д массиве?

    adugin
    @adugin Куратор тега Python
    Написал довольно производительное решение на свёртках. Для вычисления свёртки conv матрицы mask с ядром kernel используется filter2d из OpenCV, но эта функция может быть заменена на аналогичную из любой другой математической библиотеки - надо смотреть, какая быстрее. Также принципиально, что вычисления производятся во float32, а не в целых числах - так на порядки (!) быстрее.

    import cv2
    import numpy as np
    
    data = """1 -9 -2 8 6 1
    8 -1 -11 -7 6 4
    10 12 -1 -9 -12 14
    8 10 -3 -5 17 8
    6 4 10 -13 -16 19"""
    
    # matrix = np.random.randint(-128, 128, (1000, 1000), dtype=np.int32)
    matrix = np.int32([line.split() for line in data.splitlines()])
    
    def find_max_kernel(matrix, border=cv2.BORDER_ISOLATED):
        max_area = 0
        mask = np.float32(matrix < 0)
        ones = np.ones_like(mask)
        conv_x = np.zeros_like(mask)
        conv_y = np.zeros_like(mask)
        max_h, max_w = mask.shape
        for h in range(1, max_h + 1):
            cv2.filter2D(mask, -1, ones[:h, None, 0], conv_y, (0, 0), 0, border)
            for w in range(1, max_w + 1):
                area = h * w
                if area > max_area:
                    cv2.filter2D(conv_y, -1, ones[None, 0, :w], conv_x, (0, 0), 0, border)
                    if conv_x.max() == area:
                        max_area, shape = area, (h, w)
                    else:
                        if w == 1:
                            max_h = h - 1
                        if h == 1:
                            max_w = w - 1
                        break
            if h >= max_h:
                break
        cv2.filter2D(mask, -1, np.ones(shape, np.float32), conv_x, (0, 0), 0, border)
        p1 = np.array(np.unravel_index(conv_x.argmax(), conv_x.shape))
        p2 = p1 + shape - 1            
        return p1, p2
    
    print(*find_max_kernel(matrix), sep='\n')

    Матрица 1000 х 1000 на моих 2 ядрах обрабатывается в среднем за 82 мс:
    5de1dfa69874f249734492.png
    Пример применения алгоритма: найдена самая большая субматрица - вписанный квадрат
    5ddedb4405be8854388006.png
    Ответ написан
    Комментировать

Лучшие вопросы пользователя

Все вопросы (10)