Самый быстрый способ увеличить числовой числовой массив
Требования:
- Мне нужно собрать массив, произвольно большой от данных.
- Я могу угадать размер (примерно 100-200) без каких-либо гарантий, что массив будет соответствовать каждый раз
- Как только он вырастет до его окончательного размера, мне нужно выполнить числовые вычисления на нем, поэтому я предпочел бы, в конечном итоге, перейти к массиву с двумя размерами.
- Скорость критическая. Например, для одного из 300 файлов метод update() называется 45 миллионов раз (занимает 150 с или около того), а метод finalize() называется 500k раз (занимает в общей сложности 106 секунд)... в общей сложности 250 или так.
Вот мой код:
def __init__(self):
self.data = []
def update(self, row):
self.data.append(row)
def finalize(self):
dx = np.array(self.data)
Другие вещи, которые я пытался, включают следующий код... но это waaaaay медленнее.
def class A:
def __init__(self):
self.data = np.array([])
def update(self, row):
np.append(self.data, row)
def finalize(self):
dx = np.reshape(self.data, size=(self.data.shape[0]/5, 5))
Вот схема, как это называется:
for i in range(500000):
ax = A()
for j in range(200):
ax.update([1,2,3,4,5])
ax.finalize()
# some processing on ax
Ответы
Ответ 1
Я пробовал несколько разных вещей, с учетом времени.
import numpy as np
-
Метод, который вы указываете как медленный: (32.094 секунды)
class A:
def __init__(self):
self.data = np.array([])
def update(self, row):
self.data = np.append(self.data, row)
def finalize(self):
return np.reshape(self.data, newshape=(self.data.shape[0]/5, 5))
-
Обычный список python: (0.308 секунд)
class B:
def __init__(self):
self.data = []
def update(self, row):
for r in row:
self.data.append(r)
def finalize(self):
return np.reshape(self.data, newshape=(len(self.data)/5, 5))
-
Попытка реализовать arraylist в numpy: (0.362 секунд)
class C:
def __init__(self):
self.data = np.zeros((100,))
self.capacity = 100
self.size = 0
def update(self, row):
for r in row:
self.add(r)
def add(self, x):
if self.size == self.capacity:
self.capacity *= 4
newdata = np.zeros((self.capacity,))
newdata[:self.size] = self.data
self.data = newdata
self.data[self.size] = x
self.size += 1
def finalize(self):
data = self.data[:self.size]
return np.reshape(data, newshape=(len(data)/5, 5))
И вот как я его приурочил:
x = C()
for i in xrange(100000):
x.update([i])
Итак, похоже, что обычные старые списки Python довольно хороши;)
Ответ 2
np.append() каждый раз копирует все данные в массиве, но список увеличивает емкость в 1,125 раза. список быстрый, но использование памяти больше, чем массив. Вы можете использовать модуль массива стандартной библиотеки python, если вам нужна память.
Вот обсуждение этой темы:
Как создать динамический массив
Ответ 3
Используя объявления класса в почте Owen, здесь приведено пересмотренное время с некоторым эффектом финализации.
Короче говоря, я нахожу класс C, чтобы обеспечить реализацию, которая на 60 раз быстрее, чем метод в исходном сообщении. (извинения за стену текста)
Файл, который я использовал:
#!/usr/bin/python
import cProfile
import numpy as np
# ... class declarations here ...
def test_class(f):
x = f()
for i in xrange(100000):
x.update([i])
for i in xrange(1000):
x.finalize()
for x in 'ABC':
cProfile.run('test_class(%s)' % x)
Теперь полученные результирующие тайминги:
903005 function calls in 16.049 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 16.049 16.049 <string>:1(<module>)
100000 0.139 0.000 1.888 0.000 fromnumeric.py:1043(ravel)
1000 0.001 0.000 0.003 0.000 fromnumeric.py:107(reshape)
100000 0.322 0.000 14.424 0.000 function_base.py:3466(append)
100000 0.102 0.000 1.623 0.000 numeric.py:216(asarray)
100000 0.121 0.000 0.298 0.000 numeric.py:286(asanyarray)
1000 0.002 0.000 0.004 0.000 test.py:12(finalize)
1 0.146 0.146 16.049 16.049 test.py:50(test_class)
1 0.000 0.000 0.000 0.000 test.py:6(__init__)
100000 1.475 0.000 15.899 0.000 test.py:9(update)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
100000 0.126 0.000 0.126 0.000 {method 'ravel' of 'numpy.ndarray' objects}
1000 0.002 0.000 0.002 0.000 {method 'reshape' of 'numpy.ndarray' objects}
200001 1.698 0.000 1.698 0.000 {numpy.core.multiarray.array}
100000 11.915 0.000 11.915 0.000 {numpy.core.multiarray.concatenate}
208004 function calls in 16.885 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.001 0.001 16.885 16.885 <string>:1(<module>)
1000 0.025 0.000 16.508 0.017 fromnumeric.py:107(reshape)
1000 0.013 0.000 16.483 0.016 fromnumeric.py:32(_wrapit)
1000 0.007 0.000 16.445 0.016 numeric.py:216(asarray)
1 0.000 0.000 0.000 0.000 test.py:16(__init__)
100000 0.068 0.000 0.080 0.000 test.py:19(update)
1000 0.012 0.000 16.520 0.017 test.py:23(finalize)
1 0.284 0.284 16.883 16.883 test.py:50(test_class)
1000 0.005 0.000 0.005 0.000 {getattr}
1000 0.001 0.000 0.001 0.000 {len}
100000 0.012 0.000 0.012 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1000 0.020 0.000 0.020 0.000 {method 'reshape' of 'numpy.ndarray' objects}
1000 16.438 0.016 16.438 0.016 {numpy.core.multiarray.array}
204010 function calls in 0.244 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.244 0.244 <string>:1(<module>)
1000 0.001 0.000 0.003 0.000 fromnumeric.py:107(reshape)
1 0.000 0.000 0.000 0.000 test.py:27(__init__)
100000 0.082 0.000 0.170 0.000 test.py:32(update)
100000 0.087 0.000 0.088 0.000 test.py:36(add)
1000 0.002 0.000 0.005 0.000 test.py:46(finalize)
1 0.068 0.068 0.243 0.243 test.py:50(test_class)
1000 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1000 0.002 0.000 0.002 0.000 {method 'reshape' of 'numpy.ndarray' objects}
6 0.001 0.000 0.001 0.000 {numpy.core.multiarray.zeros}
Класс A уничтожается обновлениями, класс B уничтожается финализацией. Класс C является надежным перед обоими из них.
Ответ 4
существует большая разница в производительности в функции, которую вы используете для завершения. Рассмотрим следующий код:
N=100000
nruns=5
a=[]
for i in range(N):
a.append(np.zeros(1000))
print "start"
b=[]
for i in range(nruns):
s=time()
c=np.vstack(a)
b.append((time()-s))
print "Timing version vstack ",np.mean(b)
b=[]
for i in range(nruns):
s=time()
c1=np.reshape(a,(N,1000))
b.append((time()-s))
print "Timing version reshape ",np.mean(b)
b=[]
for i in range(nruns):
s=time()
c2=np.concatenate(a,axis=0).reshape(-1,1000)
b.append((time()-s))
print "Timing version concatenate ",np.mean(b)
print c.shape,c2.shape
assert (c==c2).all()
assert (c==c1).all()
Использование concatenate, кажется, в два раза быстрее, чем первая версия и более чем в 10 раз быстрее, чем вторая версия.
Timing version vstack 1.5774928093
Timing version reshape 9.67419199944
Timing version concatenate 0.669512557983
Ответ 5
Если вы хотите улучшить производительность при работе с списками, посмотрите на библиотеку blist. Это оптимизированная реализация списка python и других структур.
Я еще не оценил его, но результаты на их странице кажутся многообещающими.
