Блог

Я читал о последовательностях Котлина и видел, что этот distinct метод является stateful intermediate операцией. Я предполагаю, что он отслеживает состояние, потому что, очевидно, ему нужно отслеживать, какие элементы он только что видел, чтобы иметь возможность удалять дубликаты; а также какой-то код, где-то действительно выполняющий проверку дубликатов, верно ?

Когда я проверил , сколько времени занимает мой код, пока он не используется Sequence.distinct , он 50920 ms выполнялся. Но с distinct операцией это заняло еще меньше времени, 32548 ms . Для меня это не имеет смысла, так как должен быть дополнительный код для проверки на наличие дубликатов.. В чем здесь компромисс и что я пропустил?

Вот код, который я использовал для тестирования, я просто составляю последовательность алфавитов несколько раз, а затем вызываю distinct :

 val alphabet = sequenceOf( "", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9")

fun iterate(digits: Int): Sequence<String> {
    var sequence = alphabet.asSequence()
    for (i in 1 until digits)
        sequence = iterate(sequence)
    return sequence.distinct()    // <--- this is where i add or remove the distinct
}

fun iterate(sequence: Sequence<String>) = sequence {
    sequence.forEach { c1 ->
        alphabet.forEach { c2 ->
            yield("$c1$c2")
        }
    }
}
 

Во время тестирования я занимался :

 iterate(7).forEach(::println)
 

Так возможно ли, что println проверка занимает больше времени, чем проверка дубликатов, так I/O как она всегда тяжелая ? Я совершенно невежествен и немотивирован, поэтому любое объяснение было бы очень ценно.

Редактировать:

Основываясь на cactustictacs ответе, я повторно запустил код , генерируя 7-значные слова, чтобы 11^7 == 19'487'171 сгенерировать общее количество слов (я пробовал 8-значные слова, но я продолжаю получать OutOfMemoryError их каждый раз, когда использовал distinct , вероятно, из-за того, что он отслеживал найденные элементы, поэтому я не могу сравнивать с другими).

Вот результаты (в мс) :

Значит, это тот же код, только с дополнительной distinct() операцией в конце? Да, это должно занять больше времени, так как вы выполняете дополнительную работу, которая не делает ее более эффективной.

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

Возможно, вам понадобится гораздо большая финальная последовательность, чтобы увидеть какую-либо заметную последовательную разницу между запуском distinct или нет!

правка — я пропустил, что вы печатаете каждый элемент в последовательности с очень большими цифрами, в этом случае да, вы правы, это, вероятно, будет узким местом! Вызов distinct() здесь значительно сократит эту работу, потому что способ, которым вы генерируете последовательность, создает много дубликатов, особенно по мере увеличения количества итераций:

 fun main() {
    for (i in 1..5) {
        val results = iterate(i)
        val total = results.count()
        val distinct = results.distinct().count()
        println("$i) total: $total - difference: ${total - distinct}")
    }
}

1) total: 11 - difference: 0
2) total: 121 - difference: 10
3) total: 1331 - difference: 220
4) total: 14641 - difference: 3530
5) total: 161051 - difference: 49940
 

За 5 итераций вы удаляете почти треть результатов! Такая работа, как правило, выполняется быстро, печать на выходе не так уж и много. Попробуйте провести сравнительный анализ каждого этапа (обработка и печать) и посмотрите, каковы их средние значения — поскольку это последовательность, вам нужно будет использовать ее, чтобы просто выполнить шаг «обработка» в одиночку, запуск count() -это легкий способ сделать это. Затем вы можете сравнить это с версией «обработка печать» и посмотреть, сколько накладных расходов добавляет печать

К вашему сведению (в случае, если вы не делаете это в качестве стресс-теста), вы можете избежать distinct вызова, просто выдавая каждую цифру как часть каждой итерации:

 // you don't really gain anything by having this as a sequence (it's slower too),
// but I'm keeping it the same for comparison's sake
val alphabet = (0..9).map(Int::toString).asSequence()

fun iterate(sequence: Sequence<String>) = sequence {
    // combo each item with each element in the sequence (if any)
    // this produces items at least two-digits long
    sequence.forEach { c1 ->
        alphabet.forEach { c2 ->
            yield("$c1$c2")
        }
    }
    // also yield all the single digits
    alphabet.forEach( { yield(it) })
}
 

Таким образом, 1-я итерация просто создает однозначные элементы. Следующий расширяет каждый из них, чтобы создать все двузначные комбинации, и добавляет в них также однозначные элементы. 3-я итерация расширяет каждую из них, создавая все 3-значные и 2-значные комбинации, и добавляет обратно однозначные…

Вы никогда не создаете дубликатов, потому что каждый раунд фактически просто добавляет все возможные расширения текущей последовательности. Использование пустого символа, как вы делаете, усложняет это, потому что каждый раунд добавляет расширенные версии каждого элемента, но также и не расширенные дубликаты всего. Проще просто превратить все элементы длиной x во все возможные элементы длиной x 1, а затем вернуть все элементы с одной цифрой (так как элементы в предыдущей последовательности были расширены до двух цифр).

Я надеюсь, что это не слишком запутанно, я чувствую, что это слишком сложное объяснение. Также этот способ не дает пустой строки как части последовательности (комбинации "" "" ""... ) — если вам нужно, что вы могли бы сделать return sequence.plus("") или что-то в этом роде

При этом я получаю увеличение скорости в 2-3 раза за 5 итераций-это не просто distinct вызов, вы в первую очередь избегаете выполнения повторяющейся работы, а с большим количеством итераций эта неэффективность действительно может увеличиться! Особенно для sequence s, которые эффективны для работы с памятью и позволяют вам останавливаться раньше, но работать намного медленнее, чем iterable s