?

Log in

No account? Create an account
nyaload

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

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

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

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

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

На С++:

class IDataStream;

int Acum1(IDataStream *s);
int Acum2(IDataStream *s);

class IDataStream
{
public:
    virtual int GetNext() = 0;
    virtual bool EOF() = 0;
};


// ??????????????????????                                                          //
// мы можем вклинить свой кэллбэк, когда Accum берёт следующее значение из потока  //
class MyWrapper: IDataStream
{
    MyWrapper(IDataStream *wrapped) : m_wrapped(wrapped) {}
    virtual int GetNext() { }     
};
_Winnie C++ Colorizer




На 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 на блоках, а не на списках целиком.


  • 1
Я не совсем понял задание.

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

(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)

Можно код? afaik, возвращаться в функцию из которой мы вышли нельзя, функции посередине получат локальные переменные и retaddr, затёртые случайным мусором


#include <setjmp.h>

jmp_buf  back_to_the_main;
jmp_buf  back_to_g;

#define BACK 1

void g()
{
    if (setjmp(back_to_g) != BACK)
    {
        printf("%d\n", 2);
        longjmp(back_to_the_main, BACK);
    }
    printf("%d\n", 4);
    //just return to the destructed stack....
}


void f()
{
    int i = 0;
    int numbers[5];
    for (i = 0; i < 5; ++i)
        numbers[i] = i*i;
    g();
    for (i = 0; i < 5; ++i)
        printf("%d, ", numbers[i]);
    printf("\n");
}


int main()
{
    if (setjmp(back_to_the_main) != BACK)
    {
        printf("%d\n", 1);
        f();
    }
    else
    {
        printf("%d\n", 3);
        longjmp(back_to_g, BACK);
    }
}




(Deleted comment)
(Deleted comment)
на scheme c call/cc (shift/reset) пойдет?

Наверное не надо тратить время, так как я всё равно не пойму :(

Интересует возможно ли это вообще на одном системном стеке в С++.

(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)
(Deleted comment)
>virtual int GetNext() = 0;

Этой строчки мало. Уточни, как выглядит конец потока данных.
1) Заранее выбранное значение int'а?
2) Особое значение, не входящее int?
Тогда можно переформулировать интерфейс, например, так:
virtual boost::optional<int> GetNext() = 0;
3) Иначе нужны два метода — инкремент и разыменование (MoveNext() и Current в C#; operator ++() и operator *() в C++). Причём MoveNext осуществляет проверку — если вернёт true, то можно разыменовывать перечислитель, если false, то поток закончился.

Мне больше нравится второй вариант.

upd: Добавил bool EOF(). Вообще-то интересней идея, но так как часто без кода идея имеет вид тумана, то уточнил интерфейс.

(Deleted comment)
(Deleted comment)
Я когда-то пытался решить такую задачу. Переформулирую для осознания практической применимости:
Есть два (или n) алгоритма, управляющих виртуальными роботами. Они периодически вызывают методы Мира - типа, посмотреть что вокруг, или дать команду своему роботу.
Задача: сделать так, чтобы при каждом вызове метода Мира любым из алгоритмов он, Мир, мог бы просчитать своё состояние up to момент вызова. Позволяя другому алгоритму _перед этим_ получить свои результаты и ещё что-то вызвать, если у того есть неиспользованное виртуальное время.

То есть, слева виртуальное время, два алгоритма, А и Б:
0: А начинает работать
10: А вызывает World.LookAround()
0: Б начинает работать.
7: Б вызывает World.LookAround()
10: А получает ответ.
11: А вызывает World.MoveTo(bla, bla)
13: Б получает ответ (уже с учётом того, что А два тика как едет куда-то)

... и так далее

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

Я тогда не придумал ничего лучше, как эмулировать continuations тредами. Завтра ещё подумаю, потому что появились мысли про Новые и Улучшенные питоновские генераторы и, может быть, про монады.

(Deleted comment)
красивая задачка. По-моему должна относительно легко решаться с continuation'ами, надо будет подумать и расписать. Вообще сама постановка мне напоминает coroutines.

Если известно, что функции монотонные (как, например, min и max), то возможно простое решение без continuation'ов.

В Haskell, как уже написали, должны быть монады, а не бесконечные списки, чтоб честно было.

Я думаю что на одном потоке так сделать не получится. Так как фукнции accum1 и accum2 обычные, а не генераторы или монады, то на обычном стеке может быть только два варианта:

1) функции вызываются по очереди. Тут понятно что первая засосет весь поток
2) из одной функции (опосредованно) вызывается вторая. Тут соотвественно вторая засосет весь поток.

На одном потоке никак не получается )

Блин, накаркали! Свеженькое:

http://wordaligned.org/articles/sums-and-sums-of-squares ;-)

Нет, задачка посчитать две функции в один проход там не ставится, но зато рассказывается об n разных способах написать fold на плюсах.

... Я превратил его живой вес в атомный ...

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

Думаю, что чисто теоретически, для соблюдения всех условий ты должен хранить полное состояние обеих функций. Для этого нужно либо грабить стек с регистрами, востонавливая в калбеке и передавая управления назад (hand-made threading), либо неуниверсально. :)

Просто в силу того, что всегда можно придумать f и g для которых надо будет именно хранить состояние (хорошо если они к глобальным переменным не лезут).

Потому абcтракция классов-функций рулит, но это и без меня понятно.

Это как "на одной платформе делается". Тут конечно речь идет не о своем трединге, а когда тупо не хватает регистров, то компилятор генерит специальный код, который пишет в память и в регистр это сохраняет.
Вообще конечно решение возможное, но к сожалению пушистег наверное хотит получить что-то менее из уличной магии :)

В питоне на yield ты не столько генератор сам по себе, сколько сопрограмму на трюке с генератором делаешь :)
Ну а будут сопрограммы жить в волокнах (fiber), нитях (thread) или процессах - это мелочи.

По сути, ты или компилятор за тебя превращает монолитный поток управления в (бес)конечный автомат. В точках yield - состояния, код между ними - переходы.
Ну а потом ты двум конечным автоматам скармливаешь одну и ту же последовательность.

Что-то мне подсказывает, что на хаскеле это делается путём переписывания функции в стрелку (а потом превращения двух стрелок - в одну здоровенную стрелку). Врать не буду, потому что эту сторону уличной магии я ещё не осилил.
Твои функции - это катаморфизмы; значит, их можно (попробовать) выразить с помощью foldl' или foldr.
-- допустим, что переписали
accum1 = done1 . foldl' cat1 init1
accum2 = done2 . foldl' cat2 init2

-- accum1 &&& accum2
accum12 = done12 . foldl' cat12 init12 where
  init12 = (init1,init2)
  cat12 (tmp1,tmp2) x = (cat1 tmp1 x, cat2 tmp2 x)
  done12 (tmp1,tmp2) = (done1 tmp1, done2 tmp2)

Если компилятор хаскелла умеет самостоятельно трансформировать морфизм произвольного вида, то и финальный аккорд сможет выполнить.

ага, красивый подход, правда немного не соответствует условию задачи

А каков аргумент этих функций?

> Имеется две функции

Откуда эти функции берут данные? Как я понял, им даётся некий дескриптор, по которому они поштучно вытаскивают элементы потока и считают по ним что им задано. Ну так надо подменить им дескриптор, чтобы вместо read(из_файла) они вызывали твою функцию. Твоя функция должна различать, кто её вызвал; или знать, что каждое данное у неё должны взять два раза.

> Интересует возможно ли это вообще на одном системном стеке в С++.

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

PS: Всё вышенаписанное - IMHO.

  • 1