Я хочу конвертировать из Python в Scala эту функцию разделения, используя Vector - PullRequest
Новая
       41

Я хочу конвертировать из Python в Scala эту функцию разделения, используя Vector

1 голос
/ 26 сентября 2019

Я начал изучать Scala.Мне трудно понять коллекции Scala.Я хочу запрограммировать функцию Partition , но я имею в виду код, уже написанный с использованием Python.Не могли бы вы сказать мне тот же код Scala.

Я использую SBT 2.12.0.

Я хочу обрабатывать большие данные.Я слышал, что тип Vector быстрый, поэтому я пытаюсь его использовать, но можете ли вы сказать, есть ли более подходящий тип коллекции?Мне было трудно обрабатывать тип Stream, но данные можно было хранить с использованием множества обратных данных.Вычисление медленнее, если обратная обработка выполняется каждый раз?

Версия Python 

class PartitionNumbers:
    def __init__(self):
        self.points_list = list()

    def _partition_function(self, n, k, tmp_list=[]):
        if n == 0:
            self.nums_list.append(tmp_list)
        elif n == 1:
            self.nums_list.append(tmp_list + [1])
        elif k == 1:
            self.nums_list.append(tmp_list + [1] * n)
        else:
            if n >= k:
                self._partition_function(n - k, k, tmp_list + [k])
            self._partition_function(n, k - 1, tmp_list)
        return self.points_list

    def create(self, n):
        self.points_list = list()
        return self._partition_function(n, n)

Этот код дает следующий результат: 

pn = PartitionNumbers()

pn.create(3)  # -> [[3], [2, 1], [1, 1, 1]]
pn.create(6)  # -> [[6], [5, 1], [4, 2], [4, 1, 1], [3, 3], [3, 2, 1], [3, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]

Версия Scala 

object PartitionNumbers {

  def partitionFunction(n: Int, k: Int, v: Vector[Int] = Vector(), numsVector: Vector[Int] = Vector()): Vector[Int] = {
    var tmp: Vector[Int] = Vector()
    if (n == 0) {
      tmp ++= numsVector ++ v
    } else if (n == 1) {
      tmp ++= numsVector ++ v ++ List(1)
    } else if (k == 1) {
      tmp ++= numsVector ++ append(n, v)
    } else {
      if (n >= k) {
        partitionFunction(n - k, k, v :+ k, numsVector)
      }
      partitionFunction(n, k - 1, v, numsVector)
    }
    tmp
  }

  def append(n: Int, v: Vector[Int]): Vector[Int] = {
    if (n == 0) {
      v
    } else {
      append(n - 1, v :+ 1)
    }
  }

  def create(n: Int): Vector[Int] = {
    partitionFunction(n, n)
  }
}

Я ожидаю вывод той же версии Python, но фактический вывод будет 

Vector()
Vector()

(Добавить: 2019-09-27 17:49 [JST])

Я попробовал версию потока типа.Насколько я понимаю, тип потока может добавлять элемент только в заголовке, поэтому порядок чисел меняется с первого кода.
Цель этого кода - получить максимальное значение из результата вычисления с использованием разделаЧисла. 

import scala.math.floor

class PartitionNumbers(startNum: Int, point: Int) {
  var maxNum = 0
  var tmpNum = 0

  private def appendOnes(n: Int, s: Stream[Int] = Stream.empty[Int]): Stream[Int] = {
    if (n == 0) s
    else appendOnes(n - 1, 1 #:: s)
  }

  private def partition(n: Int, k: Int, tmpStream: Stream[Int] = Stream.empty): Int = {
    if (n == 0) tmpNum = addPercent(tmpStream)
    else if (n == 1 | k == 1) tmpNum = addPercent(appendOnes(n))
    else {
      if (n >= k) partition(n - k, k, k #:: tmpStream)
      partition(n, k - 1, tmpStream)
    }
    if (maxNum < tmpNum) maxNum = tmpNum
    maxNum
  }

  def searchMax(n: Int = point): Int = {
    partition(n, n)
  }

  def addPercent(usePointsStream: Stream[Int], num: Int = startNum): Int = {
    if (usePointsStream.isEmpty) {
      num
    } else {
      addPercent(usePointsStream.init, floor(num * (100 + usePointsStream.last) / 100).toInt)
    }
  }

}

Это дало мне следующие результаты: 

val pn_1 = new PartitionNumbers(100, 10)
println(pn_1.searchMax())  // -> 110

val pn_2 = new PartitionNumbers(1000, 50)
println(pn_2.searchMax())  // -> 1630

Вывод этого кода правильный, но PartitionNumbers.point не может обработать до 100. Мне нужно этообработка более 1000.

Что мне нужно прямо сейчас: понимание типа или другие соображения алгоритма?

(Добавить: 2019-09-28 03:11 [JST])
добавить вопрос: Исправлен код Scala с использованием номеров разделов с вычислением потока, НО слишком медленно

1 Ответ

1 голос
/ 27 сентября 2019

Отсутствие типов в Python - это то, что затрудняет перенос.Кажется, что даже если тип tmp_list будет Vector[Vector[Int]], это: 

(tmp_list + [2]) + [1] == [1, 2]

, что безумие, оно должно быть [[1], [2]], если оно строго напечатано.

Учитывая это, вот прямой перевод: 

class PartitionNumbers {
  private var pointsList: Vector[Vector[Int]] = null

  private def partition(n: Int, k: Int, tmpList: Vector[Int] = Vector.empty): Vector[Vector[Int]] = {
    if (n == 0) pointsList :+= tmpList
    else if (n == 1) pointsList :+= (tmpList :+ 1)
    else if (k == 1) pointsList :+= (tmpList ++ (1 to n).map(_ => 1).toVector)
    else {
      if (n >= k) partition(n - k, k, tmpList :+ k)
      partition(n, k - 1, tmpList)
    }

    pointsList
  }

  def create(n: Int): Vector[Vector[Int]] = {
    pointsList = Vector.empty
    partition(n, n)
  }
}

Если вы хотите обрабатывать большие данные, однако, используя «raw scala» (например, ничего похожего на spark), потоком будет путь.Это потому, что он может считывать данные по одному и сохранять постоянную память.Однако, чтобы понять, как правильно их использовать, нужно изменить образ мышления на стиль FP.

Я бы порекомендовал использовать потоки Akka или потоки FS2.

Вот видеоот Scala Toronto о FS2, стоит посмотреть:

https://www.youtube.com/watch?v=B1wb4fIdtn4&t=2s

...