Как реализовать скользящее окно над строкой в ​​Python, чтобы каждое новое окно строилось в O (1) - PullRequest
Новая
       26

Как реализовать скользящее окно над строкой в ​​Python, чтобы каждое новое окно строилось в O (1)

0 голосов
/ 13 июня 2019

Я пытаюсь оптимизировать скорость алгоритма.Это скользящее окно фиксированного размера m поверх длинной строки n.Пока что это работает за (n - m)m время, где m берется за конструкцию раздвижного окна tmp длины m.

for i in range(0, n - m + 1):
  tmp = string[i:i + m]
  # then doing smth with tmp string

Интересно, смогу ли я сократить время до n - m, используя соединение, потому что каждый раз, когда я делаю сдвиг в один символ и все, что мне нужно, это обрезать первый символ и добавитьследующий 

tmp = string[:m]
for i in range(1, n - m + 1):
  tmp = ''.join([tmp[1:], string[i + m - 1]])
  # then doing smth with tmp string

Проблема в том, что я не могу понять, как выполнить tmp[1:] в постоянное время.

У вас есть идеи, пожалуйста?

1 Ответ

1 голос
/ 13 июня 2019

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

Мой тест должен был иметь список длиной 10000 и иметь окно размером 1000, скользящее по нему. Затем в каждой итерации просто суммируйте все элементы окна, а затем суммируйте все результаты всех итераций.

Таковы результаты: 

run_sliced:       296.210 ms/it (Iterations: 7)
run_memoryview:   409.670 ms/it (Iterations: 5)
run_shift:        296.495 ms/it (Iterations: 7)
run_cpp:            3.066 ms/it (Iterations: 653)
run_rust:           1.132 ms/it (Iterations: 1768)

Самая странная часть этого теста - то, что memoryview был самым медленным. Не совсем уверен, что с этим делать.

Python: 

import time
import array

# Our external c++ and rust functions
import ext_cpp
import ext_rust

# List of size 10000.
# Our moving window is size 1000. That means we need to slice 9000 times.
# We simply take the sum of all numbers in the window,
# and then again the sum of all windows.
# Just to prevent any optimizations from happening.

listSize = 10000
windowSize = 1000

a = list(range(listSize))
numWindows = listSize - windowSize + 1

def time_it(name, func):
    t0 = time.perf_counter()
    iterations = 0

    while True:
        assert(func(a) == 45000499500)
        iterations += 1
        t1 = time.perf_counter()
        if t1 - t0 > 2:
            break

    per_iteration = 1000.0*(t1-t0)/iterations
    print("{:<15}".format(name+":")
          + "{:>10}".format(format(per_iteration, '.3f')) + " ms/it"
          + " (Iterations: " + str(iterations) + ")")

def run_sliced(a):
    r = 0
    for i in range(numWindows):
        window = a[i:i+windowSize]
        for el in window:
            r += el
    return r

def run_memoryview(a):
    r = 0
    a_raw = array.array('l', a)
    a = memoryview(a_raw)
    for i in range(numWindows):
        window = a[i:i+windowSize]
        for el in window:
            r += el
    return r

def run_shift(a):
    r = 0    
    window = a[:windowSize]
    for el in window:
        r += el
    for i in range(1, numWindows):
        window = window[1:]
        window.append(a[i + windowSize - 1])
        for el in window:
            r += el
    return r

def run_cpp(a):
    return ext_cpp.run(a, numWindows, windowSize)

def run_rust(a):
    return ext_rust.run(a, numWindows, windowSize)


time_it('run_sliced', run_sliced)
time_it('run_memoryview', run_memoryview)
time_it('run_shift', run_shift)
time_it('run_cpp', run_cpp)
time_it('run_rust', run_rust)


C ++ (pybind11): 

long run(std::vector<long> a, long windowSize, long numWindows){
    long r = 0;
    for(long i = 0; i < numWindows; i++){
        const long* window = &a[i];
        for(long j = 0; j < windowSize; j++){
            r += window[j];
        }
    }
    return r;
}


Ржавчина (PyO3): 

fn run(_py: Python, a: Vec<u64>, num_windows: usize, window_size: usize)
    -> PyResult<u64>
{
    let mut r = 0;
    for i in 0..num_windows {
        let window = &a[i..i+window_size];
        for el in window {
            r += el; 
        }
    }
    Ok(r)
}
...