Я реализовал Решето Эратосфена в Котлине для генерации простых чисел. Я заметил проблему, из-за которой вторая версия моего кода работает неправильно, и недоумеваю, почему в выводе отсутствует цифра 4.
Вот код, который работает правильно:
val primes: Sequence<Int> = sequence {
var numbers = generateSequence(2) { it + 1 }
Log.d("testsss", "Initial numbers: ${numbers.take(10).toList()}") // Initial numbers
while (true) {
val prime = numbers.first()
Log.d("testsss", "Current prime: $prime")
yield(prime)
numbers = numbers.drop(1).filter { it % prime != 0 }
Log.d("testsss", "After filtering with prime $prime: ${numbers.take(10).toList()}") // After filtering
}
}
val primesList = primes.take(10).toList()
Log.d("testsss", "Final primes: $primesList")
println(primesList)
Логи рабочего кода следующие:
Initial numbers: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Current prime: 2
After filtering with prime 2: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
Current prime: 3
After filtering with prime 3: [5, 7, 11, 13, 17, 19, 23, 25, 29, 31]
Current prime: 5
After filtering with prime 5: [7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
Current prime: 7
After filtering with prime 7: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
Current prime: 11
After filtering with prime 11: [13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Current prime: 13
After filtering with prime 13: [17, 19, 23, 29, 31, 37, 41, 43, 47, 53]
Current prime: 17
After filtering with prime 17: [19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
Current prime: 19
After filtering with prime 19: [23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
Current prime: 23
After filtering with prime 23: [29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
Current prime: 29
Final primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Теперь вот код, который работает неправильно:
val primes: Sequence<Int> = sequence {
var numbers = generateSequence(2) { it + 1 }
Log.d("testsss", "Initial numbers: ${numbers.take(10).toList()}") // Initial numbers
var prime: Int
while (true) {
prime = numbers.first()
Log.d("testsss", "Current prime: $prime")
yield(prime)
numbers = numbers.drop(1).filter { it % prime != 0 }
Log.d("testsss", "After filtering with prime $prime: ${numbers.take(10).toList()}") // After filtering
}
}
val primesList = primes.take(10).toList()
Log.d("testsss", "Final primes: $primesList")
println(primesList)
Журналы проблемного кода:
Initial numbers: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Current prime: 2
After filtering with prime 2: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
Current prime: 3
After filtering with prime 3: [5, 7, 8, 10, 11, 13, 14, 16, 17, 19]
Current prime: 5
After filtering with prime 5: [6, 7, 8, 9, 11, 12, 13, 14, 16, 17]
Current prime: 6
After filtering with prime 6: [7, 8, 9, 10, 11, 13, 14, 15, 16, 17]
Current prime: 7
After filtering with prime 7: [8, 9, 10, 11, 12, 13, 15, 16, 17, 18]
Current prime: 8
After filtering with prime 8: [9, 10, 11, 12, 13, 14, 15, 17, 18, 19]
Current prime: 9
After filtering with prime 9: [10, 11, 12, 13, 14, 15, 16, 17, 19, 20]
Current prime: 10
After filtering with prime 10: [11, 12, 13, 14, 15, 16, 17, 18, 19, 21]
Current prime: 11
After filtering with prime 11: [12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
Current prime: 12
Final primes: [2, 3, 5, 6, 7, 8, 9, 10, 11, 12]
Я понимаю, что из-за ленивой оценки последовательностей Kotlin часть фильтра ссылается на неправильные простые значения. Однако если ленивая оценка фильтра происходит для всех простых чисел, то должно появиться 4. Если фильтр был применен правильно для простого числа = 2, последующие числа, кратные 2, например 6, 8, 10 и 12, не должны появляться в результатах. Какую ошибку я могу допустить в своем понимании?
Проблема здесь:
numbers.drop(1).filter { it % prime != 0 }
Лямбда (выражение в фигурных скобках) выполняется только тогда, когда к последовательности применяется оператор терминала, т. е. first()
вызывается на следующей итерации цикла while. Чтобы впоследствии Kotlin мог выполнить лямбду, он фиксирует все используемые переменные. В данном случае это prime
. Примечание. Записывается переменная, а не ее значение.
Для каждой итерации цикла while применяется еще один filter
(т. е. для каждого простого числа). Итак, существует несколько лямбд, каждая из которых захватывает prime
. Однако это одна и та же переменная для всех захватов. Когда все фильтры выполняются, все они используют текущее состояние prime
, поэтому все они будут фильтровать одно и то же значение:
В начале третьей итерации prime
вызывается 3
и first()
. Теперь все фильтры выполнены. На данный момент на numbers
есть два фильтра:
filter { it % prime != 0 }
filter { it % prime != 0 }
Первый применялся, когда prime
было 2
, второй — когда 3
. Однако это не имеет значения, поскольку берется текущее значение prime
, а не то, которое было при определении фильтра. И эта ценность сейчас 3
. Таким образом, один и тот же фильтр выполняется дважды, а предполагаемый фильтр для it % 2
не возникает, поэтому 4
никогда не фильтруется.
В вашем первом примере все по-другому: каждая итерация цикла while имеет свою собственную переменную prime
, поэтому захват лямбды фильтра каждый раз фиксирует другую переменную, которая никогда не изменится. Когда в конечном итоге выполняются несколько фильтров, каждый из них использует свою собственную переменную prime
, поэтому каждый из них будет фильтровать свое значение, что приведет к ожидаемому результату.
[вторые] числа: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 простые числа: 2, 3 После отбрасывания 3: числа: 4, 5, 6, 7, 8, 9, 10, 11 , 12, 13 Фильтр с простым = 3: числа: 4, 5, 7, 8, 10, 11, 13, 14, 16, 17 [третьи] числа: 4, 5, 7, 8, 10, 11, 13, 14, 16, 17 простых чисел: 2, 3, 4??????? Следуя этой логике, простые числа будут включать 4, что противоречит окончательным неправильным выводам 2, 3, 5, 6, 7, 8, 9, 10, 11, 12. Где может быть ошибка? Есть ли ошибка в моих расчетах или я неправильно понял ваше объяснение? Спасибо!
Спасибо за ваш ценный ответ. Поскольку я не очень хорошо владею английским языком, я воспользовался переводчиком как для своего вопроса, так и для этого комментария. Приношу извинения за возможные недостатки и прошу вашего понимания. Основываясь на вашей идее, вы упомянули, что фильтрация работает правильно, начиная с того момента, когда простое число равно 3. Однако, когда я рассчитал следующие шаги, все кажется другим: [первые] числа: 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11 простые числа: 2 После удаления 2: числа: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 Фильтр с простым числом = 2 не работает (из-за ленивой оценки)