Как максимально быстро получить определенную последовательность чисел (все числа дважды, кроме первого и последнего) с помощью numpy?
Зная окончательное число (например, 5), я хотел бы создать массив, содержащий следующую последовательность:
[0,1,1,2,2,3,3,4,4,5]
Это означает, что список должен содержать все числа, повторяющиеся дважды, кроме первого и последнего.
Вот код, который я использую для этого:
import numpy as np
# final number
last = 35
# first sequence
sa = np.arange(0,last,1)
# second sequence (shifted by 1 unit)
sb = np.arange (1,last+1,1)
# concatenation and flattening
sequence = np.stack((sa, sb), axis=1).ravel()
# view the result
print(sequence)
Как вы думаете, существует ли более прямой и/или эффективный способ достичь того же результата?
@ScottHunter Я имею в виду прямо и как можно быстрее. Пример соответствует минимальной ситуации. Итоговое число этого скрипта (last) будет намного больше (примерно 10 000 -> 1 000 000).
Ответы 4
А как насчет использования упорядочить на 2*N, добавить 1 и разделить этаж на 2?
N = 5
out = (np.arange(2*N)+1)//2
# or variant suggested by @TlsChris
# out = (np.arange(2*N)+1)>>1
Альтернативно, с повторением и исключением первого/последнего:
out = np.repeat(np.arange(N+1), 2)[1:-1]
Или с трансляцией:
out = (np.arange(N)[:, None]+[0, 1]).ravel()
Вывод: array([0, 1, 1, 2, 2, 3, 3, 4, 4, 5])
тайминги
Сравнение разных ответов
Относительное время, около 10 000 элементов, исходный ответ кажется наиболее эффективным, в противном случае np.repeat(np.arange(N+1), 2)[1:-1] — самый быстрый:
Замена деления на небольшой сдвиг //2 на >>1 дает значительный прирост производительности mozway_division.
@TlsChris это хорошее предложение, хотя, похоже, это не всегда так. Я обновил тайминги.
На данный момент это было лучшее :D Смотрите мой ответ.
Просто мини-демо; но это помогает. Это быстрее? Для таких коротких массивов вы, вероятно, не заметите :)
a = np.arange(6)
np.array((a,a)).T.ravel()[1:-1]
Вдохновение взято из здесь
Вы можете использовать numpy.kron, чтобы каждый элемент повторялся дважды следующим образом.
import numpy as np
arr = np.kron(np.arange(6),[1,1])[1:-1]
print(arr) # [0 1 1 2 2 3 3 4 4 5]
Я создаю массив, в котором каждый элемент повторяется дважды, затем разрезаю его, чтобы избавиться от первого и последнего элемента.
Это интересная идея, но довольно медленная. В конце концов, это эквивалентно более эффективному np.repeat(np.arange(N+1), 2)[1:-1] (на самом деле это самый быстрый подход в целом, я бы сделал ставку на +1//2) ;)
Если можно, я еще не играл. Довольно нестандартный метод (не без недостатков. Должен быть int32, поэтому N ограничено 4 миллиардами :D)
np.arange(0, (N+1)<<32, 0x100000001).view(np.int32)[1:-1]
Если перевести в десятичную систему счисления, это похоже на то, как если бы я считал с шагом 101 по 4 цифры, а затем делил цифры пополам. Итак, 0000, 0101, 0202, 0303,... превратились в «00, 00, 01, 01, 02, 02, 03, 03», игнорируя первый и последний.
Он должен работать как с большими, так и с маленькими машинами. И, по моему мнению, на данный момент это быстрее, чем самый быстрый алгоритм.
Таким образом, учитывая соотношения между большинством этих решений (за исключением решения jkguttormsen, соотношение находится на уровне коэффициента 2 между худшим и лучшим решением), этот коэффициент 10 — это много. За это приходится платить (необходимость указывать конкретный тип: можно адаптировать для int32, int16 или int8, но не для int64 и, конечно, не с плавающей точкой), но, ну, пока что он выигрывает приз :D
Это хороший, может быть, немного загадочный, но определенно умный ;)
Вы можете ускорить его еще больше: не нужно обрезать первое и последнее значение, просто отрегулируйте границы: np.arange(0x100000000, N<<32, 0x100000001).view(np.int32) (Итак, при переводе в 10-е число будет начинаться с 0001, а не с 0000, затем продолжаться с 0102, 0203 и т. д. . – хотя это может зависеть от порядка байтов базовой системы). Кстати, невероятно элегантное и умное решение! Мне бы такое никогда не пришло в голову :)
Обновление: это определенно будет зависеть от порядка байтов системы. Решение с прямым порядком байтов (соответствует моему комментарию выше l = np.arange(0x100000000, N<<32, 0x100000001, dtype='<i8').view('<i4'); решение с прямым порядком байтов: b = np.arange(1, (N-1)<<32, 0x100000001, dtype='>i8').view('>i4')
@саймон. Да, в самом деле. Отсюда причина, по которой мне было лень «удалить первую и последнюю» часть. Обеспечение того, чтобы все 64-битные числа состояли из пар «X,X», поэтому не особо заботится о том, как именно кодируется X ((0,0,0,7,0,0,0,7) или (7,0,0 ,0,7,0,0,0) для пары цифр 7 с прямым порядком байтов). В любом случае, удаление первого и последнего, вероятно, является незначительным шагом по сравнению с остальными. Если только N не маленькое, но если бы N было маленьким, ОП не задал бы этот вопрос: D
@chrslg Я понял, что вы, должно быть, уже заметили это сами, только когда я внимательно перечитал ваш ответ и заметил, что вы уже упомянули порядок байтов. Итак: извините за это!
@саймон. Именно поэтому я на этом остановился, когда сначала хотел заметить, что можно пойти еще дальше и считать по шагам 0x0001000100010001, начиная с 0x0000000100010002, а затем конвертируя в 16 бит. Но для этого потребуется начать с 0x0002000100010000, а не с 0x0000000100010002, в зависимости от порядка байтов. Не говоря уже о вопросе «когда остановиться», это подразумевает некоторые случаи, зависящие от N%4. И на этот раз в 16 битах нельзя лениться и просто генерировать лишний 0 и лишний N.
@саймон. Нет, это было хорошее замечание. Если мы знаем порядок байтов, это общий способ сделать это. Диапазон от 0x2first32bitsNumbersPackedIn64bits до 0x2last32bitsNumbersPackedIn64bits с шагом 0x0000000100000001. Или диапазон от 0x4first16bitsPackedIn64 до 0x4last16bitsPackedIn64 с шагом 0x0001000100010001. И т. д. В конце концов, это то, что делают расширение MMX и другие инструкции «векторизации» ЦП: перехват 64-битных операций для выполнения 2 параллельных 32-битных операций, или 4 параллельных 16-битных операций, или 8 параллельных 8-битных операций. Конечно, процессорам это проще, поскольку они сами осознают свою последовательность байтов.
@chrslg Большое спасибо за расширенный ответ. Сегодня я многому научился (обычно я редко работаю над побитовым уровнем кода) :)
Что вы подразумеваете под «более эффективным»?