Изменяет ли memmove элементы (так же, как это делает цикл for), или он захватывает весь блок памяти одновременно?
В моем классе алгоритмов мы должны включить алгоритмы для удаления дубликатов списка целых чисел и стрелять для наименьшей возможной сложности. В моем алгоритме, когда я вижу дублированное целое число, я сдвигаю каждый элемент после этого целого числа на один индекс вниз, чтобы удалить дублированный элемент, используя цикл for; вот так:
for(int i=dup_index; i<arr_size-1; i++)
{
arr[i] = arr[i+1];
}
Будет ли мой алгоритм более эффективным использовать memmove? Кроме того, если моя работа заключается в разработке алгоритма, и если предположить, что memmove снижает сложность моего алгоритма, можно ли использовать memmove как «обман»?
Решение
Я не знаю об измене, но memmove в основном делает то, что делает ваш цикл, только более эффективно.
Кроме того, это одна из самых основных утилитарных функций, поэтому я не понимаю, почему вы не должны ее использовать.
Что касается сложности, порядок алгоритма не изменится, он просто будет быстрее. memmove реализован в сборке и пытается в полной мере использовать выравнивание для копирования слова по слову вместо байта на байт.
РЕДАКТИРОВАТЬ:
ну ладно, могут быть случаи, когда ручная копия может быть на пару инструкций короче, чем вызов memmove, но если вы начинаете перемещать данные в памяти, вы выполняете дорогостоящую операцию, поэтому оптимизация нескольких циклов ЦП не будет иметь никакого значения для общей картины.
Если ваш проект предусматривает перемещение на месте для данных, критичных к производительности, лучше изменить базовую структуру данных на что-то, что полностью исключает копии (список, дерево, хэш-таблица и т. Д.).
Другие решения
Ваша программа может работать быстрее, используя memmove, насколько настенные часы, но ваш цикл for в основном достигает того же самого. Сложность алгоритма не изменится.
Функционально memmove делает именно то, что делает ваш цикл. Однако компилятор и / или среда выполнения C могут реализовывать memmove с использованием более эффективного машинного кода. Некоторые архитектуры имеют специализированные инструкции, которые будут выполнять такую операцию полностью в одной инструкции. Это может быть также указано компилятором.
Он не меняет сложность алгоритма, он просто делает это быстрее.
Что касается того, будет ли это считаться мошенничеством в вашем задании — это вопрос для вашего профессора, конечно? Никто здесь не может сказать вам это.
Если есть несколько дубликатов, вы можете использовать вспомогательный для хранения не дубликатов: —
int aux[arr_size],cnt=0;
for(int i=0;i<arr_size;i++) {
if(arr[i]!=dup) {
aux[cnt++] = arr[i];
}
}
Если вам нужно на месте: —
int i = dup_index;
int j = dup_index+1;
int dup = arr[i];
while(j<arr_size) {
if(arr[j]!=dup) {
arr[i++] = arr[j];
}
j++;
}
Функции библиотеки (например, memmove(3)) тщательно оптимизированы. Если вы посмотрите, как ваш любимый компилятор записывает это на ассемблере разной длины (задается как константа), вы, вероятно, получите огромный сюрприз.
Тем не менее, копирование $ n $ байтов из одного места в другое займет время $ \ Theta (n) $, если только вы не знаете что-то, что помогает избежать части перемешивания данных, которая не просто сокращает их на фиксированную долю ,