Понимание функции перетасовки
Я нашел на эта тема следующую функцию для перемешивания любых типов данных:
#define NELEMS(x) (sizeof(x) / sizeof(x[0]))
/* arrange the N elements of ARRAY in random order.
* Only effective if N is much smaller than RAND_MAX;
* if this may not be the case, use a better random
* number generator. */
static void shuffle(void *array, size_t n, size_t size) {
char tmp[size];
char *arr = array;
size_t stride = size * sizeof(char);
if (n > 1) {
size_t i;
for (i = 0; i < n - 1; ++i) {
size_t rnd = (size_t) rand();
size_t j = i + rnd / (RAND_MAX / (n - i) + 1);
memcpy(tmp, arr + j * stride, size);
memcpy(arr + j * stride, arr + i * stride, size);
memcpy(arr + i * stride, tmp, size);
}
}
}
Я тестировал, и, похоже, все работает нормально, но мне трудно понять, как и почему это работает.
- Как и почему он не меняет местами элемент массива прямо на
array - Почему можно присвоить массив char*:
char *arr = array; - Смещение
i * strideилиj * strideв функциях memcpy больше, чем общий размер массива (sizeof(array)). Как здесь работает арифметика указателей?
Возможно, вам стоит приобрести книгу C.
@AnttiHaapala Есть ли что-то, что вы бы порекомендовали?
@fassn stackoverflow.com/questions/562303/…
Ключевым моментом, не упомянутым в ответах, является то, что стандарт C не позволяет вам выполнять арифметические операции с указателями, используя переменные типа void *. GCC допускает это как расширение — и предполагает, что размер указанного типа равен 1, такой же, как char. Так как у void * и char * очень тесные отношения. См. C11 §6.2.5 Типы ¶28 — Указатель на void должен иметь те же требования к представлению и выравниванию, что и указатель на символьный тип. и ссылки на сноску 48) […продолжение…]
void * в char * позволяет корректно работать с указателями в соответствующих компиляторах (а также в GCC и Clang).
Ответы 2
arrayотносится к типуvoid*. Это просто указатель без интерпретации, поэтому мы не знаем, на какой тип данных он указывает. Количество элементов указано вn, а размер каждого вsize. Это сделано таким образом, чтобы функцию можно было использовать с массивами любого типа.char *arr = array;интерпретирует указатель void как указатель на последовательность байтов.sizeof(array)дает размер указатель, а не размер фактического массива. Фактический размер в байтахi * size.
Алгоритм тасования выглядит как Перетасовка Фишера-Йейтса.
Также замечу, что * sizeof(char) бессмысленно, так как sizeof(char) равно 1 по определению.
Для лучшего понимания я перетасую порядок ответов:
2 - array является указателем типа void. В C указатели могут быть назначены указателям типа void* и из них. Любой указатель на объект может быть преобразован в тип void* без потери информации. Если результат преобразуется обратно в исходный тип указателя, исходный указатель восстанавливается.
1. Это не работает для отдельных элементов, у вас нет универсального типа, который можно назначить любому типу. Таким образом, код переключает содержимое указанной памяти.
3 — n — количество элементов в массиве, а size — размер одного элемента в массиве. stride = size * sizeof(char); означает, что stride равно size, так как sizeof(char) равно 1. Размер массива sizeof(array) равен n * size - количеству элементов в массиве, умноженному на размер элемента. Так как и i, и j меньше, чем n, i * stride и j * stride
никогда не будет больше памяти, используемой массивом. Интересно, почему использование этого stride, насколько мне известно, sizeof(char) всегда равно 1.
"...я перетасую порядок ответов" -- вот это умно. ;-)
Вы не можете поменять элемент напрямую. Не все процессоры имеют инструкцию подкачки память-память
XCHG.