Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
PD>>>Что значит сам себя ? Ждет один поток сигнала от другого. И без ожидания написать многопоточный код , вообще-то, нельзя, просто в силу наличия общих модифицируемых данных. S>>Вот в силу наличия этих данных императив и сливает за счет ожидания.
PD>Я чего-то не понял. Кто мне мешает в императиве иметь неизменяемые данные и не ждать ? Просто это редкий случай.
Вот-вот.
PD>>>А если ты хочешь сказать, что можно от них избавиться, перейдя к иммутабельным данным, то это применимо очень и очень не всегда. Для дерева ты это сделаешь, проиграв в быстродействии, ладно. А для файла на диске ? Его-то не сдублируешь и копию не сделаешь. S>>Разве нельзя сделать копию файла?
PD>А нельзя, допустим. Вот у меня модифицируется разными потоками файл размером в 1 Гб. Что, копию на каждое изменение байта будем делать ?
По поводу файлов у ФП отдельная философия. Любой ввод-вывод относится к взаимодействию с "внешним миром" где чистота не требуется. Так что на каждое изменение копирования файла не будет, если специально этим не озадачиться.
S>>Дык причем тут файл-то, если речь идет о распараллеливании? Обычно когда распараллеливают, имеют цель выполнить быстрее счет, а не записать быстрее в файл. Обращение к диску это не CPU-емкие операции.
PD>Ну тут ты меня просто удивил. Почитай иные форумы, там сплошь и рядом задача распараллеливания с записью в файл. Разные потоки , например, независимо ведут операции, а писать надо в один и тот же файл. А операции счета я и так могу вести независимо и ничего не ждать, если они не работают с общими данными.
С файлами у ФП дела обстоят не хуже чем в императивном мире.
Здравствуйте, samius, Вы писали:
PD>>Я чего-то не понял. Кто мне мешает в императиве иметь неизменяемые данные и не ждать ? Просто это редкий случай. S>Вот-вот.
Но я могу сделать это. Просто не надо. И неудобно к тому же.
S>По поводу файлов у ФП отдельная философия. Любой ввод-вывод относится к взаимодействию с "внешним миром" где чистота не требуется. Так что на каждое изменение копирования файла не будет, если специально этим не озадачиться.
Надеюсь, что не будет
S>С файлами у ФП дела обстоят не хуже чем в императивном мире.
При том что иммутабельное заполнение дерева в 3 и более раз короче, оно во столько же раз проигрывает по производительности императивному на миллионе вставок.
Можно сказать паритет
Здравствуйте, Pavel Dvorkin, Вы писали:
VD>>Это вопрос взглядов на алгоритмы.
PD>Я бы так сказал — это вопрос алгоритма. Поиск в BST, например, этого совсем не требует.
Нет. Именно взглядов, так как любой алгоритм можно написать по разному.
PD>Хм... Ну а доведись тебе все же ее писать (алгоритм-то стандартный, школьный, можно сказать) — что напишешь ?
Доведись мне ее писать (а мне доводилось и не раз) я бы такой метод не добавил. Для справки в том же Dictionary<K, V> для оптимизации паттерна "поиск и вставка элемента если он не найден" используется пара методов TryGetValue и Add. Действия тоже императивные, но тем не менее обледенения двух действий в одно не происходит.
VD>>Но могу сказать, что ты мыслишь одной записью (так скажем). Ты не думаешь в терминах преобразований, а ФП рассчитан как раз на такое мышление.
PD>В общем-то верно. Добавляется одна запись. Но тогда ФП не есть замена императивному коду, а только дополнение. Так ?
Не так. ФП — это альтернативный стиль. Он может быть не всегда эффективным, но за то почти всегда дает заметный выигрышь в объеме и понятности кода.
Пойми простую истину. Твоя мысль действует на более низком уровне нежели мысль того кто пишет функциональный код. Ты думаешь как вставить один элемент в процессе перебора других и возможно еще каких-то там условиях. А функциональное мышление подразумевает мыслить только об исходном наборе данных и преобразованном. В нем нет место одной записи. Там (как и в современных базах данных) мышление ведется на уровне наборов данных (назовем их резалт-сетами).
PD>Вот смотри. Мы тут с samius и Dufrenite пообсуждали деревья, и решение для всякого поиска они предложили на LinQ. Теперь представь себе, что есть у меня BST. Откуда взялось — не важно, но в данный момент сформировано окончательно и изменениям не подлежит (это мне так кажется). Я беру их код с поиском на LinQ и вставляю к себе. Все на ура. И тут выясняется, что я кое-что не учел, и если поиск неудачен, то надо этот ненайденный ключ вставить в BST. Что делать-то ?
PD> Выбросить весь код и переписать в императивном стиле ?
Одно из двух. Или ты просто вставишь нужный элемент в императивном стиле (смешав его с функцональным кодом), или будешь мыслить в терминах преобразования коллекций где не нужно вставлять элементы в старую коллекцию, так как результат каждой операции — это новая коллекция.
Вот смотри. В Map.n находится реализация функционального Map-а (ассоциативного массива построенного на базе дерева). А вот пример его использования:
Обрати внимания, что практически все действия возвращают новый map который можно дальше обрабатывать функционально (в том числе с помощью линка).
PD>Влад, я думаю, не стоит опять начинать дискуссию насчет объемов данных и осмысленности копирования, мы это уже не раз обсуждали, без толку. Но хочу отметить, что в моем примере чуть выше это просто не пройдет.
Обсуждать и правда бессмысленно, так как все идет по кругу. Про твой пример я уже много раз говорил. Так что откланиваюсь.
PD>Ну не предлагаешь же ты скопировать все BST ради вставки одного элемента — это же чепуха совсем получится! Да и как это сделать — все равно же вставлять придется ?
На это я очередной раз отвечу тебе — учи мат.часть. Есть функциональные структуры данных которые не приводят к полному копированию элементов, но при этом порождают новые копии коллекций. Неизменяемость позволяет копировать не копируя. Вот такой вот парадокс. С хэш-таблицей такое не пройдет (а с деревом, за просто), но и с ней можно порождать итераторы которые имеют копеечную стоимость.
PD>Побойся бога! Это один из классических алгоритмов!
Точнее будет сказать — доисторических.
PD>Более того, никакого другого способа строить BST я не знаю, его просто нет.
BST — это вообще что?
PD>Вот это я так и понимаю. Но мой вопрос остается. Сформулирую его точно. PD>Мне надо работать с BST. Делать BST буду сам
PD>class TreeElem { PD> int key; PD> TreeElem Left, Right; PD>}
PD>Операция, в сущности одна — SearchAndInsert. Иногда только Search, то есть вместо вставки вернуть null, если не найдено.
PD>LinQ не пойдет ? Да или нет ?
Как ты сам уже говорил. Повторяться тут бессмысленно. Не хочешь понимать, не понимай.
PD>>>Хм... Ну ладно. Хотя вроде как выносить мелкие алгоритмы в отдельные функции мы и так умели давно. И даже передавать им в качестве параметров иные функции, хоть и не лямбды.
VD>>Ну, значит ты давно пользовался ФП не подозревая об этом. Хотя более правдоподобным выглядит предположение о том, что ты преувеличиваешь.
PD>Что я преувеличиваю ? Вспомни нелюбимый тобой Win32, там функций с callback параметрами полным-полно. А это даже не С++, а чистый С.
Вот это и преувеличиваешь. Колбэки имеют примерно столько же общего с ФВП, как ассемблер с ООП.
Ну, и твоя настойчивость в вопросе возни с отдельными элементами четко показывает, что абстрагировать мелкие операции ты не умеешь и каждый раз программируешь их на самом нижнем (снова и снова).
VD>>Функцию ты может и мог передать, но без замыканий толку от этого не много. Ведь для вынесения алгоритма уровня цикла в отдельную функцию нужно в эту функцию передавать контекст вычислений. А без замыканий это сделать невозможно.
PD>Ну не знаю.
Так познакомься. Там делов то.
PD>Может, мы о разных вещах говорим.
Ага, о разных. Ознакомься.
PD>>>ИМХО все же дерево — это дерево, а не последовательность. Линейный и разветвленные структуры — это все же не одно и то же, принципиально. Так следующим шагом ты и граф в последовательность превратишь Конечно, я говорю о самой структуре, а не о результате ее сериализации.
VD>>Ну, ты уж как-то давай сам решай. Или ты задаешь вопросы и получаешь ответы, или ты уже сам все решил, но тогда не стоит задавать вопросы.
PD>Опять ты на свой тон сбиваешься.
Какой тон? Ты задал вопрос, и вместо того чтобы разобраться в том, что тебе ответили начал снова гнуть свою линию. Хочешь просто поспорить, так не задавай вопросы, а делай утверждения. А уж если задал вопрос, так будь добр не спорить, а осмысливать ответы.
PD> Я не задаю вопросы
что?
PD>и не получаю ответы, я веду дискуссию, и в ней могу высказать свое мнение, тем более, что здесь речь идет не о LinQ, которого я не знаю, а о структурах данных — разделе, где у меня есть некоторые основания высказывать свое мнение
Да дискутируй сколько влезет. Только без меня. Я не вижу в себе сил тебя переубедить. А тратить время впустую не хочу. Ты задал вопрос, я на него ответил. Не нравится ответ — твои проблемы.
VD>>Твое ИМПХО базируется на старых привычках.
PD>Если речь идет о дереве — то оно базируется все же на концепциях структур данных, которые опять же ИМХО ни от чего не зависят, ибо базис.
Ну, ссылку на функциональное дерево я тебе дал. Погляди на досуге его интерфейс. Будешь удивлен но он практически аналогичен линку.
>>У меня было тоже самое, но я сумел перестроиться. Попробуй и ты. Не выйдет, значит и дальше ничего в линке не будешь видеть. В принципе не проблема. На циклах тоже можно программировать. Несколько медленнее конечно, но не смертельно.
PD>Да никакой проблемы нет.
Ну и славно.
PD> Для моих задач LinQ совершенно неуместен,
Не буду тебя разубеждать. Чем дольше ты пишешь софт и чем его тяжелее поддерживать тем лучше конкурентам. Главное постарайся не убеждать учеников в этом.
PD> и я его использовать не буду, там скорость критична. Мне просто интересно, с чего вы все так на него набросились при всех его недостатках. Вот и пытаюсь разобраться, что он может, а что нет. Из чисто познавательских целей.
Я за других не скажу. Скажу за себя. Для меня критична скорость разработки и простота сопровождения. Разумное использование ФП в целом и линка в частности позволяет добиться этого. Скорость для меня тоже критична, но я как-то научился добиваться приемлемой скорости используя ФП (где возможно) и ИП (где необходимо).
Я не фанат ни ФП, ни ИП ни чего бы то ни было другого. Я фанат комфорта и удобства. По сему в меру использую все новое что смог осознать и что дает реальный толк.
Кстати, в мире ФП есть и другие красивые решения. Например, алгебраические типы и сопоставление с образцом. В некоторых задачах позволяет координально упростить решение задачи.
Ну, а для того чтобы скорость была высокой и при этом решение не страдало от переусложненности я стараюсь применять МП. Ведь сгенерировать оптимальное решение по вполне простому и декларативному описанию намного легче чем выгадывать такты на каждой операции усложняя при этом свой код до безобразия.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А мне не по душе, когда я вижу код, который мог бы работать быстрее, думая о том парне, которому придется с этой программой работать
Поверьте человеку, сотню раз наступившему на грабли. Если с самого начала не заложить в систему максимальную гибкость и модифицируемость, можно увидеть её благополучную кончину ещё до рождения. Грошовые оптимизации на начальном этапе действительно приводят к масштабным переписываниям кода ближе к концу проекта.
Я не имею в виду конкретно способы обхода дерева, эти вещи в принципе тривиальны. Плох сам принцип. Преждевременная оптимизация зло — доказано теорией и проверено на практике.
Здравствуйте, vdimas, Вы писали:
V>Угу, хотел добавить, что при любой рекурсии итераторов динамически создается их цепочка длиной в глубину рекурсии (обсуждали это здесь еще в 2005-м году), и затраты на переход к след. элементу зависят от длины цепочки.
Я не присутствовал на этом обсуждении, поэтому пришлось открывать данный факт самостоятельно.
Здравствуйте, Dufrenite, Вы писали:
D>Я не имею в виду конкретно способы обхода дерева, эти вещи в принципе тривиальны. Плох сам принцип. Преждевременная оптимизация зло — доказано теорией и проверено на практике.
С другой стороны, чем позже архитектура начинает учитывать некоторые особенности задачи, тем менее приспособленной она становится для внесения соответствующих изменений. Среди таких особенностей легко могут оказаться проблемы производительности и тогда теория окажется недоказанной, а практика непроверенной.
Я не защищаю Дворкина, у него ковыряние в битах — это игрушка, которую он не отдаст никому. Но приложений, страдающих от недооптимизаций ничуть не меньше, чем пострадавших от излишней оптимизации.
Если нам не помогут, то мы тоже никого не пощадим.
Здравствуйте, Dufrenite, Вы писали:
D>Плох сам принцип. Преждевременная оптимизация зло — доказано теорией и проверено на практике.
Преждевременная пессимизация (например, использование для поиска пробега по списку вместо словаря или бинарного поиска) это тоже зло, ничуть не меньшее чем преждевременная оптимизация.
Боже, зачем же так сложно и длинно ? Да еще ArgumentNullException, которого тут вообще не должно быть!
class Node<T>
{
public Node(T value, Node<T> left, Node<T> right)
{
Value = value;
Left = left;
Right = right;
}
public T Value { get; set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
// мне пришлось заменить свойства на поля, так как свойства нельзя передавать по ref
// public их делать совсем не обязательно, но лень было возиться :-)
// так что в моем коде не используются твои Left и Right, а используются мои left и rightpublic Node<T> left;
public Node<T> right;
}
static class Program
{
static Node<T> Insert<T>(this Node<T> tree, T value)
{
if (tree == null)
return new Node<T>(value, null, null);
var eq = Comparer<T>.Default.Compare(tree.Value, value);
if (eq == 0)
return tree;
return eq > 0
? new Node<T>(tree.Value, Insert(tree.Left, value), tree.Right)
: new Node<T>(tree.Value, tree.Left, Insert(tree.Right, value));
}
static bool SearchAndInsert<T>(this Node<T> tree, T value)
{
if (tree == null)
throw new ArgumentNullException("tree");
var eq = Comparer<T>.Default.Compare(tree.Value, value);
if (eq == 0)
return true;
if (eq > 0)
{
if (tree.Left != null)
SearchAndInsert(tree.Left, value);
else
tree.Left = new Node<T>(value, null, null);
}
else
{
if (tree.Right != null)
SearchAndInsert(tree.Right, value);
else
tree.Right = new Node<T>(value, null, null);
}
return false;
}
// а вот и моя версия - чистая калька с С++
// DPL - это я (Дворкин Павел Лазаревич :-)
// как видишь, она ничуть не сложнее твоей LinQ-овской, скорее проще :-)static bool DPLSearchAndInsert<T>(ref Node<T> tree, T value)
{
if (tree == null)
{
tree = new Node<T>(value, null, null);
return false;
}
var eq = Comparer<T>.Default.Compare(tree.Value, value);
if (eq == 0)
return true;
if (eq > 0)
return DPLSearchAndInsert(ref tree.left, value);
else
return DPLSearchAndInsert(ref tree.right, value);
}
static Node<T> BuildTree<T>(IEnumerable<T> data)
{
return data.Aggregate(default(Node<T>), Insert);
}
static Node<T> BuildTreeM<T>(IEnumerable<T> data)
{
var iter = data.GetEnumerator();
if (!iter.MoveNext())
{
throw new ArgumentException();
}
var result = new Node<T>(iter.Current, null, null);
while (iter.MoveNext())
SearchAndInsert(result, iter.Current);
return result;
}
// это мои построительstatic Node<T> DPLBuildTreeM<T>(IEnumerable<T> data)
{
var iter = data.GetEnumerator();
if (!iter.MoveNext())
{
throw new ArgumentException();
}
// пришлось заменить var на Node<T>, так как var нельзя присвоить null
Node<T> result = null;
while (iter.MoveNext())
DPLSearchAndInsert(ref result, iter.Current);
return result;
}
static void Main()
{
var buffer = Enumerable.Range(0, 1000000).ToArray();
var rnd = new Random();
for (int i = 0; i < buffer.Length; i++)
{
int j = rnd.Next(buffer.Length);
var tmp = buffer[i];
buffer[i] = buffer[j];
buffer[j] = tmp;
}
Test(() => BuildTree(buffer), "Immutable insert");
Test(() => BuildTreeM(buffer), "SearchAndReplace");
Test(() => DPLBuildTreeM(buffer), "DPLSearchAndReplace");
Console.ReadKey();
}
static void Test(Action action, string name)
{
Console.WriteLine();
Console.WriteLine(name);
var sw = Stopwatch.StartNew();
action();
Console.WriteLine(sw.Elapsed);
}
}
S>При том что иммутабельное заполнение дерева в 3 и более раз короче, оно во столько же раз проигрывает по производительности императивному на миллионе вставок.
Immutable insert
00:00:09.9648256
SearchAndReplace
00:00:03.2450794
DPLSearchAndReplace
00:00:02.8752006
S>Можно сказать паритет
Нет, 2.5:0.5 в мою пользу. Я сделал эту DPLSearchAndInsert столь же простой, как твоя, и даже проще, а выигрыш по времени в 3 раза и ни одного лишнего new. Так что я выиграл и по памяти, и по времени, а вот по простоте кода — в лучшем случае паритет
P.S. А вот машина у тебя получше раза в 2. Если не секрет, какой процессор ? У меня Athlon Dual 4200+
Здравствуйте, Dufrenite, Вы писали:
D>Поверьте человеку, сотню раз наступившему на грабли. Если с самого начала не заложить в систему максимальную гибкость и модифицируемость, можно увидеть её благополучную кончину ещё до рождения. Грошовые оптимизации на начальном этапе действительно приводят к масштабным переписываниям кода ближе к концу проекта.
Не поверю. Грошовые оптимизации меня мало интересуют. А вот неправильный выбор структур данных и алгоритмов в задачах, где скорость критична, приведет к созданию продукта, который будет работать, но окажется никому не нужен.
D>Я не имею в виду конкретно способы обхода дерева, эти вещи в принципе тривиальны. Плох сам принцип. Преждевременная оптимизация зло — доказано теорией и проверено на практике.
Смотря что под ней понимать. Преждевременное выжимание тактов в цикле путем трюков — да, согласен. Но предварительный анализ задачи, оценка ее временнОй и ресурсной зависимости , выбор оптимального алгоритма и структур данных — это именно то, что аналитик должен сделать до того, как будет написана хоть одна строчка кода. Если, конечно, задача не тривиальна.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
PD>Боже, зачем же так сложно и длинно ? Да еще ArgumentNullException, которого тут вообще не должно быть!
Поспешил
PD>// мне пришлось заменить свойства на поля, так как свойства нельзя передавать по ref PD>// public их делать совсем не обязательно, но лень было возиться PD>// так что в моем коде не используются твои Left и Right, а используются мои left и right
По поводу ref у меня пунктик, да и у много кого тоже. Framework Design Guidlines его тоже не рекоммендуют. Хотя, как средство оптимизации он хорош.
Действительно, если метод вставки затолкать в Node<T>, то поля делать публичными не обязательно.
PD>// а вот и моя версия — чистая калька с С++ PD>// DPL — это я (Дворкин Павел Лазаревич PD>// как видишь, она ничуть не сложнее твоей LinQ-овской, скорее проще
Проще — нет, ref-ы ее не делают проще. Но визуально меньше кода — это да.
S>>При том что иммутабельное заполнение дерева в 3 и более раз короче, оно во столько же раз проигрывает по S>>Можно сказать паритет
PD>Нет, 2.5:0.5 в мою пользу. Я сделал эту DPLSearchAndInsert столь же простой, как твоя, и даже проще, а выигрыш по времени в 3 раза и ни одного лишнего new. Так что я выиграл и по памяти, и по времени, а вот по простоте кода — в лучшем случае паритет
По времени и памяти — соглашусь.
По простоте кода — нет. Считаем кол-во непустых линий методов вставки и построения дерева:
Моих — 9
Ваших — 21 (если выкинуть скобки, то 19)
+ ref. Лично у меня с ним проблем нет, но он не делает код проще — это точно.
PD>P.S. А вот машина у тебя получше раза в 2. Если не секрет, какой процессор ? У меня Athlon Dual 4200+
Intel Core 2 Duo E6600
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
S>По поводу ref у меня пунктик, да и у много кого тоже.
А у меня нет пунктика такого. Я к этому (на Паскале еще — помнишь передачу по var ?) привык. По крайней мере я решительно не вижу, что можно возразить против его применеия в данном конкретном случае.
PD>>Нет, 2.5:0.5 в мою пользу. Я сделал эту DPLSearchAndInsert столь же простой, как твоя, и даже проще, а выигрыш по времени в 3 раза и ни одного лишнего new. Так что я выиграл и по памяти, и по времени, а вот по простоте кода — в лучшем случае паритет S>По времени и памяти — соглашусь. S>По простоте кода — нет. Считаем кол-во непустых линий методов вставки и построения дерева: S>Моих — 9 S>Ваших — 21 (если выкинуть скобки, то 19)
Можно на "ты", как это здесь принято
Ну если суммировать с кодом построения, то да. Но он сам по себе. В С++ не было бы у меня никакого Enumerator и Enumerable и тем более ArgumentException (который здесь вообще-то ни при чем. И чего вы все любите так искать возможные exception ? Ну нет их в этом алгоритме вообще никаких, кроме разве что OutOfMemory). А было бы просто
Node result = NULL;
while(GetNext(value))
SearchAndInsert(result, value);
GetNext — 2 строчки, return buffer[i++] и проверка на окончание.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А у меня нет пунктика такого. Я к этому (на Паскале еще — помнишь передачу по var ?) привык. По крайней мере я решительно не вижу, что можно возразить против его применеия в данном конкретном случае.
Да, помню var, и &. Если честно, ref-ом активно не пользуюсь только потому что мне не хватает const& -а. Здесь, правда, как раз не тот случай, чтобы const совать.
PD>Можно на "ты", как это здесь принято
Я только "за", ждал твоего предложения
PD>Ну если суммировать с кодом построения, то да. Но он сам по себе. В С++ не было бы у меня никакого Enumerator и Enumerable и тем более ArgumentException (который здесь вообще-то ни при чем. И чего вы все любите так искать возможные exception ?
НЕНАВИЖУ ИХ!!! Но это формальная проверка предусловия, которая более детерминированная чем NullReferenceException, который может выстрелить а может и нет. По какому пути пойдет алгоритм. Язык такой, null-ы летают над головой. Вот в F# немного проще с ними, а в Haskell — вообще лофа!
PD>Ну нет их в этом алгоритме вообще никаких, кроме разве что OutOfMemory).
А StackOverflow!!!
PD>А было бы просто PD>
PD>Node result = NULL;
PD>while(GetNext(value))
PD> SearchAndInsert(result, value);
PD>
PD>GetNext — 2 строчки, return buffer[i++] и проверка на окончание.
А кто будет хранить buffer и i? Ниужели замыкание?
Здравствуйте, samius, Вы писали:
PD>>Можно на "ты", как это здесь принято S>Я только "за", ждал твоего предложения
Так по умолчанию же.
PD>>Ну нет их в этом алгоритме вообще никаких, кроме разве что OutOfMemory). S>А StackOverflow!!!
Ну теоретически да. Но реально я с ним бороться буду не с помощью try-catch, а просто установив нужный размер стека. В С++, кстати, stack overflow сделать — пара пустяков
int main()
{
int a[1000000];
// и вот он
}
/ccode]
Лечится элементарно
PD>>А было бы просто
PD>>[ccode]
PD>>Node result = NULL;
PD>>while(GetNext(value))
PD>> SearchAndInsert(result, value);
PD>>
PD>>GetNext — 2 строчки, return buffer[i++] и проверка на окончание. S>А кто будет хранить buffer и i? Ниужели замыкание?
Если С++ — сделаю их членами класса, и GetNext туда же. ctor (или Create) создает этот массив и рандомизирует.
Если начнешь опять про линии кода говорить — имей в виду, я уже начал Enumerator писать. Я тогда весь его код на тебя повешу
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
PD>>>Ну нет их в этом алгоритме вообще никаких, кроме разве что OutOfMemory). S>>А StackOverflow!!!
PD>Ну теоретически да. Но реально я с ним бороться буду не с помощью try-catch, а просто установив нужный размер стека. В С++, кстати, stack overflow сделать — пара пустяков
На C# тоже можно. Кстати, в Debug режиме или при запуске из под студии, на миллионе элементов стека уже не хватает для рекурсивных методов.
PD> int a[1000000]; PD> // и вот он
В C# тоже можно такое сделать в unsafe режиме (stackalloc)
PD>Лечится элементарно
За C# не отвечу.
PD>>>GetNext — 2 строчки, return buffer[i++] и проверка на окончание. S>>А кто будет хранить buffer и i? Ниужели замыкание?
PD>Если С++ — сделаю их членами класса, и GetNext туда же. ctor (или Create) создает этот массив и рандомизирует.
Я так и подумал, что добавление из массива — один класс, из списка — другой.
PD>Если начнешь опять про линии кода говорить — имей в виду, я уже начал Enumerator писать. Я тогда весь его код на тебя повешу
Молчу
S>В C# тоже можно такое сделать в unsafe режиме (stackalloc)
Ну хоть это сделать можно
PD>>Лечится элементарно S>За C# не отвечу.
Я тоже.
PD>>>>GetNext — 2 строчки, return buffer[i++] и проверка на окончание. S>>>А кто будет хранить buffer и i? Ниужели замыкание?
PD>>Если С++ — сделаю их членами класса, и GetNext туда же. ctor (или Create) создает этот массив и рандомизирует. S>Я так и подумал, что добавление из массива — один класс, из списка — другой.
Можно создать абстрактный класс, в нем GetNext, от него отнаследовать список и массив. Собственно, реализации IEnumerator GetNext это и делают — ну нельзя же реально ходить по связанному списку аки по массиву.
Понимаешь, с моей точки зрения я всегда вначале думаю — а что там в конечном счете будет ? Хоть какие обертки накрути, но список останется списком, и p=p.next там в том или виде будет в виде LEA, MOV и т.д. Вот это меня в первую очередь интересует, а уж потом — в какие фантики это обернуто.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, samius, Вы писали:
PD>Можно создать абстрактный класс, в нем GetNext, от него отнаследовать список и массив. Собственно, реализации IEnumerator GetNext это и делают — ну нельзя же реально ходить по связанному списку аки по массиву.
И для решения этой проблемы нужна хорошая абстракция, желательно вшитая в библиотеки.
PD>Понимаешь, с моей точки зрения я всегда вначале думаю — а что там в конечном счете будет ? Хоть какие обертки накрути, но список останется списком, и p=p.next там в том или виде будет в виде LEA, MOV и т.д. Вот это меня в первую очередь интересует, а уж потом — в какие фантики это обернуто.
Меня в первую очередь интересует, сколько придется писать коду чтобы стала доступна комфортная работа (например с контейнером). Если для построения моего контейнера из другого контейнера нужно писать специальный класс, меня это напряжет. Я сделал дерево и хочу строить его из всего!
И только когда меня серьезно напряжет высокоуровневое решение по производительности, когда я реально начну считать убегающие секунды, только тогда я вспомню про оптимизацию на низком уровне после того как попытаюсь что-нибудь предпринять на высоком.
Построение дерева из миллиона элементов за 10 сек — меня это устраивает, даже если можно сделать быстрее. Решение какой-то конкретной задачи за 10 сек — тут зависит от задачи. Может и не устроить, тогда я выберу другую реализацию.
Здравствуйте, samius, Вы писали:
S>Построение дерева из миллиона элементов за 10 сек — меня это устраивает, даже если можно сделать быстрее. Решение какой-то конкретной задачи за 10 сек — тут зависит от задачи. Может и не устроить, тогда я выберу другую реализацию.
Если нам не помогут, то мы тоже никого не пощадим.
