Вопросы Теги

Производительность рекурсии списка Scala

Возможно, проект был переименован еще прекращенный. Я полагаю, что это - решение Вашей дилеммы с 12,04. Откройте терминал ( Ctrl + Высокий звук + T ) и введите это: 

sudo add-apt-repository ppa:ddudek/stereo3d-stable
sudo apt-get update
sudo apt-get install compiz-plugin-stereo3d

Hope это - ответ, который все ищут

Ссылка на сайт создателя

14
задан Peter Mortensen 2 May 2013 в 16:54
поделиться

1 ответ

Во-первых, Haskell не является строгим, поэтому эти вызовы функций в хвосте могут вообще никогда не выполняться. Scala, с другой стороны, вычислит весь список перед возвратом. Более близкой реализацией того, что происходит в Haskell, будет следующее: 

def myFunction[T](l: List[T]): Stream[T] = l match {   
  case Nil => Stream.empty  
  case x :: xs => x #:: myFunction(xs)
}

Это получает List , который является строгим, и возвращает Stream , который не является строгим.

Теперь , если вы хотите избежать сопоставления с образцом и экстракторов (хотя ни один из них не вызывается в данном конкретном случае - см. ниже), вы можете просто сделать это: 

def myFunction[T](xs: List[T]): Stream[T] =
  if (xs.isEmpty) Stream.empty else xs.head #:: myFunction(xs.tail)

Я только что понял, что вы собираетесь использовать хвостовую рекурсию. То, что вы написали, не является хвостовой рекурсией, потому что вы добавляете x к результату рекурсии. При обработке списков вы получите хвостовую рекурсию, если вычислите результаты в обратном порядке, а затем инвертируете: 

def myFunction[T](xs: List[T]): List[T] = {
  def recursion(input: List[T], output: List[T]): List[T] = input match {
    case x :: xs => recursion(xs, x :: output)
    case Nil => output
  }
  recursion(xs, Nil).reverse
}

Наконец, позвольте ' s декомпилировать пример, чтобы увидеть, как это работает: 

class ListExample {
  def test(o: Any): Any = o match {
    case Nil => Nil
    case x :: xs => xs
    case _ => null
  }
}

Генерирует: 

public class ListExample extends java.lang.Object implements scala.ScalaObject{
public ListExample();
  Code:
   0:   aload_0
   1:   invokespecial   #10; //Method java/lang/Object."<init>":()V
   4:   return

public java.lang.Object test(java.lang.Object);
  Code:
   0:   aload_1
   1:   astore_2
   2:   getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   5:   aload_2
   6:   invokestatic    #24; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z
   9:   ifeq    18
   12:  getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   15:  goto    38
   18:  aload_2
   19:  instanceof      #26; //class scala/$colon$colon
   22:  ifeq    35
   25:  aload_2
   26:  checkcast       #26; //class scala/$colon$colon
   29:  invokevirtual   #30; //Method scala/$colon$colon.tl$1:()Lscala/List;
   32:  goto    38
   35:  aconst_null
   36:  pop
   37:  aconst_null
   38:  areturn

public int $tag()   throws java.rmi.RemoteException;
  Code:
   0:   aload_0
   1:   invokestatic    #42; //Method scala/ScalaObject$class.$tag:(Lscala/ScalaObject;)I
   4:   ireturn

}

Декодирование, сначала вызывается метод равный переданному параметру и объекту Nil . Если true, возвращает последнее. В противном случае он вызывает instanceOf [::] для объекта. Если true, он приводит объект к этому и вызывает для него метод tl . В противном случае загружает коснант null и возвращает его.

Итак, вы видите, x :: xs не вызывает никакого экстрактора.

Что касается накопления, есть еще один шаблон, который вы, возможно, захотите рассмотреть: 

val list = List.fill(100)(scala.util.Random.nextInt)
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0)
val accumulator = list.foldLeft(Accumulator())( (acc, n) => 
  n match {
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1)
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1)
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1)
  })

Параметры по умолчанию и методы копирования - это функция Scala 2.8, которую я использовал только для упрощения примера, но дело в том, чтобы использовать метод foldLeft , когда вы хотите накапливать вещи над списком. 

class ListExample {
  def test(o: Any): Any = o match {
    case Nil => Nil
    case x :: xs => xs
    case _ => null
  }
}

Генерирует: 

public class ListExample extends java.lang.Object implements scala.ScalaObject{
public ListExample();
  Code:
   0:   aload_0
   1:   invokespecial   #10; //Method java/lang/Object."<init>":()V
   4:   return

public java.lang.Object test(java.lang.Object);
  Code:
   0:   aload_1
   1:   astore_2
   2:   getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   5:   aload_2
   6:   invokestatic    #24; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z
   9:   ifeq    18
   12:  getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   15:  goto    38
   18:  aload_2
   19:  instanceof      #26; //class scala/$colon$colon
   22:  ifeq    35
   25:  aload_2
   26:  checkcast       #26; //class scala/$colon$colon
   29:  invokevirtual   #30; //Method scala/$colon$colon.tl$1:()Lscala/List;
   32:  goto    38
   35:  aconst_null
   36:  pop
   37:  aconst_null
   38:  areturn

public int $tag()   throws java.rmi.RemoteException;
  Code:
   0:   aload_0
   1:   invokestatic    #42; //Method scala/ScalaObject$class.$tag:(Lscala/ScalaObject;)I
   4:   ireturn

}

Декодирование, сначала вызывается метод , равный для переданного параметра, и объект Nil . Если это правда, возвращает последнее. В противном случае он вызывает instanceOf [::] для объекта. Если истинно, он приводит объект к этому и вызывает для него метод tl . В противном случае загружает коснант null и возвращает его.

Итак, вы видите, x :: xs не вызывает никакого экстрактора.

Что касается накопления, есть еще один шаблон, который вы, возможно, захотите рассмотреть: 

val list = List.fill(100)(scala.util.Random.nextInt)
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0)
val accumulator = list.foldLeft(Accumulator())( (acc, n) => 
  n match {
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1)
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1)
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1)
  })

Параметры по умолчанию и методы копирования - это функция Scala 2.8, которую я использовал только для упрощения примера, но дело в том, чтобы использовать метод foldLeft , когда вы хотите накапливать вещи над списком. 

class ListExample {
  def test(o: Any): Any = o match {
    case Nil => Nil
    case x :: xs => xs
    case _ => null
  }
}

Генерирует: 

public class ListExample extends java.lang.Object implements scala.ScalaObject{
public ListExample();
  Code:
   0:   aload_0
   1:   invokespecial   #10; //Method java/lang/Object."<init>":()V
   4:   return

public java.lang.Object test(java.lang.Object);
  Code:
   0:   aload_1
   1:   astore_2
   2:   getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   5:   aload_2
   6:   invokestatic    #24; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z
   9:   ifeq    18
   12:  getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   15:  goto    38
   18:  aload_2
   19:  instanceof      #26; //class scala/$colon$colon
   22:  ifeq    35
   25:  aload_2
   26:  checkcast       #26; //class scala/$colon$colon
   29:  invokevirtual   #30; //Method scala/$colon$colon.tl$1:()Lscala/List;
   32:  goto    38
   35:  aconst_null
   36:  pop
   37:  aconst_null
   38:  areturn

public int $tag()   throws java.rmi.RemoteException;
  Code:
   0:   aload_0
   1:   invokestatic    #42; //Method scala/ScalaObject$class.$tag:(Lscala/ScalaObject;)I
   4:   ireturn

}

Декодирование, сначала вызывается метод , равный для переданного параметра, и объект Nil . Если true, возвращает последнее. В противном случае он вызывает instanceOf [::] для объекта. Если истинно, он приводит объект к этому и вызывает для него метод tl . В противном случае загружает коснант null и возвращает его.

Итак, вы видите, x :: xs не вызывает никакого экстрактора.

Что касается накопления, есть еще один шаблон, который вы, возможно, захотите рассмотреть: 

val list = List.fill(100)(scala.util.Random.nextInt)
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0)
val accumulator = list.foldLeft(Accumulator())( (acc, n) => 
  n match {
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1)
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1)
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1)
  })

Параметры по умолчанию и методы копирования - это функция Scala 2.8, которую я использовал только для упрощения примера, но суть заключается в использовании метода foldLeft , когда вы хотите накопить вещи над списком.

сначала он вызывает метод , равный для переданного параметра, и объект Nil . Если true, возвращает последнее. В противном случае он вызывает instanceOf [::] для объекта. Если true, он приводит объект к этому и вызывает для него метод tl . В противном случае загружает коснант null и возвращает его.

Итак, вы видите, x :: xs не вызывает никакого экстрактора.

Что касается накопления, есть еще один шаблон, который вы, возможно, захотите рассмотреть: 

val list = List.fill(100)(scala.util.Random.nextInt)
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0)
val accumulator = list.foldLeft(Accumulator())( (acc, n) => 
  n match {
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1)
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1)
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1)
  })

Параметры по умолчанию и методы копирования - это функция Scala 2.8, которую я использовал только для упрощения примера, но дело в том, чтобы использовать метод foldLeft , когда вы хотите накапливать вещи над списком.

сначала он вызывает метод , равный для переданного параметра, и объект Nil . Если это правда, возвращает последнее. В противном случае он вызывает instanceOf [::] для объекта. Если истинно, он приводит объект к этому и вызывает для него метод tl . В противном случае загружает коснант null и возвращает его.

Итак, вы видите, x :: xs не вызывает никакого экстрактора.

Что касается накопления, есть еще один шаблон, который вы, возможно, захотите рассмотреть: 

val list = List.fill(100)(scala.util.Random.nextInt)
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0)
val accumulator = list.foldLeft(Accumulator())( (acc, n) => 
  n match {
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1)
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1)
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1)
  })

Параметры по умолчанию и методы копирования - это функция Scala 2.8, которую я использовал только для упрощения примера, но суть заключается в использовании метода foldLeft , когда вы хотите накапливать вещи над списком.

В противном случае он вызывает instanceOf [::] для объекта. Если истинно, он приводит объект к этому и вызывает для него метод tl . В противном случае загружает коснант null и возвращает его.

Итак, вы видите, x :: xs не вызывает никакого экстрактора.

Что касается накопления, есть еще один шаблон, который вы, возможно, захотите рассмотреть: 

val list = List.fill(100)(scala.util.Random.nextInt)
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0)
val accumulator = list.foldLeft(Accumulator())( (acc, n) => 
  n match {
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1)
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1)
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1)
  })

Параметры по умолчанию и методы копирования - это функция Scala 2.8, которую я использовал только для упрощения примера, но суть заключается в использовании метода foldLeft , когда вы хотите накопить вещи над списком.

В противном случае он вызывает instanceOf [::] для объекта. Если истинно, он приводит объект к этому и вызывает для него метод tl . В противном случае загружает коснант null и возвращает его.

Итак, вы видите, x :: xs не вызывает никакого экстрактора.

Что касается накопления, есть еще один шаблон, который вы, возможно, захотите рассмотреть: 

val list = List.fill(100)(scala.util.Random.nextInt)
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0)
val accumulator = list.foldLeft(Accumulator())( (acc, n) => 
  n match {
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1)
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1)
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1)
  })

Параметры по умолчанию и методы копирования - это функция Scala 2.8, которую я использовал только для упрощения примера, но дело в том, чтобы использовать метод foldLeft , когда вы хотите накапливать вещи над списком.

19
ответ дан 1 December 2019 в 13:21
поделиться
Другие вопросы по тегам:

Похожие вопросы: