Добрый вечер! Хотел бы небольшую консультацию пожалуйста! Есть некий АДТ

Question

Добрый вечер! Хотел бы небольшую консультацию пожалуйста! Есть некий АДТ

токен, может иметь несколько состояний.
Есть коллекция этих АДТ, пример:

Seq(Foo(), Foo, Spec(" "), Foo(), Spece(" "), Space(" "), Foo())

Моя задача после каждого Spec(" ") добавить Spec("+") НО только если не идёт два или больше Spec(" ") ПОДРЯД. Т.е из примера выше я должен сделать

Seq(Foo(), Foo(), Spec(" "), Spec("+"), Foo(), Spec(" "), Spec(" "), Foo()).

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

Первый алгоритм, это просто перебор этой коллекции, и добавлять после каждого Spec(" ") Spec("+") но только если нету двух или больше Spec(" ") подряд, в реализации данный алгоритм топорный и тяжелой.

Второй алгоритм, это пройти по коллекции и разбирать ее на кусочки, то есть, встречаем Spec(" "), проверяем чтобы не было дальше подряд ещё Spec(" "), отрезаем этот кусок(со с Spec(" ") включительно) и идём дальше, короче говоря что-то типа split для коллекции.

Потом суём все эти кусочки в List, проходимся по нему, в конце каждого кусочка добавляем Spec("+"), и потом собираем кусочки в месте.

Алгоритм вроде как бы, более интересный, НО есть вопрос в производительности. Допусти кусочки у нас будут имутабельные, считаем сколько получиться коллекций с моего простого примера.

Первая и изначальная коллекция, делим на куски получаем уже 3(изначальная и два кусочка) коллекции, потом добавляем это все в лист, и получаем 4 коллекции, потом проходимся по List и добавляем в конец каждого кусочка плюсик(это уже новые коллекции) получается 6 коллекций, а потом, когда собираем все назад, получается ещё одна коллекция(но если собирать через fold например, будет больше), и того 7 коллекций, и это только с двух Spec(" ")... А что если их будет 100? 1000? Мы можем сделать в принципе кусочки мутабельными, и тогда при добавлении плюсика будут оставаться изначальные коллекции. Но их все равно будет не мало.

Скажите что думаете, и спасибо за раннее!

#programming #russian #scala

0

13.11.2018

1 ответов

39 просмотров

sherzod · Accepted Answer

sherzod

Думаю надо пробовать что-то написать

0

14.11.2018

169 похожих чатов

Добрый вечер! Хотел бы небольшую консультацию пожалуйста! Есть некий АДТ

1 ответов

Похожие вопросы