NumPy не ускоряет работу с массивами больших чисел. Что надо изменить для эффективности?

Question

Решил найти палиндромы, которые образованы произведением двух зеркальных чисел. Написал программу на Python обычном

from math import isqrt
def g(n): #функция для нахождения тех палиндромов, которые представимы в виде произведения двух зеркальных чисел
    d, b = [], [] #два пустых массива
    for i in range(1, isqrt(n)+1): #стандартный цикл для нахождения делителей
        if n%i==0:
            d.append(i)
            if i!=n//i: d.append(n//i)
    for x in d: #для каждого делителя смотрим получится ли n путём произведения на зеркальное
        s = int(str(x)[::-1])
        if s*x == n:
            b.append(x)
            if x != s: b.append(s)
            break
    return b
for i in range (1_000_000_000, 2_000_000_000): #запускаем в этом диапазоне
    if i == int(str(i)[::-1], 10): #проверка на палиндром
        result = g(i)
        if result: print(result) #выводим все нужные делители и их зеркальные копии

и с библиотекой NumPy

import numpy as np
from math import isqrt
def f(n): #функция для нахождения тех палиндромов, которые представимы в виде произведения двух зеркальных чисел
    d = np.array([], dtype=int) #два пустых массива
    b = np.array([], dtype=int)  
    for i in range(1, isqrt(n)+1): #стандартный цикл для нахождения делителей
        if n%i==0:
            d = np.append(d, i)
            if i!=n//i: d = np.append(d, n // i)   
    for x in d: #для каждого делителя смотрим получится ли n путём произведения на зеркальное
        s = int(str(x)[::-1])
        if s*x == n:
            b = np.append(b, x)
            if x != s: b = np.append(b, s)
            break
    return b
for i in range (1_000_000_000, 2_000_000_000): #запускаем в этом диапазоне
    if i == int(str(i)[::-1], 10): #проверка на палиндром
        result = f(i)
        if result.size > 0: print('[' + ', '.join(map(str, result)) + ']') #выводим все нужные делители и их зеркальные копии

На NumPy всегда работает медленнее, при работе в диапазоне до 10_000 (до двух раз) или до 2_000_000_000 (от 5 до 10 секунд) Как это исправить? Как заставить NumPy работать как надо? Что я сделал не так в коде?

Answer 1

Вы никак не используете преимуществ numpy - массовой обработки массивов.

А вот накладные расходы для преобразования питоновских типов данных в нумпаевские и назад как раз могут дать замедление.

Заметьте, что больший эффект даст смена алгоритма - например, вместо цикла длиной в два миллиарда достаточно перебрать числа до 44722, сделать зеркальные им, и проверить произведение.

(также можно не проверять все числа огромного диапазона на палидромность, а генерировать только палиндромы, но мне кажется, что описанное выше будет быстрее, т.к. не требует разложения)

БЛОГ НА HUSL

NumPy не ускоряет работу с массивами больших чисел. Что надо изменить для эффективности?

Ответы (1 шт):