2

命令型コードを使用してソートされていない配列の最大値を見つけるのは非常に簡単です

たとえば、Javaで（説明目的でのみ使用され、より適切に記述できると確信しています）

public class Main {
    public static void main(String[] args) {
        int[] array = {1,3,5,4,2};
        int max = findMax(array);
        System.out.println(max);
    }

    public static int findMax(int[] array){
        int max = Integer.MIN_VALUE; //or array[0], but it requires a null check and I want to keep it simple :)
        for (int i = 0, size = array.length; i < size ; i++) {
            int current = array[i];
            if(current > max) max = current;
        }
        return max;
    }
}

それを行う機能的な方法は何ですか？例えば

  • 可変変数なし (例: maxvalを Scala / finalJava で a にする)
  • ループなし (例: 再帰を使用、末尾を優先)

Scala のソースでは、recudeLeft を使用して行われていることがわかりました。これは非常に賢いようです。

  def max[B >: A](implicit cmp: Ordering[B]): A = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.max")

    reduceLeft((x, y) => if (cmp.gteq(x, y)) x else y)
  }

しかし、(何らかの理由で) reduce / reduceLeft が利用可能 / 実装されていないとしましょう (そして、何らかの理由でそれを実装したくない / 実装できない、つまり、プレーンな Java で作業している)

他の機能的な方法に依存せずに最大値を実行する「慣用的な」機能的な方法は何ですか (たとえば、機能的なパラダイムを念頭に置いて、ベアボーン Java でどのように実装しますか)

回答はどの言語でもかまいません (Java / Scala が望ましい)

4

3 に答える 3

4

これは、最大値のアキュムレータを使用したテール コール再帰の実装です。

public class Main {

    public static void main(String[] args) {
        System.out.println(max(new int[]{6, 3, 9, 4}));
    }

    public static int max(int[] ints) {
        return max(ints, Integer.MIN_VALUE);
    }

    public static int max(int[] ints, int max) {
        if (ints.length == 0) {
            return max;
        } else {
            return max(Arrays.copyOfRange(ints, 1, ints.length), ints[0] > max ? ints[0] : max);
        }
    }

}
于 2013-04-22T21:43:48.513 に答える
1

単純な再帰で実行できますが、maba の末尾再帰バージョンの方がパフォーマンスが優れているはずです。

import java.util.Arrays;
public class TestMax {
public static int findMax(int[] array) {
    if(array.length == 1)
        return array[0];
    int[] newArray = Arrays.copyOfRange(array, 1, array.length);
    if(array[0] > findMax(newArray))
        return array[0];
    else
        return findMax(newArray);
}
/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = {1,3,5,4,2, 9};
    int max = findMax(array);
    System.out.println(max);
}
}
于 2013-04-22T21:53:32.393 に答える
1

マバの優れた回答に基づいて、誰かが興味を持っていれば、Scala バージョンがここにあります

  def max(list: List[Int]) = {
    maxAcc(list, Int.MinValue)
  }                                               

  def maxAcc(list: List[Int], curMax:Int):Int = {
    list match {
        case Nil => curMax
        case head :: tail => maxAcc(tail, if (head > curMax ) head else curMax )
    }
  }

編集：@tailrecに関するmabaのコメントのおかげで-これが修正版です

 def max(list: List[Int]) = {
    @tailrec def maxAcc(list: List[Int], curMax: Int): Int = {
      list match {
        case Nil => curMax
        case head :: tail => maxAcc(tail, if (head > curMax) head else curMax)
      }
    }
    maxAcc(list, Int.MinValue)
  }
于 2013-04-22T22:21:41.560 に答える