避免在Java 8中使用全局變量流減少方法

Question

我試圖用Java 8重寫Moore’s Voting Algorithm的實現來查找數組中的多數元素。

的Java 7的實施將是這樣的：

public int findCandidate(int[] nums) { 

    int maj_index = 0, count = 1; 
    for(int i=1; i<nums.length;i++){ 
     if(count==0){ 
      count++; 
      maj_index=i; 
     }else if(nums[maj_index]==nums[i]){ 
      count++; 
     } else { 
      count--; 
     } 
    } 
    return nums[maj_index]; 
} 

我能想到的是使用流減少，以獲得最終結果

public int findCandidate(int[] nums) { 
    int count = 1; 
    Arrays 
      .asList(nums) 
      .stream() 
      .reduce(0, (result, cur) -> { 
       if (count == 0) { 
        result = cur; 
        count++; 
       } else if (result == cur){ 
        count++; 
       } else { 
        count --; 
       } 
      }); 
    return result; 
} 

的方法，但這種方法有編譯錯誤，此外，它也打破了功能純粹主義者，我多次遇到這種情況，那麼在lambda表達式中處理全局變量的最佳方式是什麼？

Answer 1

所以就像我在我的評論中告訴你的那樣，在你的lambda表達式中使用可變對象是不好的。但在你的情況下，如果你真的想要應用相同的算法，這將是困難的。

這裏有一個會做同樣的，你想要什麼，如果沒有大多數被發現，它返回-1

public static int findCandidate(int ... nums) { 
    Map<Integer, List<Integer>> map = 
    Arrays.stream(nums) 
      .boxed() 
      .collect(Collectors.groupingBy(x -> x)); 
    int value = 
      map 
      .entrySet().stream() 
      .max((e1, e2) -> Integer.compare(e1.getValue().size(), e2.getValue().size())) 
      .map(e -> e.getKey()) 
      .get(); 
    int result = map.get(value).size(); 
    return result > nums.length/2 ? value : -1; 
} 

Answer 2

Yassin Hajaj's answer展示了一些不錯的流技術。 （+1）基本上我認爲它使用正確的方法。不過，有一些小改進可以實現。

第一個更改是使用counting()收集器來計算每個組中的項目，而不是將它們累積到列表中。由於我們正在尋找多數，我們需要的只是數量，而不是實際的元素，我們避免必須比較列表的長度。

第二個變化是過濾列表尋找一個組的計數是多數。根據定義，最多隻能有一個，因此我們只是使用此謂詞過濾映射條目，並用findAny而不是max來終止流。

第三個變化是讓函數返回OptionalInt，它更接近它的意圖。 OptionalInt包含大多數值，或者如果沒有多數值，則爲空。這避免了必須使用實際可能在數據中發生的哨兵值，例如-1。由於findAny返回OptionalInt，我們完成了。

最後，我在幾個地方依靠靜態導入。這主要是風格問題，但我認爲它會清理代碼。

這裏是我的變化：

static OptionalInt majority(int... nums) { 
    Map<Integer, Long> map = 
     Arrays.stream(nums) 
       .boxed() 
       .collect(groupingBy(x -> x, counting())); 

    return map.entrySet().stream() 
       .filter(e -> e.getValue() > nums.length/2) 
       .mapToInt(Entry::getKey) 
       .findAny(); 
} 

Answer 3

你這裏的問題是Java流沒有真正list fold operation。通過真正的摺疊操作，將功能編寫爲左摺疊並不困難。例如，在Haskell：

import Data.List (foldl') 

-- A custom struct to represent the state of the fold. 
data MooreState a = MooreState { candidate :: a, count :: !Int } 

findCandidate :: Eq a => [a] -> Maybe a 
findCandidate (first:rest) = Just result 
    where 
     Moore result _ = foldl' combiner (MooreState first 1) rest      

     combiner :: Eq a => MooreState a -> a -> MooreState a 
     combiner (Moore candidate count) current 
      | count == 0   = MooreState current 1 
      | candidate == current = MooreState candidate (count + 1) 
      | otherwise   = MooreState candidate (count - 1) 

-- The empty list has no candidates. 
findCandidate [] = Nothing 

Java的reduce()方法是它有一個真正的左摺疊最接近的，但如果你看看the Javadoc for the reduce() method that you're using，你會注意到它說：

1. 它「不限制順序執行」;
2. 它需要積累功能爲聯想。

這個文檔很難解釋，但我讀到它的方式是這樣的。儘管它可以處理要素按順序：

• 如果您累積功能是聯想然後可以保證，如果你處理的流依次產生相同的結果;
• 如果您的累積函數不是關聯的，那麼它可能會產生與簡單順序過程不同的結果。

爲什麼這很重要？那麼，首先，你正在改變一個外部變量的事實意味着你使用count的方式被破壞了。爲了您所知，可以在元素＃5之前處理元素＃7。

更多不知不覺，在Haskell的版本combine操作上述結合不同類型（Moore a和a）的輸入，但你使用Java reduce方法基於一個BinaryOperator<T>，它結合了兩個相同類型的對象。有another overload of reduce that uses a BiFunction<U, T, U>，但這需要您提供BinaryOperator<U> combiner及其U identity以及。這是因爲Java的reduce方法被設計爲可以：

1. 將輸入流拆分爲連續的塊;
2. 並行處理多個塊;
3. 將相鄰塊的結果按順序組合起來。

因此，關聯性和身份要求可以保證這種並行處理產生與順序執行相同的結果。但是這意味着雖然算法有一個直接的功能實現，但是用Java的Stream類型編寫它卻沒有直接的方法。 （這有一種非直接的方式，但是這會陷入一些巫術，這將會（一）真的很複雜，（b）在Java中非常緩慢。）

所以我個人只會接受Java不是很棒函數式編程語言，單獨留下足夠的好處並按原樣使用命令式的版本。但如果出於某種奇怪的原因，我真的堅持在功能上做，我會去像jOOλ這樣的圖書館，它提供true left folds in Java。然後，你可以做同樣的哈斯克爾溶液（未經測試的僞代碼）：

import org.jooq.lambda.Seq; 
import org.jooq.lambda.tuple.Tuple2; 

class MooreState<A> { 
    private final A candidate; 
    private final int count; 
    // ...constructors and getters... 
} 

public static Optional<A> findCandidate(Seq<A> elements) { 
    Tuple2<Optional<A>, Seq<A>> split = elements.splitAtHead(); 
    return split.v1().map(first -> { 
     Seq<A> rest = split.v2(); 
     return rest.foldLeft(
      new MooreState<>(first, 1), 
      (state, current) -> { 
       if (state.getCount() == 0) { 
        return new MooreState<>(current, 1); 
       } else if (state.getCandidate().equals(current) { 
        return new MooreState<>(state.getCandidate(), 
              state.getCount() + 1); 
       } else { 
        return new MooreState<>(state.getCandidate(), 
              state.getCount() - 1); 
       } 
      } 
     ); 
    }); 
} 

...這可能是可怕緩慢。

Answer 4

@Stuart Marks寫了簡潔的代碼。但是它仍然可以通過AbacusUtil

Stream.from(nums).groupBy(Function.identity(), Collectors.counting()) 
    .findAny(e -> e.getValue() > nums.length/2) 

披露簡化：我AbacusUtil的開發商。