Быстрый способ удалить байты из буфера

Question

Есть ли более быстрый способ сделать это:

Vector3* points = malloc(maxBufferCount*sizeof(Vector3)); 
    //put content into the buffer and increment bufferCount   
    ... 

    // remove one point at index `removeIndex` 
    bufferCount--; 
    for (int j=removeIndex; j<bufferCount; j++) { 
     points[j] = points[j+1]; 
    } 

Я спрашиваю, потому что у меня есть огромный буфер, из которого я удалить элементы довольно часто.

Answer 1

Нет, извините - удаленные элементы из середины массива принимают O(n) раз. Если вы действительно хотите часто изменять элементы (например, удалять определенные элементы и/или добавлять другие), вместо этого используйте связанный список, который имеет постоянное удаление и добавление. Напротив, массивы имеют постоянное время поиска, в то время как связанные списки могут быть доступны (прочитаны) в линейном времени. Поэтому решите, что вы будете делать чаще (чтение или письмо) и выберите соответствующую структуру данных, основанную на этом решении.

Обратите внимание, однако, что я (любезно) предположил, что вы не пытаетесь совершить преступление преждевременной оптимизации. Если вы не отметили, что это узкое место, то, вероятно, просто не беспокойтесь об этом.

Answer 2

Если вы не знаете, что это узкое место, вы, вероятно, можете оптимизировать для вас компилятор, но вы можете попробовать memmove.

Выбранный ответ здесь довольно всеобъемлющая: When to use strncpy or memmove?

описание здесь: http://www.kernel.org/doc/man-pages/online/pages/man3/memmove.3.html

Answer 3

Несколько вещей, чтобы сказать. Функция memmove, вероятно, будет скопирована быстрее, чем вы, часто ее авторы оптимизируют для использования специальных инструкций, которые доступны на языке C без встроенного ассемблера. Я считаю, что эти инструкции называются инструкциями SIMD (Single Instruction Multiple Data)? Кто-то меня исправит, если я ошибаюсь.

Если вы можете сохранить элементы, которые нужно удалить, то вы можете оптимизировать, отсортировав список предметов, которые вы хотите удалить, а затем, выполнив один проход. Это не сложно, а просто требует какой-то смешной арифметики.

Также вы можете просто сохранить каждый элемент в связанном списке, удаление элемента тривиально, но вы теряете случайный доступ к вашему массиву.

Наконец, вы можете иметь дополнительный массив указателей, одинаковый размер вашего массива, каждый указатель указывает на элемент. Затем вы можете получить доступ к массиву с помощью двойной косвенности, вы можете отсортировать массив с помощью указателей подкачки, и вы можете удалить элементы, указав свой указатель NULL.

Надеюсь, это даст вам некоторые идеи. Обычно есть способ оптимизировать вещи, но тогда он становится более специфичным для приложения.