Первичная факторизация положительного целого с потоками

Question

В настоящее время я пытаюсь включить Stream API Java 8 в свой ежедневный инструментарий Java. Я пытаюсь использовать Streams для поиска простых коэффициентов положительного целого числа, а затем хранить каждый из факторов в массиве (или ArrayList) с их множественностью в параллельном массиве. В качестве альтернативы, я пытаюсь создать Stream of say ... FactorWithMultiplicity объектов или даже Map с коэффициентом как ключ и кратность как значение. Было бы неплохо, если бы факторы были отсортированы в порядке возрастания, и если бы он мог обрабатывать очень большие числа (например, смею сказать, Long.MAX_VALUE).

В настоящее время мой код выглядит так, но, поскольку я новичок в Streams, я уверен, что для выполнения этой задачи существует более быстрый или лучший способ. Используйте Streams для создания своего решения, хотя, если вы знаете, что какое-то решение без потоковой передачи работает быстрее, не стесняйтесь указывать и на этот код.

int num = getPositiveInt(); 
ArrayList<Integer> factors = new ArrayList<>(); 
ArrayList<Integer> multiplicities = new ArrayList<>(); 
boolean isPrime = IntStream.rangeClosed(2, num/2) 
    .reduce(num, (int temp, int factor) -> { 
     int count = 0; 
     while (temp % factor == 0) { 
      temp /= factor; 
      count++; 
     } 
     if (count > 0) { 
      factors.add(factor); 
      multiplicities.add(count); 
     } 
     return temp; 
    }) > 1; 

Answer 1

Если вы специально хотите потоков на основе решения, вы можете иметь метод, который рекурсивно факторов число:

IntStream factors(int num) { 
    return IntStream.range(2, num) 
     .filter(x -> num % x == 0) 
     .mapToObj(x -> IntStream.concat(IntStream.of(x), factors(num/x))) 
     .findFirst() 
     .orElse(IntStream.of(num)); 
} 

Затем вы можете использовать следующий код, чтобы сделать ваши два списка:

Map<Integer, Integer> f2m = factors(2, num).boxed() 
     .collect(toMap(f -> f, f -> 1, Integer::sum)); // or groupingBy with summingInt(f->1), whichever you prefer 

List<Integer> factors = new ArrayList<>(f2m.keySet()); 
List<Integer> multiplicities = factors.stream().map(f2m::get).collect(toList()); 

Если вы хотите получить более высокую производительность, вы можете передать последний найденный коэффициент в factors и использовать его вместо 2.

Если вы хотите, чтобы фактор лонги, вот версия с некоторыми улучшениями производительности:

static LongStream factors(long lastFactor, long num) { 
    return LongStream.rangeClosed(lastFactor, (long) Math.sqrt(num)) 
      .filter(x -> num % x == 0) 
      .mapToObj(x -> LongStream.concat(LongStream.of(x), factors(x, num/x))) 
      .findFirst() 
      .orElse(LongStream.of(num)); 
} 

Если вы хотите, чтобы результат в отсортированном порядке, вы можете использовать

SortedMap<Long, Integer> f2m = factors(2, num).boxed() 
     .collect(toMap(f -> f, f -> 1, Integer::sum, TreeMap::new)); 

Или, в качестве альтернативы, сохранить Map как было и использовать

List<Long> factors = f2m.keySet().stream().sorted().collect(toList()); 

Answer 2

При факторизации целых чисел, наиболее прибыльными оптимизации, чтобы попытаться делителей до квадратного корня из числа (включительно, напр .: попробуйте факторинг 49). Кроме того, после проверки на 2, вы можете проверить потом только с нечетными номерами.

int num = getPositiveInt(); 
ArrayList<Integer> factors = new ArrayList<>(); 
ArrayList<Integer> multiplicities = new ArrayList<>(); 
int factor = 2; 
int f_delta = 1; // to increase by +1 only once (2 to 3) 
while ((factor*factor)<=num) { 
    int count = 0; 
    while (num % factor == 0) { 
    num /= factor; 
    count++; 
    } 
    if (count > 0) { 
    factors.add(factor); 
    multiplicities.add(count); 
    } 
    factor += f_delta; 
    f_delta = 2; 
} 

Answer 3

После тщательного изучения, я обнаружил, что это огромное улучшение скорости по сравнению с тем, что я опубликовал в вопросе. Единственный более быстрый - это тот, который был отправлен @Misha после изменения их функции factors вместо .rangeClosed(prevFactor, Math.sqrt(num)). Однако this other solution - это самое быстрое решение ... период ... но не использует потоки.

public static Map<Long, Integer> factorize(long num) { //NOW USING LONG 
    Map<Long, Integer> factors = new LinkedHashMap<>(); //NOW USING MAP 
    long lastRemainder = LongStream.rangeClosed(2, (long) Math.sqrt(num)) //NOW USING SQRT 
      .filter(x -> (x== 2||x%2>0)&&(x==3||x%3>0)&&(x==5||x%5>0)) //ADDED THIS 
      .reduce(num, (temp, factor) -> { 
       if (factor <= temp/factor) { //ADDED THIS 
        int count = 0; 
        while (temp % factor == 0) { 
         temp /= factor; 
         count++; 
        } 
        if (count > 0) 
         factors.put(factor, count); 
       } 
       return temp; 
      }); 
    if (lastRemainder != num && lastRemainder > 1) //ADDED THIS 
     factors.put(lastRemainder, 1); 
    return factors; 
} 

Answer 4

Другой вариант, который wo uld полезно, если вы хотите повторно позвонить factorsOf. (Я где-то украл основную идею решета.)

Идея здесь состоит в том, чтобы использовать простые числа как поток, фильтровать факторы и определять их множественность для создания объектов FactorTimes, устанавливающих результат.

public class PrimeFactors { 
    private final int limit = 1_000_000; 
    private BitSet sieve = new BitSet(limit+1); 
    public PrimeFactors(){ 
    sieve.set(2, limit); 
    long count = sieve.stream() 
    .peek(x -> { if((long)x*x < limit) 
        for(int i = x*x; i <= limit; i += x) 
         sieve.clear(i); 
       }) 
    .count(); 
    } 
    public FactorTimes[] factorsOf(int num){ 
    FactorTimes[] fts = sieve.stream() 
    .limit(num/2) 
    .filter(x -> num % x == 0) 
    .mapToObj(x -> { int n = 1; 
         int k = num/x; 
         while(k % x == 0){ k /= x; n++; } 
         return new FactorTimes(x, n); 
        }) 
    .toArray(FactorTimes[]::new); 
    return fts; 
    } 
    public static void main(String[] args){ 
    PrimeFactors pf = new PrimeFactors(); 
    for(FactorTimes ft: pf.factorsOf(4504500)){ 
     System.out.println(ft); 
    } 
    } 
} 

class FactorTimes { 
    private int factor, multiplicity; 
    public FactorTimes(int f, int m) { 
    factor = f; multiplicity = m; 
    } 
    public int getFactor() { return factor; } 
    public int getMultiplicity() { return multiplicity; } 
    public String toString(){ 
    return multiplicity > 1 ? factor + "(" + multiplicity + ")" 
          : Integer.toString(factor); } 
} 

Answer 5

Чтобы генерировать основные факторы, вам необходимо отслеживать несколько состояний. Поэтому Streams не подходят для этой задачи.

Что вы можете сделать, это создать собственный Spliterator, чтобы создать IntStream. Теперь вы способны генерировать массив или группировку операций:

public static IntStream primeFactors(int n) { 
    int characteristics = Spliterator.ORDERED | Spliterator.SORTED | Spliterator.IMMUTABLE | Spliterator.NONNULL; 
    Spliterator.OfInt spliterator = new Spliterators.AbstractIntSpliterator(Long.MAX_VALUE, characteristics) { 
    int val = n; 
    int div = 2; 

    @Override 
    public boolean tryAdvance(IntConsumer action) { 
     while (div <= val) { 
     if (val % div == 0) { 
      action.accept(div); 
      val /= div; 
      return true; 
     } 
     div += div == 2 ? 1 : 2; 
     } 
     return false; 
    } 

    @Override 
    public Comparator<? super Integer> getComparator() { 
     return null; 
    } 
    }; 
    return StreamSupport.intStream(spliterator, false); 
} 

И называют что-то вроде этого:

int n = 40500; 
System.out.println(Arrays.toString(primeFactors(n).toArray())); 
System.out.println(primeFactors(n).boxed().collect(
    Collectors.groupingBy(Function.identity(), Collectors.summingInt(i -> 1))) 
); 

Вы должны получить желаемые результаты:

[2, 2, 3, 3, 3, 3, 5, 5, 5] 
{2=2, 3=4, 5=3}