5

Как вычислить все возведения в степень с x_min ^ y_min по x_max ^ y_max без повторов результатов?

Например:

  • x2 ^ x8 = z
  • ...
  • x85 ^ y23 = p
  • ...
  • но x85 ^ y28 = z !

Как видно, результат z повторяется у разных вычислений.

Kаким образом можно пропускать все следующие вычисления при условии, что сравнивать с ранее вычисленными результатами не допустимо?

# code python 3
min_x, max_x = 5, 127
min_y, max_y = 2, 250
result = ''
for x in range(min_x, max_x):
    for y in range(min_y, max_y):
        result += str(x ** y)
9
  • почему недопустимо? откуда такие требования? И да, что именно запрещено делать?
    – pavel
    7 июн 2016 в 18:47
  • Потому что это занимает очень долгое время. Так как значения x и y могут быть намного больше, чем 1 000, и все вычисленные результаты сохраняются в переменную result.
    – Viaches
    7 июн 2016 в 19:13
  • вопрос только в производительности? 7 июн 2016 в 19:17
  • И да и нет. Я так же не хочу тратить лишнюю память, потому что планируется использовать как минимум 2 гигабайта только для хранения переменой result. Разве нет какой нибудь мат формулы для решения данной проблемы? Просто представьте сколько по времени искать подстроку хотя бы в 300МБ.. :)
    – Viaches
    7 июн 2016 в 19:23
  • ну 300 метров это немного) вычислите всё, отсортируйте и удалите дубликаты)
    – pavel
    7 июн 2016 в 19:26

2 ответа 2

6

UPDATE: - только что проверил с вашими числами - Python "занимал" около 1GB памяти, timing я обновил для ваших чисел

In [105]: x = np.arange(5, 8800, dtype=np.uint64)

In [106]: y = np.arange(2, 8250, dtype=np.uint64)

In [107]: r = np.unique(np.array([np.power(x, np.repeat([pw], len(x))) for pw in np.nditer(y)]))

In [108]: len(''.join(r.astype(str)))
Out[108]: 457656

In [109]: %timeit np.unique(np.array([np.power(x, np.repeat([pw], len(x))) for pw in np.nditer(y)]))
1 loop, best of 3: 11.3 s per loop

In [115]: np.version.version
Out[115]: '1.10.4'

numpy solution:

x = np.arange(5, 127, dtype=np.uint64)
y = np.arange(2, 250, dtype=np.uint64)

r = np.unique(np.array([np.power(x, np.repeat([pw], len(x))) for pw in np.nditer(y)]))

# чтобы сэкономить память записываем строку в `r`
r = ''.join(r.astype(str))
print(r)

Timing для 5000 x 5000 массива:

In [102]: %timeit np.unique(np.array([np.power(x, np.repeat([pw], len(x))) for pw in np.nditer(y)]))
1 loop, best of 3: 3.89 s per loop

In [103]: x.shape
Out[103]: (4995,)

In [104]: y.shape
Out[104]: (4998,)
14
  • С маленькими числами работает действительно быстро! Но вот с такими данными вообще вылетает momory error: x = np.arange(5, 8800, dtype=np.uint64); y = np.arange(2, 8250, dtype=np.uint64) Как-нибудь можно избежать это?) Памяти хоть за глаза, может быть это ошибка numpy?
    – Viaches
    7 июн 2016 в 20:14
  • я немного поменял решение - np.repeat() вместо np.array() - это должно экономить память. Какая у вас версия numpy? 7 июн 2016 в 20:21
  • Проверил новый код, процесс питона доходит до 750МБ и падает на той же ошибке. PyCharm last upd, Python 3.4.4 x32, numpy 1.11.0
    – Viaches
    7 июн 2016 в 20:27
  • Памяти хоть за глаза и x32 - не совсем совместимые понятия ;) Попробуйте закрыть лишние приложения, включая IDEA и запустить скрипт из ком. строки 7 июн 2016 в 20:29
  • Я имел ввиду, что свои честные 3 ГБ он должен отработать :) Запустил скрипт из CMD на python 2.7, но ничего не закрывал и сработало! В 3.x откатился на 1.10.4 но по прежнему ошибка: File "C:\Users\..\AppData\Roaming\Python\Python34\site-packages\numpy\lib\arraysetops.py", line 176, in unique ar = np.asanyarray(ar).flatten() MemoryError
    – Viaches
    7 июн 2016 в 20:36
2

Так как основная проблема автора - недостаток ресурсов (или все-таки какая-то абстрактная задачка?), то можно предложить такой выход из положения: не генерировать сразу все-все значения, а написать генератор, который будет выдавать значения тогда, когда это будет нужно. Эти значения ведь все равно где-то будут использованы - будь то запись в файл или какие-нибудь операции над получившимся вектором - и использованы они будут по-одному.

def give_me_square():
    first = range(5, 8800)
    second = range(2, 9000)
    for i in first:
        for j in second:
            yield i**j

counter = 0
total = 8800*9000

for square in give_me_square():
    if counter % 10000 == 0:
        print(counter, "of", total)
    counter += 1

Работает совсем нешустро, зато память не ест. Такой генератор можно сделать асинхронным, можно отдать его в multiprocessing.Pool.map, много чего можно придумать.

15
  • кстати - это надежный вариант. только надо добавить фильтрацию на дупликаты 7 июн 2016 в 20:42
  • да, такой вариант я как раз и отбросил из за долгого поиска и удаления дубликатов :) Мне как раз нужны сразу все значения, они записываться в файл не будут, хранятся только в виртуальной памяти
    – Viaches
    7 июн 2016 в 20:52
  • 1
    @sergus, как так сразу все? Как вы собираетесь в дальнейшем использовать список всех неповторяющихся значений? Если хранить все эти числа - неважно как именно, то можно попрощаться с мечтой о том, что все влезет в память. Сложность по памяти - O(n*m) - это, во-первых. Во-вторых, 1000 в степени 1000 - это огромное число - намного больше чем int64 (2**64). При вычислении такого числа используется уже арифметика на строках - а это совсем другой разговор по части быстродействия и памяти, потому что "дешево" работать с такими числами не получится, ну никак.
    – m9_psy
    7 июн 2016 в 21:03
  • да, "слона то я и не заметил"... numpy - не сможет правильно посчитать 1000^1000. Вот пример: x = np.array([1000], dtype=np.uint64); np.power(x, x) Output: array([9223372036854775808], dtype=uint64) 7 июн 2016 в 21:10
  • Спасибо за ответ! Мне требуется произвести поиск чисел в этом массиве. Как писал выше в комментариях, я думаю разделять на порции и проверять подстроку. Эх досада какая. То есть сейчас скрипт не вычисляет 1000^1000? Что посоветуете в таком случае? Я мало знаком с numpy, не пинайте сильно :)
    – Viaches
    7 июн 2016 в 21:12

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.