?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

(no subject)
nyaload
_winnie
Программисткая задачка, её подкинул slobin.
Как решить - пока не знаю, может это я туплю и это очевидно, может нет.

Имеется две функции, которые вычисляют какую-то характеристику потока данных (например максимум, или CRC32-сумму, или минимум, или тп). К сожалению, функции мы переписывать не можем, зато можем дать им любой кэллбек.
Как вычислить обе функции, за один проход по потоку данных? Память константная, поток большой. Если невозможно, то хочется какое-то доказательство на пальцах, почему.

upd: тоже самое другими словами:
Надо найти минимум и максимум в последовательности. Последовательность идёт из большого файла на диске.
Функции минимума и максимума (или суммы, или подсчёта CRC32) уже написаны, или переданым нам как параметр. Надо между ними как-то переключаться, что бы они работали параллельно.

На С++:
Read more...Collapse )

На python: IDataStream - это генератор, Acum1/Acum2 берут на вход генератор.
На Haskell: бесконечный список. И чур не хранить его целиком в памяти! И функции увы уже написаны/переданы как параметр, [Int] -> Int.

С использованием OS-Thread и системных функции вроде CreateFiber и тп - понятно как сделать, можно ли обойтись одним потоком выполения?

upd: в указаных ограничениях, похоже нельзя. Нужна либо бесконечная память, либо OS threads, либо предъявить к функциям Acum дополнительные требования, что бы можно было временно из них выходить ( не фиксировать тип [Int]->Int в Haskell, что бы они были генераторами в Python, что-то вроде AddЕщёData в C++ ).
Можно ещё потребовать что бы Acum была ассоциативна, т.е. Accum(x1, x2, x3, ..., xk, ... xn) = Accum(Accum(x1, x2, x3, .. xk), xk+1 ... xn). Тогда можно разбить списки на блоки, и запускать разные Accum на блоках, а не на списках целиком.