Как Scala добиться улучшения производительности для Map и Set, используя разные классы в зависимости от размера?

Question

Я новичок в Scala, и я только что узнал, что у Scala есть scala.collection.immutable.EmptySet, Set1, Set2, Set3, Set4 и HashSet.То же самое в случае Map.Упоминается, что это помогает улучшить производительность.Улучшает ли это производительность, работая с коллекцией элементов размером менее 5 на основе индекса и более 4 с помощью хеширования?Если да, то есть ли какое-либо математическое объяснение того, как размер коллекции меньше 5 не подходит для хеширования?

Answer 1

при работе с коллекцией элементов размером менее 5 на основе индекса

Нет, индексация отсутствует. Давайте посмотрим на самый важный метод для Set:

1. EmptySet.contains(x) просто возвращает false, вообще ничего не нужно делать.

2. Set1(elem1).contains(elem) просто нужно сделать одно сравнение elem == elem1, что нужно будет сделать и с набором хешей после сравнения хешей (поскольку хеши разных значений могут быть одинаковыми) .

3. Set2, Set3 и Set4 также просто необходимо (от 1 до 4) сравнений на равенство и ||.

HashSet.contains является также однострочным за исключением того, что вся работа выполняется get0 и computeHash, что довольно сложно. Так что даже в лучшем случае он должен выполнять больше работы.

Методы, отличные от contains, также могут быть специализированы для небольших размеров. Обратите внимание, что в размере 4 нет ничего особенного, вполне вероятно, что Set5, Set6 и т. Д. Также будут быстрее, чем HashSet; но в конечном итоге они станут медленнее, и точка, когда они это сделают, не является фиксированной. Кроме того, их добавление означает, что нужно загружать больше кода, что повсеместно ухудшает производительность. Так что просто нужно где-то остановиться, и было выбрано 4.