Оптимальный способ выполнить операцию сдвига на массиве
JavaScript, язык, был на первом месте из Netscape.
Microsoft перепроектировала JavaScript и назвала его JScript для предотвращения фирменных проблем с Sun. (Netscape и Sun сотрудничали в то время, таким образом, это было меньшим количеством проблемы)
, языки идентичны, оба - диалекты сценария ECMA, после совершения стандарт.
, Хотя языки идентичны, начиная с выполнений JScript в Internet Explorer, он имеет доступ к различные объекты, представленные браузером (такие как ActiveXObject)
6 ответов
Если вы хотите круговой сдвиг элементов:
std::rotate(&arr[0], &arr[1], &arr[10]);
... подойдет. Вам потребуется # включить заголовок алгоритма.
Если вы единственный человек, имеющий указатель на массив, просто увеличивайте указатель на единицу и уменьшайте длину.
Просто не забудьте сохранить исходный указатель, когда вы освободите его.
Пока массив можно изменять, вы можете использовать memmove для их сдвига (но не используйте по ошибке memcpy, поскольку memcpy не предназначен для перекрывающихся регионов):
memmove(&arr[0], &arr[1], sizeof(arr) - sizeof(*arr));
(sizeof (arr ) - sizeof (* arr) - размер в байтах всех элементов массива, кроме 1).
Интересно, стоит ли вам использовать std :: valarray.
Если вам действительно нужна скорость BLAZING, посмотрите на ассемблерный сдвиг с операциями переноса. http://en.wikibooks.org/wiki/X86_Assembly/Shift_and_Rotate#Shift_With_Carry_Instructions В сочетании с циклом вы можете сдвигать массив в битах за миллисекунды.
Если вы ищете решение на чистом языке C, вот оно, включая программу драйвера. Оказывается, это довольно просто: чтобы повернуть на n , вы:
- переворачиваете первые
nэлементов на месте, - меняете местами остальные элементы, и
- перевернуть весь массив на месте.
Это требует дополнительного хранилища на один элемент (для реверсирования).
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
/* print an array */
static void print_array(unsigned char *arr, size_t n, const char *prefix)
{
size_t i;
if (prefix) {
printf("%s: ", prefix);
}
for (i=0; i < n; ++i) {
printf("%02x ", (unsigned int)arr[i]);
}
printf("\n");
}
/* reverse 'arr', which has 'narr' elements */
static void reverse(unsigned char *arr, size_t narr)
{
size_t i;
for (i=0; i < narr / 2; ++i) {
unsigned char tmp = arr[i];
arr[i] = arr[narr-i-1];
arr[narr-i-1] = tmp;
}
}
/* rotate 'arr' of size 'narr' by 'shift' */
static void rotate(unsigned char *arr, size_t narr, unsigned long shift)
{
reverse(arr, shift);
reverse(arr + shift, narr - shift);
reverse(arr, narr);
}
/* driver program */
int main(int argc, char *argv[])
{
unsigned char arr[]= {0,1,2,3,4,5,6,7,8,9,10};
size_t narr = sizeof arr / sizeof arr[0];
unsigned long shift = 2;
if (argc > 1) {
char *eptr;
shift = strtoul(argv[1], &eptr, 0);
if (*eptr || errno == ERANGE) {
perror("strtoul");
return EXIT_FAILURE;
}
}
print_array(arr, narr, "before shift");
rotate(arr, narr, shift);
print_array(arr, narr, "after shift");
return EXIT_SUCCESS;
}