Самый быстрый способ скопировать в массив случайные элементы из другого массива Stack Overflow
В заголовке почти все сказано, но я приведу пример: предположим, что у вас есть массив символов a и другой массив символов b. Есть ли лучший способ поставить только символ, расположенный в простых позициях в b? Предположим, что у нас есть массив с простыми позициями.
Пока мой наивный код выглядит так.
for(i = 0; i < n; i++)
a[i] = b[j + prime[i]];
Здесь штрих [i] хранит первичные позиции b, а b намного больше, чем a, j — произвольная позиция в b (не будет внешней проблемы, потому что j + prime [i] не превышает границу b) ,
Решение
Что лучше? Один из способов: если основные [] местоположения известны во время компиляции, то мы могли бы добавить предварительную выборку, чтобы заблаговременно получить строки кэша.
Это делает время доступа к памяти лучше.
Другие решения
Вы можете сделать это, когда вы читаете (или копируете) значения в массив, используя простую функцию, которая сообщает вам, является ли число простым или нет.
Способ, который я набросал быстро, состоит в том, чтобы генерировать простые числа до тех пор, пока они не достигнут емкости вашего массива, и просто перебирать их и копировать нужные элементы из массив. Я могу придумать несколько способов оптимизировать это, например, иметь функцию «предварительной обработки», которая генерирует простые числа в вашей программе, чтобы вы могли повторно использовать список.
Список простых чисел будет кэширован, и к нему потребуется гораздо меньше времени (маловероятно, что у вас чрезвычайно большой список простых чисел)
Давайте посмотрим на это с алгоритмической точки зрения.
Вы хотите выполнить хэш-функцию для каждой записи в массиве A. Предполагая, что вы ничего не знаете о состоянии элементов в массиве A, тогда нижняя граница времени выполнения для алгоритма устанавливается в O (n), линейная время. Вы должны пройти через каждого участника, потому что у вас нет больше информации, которая могла бы помочь вам «пропустить» некоторые элементы или оптимизировать процесс.
Тем не менее, задача становится удержание алгоритма на уровне O (n). Код, который вы демонстрируете, делает это, если вы затем продолжите копировать не простые числа тем же способом. Таким образом, для этапа копирования нет способа ускорить процесс с точки зрения алгоритма. Это не значит, что выполнение шага хэширования не повлияет на скорость.