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

PD>Произвольный доступ используется там, где без него нельзя обойтись.

Глупо спорить с этим

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

Pavel Dvorkin wrote:
> Если ключевое слово — *сохранение состояния*, а не *в последовательную
> форму*, то я готов немедленно согласиться и закончить дискуссию. Если
> сериализация есть сохранение состояния (в последовательную,
> индексно-последовательную, бинарное дерево, БД, zip-архив и т.д. и т.п)
> — я согласен и готов не спорить о терминах. Только вот по крайней мере
> MFC сериализация требует именно
> *в последовательную форму*. Насчет .Net — не берусь судить, не настолько
> хорошо знаю.
>
> VD>"Выкладывание объекта в ряд" — это или пример извращеной
> терминалогии, или не понимания смысла процесса. Так что не нужно вообще
> так говорить.
Serialization от слова "serial" — "последовательный". Сериализовать можно не с целью сохранения состояния, а, например,
для передачи по сети.
Если же сохранение состояния, то persistence.
В поток сериализуют, а в БД персистят.

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

VD>>Ну, извини. Что вижу, то и говрю. Обижать тебя ни малейшего желания не было.

PD>Ok. Но если это повторится — вынужден буду прекратить дискуссию.

Еще раз извиняюсь, если задел. Постораюсь это не делать. Но и ты не принимай указание на твои ошибки за оскорбление.

PD>Если ключевое слово — сохранение состояния, а не в последовательную форму, то я готов немедленно согласиться и закончить дискуссию. Если сериализация есть сохранение состояния (в последовательную, индексно-последовательную, бинарное дерево, БД, zip-архив и т.д. и т.п) — я согласен и готов не спорить о терминах. Только вот по крайней мере MFC сериализация требует именно
PD>в последовательную форму. Насчет .Net — не берусь судить, не настолько хорошо знаю.

Последователная форма в данном случае означает "форма с которой легко манипулировать". Если говорить не псевдонаучным языком, а по простому. Сериализация — это превращение состояния графа объектов в некую простую структуру данных. Онятно, что некое бинарное дерево вряд ил можно назвать простой структурой. По этому в МФЦ или других фрэймворках под простой структурой понимают или массив байтов или поток. Делается это исключительно по той причине, что это самые примитивные абстракции в следствии чего с ними можно манипулировать наиболее абстрано. Их можно передавать по сети, записывать в файлы, шифровать, пихать в БД...

Что косается сохранения в БД, то тут могут быть разночтения. В БД можно сохранить состояние в виде BLOB-а, а можно в виде записей БД где поля объектов отражаются на колонки таблиц БД. Второе обычно называют persistens хотя иногда и сериализацией. Второе не очень верно, так как все же состояние хотя и сохраняется, но не в простой форме. В общем, то вотрой способ более гибок, но более расточителен.

Но еще раз замечу, что сериализация не подразумевает того, что она должна делать последовательно. Важно, что в итоге ты получашь поток или массив. Формировать же его можно по разному. И это уже вопрос реализации и эффектиности. Причем не нужно смешивать вопрос обстракции (поток/массив) с вопросами эффективности (того как пихать данные в эти самые массивы/потоки).

PD>Да бога ради, я на 100% согласен. В конце концов я ведь тоже в файл выкладывал, а он после закрытия уж на 100% последовательность байт, с этим не поспоришь.

Именно. Но еще раз. Не надо применять термин "выкладывал". Записывал будет понятнее и непротиворичивее.

PD> Я же совсем не об этом говорю, а о том, что сериализация, как она реализована (в MFC) требует, чтобы механизм (алгоритм) был последовательного выкладывания. Вот эта идея мне в общем случае не кажется верной.

В MFC сделано решение позволяющее уростить сериализацию. И ты волен его не использовать. MFC просто пытается облегчить тебе жизнь. Я откроевнно говоря уже не помню всех тонкостей, но если не ошибаюсь ты можешь перехватить процесс сериализации и сделать его вручную.

Опять же то, что MFC требует чтобы в конце процесса получилась та самая последовательная форма не подразумевает что обязательно нужно последовательно формировать эти данные. Ты можешь сформировать их в буфере и отдать уже результат.

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

VD>>Естественно! Вообще многое не обязательно. Например, не обязательно выходить на улицу в одежде или при размышлениях пользоваться логикой.

PD>Глупо. Аргументы подобного уровня заставляют только сомневаться в правоте аргументирующего.

Это называется сарказм. Ты сомневашся в совершенно очевидных, на мой взгляд, вещах. Я не говорю тебе об этом открыто, а даю понять это приведением абсурдных аналогий. Так что могу посоветовать только по чаще включать юмор и улыбаться.

PD>Ох, надоело мне это упоминание больших проектов. Откуда тебе знать, в каких проектах я участвовал, что ты все время пытаешься мне это тыкать ? Проекта с суммарным размером исходников в 10 Мб хватит?

Я сужу по высказваниям. И, кстати, если ты заметил не говори тебе, что ты не участвовал в больших проектах. Просто твое не верное, на мой взгляд, отношение к абстракциям явно не способствует при работе над большими проектами.

PD>Ну спасибо, просветил. Без тебя я про структурное программирование и ООП так и не узнал бы .

Про ООП узнать мало. Еще нужно вжиться в него. Не прийми следующие слова за оскобление, но я четко вижу, что ты плохо вжился в ООП. Твое отношение к абстракциям крайне не верное. Ты смотришь на них сквозь призму реализации, а это не верно!

PD>А я и не создавал. Код, который я писал, вполне успешно работает на сотнях компьютеров, и до сих пор никто не жаловался.

Если ты вместо того, чтобы пользоваться готовыми абстракциями будешь создавать собственные аргументируя это тем, что "так быстрее", то точно создашь проблемы себе и окружающим. Что же до работы на сотнях компьюетров, то мои ранние программы работали на тысячах компьютеров, но я сказал бы, что написаны они били припохабно. Так что тут зависимости нет. Работать можно заставить даже самый бездарный код. Был бы напор и желением. А вот создать код который не только что-то делает, но и легко модифицируется и заменяется на другой елси это потребуется — это куда более сожная задача. И в больших проектах она востребована как никогда. От того я и упоминаю бльшие проекты.

PD>Да уж, действительно мелочи. будет ли в результате файл размером в 10 Кб или 10 Мб, будет ли это работать быстро или медленно — это все мелочи. Зато принципы будут соблюдены.

Раскажи мне, плиз, как связаны размеры файлов и скорость работы кода с тем, что интерфейс сериализации требует последовательной записи?

VD>>Сериализация вообще не является последовательным выкладыванием полей в поток (в прочем как и объетов). Сериализация — это преобразование состояния объекта в последовательную форму. То как это делается уже вторично. Ты можещь использовать разнообразные промежуточные структуры, сохранять только часть полей или даже некоторую функцию от состояния объекта по которой потом можно будет востановить это состояние. Это уже все детали. Главное, что в итоге ты должен получить массив байтов/поток в ктором находится состояние графа объектов.

PD>В письме к Sinclair я сформулировал конкретно задачу (с матрицей). Напиши свое решение, обсудим. Хватит обо общих принциах говорить, код в студию.

Я не буду писать тебе кокретных решений. Я тебе просто попробую написать очень простой код и донести его смысл. Сериализацию можно представить как функцию:

Stream Serialize(SomeType roor)
{
    ...
}

Ты волен реализовать эту функцию как угодно. Единственное что ты не должен менять — это сигнатуру этой функции, так как — это интерфейс между тобой и остальным миром.

Все твои рассуждения связанные со скоростью и компактностью — это рассуждения о тех трех точках. Ты же пыташся начать рассуждать о сигнатуре функции. Вот в этом и заключается ошибка.

Пойми, что твоя функция универсальна пока она соблюдает этот интерфейс. И это очень важно!

VD>>>>Вообще данный вопрс показывает то что большинство твоих проблем происходят из-за того, что ты не умешь мыслить абстракциями.

PD>Меня, честно говоря, сильно удивляет то, что ты, вроде бы неглупый человек, столь несерьезно относишься к своим заявлениям. Неужели трудно понять из моих выступлений, что мыслить твоими любимыми абстракциями я умею, но для меня это лишь половина задачи. Наверное. что такое поток, я понимаю, но бездумно использовать эту концепцию, не разобравшись в том, как она может быть в данной ситуации реализована, я не буду.

И все же ты обежашся на правду. Не, конечно может быть я ошибаюсь, но то что я говорю — это то что я вижу. Пойми другие просто пройдут мимо, возможно зларадно хихикнув. Я тебе сказал, то что думаю, и ты обидился на этом. Ну, могу конечно тоже промолчать. Лучше тебе от этого вряд ли станет. Но за-то не обно.

Если абстрогироваться от обит и поптыаться проанилизировать сви ошибки, то ты увидишь, что умение мыслить абстракциями как раз и подразумевает при размышлениях возможность отрешитья от эффективности реализации. Тебе достаточно общей характеристики для твоих размышлений. Следующим шагом будет умение выбрать компромис между универсальностью и эффективностью. Ты явно (опять же на мой взгляд) слишком сильно зациклен на эффективности от того злишся на абстракции. А это не верно! Ну, не виноваты абстракции ни в чем.

PD>Для тебя — есть объект, надо сохранить, выведем поток. Все ясно.
PD>Для меня — есть объект, надо сохранить. Можно выести в поток, а это хорошо будет ? Размер файла ? Скорость ? Хорошо ? Тогда ладно. Нет ? А что другое можно предложить ? И т.д.

Во-вот. Для меня есть здача. Далее я пытаюсь выбрать паттерны для ее решения и абстракции для представления сущьностей учавствующих в этом решении. Если задача сохранить состояние объекта в файл и загрузить его в последствии, и при этом нет нужны в анализе этого состояния, то я выберу паттерн "Сериализация". Если я выбрал это паттерн, то совершенно логично, что абстракция "Состояние" подразумеваемая этим паттерном будет поток или массив байтов. Так же совершенно логично, что сам процесс сериализации будет представлен функцией параметром которой является сериализуемый объект, а возвращаемым значением этотм самый потк (короче как в примере выше). Выбор потока обуславливается тем, что это самая универсальная абстракция из пригодных для представления состояния.
Далее я задумаюсь над реализацией той самой функции. Вот тут я как и ты задумаюсь над тем как более эффективно сериализовать состояние графа объектов. И о том, что мне важнее универсальность, скорость, размер сериализованного представления или какое-то сочетание этих аспектов. Например, если размер и скорость мне не очень важны, то я могу воспользоваться не очень эффективным встроенным механизмом сериализации в дотнете. Если мне важен размер, то я могу реализовать автоматическую сериализацния на без рефлексии. А если мне нужна и скорость, и компактность результата, то скорее всего я создам метапрограмму генерирующую код для некоторого списка классов.

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

Важно другое. У нас в корне отличается стадия анализа. Ты уже на самых ранних стадиях размышлений сваливашся на обсуждение деталией, то есть на очень низкий уровень абстракции. Я же пытаюсь этго не допустить. Только и всего.

PD>А если ее нельзя реализовать в данной ситуации эффективно ? Нельзя, и все. А неэффективно — не принимается. Ваше решение ?

Значит имеет место один из двух фактов:
1. Ты недостаточно подготовлен для грамотного решения задачи.
2. Эта абстракция неподходит и надо искать другую.

Но не в коем случае не нужно "подстругивать" абстракцию.

PD>У меня их тоже нет.

Вижу.

PD>Вообще забавно смотреть на твой менторский тон. "Возможно, ты не знаешь..." и дальше популярное объяснение. Знаю, не волнуйся.

Тем страннее.

PD> И не изучаю, а закончил небольшой проект на нем. Увы, заказчик потребовал использовать NHibernate. Клиент всегда прав, как известно. Ну что же, по крайней мере я постарался сделать так, чтобы запросы к БД были не менее эффективными, чем на чистом SQL.

Забавные клиенты пошби. Так глядишь и через некоторое время клинеты начнут заставлять соблюдать чистоту абстракций и грамотность форматирования кода.

PD>Кстати, разъясни фразу "приблизительно в 10 раз менее эффективны, чем аналогичные исползующие прямую работу с БД". Ты утверждаешь, что у меня в 10 раз больше данных выбирается, или в 10 раз больше модификаций делается, или что ? Если это — можешь быть уверен, что это далеко не так, ничего лишнего там выбираться не будет.

Под эффективностью тут имеется в виду скорость работы. O/RMapper-ы в принципе не эффективны. Пока что никому не удалось создать реализацию O/R Mapping-а которая была бы соизмерима со скоростью добротно написанного приложения работающего с БД по сдерствам запросов.

VD>>Небывает уровеня реализации. Быают разные реализации абстракций и (иногда) алгоритмические ограничения абстракций. Например, связанный список накладывает принципиальные ограничения на скорость последовательного доступа. Вот только сериализация то тут причем?

PD>Не знаю. Я могу еще заявить, что скорость ввода символов с клавиатуры человеком накладывает принципиальные ограничения на возможность вручную ввести "Войну и Мир" за одни час, и спросить — а при чем здесь сериализация? Ты задал этот вопрос, ты и отвечай. Я про связанные списки вообще ничего не говорил.

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

PD>Да давно я во всем этом разобрался. Твоя ошибка в том. что ты почему-то решил, что мне неизвестны элементарные истины, и пытаешься меня им научить, А для меня эти истины — просто нечто рабочее, о чем я и думаю-то мимоходом.

Незаметно, что-то.

PD> Стек так стек, поток так поток, дерево так дерево. Все замечательно. А теперь давайте думать — а как это сюда уляжется. С этим потоком мне уютно будет ? Нет ? А куда выводить надо, только в файл ? Да, А тогда долой отсюда этот поток. В файл я и по-другому записать могу. Вот и все.

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

Вот это и есть неумение использовать абстрации.

PD>Вот тебе абстракция — линейный список с возможностью доступа по индексу к имеющимся элементам? Годится абстракция?

Годится.

PD>А теперь ответь — можно ли использовать эту абстракцию для хранения данных, если

PD>a)

PD>1) количество элементов очень велико
Не влияет на выбор абстракции.
PD>2) операции вставки/удаления в начало производятся очень часто
Не влияет на выбор абстракции.
PD>3) операции доступа по индексу производятся очень редко
Единственный важный факт из перечисленных.
PD>4) скорость работы критична
Не влияет на выбор абстракции.

Ответ будет один — да, можно.

PD>б)

PD>1) количество элементов очень велико
Единственный важный факт из перечисленных.
PD>2) операции вставки/удаления в начало производятся очень редко
Единственный важный факт из перечисленных.
PD>3) операции доступа по индексу производятся очень часто
Единственный важный факт из перечисленных.
PD>4) скорость работы критична
Единственный важный факт из перечисленных.

Тоже можно.

PD>Непременное условие — о реализации ты ничего не знаешь, как ты и хотел. Иными словами, после того, как ты ответишь на оба вопроса, я тебе сообщу, какая именно реализация используется в библиотеке, которую ты должен использовать.

А мне не нужно сообщать. Я выбрал абстракцию. Твои условия ей не противоречат. А вот реализацию абстракции я выбиру сам исходя из тех самых критериев которые ты перечислил. Причем критерии вроде "количество элементов очень велико" для меня явлюятся пустым звуком. "Очень велико" может означать разные вещи для разных людей или разных уловий.

PD>И просьба не отвечать — дескать, если меня не устроит эта реализация, я другую сделаю. Нет у тебя такого права.

А это условие чтобы прикольнее было?

PD>Ты сам от него отказался.

Когда это? Я всего лишь отделил выбор абстракции, от выбора ее реализации. Я определился с тем, что для меня приемлема конкретная абстракция (список с произвольным доступом), и теперь могу определиться с конретной реализацей. Причем реализацию я могу и заменить в последствии. А вот абстракция уже более стабильная сущность.

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

Хм. А как же можно не говорить да, или нет?

VD>>Ну, нет никаких проблем для того, чтобы эффективно сериализовать все что угодно в поток байтов. Ну, нет! Ты можешь банально сделать это в помяти и вернуть требуемый интерфейс воспользовавшись каким-нибудь MemoryStream.

PD>Памяти нет

Куда она делась? Или это такая Матрица? "Ложки нет..."

>>Так зачем же жертвовать абстракцией и писать какие-то частные клагоритмы которые можно использовать только в отдельных случаях?

PD>Для того, чтобы самолет летал быстрее, чем паровоз ездит

Полетят у тебя они оба в одном направлении с такими подходами... под откос.

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

PD>Ну и не надо. Вполне согласен. А вот надо ли при записи в файл использовать сериализацию ?

Хороший вопрос. Может его нужно было решать до того как ты начал использовать сериализацию?

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

PD>2. Двухпроходной алгоритм не рассматривается.

А почему собственно?

И, кстати, а зачем вообще хранить длинну? Элементы фиксированной длинны. Размер матрицы известен. Читай себе пока элементы не кончатся и востанавливай значения ячеек.

Хотя это конечно частный случай. Одако не вижу проблем в том, чтобы сформировать нужный список в памяти, а потом записать в конечный покто количество элементов (если уж действительно нужно), и за ним скопировать поток.

И не надо рассказывать про скорость и лишнюю память. Память ты занимашь на наносекунды. Объем ее незначителен. Любое использование сериализованной информации (предача через сеть, запись в файл...) несоизмеримо со скоростью копирования памяти.

ЗЫ

И, кстати, натянутость самой ситуации снова настораживает. Значит при хранинии данных в памяти (которая как извесно примерно на 3 порядка дароже) ты выбирашь плоские массивы, а при хранении на диске вдрг слезно озаботился компактностью. Странно это.

Скорее всего матрица просто не самое эффективное представление данных. Или нужно использовать хэш-таблицу, или еще что-то. А при этом и слгоритмы сериализации опменяются.

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

PD>Нет, не пойдет. Если ты его запишешь в конец, как ты отличишь его от очередной тройки ? Файл-то в действительности будет двоичный, это я просто в текстовом виде привел для наглядности. И я вовсе не обещаю, что после этой матрицы там не будет других данных.

PD>Можно, конечно, после матрицы всех троек -1 записать как признак конца. Но и это некорректно —

А что же тут не корректного то?

PD>а если нумерация строк матрицы не с нуля, а произвольная ?

1. Это уже выдумывание нереальных условий в целях доказательства ради доказательства.
2. Какая разница, что использовать в качестве условия остановки -1 или int.MinValue? Используй его или нижнюю границу минус еденицу.

В общем, это разговор не очем. Для конкретного случая, конкретная реализация. А в общем, случае единственное разумное решение — это кэшировние результата. Нефига экономить на спичках.

Пойми, что большинство людей с тобой общащихся вообще не станут писать сериализацию вручную если на то нет очень весомых оснований. И оптимизировать формат тоже не станут. Ну, и что если у меня файл будет не 100 байт, а килобаймт? Современной системе это до лампочки.

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

S>Если нумерация строк произвольная (что имеет весьма слабый смысл), то достаточно в заголовке записать эти данные вместе с размерностью матрицы. Если смещения заранее известны, то даже этого не требуется. Я тебе заранее могу сказать, что вариант с маркером конца матрицы будет работать как минимум не хуже варианта с префиксом длины, что бы ты ни придумал. Потому, что математика так устроена.

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

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

_>Serialization от слова "serial" — "последовательный". Сериализовать можно не с целью сохранения состояния, а, например, для передачи по сети.

При передаче по сети, тоже передается состояние.

_>Если же сохранение состояния, то persistence.
_>В поток сериализуют, а в БД персистят.

Бывает по рзному. Бывает, что и БД сериализуют. Но в общем верно.

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

B>Потом ты ехидно заявил, что BG недоучка, не знает о прямом доступе
B>и потому везде пихает сериализацию.

М-да... Я и не думал, что мою шутку кто-то так понять ухитрится. Или ты впрямь решил, что я считаю, будто вся MS не умеет работать с файлами прямого доступа ?

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

VD>Здравствуйте, Pavel Dvorkin, Вы писали:


VD>Пойми, что большинство людей с тобой общащихся вообще не станут писать сериализацию вручную если на то нет очень весомых оснований. И оптимизировать формат тоже не станут.

Т.е будут хранить матрицу целиком ?


Ну, и что если у меня файл будет не 100 байт, а килобаймт? Современной системе это до лампочки.

Маленькая поправка.

Исходная матрица 1000*1000. Размер 4 Мб.
Ненулевых элементов 5%. Их объем при хранении 1000*1000*0.05 * 3 * 4 = 600 Кб. Можно и меньше, если более оптимальным способом хранить

Как говорят в Одессе, две большие разницы. 4 Мб и 600 Кб. Если тебе это до лампочки — на здоровье.

И зачем это люди архиваторы используют ? Хранили бы файлы как есть. Современной системе это до лампочки!

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

S>Здравствуйте, Pavel Dvorkin, Вы писали:

S>я точно так же стану использовать -1 в качестве маркера конца списка ячеек/строк. И размер данных будет таким же, как у тебя. Только fseek не будет нужен.

Хорошо, на тебе еще один пример. Для каждой строки должна храниться некая ее характеристика (ну, к примеру, среднее всех элементов). При вводе строки, для которых эта характеристика не соответствует некоему критерию, должны пропускаться. Характеристика вычисляется по каждой строке и заранее не известна.

А впрочем, зачем я все это доказываю? Ты же достаточно грамотный программист и не можешь не понимать, что во многих случаях нельзя сделать однопроходной алгоритм выкладывания без возвратов в файле. Ну не можешь ты это не понимать. иногда можно обойтись без этого, чаще — нельзя. Так зачем же доказывать недоказуемое ? Только для того, чтобы оправдать свою изначальную позицию ?

S>Вот давай теперь я тебе задам задачку: та же матрица, вот только нужно компрессировать ее данные при помощи Gzip. Требования те же: никакой дополнительной памяти, писать все в один проход. Мой код не изменится вообще — я просто отдам сериализатору в качестве таргета GzipStream.

Как красиво! А этот самый GZipStream внутри себя так-таки и не использует позиционирование в ? И не использукт дополнительной памяти ? И точно однопроходной ? Код его можно посмотреть ?

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


PD>>Ну и не надо. Вполне согласен. А вот надо ли при записи в файл использовать сериализацию ?

VD>Хороший вопрос. Может его нужно было решать до того как ты начал использовать сериализацию?

Уф, наконец-то первое здравое размышление в этой дискуссии. Я же именно об этом и говорю. Я разве против сериализации, когда она оправдана алгоритмом ? Ни в коем случае, я целиком за!!! Я против того, что сериализация бездумно используется там, где алгоритм ее вовсе не предполагает. Например, для копирования объекта в памяти. Например, для вывода объекта на диск при том, что этот вывод достаточно сложен и не укладывается в один линейный проход. И т.д.

Меня не сериализация беспокоит. Сама по себе она вполне законный метод, безусловно имеющий право на существование. Мне не нравится, когда ее применяют там, где совсем не надо. А тем более пытаются доказать, что применять ее все же стоит даже в тех случаях, когда она явно противоречит алгоритму (последнее утверждение есть непосредственно камешек в твой и Sinclair огороды)

В общем, не сотвори себе кумира из сериализации. Да и из всего другого тоже.

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

PD>>2. Двухпроходной алгоритм не рассматривается.

VD>А почему собственно?

А потому, что на него нужно лишнее время.


VD>Хотя это конечно частный случай. Одако не вижу проблем в том, чтобы сформировать нужный список в памяти,

Т.е использовать дополнительную память.


VD>И не надо рассказывать про скорость и лишнюю память. Память ты занимашь на наносекунды. Объем ее незначителен.

А откуда ты знаешь, что незначителен ? В моей программе (там, правда, не разреженная тарица была, а нечто более сложное) суммарный размер выходных данных примерно 100 Мб. И хранить промежуточные данные мне негде.


VD>ЗЫ

VD>И, кстати, натянутость самой ситуации снова настораживает. Значит при хранинии данных в памяти (которая как извесно примерно на 3 порядка дароже) ты выбирашь плоские массивы, а при хранении на диске вдрг слезно озаботился компактностью. Странно это.

Нет, не странно. Дело в том. что, к примеру, выполнять операции матричной алгебры на компактированных матрицах как бы это выразиться ... не очень удобно . Перемножение еще туда-сюда, а вот нахождение, скажем, собственных значений и векторов (диагонализация) — лично я таких алгоритмов не знаю. Там и без того N^3 по методу Якоби, а если еще в сжатом виде хранить — ждать будем до второго пришествия. А матрица именно разреженная, и очень сильно (говорю о задачах, которые решал во времена своих химических дел — расчет ИК-спектров, квантовая химия)

VD>Скорее всего матрица просто не самое эффективное представление данных.
Или нужно использовать хэш-таблицу, или еще что-то. А при этом и слгоритмы сериализации опменяются.

Предложи для начала алгоритм диагонализации матрицы, представленных в виде хеш-таблицы

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

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

PD>А впрочем, зачем я все это доказываю? Ты же достаточно грамотный программист и не можешь не понимать, что во многих случаях нельзя сделать однопроходной алгоритм выкладывания без возвратов в файле. Ну не можешь ты это не понимать. иногда можно обойтись без этого, чаще — нельзя.
Ну с чего это "чаще-нельзя"??? Павел, ты опасно заблуждаешься. Все как раз наоборот. Я вот в жизни не встречал еще необходимости делать fseek при сохранении. Обрати внимание, что когда ты пытаешься приводить свои реальные примеры, оказывается, что fseek был нафиг не нужен. Странно, правда? Поэтому твое впечатление о том, что чаще — нельзя, напрямую связано с тем, что ты просто пихал fseek где надо и где не надо.

S>>Вот давай теперь я тебе задам задачку: та же матрица, вот только нужно компрессировать ее данные при помощи Gzip. Требования те же: никакой дополнительной памяти, писать все в один проход. Мой код не изменится вообще — я просто отдам сериализатору в качестве таргета GzipStream.
PD>Как красиво! А этот самый GZipStream внутри себя так-таки и не использует позиционирование в ?
Нет, не использует. Он был специально заточен под работу с потоками.
PD>И не использукт дополнительной памяти ? И точно однопроходной ? Код его можно посмотреть ?
Там внутри стандартный LZW. Он использует небольшую дополнительную память (О(1)), но однопроходный. Код можешь посмотреть рефлектором.

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

PD>И зачем это люди архиваторы используют ? Хранили бы файлы как есть. Современной системе это до лампочки!
Вот кстати если использовать архиватор, то он сам выкинет все эти нули. А знаешь, в чем прелесть? В том, что зип сожмет и матрицу из всех единиц. А твой алгоритм разбарабанит ее вдвое. При этом для скармливания ее зипу все равно придется сначала выделить буфер размером в 8mb, потому что тебе очень хочется вернуться в начало.

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Уф, наконец-то первое здравое размышление в этой дискуссии. Я же именно об этом и говорю. Я разве против сериализации, когда она оправдана алгоритмом ? Ни в коем случае, я целиком за!!! Я против того, что сериализация бездумно используется там, где алгоритм ее вовсе не предполагает. Например, для копирования объекта в памяти. Например, для вывода объекта на диск при том, что этот вывод достаточно сложен и не укладывается в один линейный проход. И т.д.
Пример со сложным выводом в студию. Желательно реальный. Это должно быть легко — ведь в твоей практике такие выводы встречаются куда чаще, чем линейные, не так ли?
PD>Меня не сериализация беспокоит. Сама по себе она вполне законный метод, безусловно имеющий право на существование. Мне не нравится, когда ее применяют там, где совсем не надо. А тем более пытаются доказать, что применять ее все же стоит даже в тех случаях, когда она явно противоречит алгоритму (последнее утверждение есть непосредственно камешек в твой и Sinclair огороды)
Павел, в моем огороде их уже и так достаточно. Пока что ты не привел ни одного алгоритма персистенса, который бы противоречил сериализации. Я вот могу их привести. Но они настолько далеки от твоей ситуации, что пока что мы это оставим. Вплоть до момента, когда на тебя снизойдет просветление, и ты наконец поймешь, что бесчисленные преимущества сериализации перевешивают те лишние 40 секунд, который надо потратить на перепроектирование алгоритма "записи конем".
PD>В общем, не сотвори себе кумира из сериализации. Да и из всего другого тоже.
В общем, не изобретай сущностей без необходимости. В частности, не требуй для персистенса произвольного доступа.

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

PD>Нет, не странно. Дело в том. что, к примеру, выполнять операции матричной алгебры на компактированных матрицах как бы это выразиться ... не очень удобно . Перемножение еще туда-сюда, а вот нахождение, скажем, собственных значений и векторов (диагонализация) — лично я таких алгоритмов не знаю.
Знаешь. Только не даешь себе труда задуматься.
PD>Там и без того N^3 по методу Якоби, а если еще в сжатом виде хранить — ждать будем до второго пришествия.
Это ты почему так решил?
PD>А матрица именно разреженная, и очень сильно (говорю о задачах, которые решал во времена своих химических дел — расчет ИК-спектров, квантовая химия)
Спасибо за такую интересную дискуссию. Редко встречается столь идеальный собеседник
VD>>Скорее всего матрица просто не самое эффективное представление данных.
PD>Или нужно использовать хэш-таблицу, или еще что-то. А при этом и слгоритмы сериализации опменяются.

PD>Предложи для начала алгоритм диагонализации матрицы, представленных в виде хеш-таблицы
Гм. Вам там алгоритимист случайно не нужен? Похоже, все-таки программирование на плюсах некоторым людям ломает думательную часть в пользу кодописательной
Алгоритм, очевидно, будет точно таким же. Если, конечно, тим лидер или архитектор вовремя достал логарифмическую линейку и отбил пальцы битхакеру, который использовал для диагонализации матрицы ее внутреннее представление и пользовался указалелями, вычисленными по сложным формулам.
В таком случае есть некоторый алгоритм, который работает только с оператором [,] для доступа к элементам.
От того, что мы заменили реализацию этого оператора с вычисления указателя при помощи сложения и умножения на поиск в хеш-таблице, ничего не поменяется.
Это называется декомпозиция — разбиение сложной штуки на более простые. Я надеюсь, ты в курсе, что компиляторы плюсов уже лет десять как умеют получать для первого варианта матрицы точно такой же код, как и для обычного двумерного массива? Это позволяет смело пользоваться декомпозицией, не слишком заботясь о низкоуровневой производительности.

Теперь вернемся к нашей хеш-таблице. Приятной особенностью двумерного массива является время доступа за O(1) к любому элементу. Как ни странно, но нормально заполненная хеш-таблица имеет то же время порядка O(1)! Забавно, правда?
Может, нас спасет малый размер константы для массива? Увы. Павел, когда мы говорим о сильно разреженных матрицах, начинают играть большую роль эффекты второго порядка.
Вот смотри: допустим у нас матрица весит 10 мегабайт. Коэффициент заполнения — 5%. Т.е. ненулевых данных — всего 500kb. Моя машина оборудована L2 кэшем размером в 1024 kb.
Промах кэша — очень дорогая операция. Таким образом, интуиция подсказывает мне, что мы запросто можем выиграть в диагонализации разреженной матрицы за счет использования более компактного представления. У меня нет времени проверять это на практике. Но общая тенденция мне нравится — ты все время привлекаешь в качестве примеров только те ситуации, в которых ты неправ.

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

S>Здравствуйте, Pavel Dvorkin, Вы писали:
S>Пример со сложным выводом в студию. Желательно реальный. Это должно быть легко — ведь в твоей практике такие выводы встречаются куда чаще, чем линейные, не так ли?

Пожалуйста, я его уже приводил. Матрица та же. Для каждой строки должно быть выведено среднее ее элементов, так как в зависимости от его значения эти строки будут потом вводиться или нет. Читать с диска строки, для которых m < некоторого K, не разрешается, они просто должны при вводе пропускаться.
Сложным этот пример не назвать, но сойдет.

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

Условие — никаких двухпроходных алгоритмов и памяти больше O(1).

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Пожалуйста, я его уже приводил. Матрица та же. Для каждой строки должно быть выведено среднее ее элементов, так как в зависимости от его значения эти строки будут потом вводиться или нет. Читать с диска строки, для которых m < некоторого K, не разрешается, они просто должны при вводе пропускаться.
Ага, вот мы начинаем постепенно подходить к тем задачам, для которых действительно сериализация не подходит.
PD>Сложным этот пример не назвать, но сойдет.
Павел, а ты заметил, что подменил задачу? До сих пор ты вроде как говорил о персистентности, т.е. сохранении объекта с целью его последующего восстановления.
А теперь вместо восстановления объекта ты перешел к выполнению запросов.
Фактически, уже здесь лежит граница. Как только мы ставим себе задачу научиться читать не все, приходится мгновенно отказаться от сериализации. Потому, что она и при чтении позволяет читать только вперед, никаких прыжков "мимо строки" в ней нет.

Следующим этапом будет "минимизировать время внесения изменения в одну ячейку матрицы от чтения до записи на диск", и тебе не помогут даже фокусы с fseek. Потому что они подходят только для данных, длина которых известна.

Так вот я тебе открою тайну: никто и не применяет сериализацию для выполнения запросов. Для этого есть движки различной степени специализированности. Ты почему-то решил, что кто-то чем-то злоупотребляет. Нет, это ты злоупотребляешь fseek-ом там, где хватило бы оператора <<.

Здравствуйте, Pavel Dvorkin, Вы писали:
VD>>Хороший вопрос. Может его нужно было решать до того как ты начал использовать сериализацию?

PD>Уф, наконец-то первое здравое размышление в этой дискуссии.

Ты мне льстишь.

PD> Я же именно об этом и говорю. Я разве против сериализации, когда она оправдана алгоритмом?

Вот, по-моему, в этом и кроется ошибка. Она оправдана не алгоритмом, а решаемой задачей.

PD>Меня не сериализация беспокоит. Сама по себе она вполне законный метод, безусловно имеющий право на существование. Мне не нравится, когда ее применяют там, где совсем не надо.

Мне тоже. Но критерии у нас с тобой совсем разные.

PD> А тем более пытаются доказать, что применять ее все же стоит даже в тех случаях, когда она явно противоречит алгоритму (последнее утверждение есть непосредственно камешек в твой и Sinclair огороды)

Скорее это камешек брошенный вверх.
Ну, да это уже не конструктивно.

PD>В общем, не сотвори себе кумира из сериализации. Да и из всего другого тоже.

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