Как еще чуть ускорить алгоритм?

Question

[lutokris]

Всем добра. Решаю задачку по определению расстояния до ближайшего нуля в элементах списка. Типа допустим есть список вида 5 3 0 2 0 3 а на выходе должно получиться 2 1 0 1 0 1. Я конечно пошел по немного "странному" пути - но решил пойти до конца и сделать в таком виде. У меня конечно все работает, трачу минимум памяти, но не укладываюсь в отведенное время на 0.77 секунд. Никак не могу понять в каком участке кода что мне оптимизировать чтобы выиграть еще 0.77 секунд(

def know_range(n):
    result = []
    half = n // 2
    if n == 1:
        result.append(1)
        return result
    result += [x for x in range(1, half+1)]
    if n & 1: # если нечетный
        result.append(half+1)
    result += [x for x  in range(half, 0, -1)]
    return result


def file_read_to_byte_discrete(f_path):
    res_arr = 0b0
    len_arr = 0b0
    n = 0
    with open(f_path) as f:
        n = int(f.readline()) + 1
        len_arr = 0b1 << n
        buf = ""
        #for i in f.read():
        i = " "
        while i != "":
            i = f.read(1)
            if i != " " and i != "":
                buf+= i
            else:
                if int(buf) | 0:
                    res_arr = res_arr | 1
                else:
                    res_arr = res_arr | 0
                res_arr = res_arr << 1
                buf = ""
        f.close()
    res_arr = len_arr + res_arr
    res_arr = res_arr >> 1
    return res_arr


byte_arr = file_read_to_byte_discrete('input.txt')
n = len(bin(byte_arr)) - 3
result_arr = []
number = 0

# проверим левый край если там не ноль
left_null = 0
if ((byte_arr >> n-1) & 1):
    number = 0
    for i in range(n-1, -1, -1):
        if not ((byte_arr >> i) & 1): # если найдем нолик выходим
            if number != 0:
                left_null = number
            else:
                left_null = 1
            break
        else:
            number += 1
    if number != 0:
        for i in range(number, 0, -1):
            result_arr.append(i)

number = 0
for i in range(n-1-left_null, -1, -1):
    if not ((byte_arr >> i) & 1):
        # найден нолик
        if number != 0:
            result_arr = result_arr + know_range(number)
        result_arr.append(0)
        number = 0
    else:
        number += 1
# проверим правый край если там не ноль просто печатаем номера
if (byte_arr & 1):
    result_arr += [x for x in range(1, number+1)]
    

for el in result_arr:
    print(el, end=" ")

Comments

[Akina]

Вы как минимум опишите свой алгоритм, да поподробнее.

[Wataru]

Еще опишите, что там за ужас со вводом происходит. Какой формат данных в файле?

Answer 1

[Vindicar]

А не проще ли будет сделать в два прохода.
Прямым проходом делаем так: если 0, то счетчик в ноль, иначе счетчик + 1 и элемент приравниваем счетчику.
Потом то же самое делаем обратным проходом, но изменяем элемент только если он больше счетчика.
Отсюда получаем:

lst=[5, 3, 0, 2, 0, 3, 8, 2, 9, 7, 0, 0, 7, 1, 5, 3]
L = len(lst)
# если в начале списка не 0, то мы сможем задать корректные значения только на обратном ходе
# так что ставим заведомо большее значение счетчика
counter = len(lst) if lst[0] != 0 else 0
for i in range(0, L):
  if lst[i] == 0:
    counter = 0
  else:
    counter += 1
    lst[i] = counter
# обратный ход
counter = lst[-1] - 1 #чтобы не запороть последние элементы
for i in range(L-1, -1, -1):
  if lst[i] == 0:
    counter = 0
  else:
    counter += 1
    lst[i] = min(counter, lst[i])

print(lst)
# [2, 1, 0, 1, 0, 1, 2, 3, 2, 1, 0, 0, 1, 2, 3, 4]

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

Comments

[lutokris]

Я немного в шоке, потому что я сперва сам делал в подобном роде, с двойным обходом и у меня сперва возникали проблемы с памятью, а потом все равно не смог уложиться в 3 секунды. Но у вас работает всего за 2.366 секунд и это n=10^6 элементов. Я в шоке, буду подробно дебажить ваш алгоритм и попытаюсь понять за счет чего он такой быстрый.

[Vindicar]

lutokris, чем проще тем быстрее, я думаю =) Специально не оптимизировал, но тут только эквивалент цикла с параметром, чтение элемента массива и присваивание элемента массива - без модификации длины списка, без создания срезов или других списков. Гипотетически можно было попробовать использовать array для дальнейшего прироста скорости (и возможно, выигрыша по памяти), но не уверен что будет выигрыш, да и с загрузкой будут проблемы: неизвестно насколько большие числа могут быть, неясно сколько их.

Answer 2

[dmshar]

А вот так не быстрее будет?
(Пример специально усложнил)

lst=[5, 3, 0, 2, 0, 3, 8, 2, 9, 7, 0, 0,7,1, 5, 3]

l=[i for i,v in enumerate(lst) if v == 0]
m_l=[]
for i,ls in enumerate(lst):
    m=len(lst)
    for j in l:
        if m>abs(i-j):
            m=abs(i-j)
    m_l.append(m)
print (m_l)

Результат:
[2, 1, 0, 1, 0, 1, 2, 3, 2, 1, 0, 0, 1, 2, 3, 4]

Если надо еще ускорить - можно порождать список m_l сразу, т.е.
m_l=[len(lst)]*len(lst)
и
m_l.append(m)
заменить на
m_l[i]=m
За счет статики работы с списком должно бы получиться еще быстрее.

Comments

[lutokris]

Ваш алгоритм мне очень понравился за изящное использование генератора списков, но к сожалению почему-то он по времени все так же не укладывается и даже чуть медленнее чем мой громоздкий побитовый( у меня 3.076 секунд, у вашего 3.08, а при попытке ускорения - он наоборот почему то замедляется еще.

[dmshar]

lutokris, А попробуйте еще так:

l=[i for i,v in enumerate(lst) if v == 0]
с=len(lst)
m_l=[с]*с
for i in range(с):
    for j in l:
        if m_l[i]>abs(i-j):
            m_l[i]=abs(i-j)
print (m_l)

Answer 3

[Alexandroppolus]

Путь действительно странный. А главное, есть какие-то непонятные действия с массивом, которые, возможно, приводят к копированию, например result_arr = result_arr + know_range(number)

Проще всего было бы из строки получить массив с возрастающими ненулевыми интервалами, а потом пройтись по нему справа налево и "посрезать уголки":

строка "5 3 0 4 6 1 5 0 9 2 3 0"
массив после первого обхода: [inf, inf, 0, 1, 2, 3, 4, 0, 1, 2, 3, 0]
после обратного обхода, тот же массив: [2, 1, 0, 1, 2, 2, 1, 0, 1, 2, 1, 0]

Comments

[lutokris]

import time


def know_range(n):
    half = n // 2
    if n == 1:
        print("1", end=" ")
        return

    [print(x, end=" ") for x in range(1, half+1)]
    if n & 1: # если нечетный
        print(half+1, end=" ")
    [print(x, end=" ") for x  in range(half, 0, -1)]
    return


def file_read_to_byte_discrete(f_path):
    res_arr = 0b0
    len_arr = 0b0
    n = 0
    with open(f_path) as f:
        n = int(f.readline()) + 1
        len_arr = 0b1 << n
        buf = ""
        i = " "
        while i != "":
            i = f.read(1)
            if i != " " and i != "":
                buf+= i
            else:
                if buf == "":
                    break
                if int(buf) | 0:
                    res_arr = res_arr | 1
                else:
                    res_arr = res_arr | 0
                res_arr = res_arr << 1
                buf = ""
        f.close()
    res_arr = len_arr + res_arr
    res_arr = res_arr >> 1
    return res_arr


byte_arr = file_read_to_byte_discrete('input.txt')
n = len(bin(byte_arr)) - 3
number = 0

# проверим левый край если там не ноль
left_null = 0
if ((byte_arr >> n-1) & 1):
    number = 0
    for i in range(n-1, -1, -1):
        if not ((byte_arr >> i) & 1): # если найдем нолик выходим
            if number != 0:
                left_null = number
            else:
                left_null = 1
            break
        else:
            number += 1
    if number != 0:
        for i in range(number, 0, -1):
            print(i, end=" ")

number = 0
for i in range(n-1-left_null, -1, -1):
    if not ((byte_arr >> i) & 1):
        # найден нолик
        if number != 0:
            know_range(number)
        print("0", end=" ")
        number = 0
    else:
        number += 1
# проверим правый край если там не ноль просто печатаем номера
if (byte_arr & 1):
    [print(x, end=" ") for x in range(1, number+1)]

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

[Alexandroppolus]

lutokris,

я сперва считывал из файла и преобразовывал в дискретный формат типа 1110011101

думаю, это лишнее

вот, сразу из строки в массив с возрастаниями, потом обратный обход

function distances(str) {
    const arr = str.split(' ');
    let num = arr.length;
    for (let i = 0; i < arr.length; ++i) {
        num = arr[i] === '0' ? 0 : num + 1;
        arr[i] = num;
    }
    num = arr.length;
    for (let i = arr.length - 1; i >= 0; --i) {
        num = arr[i] === 0 ? 0 : num + 1;
        arr[i] = Math.min(num, arr[i]);
    }
    return arr;
}