Оптимізація коду Python
Є фрагмент коду, де обчислюється попарна евклідова відстань в
V_pd[k][i], де k — компонета координати x,y,z,.. i — номер точки.
dist = [] for i in range(0, 10): for j in range(i+1, 10): su=0 for k in range(0, D): mih=V_pd[k][i]-V_pd[k][j] su +=mih*mih dist.append(su)
Як можна пришвидшити цей обрахунок?
58 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарівкак вариант, кстати, если все данные не получается за раз засунуть в один вызов
pdist(), можно соорудить minibatch изpdist()иcdist().А какая общая задача? Может можно обойтись и без попарных дистанций.
Насправді треба знайти, всі попарні відстані коротші певної заданої довжини.
простая оптимизация: отсортируй точки по одной из координат, сразу же можно будет скипать пары, у которых дистанция больше
en.wikipedia.org/...st_pair_of_points_problem
Для цього методу написано, These approaches are not efficient for dimension d>2, в мене d>20
Полная фраза: Computing either the Delaunay triangulation or the Voronoi diagram takes O(n log n) time. These approaches are not efficient for dimension d>2, while the divide-and-conquer algorithm can be generalized to take O(n log n) time for any constant value of d..
По каждой размерности (или по1-2) можно массово отфильтровывать явно неподходящие пары и не считать их дистанции. Если граничная дистанция 2, а разница по координате 4, то эта пара явно не подходит.
en.wikipedia.org/wiki/K-d_tree — тоже прикольная штука, но для 10 точек в20-мерном пространстве выигрыша не даст.
Ну мало ли, вдруг можно на кластеры побить и работать как с единым объектом, либо отбрасывать их пачками. Вон даже N-Body задачу научились за O(n log n) решать вместо квадрата.
— хороший намек. Для десяти точек можно и в лоб, если больше, то Quad, Oct и так далее tree.scipy.spatial.distance.pdist обчислює дуже швидко, проблема в пам’яті. Наприклад, як заставити його зберігати в пам’яті відстані в int а не в float? Або зберігати лише відстані менші граничної? Я не знайшов в параметрах.
int має межі від −2**31 до 2**31-1, або від 0 до 2**32-1 (але в python нема unsigned int)
double має набагато більші межі, точно не скажу, але він принципово заточений на величезні числа, правда, за рахунок втрати точності «знизу» — my_very_long_double + 1 == my_very_long_double
.
тому, якщо ти переведеш double -> int, то для кожної відстані > 2**31-1 python переведе число в long, який принципово безрозмірний, але займає негарантовану кількість пам’яті (явно більше 4 байт) — ось тут описано stackoverflow.com/...um-value-for-long-integer
.
або якщо це якась ліба, яка працює іменно з int 4, то ти отримаєш старе добре переповнення — всі числа більші за 2**31-1, стануть від’ємними або обріжуться до 32 біт
Відстані можна масштабувати, діапазон для задачі від 0 до 10000 більш ніж достатній, так що за межі 2**31-1 не вийде.
Интересно, а чем обусловлен отступ во второй строке ?
нічим, його не повинно бути, опечатка
сцы-пай посмотри, а то велик, кажется, придумуешь
PyPy вам в помощь :)
Не підходить, бо ціною високої продуктивності та використання JIT-компіляції є більше споживання пам’яті. А пам’яті обмаль.
нада перевести координаты точек в вид
a = np.array((2,2,2,2,2))
b = np.array((4,4,4,4,4))
тогда можна делать так tmp = a — b
ну и решение переводится в вид
dist = []
for i in range(0, points):
for j in range(i+1, points):
su = np.linalg.norm(V_pd1[i]-V_pd1[j])
dist.append(su)
su это уже корень из суммы квадратов
+1 за numpy и по скорости, и по памяти. можно еще использовать numpy.float16 или какой-нибудь int для экономии памяти.
а, кстати, точно нужно вычислять все попарные расстояния, или достаточно, скажем, найти 10 ближайших точек? тогда можно сделать что-то вроде
подойдет такое?
о, нашел. все, что вам нужно —
scipy.spatial.distance.pdist():считает все расстояния за 1.3 сек на моем лаптопе. batteries included, что называется :)
В точку, те що шукав, величезне спасибі.
Для великих матриць dist.pdist жере дуже багато пам’яті. Можливо знаєте як відстані зберігати в int а не в дефолтному double?
Сорри я сейчас без компа, но попробуй сделать dtype=float16 для входных данных, и/или оставлять только n наименьших расстояний — и то, и другое есть в моём первом примере
Я робив dtype=float16, але об’єм використаної памяті той самий.
В принципі зменшення необхідної пам’яті в двічі, вирішило би проблему. Мені достатньо int діапазону від 0 до 10000 вище голови.
ну, по крайней мере, для входных данных можно объем памяти уменьшить:
400112
1600112
впрочем, 1.6M против 400K — не думаю, что это может вызвать какие-либо проблемы.
А
pdist(), похоже, всегда возвращаетfloat64:399960096результат можно сжать во
float16, используя тот же прием:99990096объем памяти, кстати, не такие уж большой — ~400M максимум. может, у вас там какие-то лишние временные объекты память отъедают?
Мені
завжди повертає число 80. Я використовуюprint memory_usage_psutil()
Для dtype=np.float16 дає 182.91 МВ, для float64 448.69 МВ. Основний об’єм пам’яті займає distances, чому ви міряєте для points ?
ну, points я мерял просто за компанию. понятно, что
distances ~ O(points^2). кстати, странно, что у вас sys.getsizeof() дает 80 — попробуйте тогда points.nbytes, это точно должно работать.в общем, если памяти все равно не хватает, то minibatch вам в помощь. разбиваем points на несколько сегментов, и для каждого считаем pdist() между точками внутри сегмента, и cdist() между точками этого сегмента и остальных. будет, конечно, не так быстро, как один pdist(), но наверняка намного быстрее обработки каждой пары отдельно.
а, сейчас напишу :) там все просто должно быть, главное, с индексами не ошибиться — ну да вы и потестируете, если что :)
якось так..
Дякую, так я розбиваю матрицю на 3×3 частини, це допомагає економити пам’ять. В мене питання, чому просунутий Python не дозволяє редукувати розмір змінних, наприклад мені би int16 вистачило з головою?
Ви пропонуєте pdist написати на С/С++?
pdist для pd.DataFrame на С/С++ не осилю.
pdist() и так написан на С, и там всегда возвращается64-bit double. так что питон тут ни при чем — это проблема конкретной библиотеки, которая легко обходится. в моем примере выше можно обрабатывать исходные данные по кускам и результаты сразу преобразовывать в нужный формат
Ніби heapq входить в Python Standard Library, але помилка:
NameError: global name ’heapq’ is not defined
D = 1000;
points = 100000;
у меня дает мемори эррор, сколько у вас точек ?
В мене d=20 і points = 10000, ерору пам’яті нема.
можна записать строку еще так , это дает гдето 15 процентов на моем компе
su += math.pow(V_pd[k][i]-V_pd[k][j], 2)
но там вверху я описал другое решение, оно дает гдето то 20%
на 20% малувато, а чи можна якось використати pandas ?
по сравнению с оригинальм кодом будет гдето 30 процентов и вы сразу получаете корень а не сумму квардратов. а кто это пандас ? на С++ можна распараллелить на количество ядер процессора, но на питоне я такое не разу не делал.
pandas-docs.github.io/pandas-docs-travis
Маю на увазі pandas Data Frames.
дык где numpy, там и pandas.. а у вас в векторе есть еще какие-то фичи? если нет, то используйте numpy и не парьтесь
Какой версии Python?
Python 2.7.6
В таком случае, попробуйте заменить range на xrange.
ок, заміню
Після deque і xrange рахує на 8% довше.
у Вас вроде как 9 точек перебирает (0..8) — если память не изменяет.
А с точки зрения скорости вначале вместо list используйте deque — подозреваю, что сейчас самая большая задержка при добавлении в конец массива. А дальше по идее можно попробовать лишние квадраты не считать, но не думаю, что тут это критично.
ок, спробую
У Вас в самом деле 10 точек или массив все же «слегка» подлиннее будет?
Если сильно подлиннее я бы переставил местами индексы — так как сейчас координаты одной точки лежат не подряд в памяти — при больших массивах падает эффективность работы кэша.
Ну и тогда можно будет использовать sum, map и т.д. вместо циклов.
Насправді набагато більше ніж 10. Переставити місцями це
mih=V_pd[k][i]-V_pd[k][j] -----> mih=V_pd[i][k]-V_pd[j][k]
да, только и заполнить массив данными именно таким образом.
А то у Вас сейчас получается [ [x0,x1,x2...], [y0,y1,y2...], [z0,z1,z2...],...], а так как во внутреннем цикле Вы перебираете координаты точки, то логичней сделать так:
[[x0,y0,z0...], [x1,y,1,z1,...], [x2,y2,z2,...]...] — чтобы данные, который обрабатываются подряд — и в памяти находились подряд. Не знаю, как в питоне — но в том же С++ при этом компилятор задействует потоковые команды (SSEx и др), что значительно ускоряет вычисления. Ну и кэш помогает.
Спробую це, бо після
і рахує на 8% довше.