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.
    – sergus
    7 июн 2016 в 19:13
  • вопрос только в производительности? 7 июн 2016 в 19:17
  • И да и нет. Я так же не хочу тратить лишнюю память, потому что планируется использовать как минимум 2 гигабайта только для хранения переменой result. Разве нет какой нибудь мат формулы для решения данной проблемы? Просто представьте сколько по времени искать подстроку хотя бы в 300МБ.. :)
    – sergus
    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?
    – sergus
    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
    – sergus
    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
    – sergus
    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
  • да, такой вариант я как раз и отбросил из за долгого поиска и удаления дубликатов :) Мне как раз нужны сразу все значения, они записываться в файл не будут, хранятся только в виртуальной памяти
    – sergus
    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, не пинайте сильно :)
    – sergus
    7 июн 2016 в 21:12

Ваш ответ

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

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