Le style de codage idiomatique Scala est-il un piège génial pour écrire du code inefficace?

Question

Je sens que la Scala de la communauté a un peu grande obsession de l'écriture "concis", "cool", "scala idiomatiques", "one-liner" -si possible - code. C'est immédiatement suivie par une comparaison avec Java/impératif/laid code.

Tout ce (parfois) conduit à facile à comprendre le code, il a également conduit à l'inefficacité de code pour 99% des développeurs. Et c'est là que Java/C++ n'est pas facile à battre.

Considérer ce problème simple: étant Donné une liste de nombres entiers, de supprimer le plus grand élément. La commande n'a pas besoin d'être conservé.

Voici ma version de la solution (Il peut ne pas être le plus grand, mais c'est ce que la moyenne des non-rockstar développeur ferait).

def removeMaxCool(xs: List[Int]) = {
  val maxIndex = xs.indexOf(xs.max);
  xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}

C'est Scala idiomatiques, concis, et en utilise qu'une belle liste de fonctions. Il est également très inefficace. Il parcourt la liste d'au moins 3 ou 4 fois.

Voici mon totalement cool, Java-comme solution. C'est aussi ce raisonnable développeur Java (ou Scala novice) serait d'écrire.

def removeMaxFast(xs: List[Int]) = {
    var res = ArrayBuffer[Int]()
    var max = xs.head
    var first = true;   
    for (x <- xs) {
        if (first) {
            first = false;
        } else {
            if (x > max) {
                res.append(max)
                max = x
            } else {
                res.append(x)
            }
        }
    }
    res.toList
}

Totalement non-Scala idiomatiques, non fonctionnels, non-concise, mais elle est très efficace. Il parcourt la liste qu'une seule fois!

Donc, si 99% des développeurs Java écrire du code plus efficace que 99% de la Scala de développeurs, c'est un énorme obstacle à la croix pour plus de Scala adoption. Est-il un moyen de sortir de ce piège?

Je suis à la recherche de conseils pratiques pour éviter de telles "l'inefficacité des pièges" tout en gardant la mise en œuvre clair sna concis.

Clarification: Cette question vient d'un scénario de la vie réelle: j'ai dû écrire un algorithme complexe. D'abord je l'ai écrit en Scala, puis j'ai "dû" le réécrire en Java. L'implémentation de Java a été deux fois plus longtemps, et pas que ce soit clair, mais en même temps, il a été deux fois plus rapide. La réécriture de la Scala de code pour être efficace serait probablement prendre un certain temps et un peu plus profonde compréhension de la scala, de l'efficacité interne (par contre la carte vs pli, etc)

Answer 1

Nous allons discuter d'une erreur dans la question:

Donc, si 99% des développeurs Java écrire du code plus efficace que 99% de Scala développeurs, c'est un énorme obstacle à la croix pour plus de Scala l'adoption. Est-il un moyen de sortir de ce piège?

C'est présumée, avec absolument aucune preuve de la sauvegarder. Si la valeur est false, la question est discutable.

Est-il prouvé le contraire? Eh bien, nous allons examiner la question elle-même, il ne faut pas prouver quoi que ce soit, mais montre les choses ne sont pas claires.

Totalement non-Scala idiomatiques, non fonctionnel, non concis, mais c'est très efficace. Il parcourt la liste qu'une seule fois!

Des quatre revendications dans la première phrase, les trois premiers sont le vrai, et le quatrième, comme indiqué par utilisateur inconnu, est faux! Et pourquoi c'est faux? Parce que, contrairement à ce que la deuxième phrase unis, il parcourt la liste plus d'une fois.

Le code appelle les méthodes suivantes sur elle:

res.append(max)
res.append(x)

et

res.toList

Considérons tout d'abord append.

1. append prend un vararg paramètre. Cela signifie que max et x sont d'abord encapsulé dans une séquence d'un certain type (un WrappedArray, en fait), puis est passé en paramètre. Une meilleure méthode aurait été +=.

2. Ok, append des appels ++=, qui délègue à +=. Mais, d'abord, il appelle ensureSize, ce qui est la seconde erreur (+= des appels que trop -- ++= seulement optimise que pour plusieurs éléments). Parce qu'un Array a une taille fixe de la collection, ce qui signifie que, à chaque redimensionnement, l'ensemble de l' Array doit être copié!

Considérons donc cette. Lorsque vous redimensionnez, Java première efface la mémoire en stockant 0 dans chaque élément, puis de la Scala de copies de chaque élément du tableau précédent sur le nouveau tableau. Depuis taille double à chaque fois, ce qui se passe log(n) fois, avec le nombre d'éléments copiés augmente chaque fois qu'il se passe.

Prenons par exemple n = 16. Il le fait à quatre reprises, la copie 1, 2, 4 et 8 éléments respectivement. Depuis Java a pour effacer chacun de ces tableaux, et chaque élément doit être lu et écrit, chaque élément copié représente 4 traversals d'un élément. L'ajout de tout ce que nous avons (n - 1) * 4, ou, en gros, 4 traversals de la liste complète. Si vous comptez lire et d'écrire comme un seul passage, que les gens sont souvent, à tort, de faire, alors c'est encore trois traversals.

On peut améliorer cette situation par l'initialisation de l' ArrayBuffer avec une taille initiale égale à la liste de lecture, moins un, puisque nous allons être jeter un seul élément. Pour obtenir cette taille, nous avons besoin de la traversée de la liste une fois, même si.

Maintenant, nous allons examiner toList. Pour le dire simplement, il traverse l'ensemble de la liste pour créer une nouvelle liste.

Donc, nous avons 1 traversée de l'algorithme, 3 ou 4 traversals pour redimensionner, et 1 autre de la traversée pour toList. C'est 4 ou 5 traversals.

L'algorithme original est un peu difficile à analyser, car take, drop et ::: parcourir un nombre variable d'éléments. Ajouter tous ensemble, cependant, il ne l'équivalent de 3 traversals. Si splitAt a été utilisé, il serait réduit à 2 traversals. Avec plus de 2 traversals pour obtenir le maximum, on obtient 5 traversals -- le même numéro que le non-fonctionnels, non-concise de l'algorithme!

Donc, nous allons envisager des améliorations.

Sur l'impératif de l'algorithme, si l'on utilise ListBuffer et +=, toutes les méthodes sont constante de temps, ce qui le réduit à une seule traversée.

Sur le fonctionnel de l'algorithme, il pourrait être réécrit comme suit:

val max = xs.max
val (before, _ :: after) = xs span (max !=)
before ::: after

Qui le réduit à un pire cas de trois traversals. Bien sûr, il existe d'autres alternatives présenté, sur la base de la récursivité ou se coucher, que de le résoudre en une seule traversée.

Et, le plus intéressant de tous, de tous ces algorithmes sont O(n), et le seul qui presque engagées (accidentellement) dans le pire de la complexité a été l'impératif d'un (à cause de la matrice de copie). D'autre part, le cache des caractéristiques de l'impératif, on pourrait bien le rendre plus rapide, car les données sont contigus en mémoire. Qui, cependant, est indépendants de la grande-Oh ou fonctionnelle vs impératif, et c'est juste une question de structures de données qui ont été choisis.

Donc, si nous avons fait aller à la difficulté de l'analyse comparative, l'analyse des résultats, compte tenu de la performance des méthodes, et à examiner les possibilités d'optimisation, alors on peut trouver plus rapidement des façons de le faire d'une manière impérative que de manière fonctionnelle.

Mais tout cet effort est très différent de dire la moyenne programmeur Java code sera plus rapide que la moyenne de la Scala programmeur code -- si la question est un exemple, qui est tout simplement faux. Et même sans tenir compte de la question, nous l'avons vu aucune preuve que la prémisse fondamentale de la question qui est vrai.

MODIFIER

Tout d'abord, permettez-moi de reformuler mon point de vue, car il semble que je n'étais pas clair. Mon point est que le code de la moyenne Java programmeur écrit peut sembler plus efficace, mais ne l'est pas. Ou, dans l'autre sens, Java traditionnelle de style n'est pas le gain de performance -- seulement travailler dur n', que ce soit en Java ou Scala.

Ensuite, j'ai un indice de référence et les résultats, y compris presque toutes les solutions proposées. Deux points intéressants à ce sujet:

1. En fonction de la taille de la liste, la création d'objets peuvent avoir un impact plus important que de multiples traversals de la liste. L'original du code fonctionnel par Adrian prend avantage du fait que les listes sont persistantes des structures de données en ne copiant pas les éléments à droite de l'élément maximal à tous. Si un Vector a été utilisé au lieu de cela, les deux côtés gauche et droit serait essentiellement le même, ce qui pourrait conduire à de meilleures performances.

2. Même si l'utilisateur inconnu et paradigmatique similaires récursive des solutions, paradigmatique est beaucoup plus rapide. La raison en est qu'il évite de pattern matching. La correspondance de motif peut être vraiment lent.

L'indice de référence code est ici, et les résultats sont ici.

Answer 2

def removeOneMax (xs: List [Int]) : List [Int] = xs match {                                  
    case x :: Nil => Nil 
    case a :: b :: xs => if (a < b) a :: removeOneMax (b :: xs) else b :: removeOneMax (a :: xs) 
    case Nil => Nil 
}

Voici une méthode récursive, qui ne parcourt qu'une fois. Si vous avez besoin de performances, vous devez penser à ce sujet, si ce n'est, pas.

Vous pouvez en faire la queue-récursive de façon standard: donner un paramètre supplémentaire, carry, ce qui est, par défaut, la Liste vide, et recueille le résultat lors de l'itération. C'est, bien sûr, un peu plus long, mais si vous avez besoin de performances, vous avez à payer pour cela:

import annotation.tailrec 
@tailrec
def removeOneMax (xs: List [Int], carry: List [Int] = List.empty) : List [Int] = xs match {                                  
  case a :: b :: xs => if (a < b) removeOneMax (b :: xs, a :: carry) else removeOneMax (a :: xs, b :: carry) 
  case x :: Nil => carry 
  case Nil => Nil 
}

Je ne sais pas ce que les chances sont, qui plus tard compilateurs améliorer ralentissement de la carte-les appels à être aussi rapide que tout en boucles. Cependant: Vous aurez rarement besoin de haute vitesse à des solutions, mais si vous avez besoin d'eux, souvent, vous apprendrez vite.

Savez-vous comment grand votre collection doit être, pour utiliser une seconde pour votre solution sur votre machine?

Comme oneliner, semblable à Daniel C. Sobrals solution:

((Nil : List[Int], xs(0)) /: xs.tail) ((p, x)=> if (p._2 > x) (x :: p._1, p._2) else ((p._2 :: p._1), x))._1

mais c'est dur à lire, et je n'ai pas à la mesure de la performance efficace. Le mode normal est (x: xs) ((a, b) => /* quelque chose */). Ici, x et a sont des paires de Liste de la mesure et max-mesure, ce qui résout le problème pour amener le tout en une seule ligne de code, mais n'est pas très lisible. Toutefois, vous pouvez gagner de la réputation sur CodeGolf de cette façon, et peut-être quelqu'un qui aime faire une mesure de la performance.

Et maintenant, à notre grande surprise, quelques mesures:

Une mise à jour de temps, pour obtenir la collecte des ordures hors de la voie, et ont le hotspot-compilateur d'échauffement, d'une main, et de nombreuses méthodes de ce fil, ensemble dans un Objet nommé

object PerfRemMax {

  def timed (name: String, xs: List [Int]) (f: List [Int] => List [Int]) = {
    val a = System.currentTimeMillis 
    val res = f (xs)
    val z = System.currentTimeMillis 
    val delta = z-a
    println (name + ": "  + (delta / 1000.0))
    res
  }

def main (args: Array [String]) : Unit = {
  val n = args(0).toInt
  val funs : List [(String, List[Int] => List[Int])] = List (
    "indexOf/take-drop" -> adrian1 _, 
    "arraybuf"      -> adrian2 _, /* out of memory */
    "paradigmatic1"     -> pm1 _, /**/
    "paradigmatic2"     -> pm2 _, 
    // "match" -> uu1 _, /*oom*/
    "tailrec match"     -> uu2 _, 
    "foldLeft"      -> uu3 _,
    "buf-=buf.max"  -> soc1 _, 
    "for/yield"     -> soc2 _,
    "splitAt"       -> daniel1,
    "ListBuffer"    -> daniel2
    )

  val r = util.Random 
  val xs = (for (x <- 1 to n) yield r.nextInt (n)).toList 

// With 1 Mio. as param, it starts with 100 000, 200k, 300k, ... 1Mio. cases. 
// a) warmup
// b) look, where the process gets linear to size  
  funs.foreach (f => {
    (1 to 10) foreach (i => {
        timed (f._1, xs.take (n/10 * i)) (f._2)
        compat.Platform.collectGarbage
    });
    println ()
  })
}

J'ai renommé toutes les méthodes, et a dû modifier uu2 un peu, pour s'adapter à la commune de la déclaration de la méthode (List [Int] => List [Int]).

De la longue suite, j'ai seulement fournir le résultat de 1M invocations:

scala -Dserver PerfRemMax 2000000
indexOf/take-drop:  0.882
arraybuf:   1.681
paradigmatic1:  0.55
paradigmatic2:  1.13
tailrec match: 0.812
foldLeft:   1.054
buf-=buf.max:   1.185
for/yield:  0.725
splitAt:    1.127
ListBuffer: 0.61

Les numéros ne sont pas complètement stable, en fonction de la taille de l'échantillon, et un peu varier d'une exécution. Par exemple, pour 100k 1M pistes, dans les étapes de 100k, le moment pour splitAt a été comme suit:

splitAt: 0.109
splitAt: 0.118
splitAt: 0.129
splitAt: 0.139
splitAt: 0.157
splitAt: 0.166
splitAt: 0.749
splitAt: 0.752
splitAt: 1.444
splitAt: 1.127

La solution initiale est déjà assez rapide. splitAt est une modification de Daniel, souvent plus rapide, mais pas toujours.

Les mesures ont été réalisées sur un seul core à 2 ghz Centrino, l'exécution de xUbuntu Linux, Scala-2,8 avec Sun-Java 1.6 (de bureau).

Les deux leçons sont pour moi:

• toujours mesurer votre des améliorations de performances, il est très difficile de l'estimer, si vous ne le faites pas sur une base quotidienne
• il n'est pas seulement amusant, pour écrire du code fonctionnel - parfois, le résultat est encore plus rapide

Voici un lien vers mon benchmarkcode, si quelqu'un est intéressé.

Answer 3

Tout d'abord, le comportement des méthodes que vous avez présenté n'est pas le même. La première maintient l'élément de commande, tandis que la seconde ne l'est pas.

En deuxième lieu, parmi toutes les solutions possibles qui pourrait être qualifié de "idiomatiques", certaines sont plus efficaces que d'autres. Restant très près de votre exemple, vous pouvez par exemple utiliser la queue de la récursivité pour éliminer les variables et le manuel de gestion de l'état:

def removeMax1( xs: List[Int] ) = {
  def rec( max: Int, rest: List[Int], result: List[Int]): List[Int] = {
    if( rest.isEmpty ) result
    else if( rest.head > max ) rec( rest.head, rest.tail, max :: result)
    else rec( max, rest.tail, rest.head :: result )
  }
  rec( xs.head, xs.tail, List() )
}

ou plier la liste:

def removeMax2( xs: List[Int] ) = {
  val result = xs.tail.foldLeft( xs.head -> List[Int]() ) { 
    (acc,x) =>
      val (max,res) = acc
      if( x > max ) x -> ( max :: res )
      else max -> ( x :: res )
  }
  result._2
}

Si vous souhaitez conserver l'original de l'ordre d'insertion, vous pouvez (au détriment d'avoir deux passes, plutôt qu'un seul), sans aucun effort d'écrire quelque chose comme:

def removeMax3( xs: List[Int] ) = {
  val max = xs.max
  xs.filterNot( _ == max )
}

ce qui est plus clair que votre premier exemple.

Answer 4

La plus grande inefficacité lorsque vous écrivez un programme qui est inquiétant, sur les mauvaises choses. Ce n'est généralement pas la bonne chose à craindre. Pourquoi?

1. Développeur de temps est généralement beaucoup plus cher que le PROCESSEUR temps - en fait, il est généralement une pénurie de l'ancien et de l'excédent de ce dernier.

2. La plupart du code n'a pas besoin d'être très efficace, car il ne sera jamais en cours d'exécution sur m-élément ensembles de données plusieurs fois par seconde.

3. La plupart du code ne doivent sans bug, et moins de code, moins de place pour les bugs à cacher.

Answer 5

L'exemple que vous avez donné n'est pas très fonctionnelle, en fait. Voici ce que vous faites:

// Given a list of Int
def removeMaxCool(xs: List[Int]): List[Int] = {

  // Find the index of the biggest Int
  val maxIndex = xs.indexOf(xs.max);

  // Then take the ints before and after it, and then concatenate then
  xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}

Rappelez-vous, il n'est pas mauvais, mais vous savez quand le code fonctionnel est à son meilleur lorsqu'il décrit ce que vous voulez, au lieu de la façon dont vous le voulez. Comme une critique mineure, si vous avez utilisé splitAt au lieu de take et drop vous pourriez améliorer légèrement.

Une autre façon de faire, c'est ceci:

def removeMaxCool(xs: List[Int]): List[Int] = {
  // the result is the folding of the tail over the head 
  // and an empty list
  xs.tail.foldLeft(xs.head -> List[Int]()) {

    // Where the accumulated list is increased by the
    // lesser of the current element and the accumulated
    // element, and the accumulated element is the maximum between them
    case ((max, ys), x) => 
      if (x > max) (x, max :: ys)
      else (max, x :: ys)

  // and of which we return only the accumulated list
  }._2
}

Maintenant, nous allons discuter de la question principale. Est-ce code plus lent que le code Java? Très certainement! Est le code Java plus lent qu'un C équivalent? Vous pouvez parier qu'il est, JIT ou pas de JIT. Et si vous l'écrire directement en assembleur, vous pouvez le rendre encore plus rapide!

Mais le coût de cette vitesse, c'est que vous obtenez plus de bugs, vous passez plus de temps à essayer de comprendre le code de débogage, et vous avez moins de visibilité de ce que l'ensemble du programme est de faire comme opposée à ce qu'un petit morceau de code est de le faire-ce qui pourrait entraîner des problèmes de performances de son propre.

Donc, ma réponse est simple: si vous pensez que la vitesse de la peine de programmation Scala n'est pas la peine la plus-value qu'il apporte, vous devez programmer en assembleur. Si vous pensez que je suis radical, alors je le compteur que vous venez de choisir le familier comme étant l ' "idéal" hors commerce.

Dois-je pense que la performance n'a pas d'importance? Pas du tout! Je pense que l'un des principaux avantages de la Scala est l'optimisation des gains souvent trouvé dans typées dynamiquement les langues avec les performances d'un langage statiquement typé! Des questions de rendement, la complexité de l'algorithme est très important, et constante des coûts des matières.

Mais, chaque fois qu'il ya un choix entre la performance et de la lisibilité et de facilité de maintenance, ce dernier est préférable. Bien sûr, si les performances doivent être améliorées, alors il n'y a pas le choix: vous devez sacrifier quelque chose pour elle. Et si il n'y a pas perdu en lisibilité/maintenabilité, tels que Scala vs typées dynamiquement langues -- assurez-vous, allez à la performance.

Enfin, le gain de performance de la programmation fonctionnelle, vous devez savoir fonctionnelle algorithmes et structures de données. Assurez-vous que 99% des programmeurs Java avec 5 à 10 ans d'expérience va battre la performance de 99% de la Scala de programmeurs avec 6 mois d'expérience. Le même est vrai pour la programmation impérative vs la programmation orientée objet, il y a quelques décennies, et l'histoire montre qu'il n'a pas d'importance.

MODIFIER

Comme une note de côté, votre "rapide" de l'algorithme de souffrir d'un sérieux problème: vous utilisez ArrayBuffer. Cette collection n'a pas de temps constant ajouter, et a le temps linéaire toList. Si vous utilisez ListBuffer au lieu de cela, vous obtenez de la constante de temps append et toList.