Scala List with cached length

Question

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

Является ли length внутренним кэшем (возможно, lazy val?)? Должен ли я писать обертку вокруг List или подкласс? Могу ли я сделать это с признаком, и это будет хорошим решением? Должен ли я использовать другой класс коллекции, например, Vector?

Answer 1

Для List, length и size определены в TraversableOnce и LinearSeqOptimized, которые являются общими для изменяемых коллекций, поэтому они не могут быть в кэше. Если вы ищете стандартный источник библиотеки для val length или val size, то нет классов класса коллекции, которые появляются.

Вы не можете подклассы List, потому что это sealed, но вы можете обернуть его, если хотите. Больше работы было бы необходимо, чтобы разрешить такие вещи, как map и т. Д., А также сохранить размер.

case class WrappedList[A](list: List[A]) { 
    lazy val length = list.length 
} 

Vector представляется достойным вариантом. length не строго в кэше, но оно определяется как:

def length = endIndex - startIndex 

Где endIndex и startIndex частные конструктор Vals, что делает его гораздо быстрее, чем List#length. Не рассматривая данный алгоритм, трудно сделать дополнительные рекомендации о том, какой тип коллекции использовать.