Как группировать итератор без преобразования его в список в scala?

Предположим, что я хочу groupBy на итераторе, компилятор просит «value groupBy is not a member of Iterator[Int]». Одним из способов было бы преобразование итератора в список, который я хочу избежать. Я хочу сделать groupBy таким образом, что вход Iterator[A] и выход Map[B, Iterator[A]]. Так, что часть итератора загружается только тогда, когда к этой части элемента обращаются, а не к загрузке всего списка в память. Я также знаю возможный набор ключей, поэтому могу сказать, существует ли конкретный ключ.Как группировать итератор без преобразования его в список в scala?

def groupBy(iter: Iterator[A], f: fun(A)->B): Map[B, Iterator[A]] = { 
    ......... 
}

источник

2015-04-03 Arun

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

Например, скажем, у вас есть последовательность 1 2 3 4 5 6 и вы хотите groupBy нечетных и четных чисел:

groupBy(it, v => v % 2 == 0)

Тогда вы могли бы запросить результат либо true и false, чтобы получить итератор. Проблема должна заключаться в том, что вы зацикливаете один из этих двух итераторов до конца, чтобы вы не могли сделать то же самое для другого (поскольку вы не можете сбросить итератор в Scala).

Это было бы выполнимо, если бы элементы были отсортированы в соответствии с тем же правилом, который вы используете в groupBy.

источник

2015-04-03 06:21:01

Я бы подумал, что загружается только часть списка, которая необходима для доступа к самому последнему доступному элементу. Только эта часть будет в памяти. – Arun

@Arun, но какой товар дает вам последний доступный элемент?Как и в моем примере, если у вас есть '1 2 3 4 5 6', если вы' groupBy' и хотите получить все нечетные элементы, которые вам нужны, чтобы перебирать все это, даже через четные числа. Если вы загружаете только самый последний элемент, вы в конечном итоге загрузите четное число, и ваш итератор вернет 'false', хотя впереди могут быть нечетные числа. –

жаль, что я думал, что он загружается только при обращении к определенному элементу. Теоретически предположим, что у меня очень небольшое количество ключей (например, 4), и у меня есть огромный список элементов в итераторе. В идеале, если мы заранее знаем ключи, мне нужно будет только получить доступ к первому вступлению каждого известного ключа для создания соответствующего итератора для каждого ключа. Например (2,2,1,1,1,1,2,2,4,2,3, .......) эта часть списка достаточно, если я знаю, что ключи {1,2, 3,4}. После доступа любого элемента мы повторяем аналогичный процесс для загрузки следующего элемента в каждом итераторе. В вашем примере это крайний случай и его ok – Arun

Одна из возможностей, вы можете конвертировать итератор для просмотра и затем GroupBy, как,

iter.toTraversable.view.groupBy(_.whatever)

источник

2015-04-03 06:26:09

Как это отличается от использования 'toList'? Ну, это лениво, это правда, но, в конце концов, это все равно не загрузит все данные в память? 'toTraversable' сделает' Stream', тогда, когда вы 'groupBy', все равно нужно загрузить все данные в любом случае, верно? –

Извините, я думал, что он загружается только при обращении к определенному элементу. Теоретически предположим, что у меня очень небольшое количество ключей (например, 4), и у меня есть огромный список элементов в итераторе. В идеале, если мы заранее знаем ключи, мне нужно будет только получить доступ к первому вступлению каждого известного ключа для создания соответствующего итератора для каждого ключа. Например (2,2,1,1,1,1,2,2,4,2,3, .......) эта часть списка достаточно, если я знаю, что ключи {1,2, 3,4}. После доступа любого элемента мы повторяем аналогичный процесс для загрузки следующего элемента в каждом итераторе. В вашем примере это крайний случай и все в порядке. – Arun

@Mateusz Dymczyk, я видел, что в документе говорится, что groupBy не пересматривается взглядами, он вынужден, но почему? –

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

Решение является относительно сложным, но хорошее начало некоторые методы из Iterator признака в исходном коде Scala:

partition метод, который использует как метод buffered, чтобы сохранить значение головки в памяти, и две внутренние очереди (lookahead) для каждого из созданных итераторов.
Метод span с также метод buffered и на этот раз уникальная очередь для ведущего итератора.
duplicate способ. Возможно, менее интересно, но мы можем снова наблюдать очередное использование очереди, чтобы сохранить разрыв между двумя созданными итераторами.

В случае groupBy в приведенных выше примерах мы будем иметь переменное число созданных итераторов вместо двух. Если потребуется, я могу попытаться написать этот метод.

Обратите внимание, что вам необходимо заранее знать список ключей. В противном случае вам понадобится пройти (и буферизировать) весь итератор, чтобы собрать разные ключи для создания вашей Карты.

источник

2015-04-03 11:38:13

Как группировать итератор без преобразования его в список в scala?

ответ

Смежные вопросы