Немного перебрал
Применение DFS для каждого узла даст в итоге квадратичную сложность, вот

Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, Head Ache, Вы писали:

HA>>for each p in roots
HA>> DFS(p) // это вроде O(N)?

HA>>gc работал бы часами по такому алгоритму

I>Если O(N) так сразу часами ? Когда нужно N элементов освободить, представь, это тоже O(N) и никаких часов не требуется.

По-разному. Может быть хуже O(N) — указатель еще в куче надо найти или где-то еще.
А может быть и O(1), например:

void f()
{
    int x1;
    int x2;
    int x3; // хоть сколько угодно переменных
}  // просто вершина стека сместится на заданное число

или если переменные заданы внутри структуры

Здравствуйте, Head Ache, Вы писали:

HA>Зачем спрашиваешь, наверно и так ответ заранее знаешь
HA>Если ссылка будет жить дольше объекта — будет плохо и никто такой код не пишет.
HA>Если надо контролировать время жизни — использовать интеллектуальные указатели.
HA>Обратите внимание, подход "не плати за то, чем не пользуешься": четко обозначить проблему и решать именно ее.
HA>То есть если не нужны именно интеллектуальные указатели, они и не будут применяться.
HA>Также есть варианты со статической памятью, глубоким копированием, специализированные аллокаторы.
HA>Никто не мешает и сборщик мусора применять, только почему-то непопулярен этот подход.
HA>Ни с gc, ни с каким-либо другим.
Забавно, наверное, потом поддерживать всё это нагромождение разных подходов. Все они в той или иной степени неэффективны, поэтому и взялись за сборщик мусора. Который, конечно, тоже по своему неэффективен, но благо у нас есть выбор. Мне весь этот описанный бардак — то так сошлемся, то сяк, то смарт-поинтеры с самопальными аллокаторами — не нужен.

HA>>>Пример2(классика). Критические секции, когда после Enter() следует гарантировать выполнение Leave()
HA>>>Для C# это настолько сложная проблема, что даже понадобилось вводить новое ключевое слово lock (SyncLock в VB) !
HA>>>(так же как и using для IDisposable)
MM>>Какие-то у тебя проблемы надуманные. Это все такие мелочи: написать lock или try/finally.
HA>Не мелочи, когда надо обеспечивать строгие гарантии самому.
Что-то я не понял, о чем ты. Написать реализацию IDisposable тяжело? Написать using тяжело?

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, gandjustas, Вы писали:

HA>>>gc работал бы часами по такому алгоритму
G>>С чего ты взял? А то что стандартные аллокаторы тоже O(N) причем на каждое выделение памяти, они же не часами работают.
CC>Как же ты утомил!
CC>Хоть раз ты изволишь объяснить что ж это за "стандартные" аллокаторы такие?
Которые используются в Windows, *nix и в большинстве реализаций стандартной библиотеки.
Я тебе говорил про это.

CC>Да ещё и O(N).
Действительно O(N), потому что построены на списке свободных блоков.

Здравствуйте, Head Ache, Вы писали:

HA>Здравствуйте, gandjustas, Вы писали:

G>>Рекурсия, пока в объекте есть ссылки на другие объекты.

HA>Боюсь, что в сложных вариантах с циклами, (т.е. когда собственно и нужен полный dfs),
HA>число итераций может расти с факториальной скоростью.

Счегобы? Там же объекты помечаются. На весь этап mark уходит O(N) от количества живых объектов.

Здравствуйте, Head Ache, Вы писали:

HA>>>gc работал бы часами по такому алгоритму
I>>Если O(N) так сразу часами ? Когда нужно N элементов освободить, представь, это тоже O(N) и никаких часов не требуется.

HA>По-разному. Может быть хуже O(N) — указатель еще в куче надо найти или где-то еще.
HA>А может быть и O(1), например:

И где здесь часы ?

Здравствуйте, Head Ache, Вы писали:


HA>Немного перебрал
HA>Применение DFS для каждого узла даст в итоге квадратичную сложность, вот

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

Здравствуйте, gandjustas, Вы писали:

G>>>С чего ты взял? А то что стандартные аллокаторы тоже O(N) причем на каждое выделение памяти, они же не часами работают.
CC>>Как же ты утомил!
CC>>Хоть раз ты изволишь объяснить что ж это за "стандартные" аллокаторы такие?
G>Которые используются в Windows, *nix и в большинстве реализаций стандартной библиотеки.
Большинство реализаций стандартной библиотеки зовут системный аллокатор. Т.е. своего попросту не имеют.
В *nix используются алгоритмы типа SLAB/SLUB, в которых пулы называются cache.
В WinHeap используется LFH (с висты начиная — принудительно) который тоже на пулах.

CC>>Да ещё и O(N).
G>Действительно O(N), потому что построены на списке свободных блоков.
Ну вот мой ThreadPoolAlloc имеет списки свободных блоков.
Добавить блока в список O(1), Забрать блок из списка O(1).
Т.е. использование списка совсем не обязательно гарантирует O(N).

В современных аллокаторах (как и в .NET GC кстати) выделение блоков маленького размера и выделение блоков большого размера отличаются принципами.
Точно так же есть LOH, в котором аллокацию можно сделать неспешной, ибо редко используется.
Но и там можно использовать технику быстрого поиска подходящего блока путём вноса свободного блока в списки свободных, сгруппированные по диапазонам размера. Т.е. мы за O(1) узнаём что блока именно такого размера точно нет, и надо будет дробить блок из пула бОльшего размера.
Ну а для мелких блоков, уже паверное вообще всеми используются пулы, в которых время поиска блока как правило O(1).

Здравствуйте, gandjustas, Вы писали:

G>Здравствуйте, enji, Вы писали:

E>>Здравствуйте, Ночной Смотрящий, Вы писали:

НС>>>Здравствуйте, enji, Вы писали:

E>>>>Развитость языка — а какие именно возможности языка были бы полезны в этом случае?

НС>>>К примеру, для работы с СОМ-портом можно использовать Reactive Framework. В Дельфи аналог есть? Для асинхронности все тот же Rx или PLinq. В Дельфи аналог последнего есть?

E>>Гм, а зачем? В дельфи есть компонент, у которого есть события — получен символ, переданы данные и т.д. Компонент полностью изолирует порт. Что у него внутрях — я не знаю, может отдельный поток, может порты завершения...

E>>На его основе работа с портом пишется весьма просто.

G>Датыче? напиши-ка прогу, которая читает из порта пакеты, где в первом байте указана длина пакета, а в последующих сам пакет, в конце CRC.
G>После принятия валидного пакета его надо отправить на обработку некоторой функции, при этом порт должен продолжать принимать данные.

G>А потом сравним вариант с Rx на .NET

На дельфи написать не могу — я забросил дельфи года 3 как. Сча пишу на плюсах. С учетом того, что ваша задача для меня типична, у меня выработан вполне удобный самопальный фреймворк для обмена с устройствами. Фреймворк, что характерно, работает как на 8-бит однокристалках под самопальной мини-ос, так и на вин\лин (поверх буст асио).
С учетом этого фреймворка все сводится к примерно вот такой функции:

TCanal::TProcessResult TCanal::processReceivedBytes(uint_fast8_t cnt, byte *src, TViolationType violation)
{    
    while(cnt--)
    {
        recBuf[nextRecBtInd++] = *src++;
        
        if (recBuf[0] < 3)
          nextRecBtInd = 0;         
        
        if (nextRecBtInd > 3 && nextRecBtInd == recBuf[0]) // предполагаем 2-байтное crc младшим байтом  вперед
        {
            uint16_t crc = recBuf[nextRecBtInd-2]  + recBuf[nextRecBtInd-2]*256;
            if (crc == calcValidCRC(recBuf, nextRecBtInd-2))
                return prMessageReceive;
            else            
                nextRecBtInd = 0;            
        }
    }
    return violation.isAny() ? prStopReceive : prContinue;
}

Дальше может быть подключен произвольный физический канал (посл порт, что-нить поверх tcp или udp) и все работает.

Управление выглядит примерно вот так:

CL_line2(Control::lineCommand, LINE_COMMAND)
  enum {s1 = STEP_USER};
  CL_step0
      formCmd1();      
  CL_step
      formCmd2();
    partPostAnswer
      if (...)
        return actionRepeatLine;
  CL_stepN(s1)
      formCmd3();
  CL_step
      formCmd4();
    partAnswer
      if (...)
        return s1;
  CL_step
      if (...)
        formCmd5();
  CL_step
            formCmd6();
CL_end

Здесь на макросах реализовано что-то вроде сопроцедур — процедура прерывается, а затем выполняется начиная с точки прерывания. При этом учитывается "тип блока" — передача, обработка ответа и т.д. Подозреваю, что это — упрощенный аналог вашего Reactive Framework

Здравствуйте, gandjustas, Вы писали:

G>Вполне может решаться проще.
G>http://code.msdn.microsoft.com/RxParsers
G>вот так например

IObservable<StockAlert> alerts = ticks.Parse(parser => 
        from next in parser
        let ups = next.Where(tick => tick.Change > 0)
        let downs = next.Where(tick => tick.Change < 0)
        select (from up in ups.AtLeast(2)
                from down in downs
                where down.Change <= -11
                select new StockAlert(up.ToEnumerable(), down))
               .Or
               (from down in downs.AtLeast(2)
                from up in ups
                where up.Change >= 21
                select new StockAlert(down.ToEnumerable(), up)));

А не могли бы вы вкратце пояснить, что это делает? А то нифига не понятно

Здравствуйте, enji, Вы писали:

G>>А потом сравним вариант с Rx на .NET

Жду вашего решения

Здравствуйте, enji, Вы писали:

E>Здравствуйте, gandjustas, Вы писали:

G>>Здравствуйте, enji, Вы писали:

E>>>Здравствуйте, Ночной Смотрящий, Вы писали:

НС>>>>Здравствуйте, enji, Вы писали:

E>>>>>Развитость языка — а какие именно возможности языка были бы полезны в этом случае?

НС>>>>К примеру, для работы с СОМ-портом можно использовать Reactive Framework. В Дельфи аналог есть? Для асинхронности все тот же Rx или PLinq. В Дельфи аналог последнего есть?

E>>>Гм, а зачем? В дельфи есть компонент, у которого есть события — получен символ, переданы данные и т.д. Компонент полностью изолирует порт. Что у него внутрях — я не знаю, может отдельный поток, может порты завершения...

E>>>На его основе работа с портом пишется весьма просто.

G>>Датыче? напиши-ка прогу, которая читает из порта пакеты, где в первом байте указана длина пакета, а в последующих сам пакет, в конце CRC.
G>>После принятия валидного пакета его надо отправить на обработку некоторой функции, при этом порт должен продолжать принимать данные.

G>>А потом сравним вариант с Rx на .NET

E>На дельфи написать не могу — я забросил дельфи года 3 как.
выше выделено про компонент делфи.

E>Сча пишу на плюсах. С учетом того, что ваша задача для меня типична, у меня выработан вполне удобный самопальный фреймворк для обмена с устройствами. Фреймворк, что характерно, работает как на 8-бит однокристалках под самопальной мини-ос, так и на вин\лин (поверх буст асио).
E>С учетом этого фреймворка все сводится к примерно вот такой функции:
E>

E>TCanal::TProcessResult TCanal::processReceivedBytes(uint_fast8_t cnt, byte *src, TViolationType violation)
E>{    
E>    while(cnt--)
E>    {
E>        recBuf[nextRecBtInd++] = *src++;
        
E>        if (recBuf[0] < 3)
E>          nextRecBtInd = 0;         
        
E>        if (nextRecBtInd > 3 && nextRecBtInd == recBuf[0]) // предполагаем 2-байтное crc младшим байтом  вперед
E>        {
E>            uint16_t crc = recBuf[nextRecBtInd-2]  + recBuf[nextRecBtInd-2]*256;
E>            if (crc == calcValidCRC(recBuf, nextRecBtInd-2))
E>                return prMessageReceive;
E>            else            
E>                nextRecBtInd = 0;            
E>        }
E>    }
E>    return violation.isAny() ? prStopReceive : prContinue;
E>}
E>

Это далеко не самое интересное. Самое интересное как раз "фреймворк", который занимается заполнением буфера, а не как потом буфер обрабатывается.

E>Здесь на макросах реализовано что-то вроде сопроцедур — процедура прерывается, а затем выполняется начиная с точки прерывания. При этом учитывается "тип блока" — передача, обработка ответа и т.д. Подозреваю, что это — упрощенный аналог вашего Reactive Framework
Всетаки разговор про делфи был. Там и макросов то нет.

Здравствуйте, enji, Вы писали:

E>Здравствуйте, gandjustas, Вы писали:

G>>Вполне может решаться проще.
G>>http://code.msdn.microsoft.com/RxParsers
G>>вот так например

E>

E>IObservable<StockAlert> alerts = ticks.Parse(parser => 
E>        from next in parser  //Служебный кусок
E>        let ups = next.Where(tick => tick.Change > 0)  //Разделение потока событий на положительные  
E>        let downs = next.Where(tick => tick.Change < 0)//и отрицательные
E>        select (from up in ups.AtLeast(2) //Если сначала иду как минимум два положительных
E>                from down in downs        //Затем отрицательный
E>                where down.Change <= -11  //Когда у отрицательного изменения <= -11
E>                select new StockAlert(up.ToEnumerable(), down)) //Возвращаем StockAlert
E>               .Or //Или
E>               (from down in downs.AtLeast(2) //Сначала как минимум два отрицательных
E>                from up in ups                //Потом положительный
E>                where up.Change >= 21         //Со значением более 21
E>                select new StockAlert(down.ToEnumerable(), up))); //Возвращаем StockAlert
E>

E>А не могли бы вы вкратце пояснить, что это делает? А то нифига не понятно

А чтобы понимать как оно это делает надо изучать continuation, list и parser монады.

Здравствуйте, Ikemefula, Вы писали:

I>Да, случай интересный, ты представляешь меня секретаршей, рассказываешь про юзеров с одной сиской и одним яйцом, спрашиваешь у меня про пол...
I>

Какие у тебя фантазии. Ты об этом наблюдателям уже рассказал?

Здравствуйте, vladimir.vladimirovich, Вы писали:

VV>Здравствуйте, Ikemefula, Вы писали:

I>>Да, случай интересный, ты представляешь меня секретаршей, рассказываешь про юзеров с одной сиской и одним яйцом, спрашиваешь у меня про пол...
I>>

VV>Какие у тебя фантазии. Ты об этом наблюдателям уже рассказал?

Фантазии это у тебя. Ты единственный, кто представляет юзера как существо с одной сиськой и одним яйцом.

Ты всерьез считаешь, что у тебя все в порядке в головой ?

Ладно бы ты сказал, что юзер это чел с одной рукой, одним кривым пальцем, одним ухом и одним глазом.

Но у тебя почему то сиська и яйцо. Ты что, продавец в сексшопе что ли ?

Здравствуйте, snaphold, Вы писали:

S>Странно...
S>5 лет назад думал, что дни его сочтены. Ан нет.
S>Причины? Много уже написанного крупного софта? И получается он будет жив всегда?

Кто-то тут писал что Delphi медленно работает. Уже месяц пишу интерпретатор языка PHP с нуля на этом языке. Я не преувеличиваю, скорость интерпретатора на уровне оригинального php, ruby и подобных языков. Идите, напишите интерпретатор на C# NET 4.0 даже, настоящий интерпретатор, без зависимости фреймворка. Поддержка freepascal и lazarus, а значит кроссплатформенность. А что-то такое Mono, компания Novell, которая его разрабатывает распродается по частям, так кто умирает? Скорее .NET как платформа умрет раньше из-за политики MS, а вот Java будет жить.

Кстати, вот мега-интерпретатор написанные на pascal'e, исходники открыты (MIT): http://code.google.com/p/orionphp/

Здравствуйте, dim-s, Вы писали:

DS>Здравствуйте, snaphold, Вы писали:

S>>Странно...
S>>5 лет назад думал, что дни его сочтены. Ан нет.
S>>Причины? Много уже написанного крупного софта? И получается он будет жив всегда?

DS>Кто-то тут писал что Delphi медленно работает. Уже месяц пишу интерпретатор языка PHP с нуля на этом языке. Я не преувеличиваю, скорость интерпретатора на уровне оригинального php, ruby и подобных языков. Идите, напишите интерпретатор на C# NET 4.0 даже, настоящий интерпретатор, без зависимости фреймворка.
А ты Iron Ruby и Iron Python видел? Они какбы быстрее ruby и некоторых интерпретаторов python работают.

DS>Поддержка freepascal и lazarus, а значит кроссплатформенность.
Круто, и кому оно нафиг надо?
Обычно кроссплатформенность ради кроссплатформенности никого не интересует.

DS>А что-то такое Mono, компания Novell, которая его разрабатывает распродается по частям, так кто умирает?
Да ты не переживай, где сейчас borland? а inprise? а codegear? кто сейчас delphi занимается?

DS>Скорее .NET как платформа умрет раньше из-за политики MS, а вот Java будет жить.
А вот практика показывает обратное. Особенно в свете недавнего отказа apple саппортить java на маках.

Здравствуйте, gandjustas, Вы писали:

DS>>А что-то такое Mono, компания Novell, которая его разрабатывает распродается по частям, так кто умирает?
G>Да ты не переживай, где сейчас borland? а inprise? а codegear? кто сейчас delphi занимается?

Mono таки подохнет или скукожытся. Сейчас появляется слишком много девайсов не на вындоусе и на которых сильверлайта нет, соответсвенно ждать чуда крайне странно, особенно с проникновением html5.

Микрософт просрала свой сильверлайт, когда просрала рынки браузеров, телефонов, плейеров, таблеток.

DS>>Скорее .NET как платформа умрет раньше из-за политики MS, а вот Java будет жить.
G>А вот практика показывает обратное. Особенно в свете недавнего отказа apple саппортить java на маках.

Дотнет вряд ли умрет, но вот особых успехов ждать не приходится.

Apple отказалась Джаву суппортить, так есть Оракл, который этим скорее всего займется и поверь это будет намного лучше — свято место пусто не бывает.

Здравствуйте, gandjustas, Вы писали:

g> DS>Поддержка freepascal и lazarus, а значит кроссплатформенность.

g> Круто, и кому оно нафиг надо?
g> Обычно кроссплатформенность ради кроссплатформенности никого не интересует.

Линукс идет в массы (да-да, я сам видел), Маки цветут пышным цветом Ты не знал?

g> Да ты не переживай, где сейчас borland? а inprise? а codegear? кто сейчас delphi занимается?

CodeGear сейчас в составе Embarcadero, работают над Delphi (в том числе и кроссплатформенной). Порадуйся.

Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, gandjustas, Вы писали:

DS>>>А что-то такое Mono, компания Novell, которая его разрабатывает распродается по частям, так кто умирает?
G>>Да ты не переживай, где сейчас borland? а inprise? а codegear? кто сейчас delphi занимается?

I>Mono таки подохнет или скукожытся. Сейчас появляется слишком много девайсов не на вындоусе и на которых сильверлайта нет, соответсвенно ждать чуда крайне странно, особенно с проникновением html5.
Ниче не пойму, причем тут моно и silverlight?

I>Микрософт просрала свой сильверлайт, когда просрала рынки браузеров, телефонов, плейеров, таблеток.
Логика в отпуске...

DS>>>Скорее .NET как платформа умрет раньше из-за политики MS, а вот Java будет жить.
G>>А вот практика показывает обратное. Особенно в свете недавнего отказа apple саппортить java на маках.

I>Дотнет вряд ли умрет, но вот особых успехов ждать не приходится.

I>Apple отказалась Джаву суппортить, так есть Оракл, который этим скорее всего займется и поверь это будет намного лучше — свято место пусто не бывает.

Верующий блин