hasDefiniteSize и knownSize

Question

Я иду через List методы в Scala.

val mylist = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 3, 10)

Я весьма смущен hasDefiniteSize и knownSize.

Для List, hasDefiniteSize возвращает true и knownSize возвращает -1.

Какая точная теория стоит за этими методами?

Answer 1

Этот метод определяется суперклассом List, который является общим с возможно бесконечными коллекциями (такими как Stream s, LazyList s и Iterator s).

Для более подробной информации, я Полагаю, в документации это лучше всего изложено.

Вот вариант для hasDefiniteSize в версии 2.13.1` :

Проверяет, известен ли этот сборник иметь конечный размер. Известно, что все строгие коллекции имеют конечный размер. Для нестрогой коллекции, такой как Stream, предикат возвращает true, если все элементы были вычислены. Он возвращает false, если поток еще не оценен до конца. Непустые итераторы обычно возвращают false, даже если они были созданы из коллекции с известным конечным размером.

Примечание: многие методы сбора не будут работать с коллекциями бесконечного размера. Типичный режим отказа - бесконечный l oop. Эти методы всегда делают попытку обхода без предварительной проверки, что hasDefiniteSize возвращает true. Однако проверка hasDefiniteSize может обеспечить уверенность в том, что размер задан правильно, и отсутствие прерывания не является проблемой.

Обратите внимание, что hasDefiniteSize устарело со следующим сообщением:

(Начиная с версии 2.13.0). Проверьте .knownSize вместо .hasDefiniteSize для более подробной информации (см. Scalado c для подробной информации)

Документация для knownSize далее заявляет:

Количество элементов в этой коллекции, если это может быть дешево вычислено, -1 в противном случае. Дешево обычно означает: не требуется обход коллекции.

List является реализацией связанного списка, поэтому List(1, 2, 3).hasDefiniteSize возвращает true (коллекция не безгранична), но List(1, 2, 3).knownSize возвращает -1 (вычисление размера коллекции требует обхода всего списка).

Answer 2

Некоторые коллекции знают свой размер

Vector(1,2,3).knownSize   // 3

, а некоторые нет

List(1,2,3).knownSize     // -1

Если коллекция знает свой размер, то некоторые операции можно оптимизировать, например, рассмотрим, как Iterable#sizeCompare использует knownSize для возможного возврата рано

  def sizeCompare(that: Iterable[_]): Int = {
    val thatKnownSize = that.knownSize

    if (thatKnownSize >= 0) this sizeCompare thatKnownSize
    else {
      val thisKnownSize = this.knownSize

      if (thisKnownSize >= 0) {
        val res = that sizeCompare thisKnownSize
        // can't just invert the result, because `-Int.MinValue == Int.MinValue`
        if (res == Int.MinValue) 1 else -res
      } else {
        val thisIt = this.iterator
        val thatIt = that.iterator
        while (thisIt.hasNext && thatIt.hasNext) {
          thisIt.next()
          thatIt.next()
        }
        java.lang.Boolean.compare(thisIt.hasNext, thatIt.hasNext)
      }
    }
  }

См. Связанный вопрос Разница между размером и размеромIs