Какая самая быстрая коллекция для нарезки?

Question

Мне нужно выполнить следующую операцию:

collection.slice(x, y)
....
collection.slice(x+1, y+1)
...
collection.slice(x+n, y+n)

или

collection.slice(x-n, y-n)

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

PS на Характеристики производительности Страница «Применить» характеристика отвечает за нарезку?

PPS ищет статьи, руководства, посвященные теме.

Answer 1

Ну, Vector имеет logN производительность, хотя постоянный коэффициент может быть слишком тяжелым в зависимости от ваших требований.

С другой стороны, может быть range делает то, что вы хотите? Если это так, то SortedMap вполне может обеспечить производительность logN с меньшим постоянным коэффициентом. Может быть.

Answer 2

Ответ зависит в некоторой степени от того, насколько далеко расположены x и y, но лучше всего использовать простые массивы.Если вам не нужно ничего делать со срезами, использование представлений может быть быстрее, но доступ с представлениями медленнее, поэтому, вероятно, лучше держаться подальше от них.

В любом случае, вам, безусловно, нужно что-то с быстрым«apply» (журнал или постоянное время), и между Array, Vector и ArrayBuffer, Array самый быстрый, ArrayBuffer примерно на 50% медленнее, а Vector примерно в два раза медленнееснова для нарезки и использования каждого нарезанного элемента.

Кроме того, подумайте, будет ли sliding делать то, что вы хотите.Это не так быстро, как прямая нарезка, но очень удобно.