Здравствуйте, vdimas, Вы писали:
V>Уровень владения технологиями, технический кругозор. V>В общем, всё, что можно выяснить на собеседовании.
Имеется в виду — табличка вида "собеседовал, дата, результат". Ну, чтобы видеть, что вот это вот смутное ощущение "все стало хуже" имеет под собой какие-то основания, кроме интуитивных.
V>Трындёж — это не иметь возможности сравнить претендентов из разных эпох, но делать заявления.
V>Верно, сейчас вменяемых 1-2 человека из выпускаемой группы ВУЗ-а в 20+ человек. V>Я так и говорил, а ты споришь.
С этим я не спорю. Я спорю с тем, что раньше были какие-то особенные урожаи программистов.
V>Никто не говорил о том, что сейчас в IT стало меньше грамотных людей.
Если под "никто" понимается ТС, то он именно что это и говорил.
V>Говорят, что их доля резко упала. V>Т.е. резко упала средняя температура по больнице.
Это смотря как мерить.
V>А так-то вероятнее всего обратное, грамотных в абсолютном выражении могло стать больше из-за того, что в IT стали идти "все подряд" (по крайней мере у нас, в экс-СССР), т.е. вполне могут "раскрываться" как специалисты те люди, которые в 90-х не пошли бы учиться на программиста.
Более того — если брать средний уровень программирования среди "всего населения", то он ещё и поднялся.
V>Разговоры про "планку входа" у нас шли вовсю шли уже в первой половине нулевых.
Разговоры про планку входа идут столько, сколько лет самому программированию.
V>Я не могу себе представить эти разговоры в твоём 93-м, потому что за пределами требуемой на тот момент "планки входа" этих людей просто не было в профессии — они получали "корочку", но занимались другой деятельностью.
Я эту фразу не понимаю. Что за планка, кого именно не было в профессии?
В наших краях, к примеру, "корочек" по программированию не было примерно ни у кого. В профессии были кто угодно, кроме программистов — математики, физики, химики, экономисты, связисты.
В основном — потому, что "профильного образования" как такового не существовало до нулевых.
V>Ты ж учился не на IT, откуда у тебя статистика по однокурсникам, учившимся на IT?
У меня статистика по однокурсникам, учившимся на ФФ. Из них многие стали программистами.
V>Отож, 90% нынеших программистов принципиально неспособны писать те программы. V>Думаю, конкретно ты был бы способен, но тебе пришлось бы многое пересмотреть из нынешних своих представлений. V>Ну и прокачать некоторые навыки, например, внимательность и объективность.
S>>У меня инсайд из НИИ Автоматизированных Систем — типичное учреждение промышленного программирования. S>>Уверяю вас: никакого "любопытства", никаких "исследователей". Совершенно простые смертные. Тётеньки, которые писали унылые программы на фортране.
V>И они получают свои 5-10 тыс $$ в месяц, поэтому сидят там? ))
Какие 5-10 тыс $$ в 1980х? Очнитесь. 135р в месяц — вот их зарплата. 200 — у ведущих специалистов.
V>А тут нагло ходят на собеседования.
Это показывает не уровень образования, а тупо желание попасть на работу.
V>Я не могу представить себе подобное в других областях, где требуются определённые непростые навыки. V>Например, придти устраиваться танцором в балет, но растяжки нет, классика хромает, прыгучесть нулевая...
Как только в балете начнут платить по 5-10 $$$ в месяц, туда будут идти примерно все. Посмотрите на отборочные этапы Танцев на ТНТ — ровно то, о чём вы говорите.
V>Решат, что чел просто прикалывается. ))
Ну, так и вы решайте. Делов-то. Но вообще, это означает, что ваш HR просто отлынивал от первичной фильтрации. К нам и в 2002, и в 2005, и в 2010, и в 2015, и в 2020 приходили очень и очень вменяемые люди.
V>А сейчас аналогичные ребята уверены, что хоть где-то их возьмут, бо дефицит и всё в этом роде.
Ну, раз они уверены, то никакой проблемы нет.
V>Это в твоей непрофильной специальности из группы 1-2 любопытсвовали в IT, оттуда статистика? )) V>Вообще странно, что ты сразу не пошёл на интересующую тебя специальность.
Не существовало у нас интересующей меня специальности. ФИТ открыли уже в нулевых — я к тому моменту давно свой диплом защитил.
V>На IT-специальностях так не было, разумеется.
Как по мне, так это вообще на всех специальностях. Значительная доля народу идёт в ВУЗ чтобы пересидеть армию или выйти замуж. Ещё сколько-то — потому что "мама заставила" или "подруга посоветовала".
Из нашей не-IT специальности программистов вышло больше, чем физиков.
V>Та не мог твой ВУЗ быть совсем отсталым, даже в пик развала в 93-м. V>Просто у тебя выборка по непрофильной специальности.
Распределение IQ примерно одинаковое, от специальности не зависит. Распределение уровня мотивации примерно одинаковое, от специальности не зависит.
Распределение произведения этих двух параметров даёт неплохую оценку результирующей эффективности.
V>В Lisp и Algol абсолютно идентичные nil, никакого NULL в Algol нет, RTFM!
Продолжаете жечь? https://www.algol60.org/docsW/algolw.pdf, раздел 4.5 References.
В Lisp nil — это не "невалидная ссылка", а пустой список.
(sigh).
V>Защита от nil всегда через проверки, что в Lisp, что в Algol, безальтернативно.
(sigh).
V>Как думаешь, какой чертой пользовался сам Хоар приличную часть своей карьеры еще до всяких Windows? ))
Думаю, что прямой. Вряд ли Хоар много работал в DOS.
V>Сам термин IoC из объектно-ориентированной среды, я его использовал сугубо удобства ради.
Скорее, ради красного словца.
V>Я тебе заранее на это уже отвечал — смотри как это обыгрывается в функциональных языках или в том же Kotlin, т.е. в языках, где присутствуют исключения.
И опять смешение мух и котлет. Исключения и ФЯ ортогональны друг другу.
В ФЯ описанная проблема решается при помощи системы типов, точка.
V>В общем, ты сначала прикинь хотя бы минимально, как всё это обыграть для решения реальных задач.
Да что тут прикидывать? Всё известно от зари времён. В том-то и дело, что Хоар это понял, хоть и задним числом. А вы не понимаете по-прежнему.
V>Далее. V>Если в языке есть возможность описывать пользовательские типы, выбрасывать и перехватывать исключения, переопределять операторы и вводить алиасы типов (как typedef в С/С++), то проблема упрощается.
Ну, это просто длинный способ сделать "примерно то же самое", хоть и не совсем. В языках с нормальной системой типов приведение Null к NotNull является ошибкой времени компиляции, а не рантайм-исключением.
V>У меня выше тоже SomeTypeRef статически отличается от SomeType*. V>И никаких дополнительных фич языка не потребовалось.
V>А теперь давай про интероперабельность nullable и non-nullable типов. V>Вот проверь статически Optional<T*> без IoC или исключений. ))
Охтыж боже мой. Ну да, на С++ по-другому никак, т.к. паттерн матчинг не завезли.
А в нормальных языках с современной системой типов мы имеем
Никакого IoC тут нет, как нет и никаких функций для вызова.
V>В Хаскеле возможен только IoC вариант, т.е. рантайм-диспетчеризация как в последней строчке: V>
V>Да, до некоторого предела вложенности компилятор при оптимизации производит распространение констант, поэтому часто рантайм-диспетчеризация заменяется на прямо вызов, но в современных С++ эта оптимизация куда глубже/качественней, так шта мой С++ вариант будет соптимизирован лучше.
S>>А nullable reference нужны не чаще чем, скажем, Nullable<int>. Как-то же работает C# с int? безо всяких IoC и коллбеков. Удивительно, да?
V>Не работает, RTFM! ))
Это вы просто пользоваться не умеете. V>Выбрасывает исключения.
А может и не выбрасывать. Ведь неявного преобразования к базовому типу нет, а явное вы можете делать как насильно, через исключения, так и через ??.
V>ОК, дай мне пример языка, которым ты владеешь хотя бы на самом начальном уровне, где есть строгая первоклассная поддержка non-nullable ссылок.
Любой с поддержкой паттерн-матчинга и монады Maybe.
V>В общем, такие языки есть, но их нет в мейнстриме. V>Более того, многие из них достаточно старые.
Вот именно. В том-то и юмор, что речь не о каких-то суперновых изобретениях, а о давно известных вещах. Именно это и имеет в виду Хоар.
V>И да, в Kotlin всё хорошо именно в этом аспекте (не берусь обсуждать другие "достоинства" языка), т.е. там не хуже, чем в других языках, которые нельзя отнести, скажем, к чисто функциональным, т.е. где нет поддержки исключений.
Исключения ортогональны ФП. Жаль, что вы этого не понимаете.
V>Посмотри, например, языки, со встроенной поддержкой зависимых типов, как там обыгрывают подобные сценарии.
Ну, и как же?
V>Да нет, эта фраза показывает, что ты не понимаешь зависимых типов. V>Проблема же не только в null, ссылка вообще может ссылаться на мусор в памяти.
Конечно же нет. Как вы получите такую ссылку? Сославшись на объект, а потом убив его? Невозможно в языках с неявным управлением временем жизни.
Принудительно приведя какой-то мусор вроде целого числа к ссылке? Невозможно в языках без reinterpret cast.
Прибавив число к валидной ссылке? Невозможно в языках, где к ссылкам не прикрутили адресную арифметику.
Если единственный способ проинициализировать ссылку — это сослаться на заведомо существующий объект, да ещё и правильного типа, то ссылка никак не сможет сослаться на мусор в памяти.
Попробуйте сослаться на мусор в памяти на Rust или хотя бы на Lisp.
V>Т.е. простая проверка на не null не решает вопрос окончательно.
А окончательно и не надо. В языках семейства Алгол ситуация "ссылка на мусор" встречается в миллионы раз реже ситуации "ссылка на null".
V>В языках с зависимыми типами индекс не может вылезти за пределы массива никак, прямо на уровне типов.
Ну, вот видите. А говорите — невозможно, невозможно.
V>Точно так же, как ненулевая ссылка не может принять нулевое значение. V>Ссылка вообще не может принять невалидное значение.
V>Уфф... V>Адрес — это индекс ячейки памяти.
Это вы ссылку с указателем путаете. Технически они похожи, а с точки зрения алгебры — нет. В частности, у ссылок нет арифметики.
V>И ведет к асболютно идентичным ошибкам — к неверной реентерпретации памяти. V>Я тебе в C# запросто создам управляемую ссылку на мусор в памяти (произвольный адрес, не обязательно null).
Ну, так С# — компромиссный язык. Я на нём и иммутабл стринг могу поменять, делов-то.
V>Это ты вот это всё имел ввиду под "современным программированием"? ))
Нет конечно.
V>В общем, в языках с зависимыми типами нет принципиальной разницы на допустимые ограничения, контроллируемые системой типов, будь это [0, 1, 2] или [0, 1..] V>Там работает один и тот же механизм.
Отож.
V>Например, в языках с зависимыми типами без исключений может применяться flow control, V>т.е., некий uint[0..MAX_UINT] может быть приведёт к ограниченному типу uint[0..10] через простой if: V>
V>uint array[10] = ...;
V>uint x = readX();
V>func(array[x]); // ошибка компиляции
V>if(x < 10)
V> func(array[x]); // OK, тип переменной x модифицируется контекстом предыдущих вычислений
V>
Ну, всё верно. А к чему тогда все разговоры о какой-то невозможности?
Там же даже проверок значения x внутри func(array[x]) нет.
V>Про произвольную программу речи не идёт, речь идёт об одном аспекте — о программировании в ограничениях на уровне системы типов. V>Эти ограничения не дают неверно интерпретировать память.
Да, именно такую задачу Хоар перед собой и ставил при разработке Алгола.
V>Давай не будем о нормальности. V>Теория зависимых типов была разработана не с 0-ля в 70-е, а первые работы на эту тему были еще в 1925-м, задолго до первых компьютеров. V>Не надо считать всех идиотами. ))
Вы себе противоречите через строчку. То, по-вашему, предотвращение нулевых ссылок и выходов за границу массива — неразрешимая задача, то она была решена сто лет тому назад.
Вы уж как-нибудь определитесь с тем, что именно вы хотите аргументировать.
V>Речь тут не о теоретических вещах, бо с теорией давно всё хорошо, а сугубо об инженерных — о реализуемости, стоимости, практичности.
Ну, и что у нас с реализуемостью, стоимостью, практичностью?
V>А этих структур огромное кол-во, всё их разнообразия в виде встроенных типов данных не предусмотришь, поэтому большинство таких наколенных "безопасных" языков имеют один тип динамических данных — связанный список. )) V>В общем, интерес предоставляют не наколенные языки, а те, которые позволяют экспериментировать с произвольным лейаутом динамических данных в памяти с типизированной гарантией безопасности обращения к данным. V>Т.е., неверно обращающаяся к данным программа не должна уметь компиллироваться.
Ну вот, всё верно пишете.
S>>Кстати, вопросы индексов в массивах давно закрыты: https://www.cs.cmu.edu/~fp/papers/pldi98dml.pdf. Так то про "невозможность в компайл-тайм" — это лично ваши заблуждения. Развивайтесь, читайте.
V>- Ты куда, в баню? V>- Да нет, в баню! V>
V>Проверки в рантайм всё-равно есть, вопрос в том — сколько их. V>Ведь достаточно проверить один раз (или достоверно получить валидное значение по new) и далее распространять значение уже с признаком валидности.
Всё верно. Поэтому вопрос не во вклеивании рантайм-проверок внутрь оператора [], а в возможности устранения этих проверок на этапе компиляции.
V>Это ты в своём C# не понимаешь сути, потому что нет алиасов типов, невозможно отсутствие конструктора структуры без параметров.
Вы опять за деревьями не видите леса. Алиасы, конструкторы без параметров... Это всё частности.
Вопрос в выразительности системы типов.
V>И без переделки исходников, т.к. Optional<T*> и NotNull<T> — это умные указатели, с переопределёнными operator-> и operator*, т.е. их можно использовать там, где ожидался обычный указатель, только теперь можно распространять non-nullable указатели без лишних проверок.
Ну так в С++ не самая плохая система типов. Без переделки исходников — это в том случае, если у вас весь код написан с автовыводом типов. Иначе нужно править сигнатуры у всех функций, которые принимают T*, а вызывают функции с NotNull<T>.
V>Увы, увы. V>Программы, написанные в этом стиле, как по ссылке, построены таким образом, что в функции всегда передаются другие функции-"продолжения". V>Т.е. вся работа основной программы — это бесконечный вызов ф-ий из ф-ий. V>Но стек ведь не бесконечен? Отсюда монады и ленивость.
Монады и ленивость ортогональны рекурсии. Можно сделать в языке прямую поддержку хвостовой рекурсии, и иметь все преимущества ФП плюс гарантию неисчерпания стека безо всяких монад и ленивости.
И наоборот, можно реализовывать ленивость без рекурсии — см. yield return в С#.
V>И до чудес быстродействия там как до звёзд.
V>В 70-х только начали классифицировать типизированные лямбда-исчисления. V>Классификация была нужна для понимания (1) необходимого и достаточного набора конструктов языка для соответствия выранным критериям и (2) для понимания необходимых техник программирования в данном классе ограничений, см лямбда куб (наглядное представление классификации).
И тем не менее, вы же сами пишете — основы теории зависимых типов заложены ещё в 1925 Чему верить-то? V>В 60-х еще вопрос так не стоял, т.к. выразительные ср-ва компилятора диктовались сугубо объемом оперативной памяти, которой располагал компилятор в процессе своей работы.
Это интересная гипотеза. Не очень, правда, понятно, что вы называете "выразительными средствами". Вот, скажем, что там с выразительными средствами PL/1 по сравнению, скажем, с С?
И как они соотносятся с потребностями компилятора в оперативной памяти?
V>Нет никакого противоречия. V>Действительно, было повышенное внимание к теории языков, т.к. была надежда в продвижении статического анализа программ, что необходимо для эффективной компиляции языков с ленивой вычислительной моделью.
Ну, он где надо — там продвинулся. Помимо эффективной компиляции есть ещё много полезностей, проистекающих из статического анализа программ.
V>Как тебе задача — выделить из данной цепочки символов всевозможные подцепочки максимальной длины, встречающиеся более одного раза. V>Оцени сложность в терминах O. V>Умножь на многие мегабайты размеров современных программ. V>Это всего лишь одна из подзадач в процессе оптимизации — склейка самоповторов после стирания типов на одной из стадий оптимизации.
Это не самый эффективный способ склейки самоповторов. Вы исскусственно усложняете себе задачу, сначала складывая все типизированные "подцепочки" в одну цепочку, а потом пытаясь найти повторы внутри этой склейки.
Гораздо эффективнее сразу искать похожести между версиями подцепочек, полученных для разных типов-параметров.
V>Сначала над типами работает бета-редукция и генерирование уникального кода из генерик-представления. V>(А чуть ли не весь код на Хаскель — это сплошные генерики в терминах C#)
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, vdimas, Вы писали:
V> V>Ошибку сейчас совершил ты — имеется ввиду отношение объемов индексов и RAM. V>С древовидными индексами и размерами RAM всё было хорошо в течении нескольких десятилетий, бо рост основного дерева индекса логарифмический от роста кол-ва данных, а размеры RAM росли быстро.
Что такое "основное дерево индекса"? Есть ещё второстепенные деревья?
Что такое "рост дерева"?
Кстати, вопрос про n-tree из соседнего треда всё ещё в силе. Вместе с вопросом про индексы time series, и вероятностные индексы. Мне такие вещи интересны, всегда готов узнать что-то новое в любимой области.
V>Просто надо понимать специфику — сейчас в среднем "реальных данных" всё еще столько, что обычный b-tree индекс справляется на ура.
Не, нужно знать факты. Если бы "обычный b-tree индекс" справлялся на ура, никто бы не задурялся разработкой compressed b-tree индексов.
V>Но появилась новая отрасль — биг дата.
Что удивительно, основные статьи по компрессии индексов были опубликованы за десятилетия до появления термина big data.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
LVV>>У мееня даже была эта книжка в русском переводе. LVV>>Оттуда я почерпнул знание о 3 моделях данных того времени. S> LVV>>Для практики, наверное, не очень было нужно — не было таких объемов, как сейчас. S>Вы совершаете ту же ошибку, что и vdimas. Дело не в объёмах, как таковых, а в соотношении объёмов данных и объёмов RAM.
Наверное. Памяти было сильно меньше, чем сейчас на персоналках.
Даже в 80-х на ЕС-1052 было 512 мегабайт. МЕГА, а не гига.
И на этих мега сидел веь институт.
Моя работа тоже была далека от изысканий в области обработки данных.
1. Я работал на БЭСМ-6 и писал лексер для транслятора с фортрана на фортран.
Дисков на БЭСМ-6 не было.
2. Потом я работал на М-222, где тоже дисков не было.
И работа состояла в обработке оцифрованной космической фотографии. Это в 1976 году.
Фотка была на ленте.
3. Потом я работал на заводе в отделе АСУ на Минск-32.
Писал на русском Коболе.
Но никаких БД там не было. Сортировка наборов данных выполнялась на магнитных лентах.
Хотя диски были.
4. И только потом я попал на ЕС ЭВМ.
Писал на PL-1 задачи для Узбекского Комитета гражданской обороны, но не традиционная обработка данных.
Например, расчет шлейфа облака при химическом ударе/заражении.
И тоже как-то про БД в работе было не слыхать.
5. Потом опять же на EC но другие задачи — на графах.
В общем, я первый раз столкнулся с БД уже в кооперативах.Год примерно 1989.
Когда делал зарплату на заводе Красный Богатырь в Москве...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
А вот где могли быть БД — в КГБ.
Я в 1976 году ходил туда на предмет устройства на работу.
Думал, что у них с квартирами проблем нет.
Вышел облом с квартирой.
А вот задачи там были те, что сейчас решаются повсеместно.
Есть две фотки. Надо определить, один ли человек на фотке или разные.
Или есть отпечатки пальцев — опять же фотка оцифрованная.
Надо найти в базе подобные.
Прикинь — 1976 год!
А задачи — для искусственного интеллекта.
Причем, они уже как-то решались, требовалось улучшать, развивать и т.п.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>>>У мееня даже была эта книжка в русском переводе. LVV>>>Оттуда я почерпнул знание о 3 моделях данных того времени. S>> LVV>>>Для практики, наверное, не очень было нужно — не было таких объемов, как сейчас. S>>Вы совершаете ту же ошибку, что и vdimas. Дело не в объёмах, как таковых, а в соотношении объёмов данных и объёмов RAM. LVV>Наверное. Памяти было сильно меньше, чем сейчас на персоналках. LVV>Даже в 80-х на ЕС-1052 было 512 мегабайт. МЕГА, а не гига. LVV>И на этих мега сидел веь институт.
По теме: на память про память… «История одного байта»
PS: мопед не мой… Но оригинал я действительно читал именно тогда, в самом начале нулевых. Производит впечатление и сейчас, а тогда уж на меня сопливого да зеленого и подавно. До сих пор перед глазами: ночь, бульвар у универа, ролики на ногах, Эрик Клэптон в ушах... И этот самый пресловутый байт... байт... байт.
Здравствуйте, LaptevVV, Вы писали:
C>>По теме: на память про память… «История одного байта» LVV>Спасибо! LVV>Мне знакомы эти проблемы. LVV>В 80-х писал ось на бортовую машину...
"Бортовая машина" чего? Самолетка? Снарядка (торпедка)? Космос?
LVV>>Мне знакомы эти проблемы. LVV>>В 80-х писал ось на бортовую машину... C>"Бортовая машина" чего? Самолетка? Снарядка (торпедка)? Космос?
Для морячков.
Заводской номер 1 (ОДИН!)
Как потом оказалось, машина не вытягивала ВСЕ необходимы задачи 10 раз в секунду.
Делала только 5.
Потом уже в 90-е краем уха слыхал, что сделали типа учебный комплекс,
и стояла наша система в Сосновом Бору несколько лет — учились на ней чему-то там...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
LVV>>>В 80-х писал ось на бортовую машину... C>>"Бортовая машина" чего? Самолетка? Снарядка (торпедка)? Космос? LVV>Для морячков. LVV>Заводской номер 1 (ОДИН!) LVV>Как потом оказалось, машина не вытягивала ВСЕ необходимы задачи 10 раз в секунду. LVV>Делала только 5. LVV>Потом уже в 90-е краем уха слыхал, что сделали типа учебный комплекс, LVV>и стояла наша система в Сосновом Бору несколько лет — учились на ней чему-то там...
О как! Флот какой? Северный или еще какой?
Здравствуйте, LaptevVV, Вы писали:
LVV>В общем, я первый раз столкнулся с БД уже в кооперативах.Год примерно 1989. LVV>Когда делал зарплату на заводе Красный Богатырь в Москве...
Ну, я тоже столкнулся с СУБД в том же 1989. Ребус (нащ dBase III), потом Clipper'87, немножко фокспры и так далее.
Но это — локальные аномалии, неинтересные с т.з. информатики в целом.
Вот я в метро впервые проехался в 1986м. Штош теперь, говорить, что "первый метрополитен появился в середине 80х, а до этого для него не было достаточного пассажиропотока"?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
V>>Ошибку сейчас совершил ты — имеется ввиду отношение объемов индексов и RAM. V>>С древовидными индексами и размерами RAM всё было хорошо в течении нескольких десятилетий, бо рост основного дерева индекса логарифмический от роста кол-ва данных, а размеры RAM росли быстро. S>Что такое "основное дерево индекса"? Есть ещё второстепенные деревья?
Есть неоднородность представления дерева на листьях в зависимости от вида индекса и способа представления.
Иногда лист индекса может содержать ренж, т.е. индексировать сразу набор записей, иногда явный список записей, иногда единичную запись.
То бишь, оценка размера деревянного индекса может быть как log(N), так и log(N) + N.
Для большинства первичных ключей, которые имеют целочисленную природу и по которым записи сортированы, деревянный индекс имеет минимальное представление, бо хранит только ренжи в листьях.
S>Что такое "рост дерева"?
Действительно, что такое рост? ))
S>Кстати, вопрос про n-tree из соседнего треда всё ещё в силе. Вместе с вопросом про индексы time series
Мы это уже обсуждали.
В 1С неплохо покрыто.
Есть валюты, есть даты изменений валют, тебе надо делать join по датам от таблицы операций на таблицу курсов валют, а в той содержатся, допустим, только даты изменений курса, но не курс на каждый день.
S>и вероятностные индексы.
Мы это тоже уже обсуждали — которые имеет смысл перестраивать от статистики, инфы более чем полно.
S>Мне такие вещи интересны, всегда готов узнать что-то новое в любимой области.
Ничего нового в этой области давным давно нет.
По крайней мере в теории.
В реализации, может, сопли какие подберут, шероховатости причешут и т.д.
Но это не "новые концепции", это убожество в плане такой вещи как развитие.
"Новостью" в плане реляционных СУБД последний примерно десяток лет является то, что реляционные СУБД повернулись лицом к хранению слабоструктурированных данных, т.е. в них вылизали достаточно примитивный сценарий работы с отдельными таблицами, у каждой из которых единственный индекс-ключ, но размер таблиц большой.
Просто в этом примитивном сценарии NoSql серваки надирали "традиционным" реляционкам попку как младенцам, те теряли лицо.
Ну а больше-то и вспомнить нечего...
V>>Просто надо понимать специфику — сейчас в среднем "реальных данных" всё еще столько, что обычный b-tree индекс справляется на ура. S>Не, нужно знать факты. Если бы "обычный b-tree индекс" справлялся на ура, никто бы не задурялся разработкой compressed b-tree индексов.
Вылизыванию нет границ.
Но ускорение в разы за счёт вполне себе инженерных практик vs изменение сложности в терминах O за счёт изобретения новых алгоримтов — разные вещи.
V>>Но появилась новая отрасль — биг дата. S>Что удивительно, основные статьи по компрессии индексов были опубликованы за десятилетия до появления термина big data.
1. Компрессия данных — это инженерное решение, выдуманое раньше. Т.е. отсутствует формула изобретения.
2. Опять ты порешь эту чушь про РСУБД в 60-х.
3. За десятилетие до появления big data сами РСУБД только 5 лет как существовали во вменяемом исполнении.
Но ты пенял на "глупых программистов прошлого", что они не напомнили тебе из 60-х годов, что в будущем появятся СУБД и в них тоже можно будет хранить данные с компрессией!!!
Только не забудьте что компрессию в СУБД использовать тоже можноооо... (эхо, эхо)...
Здравствуйте, LaptevVV, Вы писали:
LVV>В общем, я первый раз столкнулся с БД уже в кооперативах.Год примерно 1989.
Первые СУБД только появились в начале 80-х и были с нынешней колокольни убоги.
Но вот как раз к 89-му более-менее перешли в юношеский возраст.
В 92-м году уже можно стало пользоваться.
Здравствуйте, Carc, Вы писали:
C>PS: мопед не мой… Но оригинал я действительно читал именно тогда, в самом начале нулевых. Производит впечатление и сейчас, а тогда уж на меня сопливого да зеленого и подавно. До сих пор перед глазами: ночь, бульвар у универа, ролики на ногах, Эрик Клэптон в ушах... И этот самый пресловутый байт... байт... байт.
Такое знакомо по архитектуре Intel 8031 — там страницы кода по 256 байт, только в пределах страницы можно делать условные переходы.
Т.е. не смещение в пределах +-128, а можно указать только младший байт адреса в команде.
Или делать безусловный jump на другую страницу кода.
В исходнике на асме у тебя никаких адресов перед глазами нет, они выясняются только после компиллирования, и начинается возня...
Одного-нескольких байт не хватало часто, приходилось постоянно задействовать серое вещество. ))
Здравствуйте, vdimas, Вы писали:
V>Есть неоднородность представления дерева на листьях в зависимости от вида индекса и способа представления. V>Иногда лист индекса может содержать ренж, т.е. индексировать сразу набор записей, иногда явный список записей, иногда единичную запись.
Мы всё ещё про B-tree? Или о чём? Что это за индекс, лист которого индексирует единичную запись?
V>То бишь, оценка размера деревянного индекса может быть как log(N), так и log(N) + N.
Повторюсь: что такое "размер" деревянного индекса? Общее место под хранение всего этого индекса?
Было бы интересно увидеть индекс с логарифмической (или хотя бы сублинейной) асимптотикой этого параметра.
V>Для большинства первичных ключей, которые имеют целочисленную природу и по которым записи сортированы, деревянный индекс имеет минимальное представление, бо хранит только ренжи в лстьях.
Что такое "ренж"?
V>Действительно, что такое рост? ))
Ну, так всё же? Обычно в рассуждениях про древовидные структуры оперируют двумя параметрами: размер и глубина. Вы, как обычно, вводите какую-то новую терминологию, неведомую простым смертным.
S>>Кстати, вопрос про n-tree из соседнего треда всё ещё в силе. Вместе с вопросом про индексы time series
V>Мы это уже обсуждали.
Не припомню такого. И вопрос про n-tree тоже пока что в силе. V>Есть валюты, есть даты изменений валют, тебе надо делать join по датам от таблицы операций на таблицу курсов валют, а в той содержатся, допустим, только даты изменений курса, но не курс на каждый день.
И как же устроен индекс, который позволяет эффективно выполнять эту операцию? Или нет, давайте так: что мешает СУБД выполнять такую операцию эффективно при использовании B-tree индекса?
Или даже так: чем отличается специализированный time series индекс для этой задачи от банального B-tree?
S>>и вероятностные индексы.
V>Мы это тоже уже обсуждали — которые имеет смысл перестраивать от статистики, инфы более чем полно.
Дайте же ссылку на примеры этой инфы, которой "полно". "Перестраивать от статистики" — это интересная идея, но таких индексов я в промышленном применении не знаю. По крайней мере для скалярных данных.
V>Ничего нового в этой области давным давно нет.
Нового для меня. V>По крайней мере в теории.
Ну, вот PGM-индекс придумали.
V>"Новостью" в плане реляционных СУБД последний примерно десяток лет является то, что реляционные СУБД повернулись лицом к хранению слабоструктурированных данных, т.е. в них вылизали достаточно примитивный сценарий работы с отдельными таблицами, у каждой из которых единственный индекс-ключ, но размер таблиц большой.
Это как раз ничего нового. Те же пестни на новый лад.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
V>>Есть неоднородность представления дерева на листьях в зависимости от вида индекса и способа представления. V>>Иногда лист индекса может содержать ренж, т.е. индексировать сразу набор записей, иногда явный список записей, иногда единичную запись. S>Мы всё ещё про B-tree?
Мы про хранение индексов.
А это не чисто-теоретическое B-tree.
S>Или о чём?
Да о твоём странном невежестве и логических ошибках.
Сорри, не дописал пред. сообщение (отвлекли), можно вернуться, прочитать дописанный вариант.
S>Что это за индекс, лист которого индексирует единичную запись?
А что ты вообще делаешь на сайте программистов? ))
Лист индекса не является листом бинарного дерева, это служебная запись о координатах целевой записи или нескольких их.
Т.е. узел дерева — это не единичный тип данных, а сумма типов:
V>>То бишь, оценка размера деревянного индекса может быть как log(N), так и log(N) + N. S>Повторюсь: что такое "размер" деревянного индекса? Общее место под хранение всего этого индекса?
И зачем ты повторяешь свои глупости?
Мы говорили про RAM.
S>Было бы интересно увидеть индекс с логарифмической (или хотя бы сублинейной) асимптотикой этого параметра.
Кошмар... ))
Выше схематично расписан тип листового узла индекса на Хаскель (на знакомом тебе C# описывать union-ы через иерархию наследников слишком многословно).
Еще выше картинка.
Включи воображение и представь, что на картинке в листовом узле не список единичных узлов, а одна записись на диапазон их, когда значения ключа идут без пропусков в этом диапазоне и соотв. строки данных хранятся на одной странице.
V>>Для большинства первичных ключей, которые имеют целочисленную природу и по которым записи сортированы, деревянный индекс имеет минимальное представление, бо хранит только ренжи в лстьях. S>Что такое "ренж"?
Диапазон.
V>>Действительно, что такое рост? )) S>Ну, так всё же?
Вопрос в силе.
S>Обычно в рассуждениях про древовидные структуры оперируют двумя параметрами: размер и глубина. Вы, как обычно, вводите какую-то новую терминологию, неведомую простым смертным.
Я гарантирую, что никакой новой терминологии.
Просто ты несешь какую-то околесицу, на которую я уже не знаю, как реагировать...
У меня и так же перебор язвительности (твои манеры заразны, старайся их контроллировать).
Ну какие в опу два параметра "размер и глубина" для сбалансированного бинарного дерева, Синклер, у тебя аккаунт украли?
Длина от корня до любого листа не может отличаться более чем на 1, т.е. одно через другое представимо, если речь об оценке размера дерева, т.е. об общем кол-ве узлов.
И расти может общее кол-во узлов дерева, ес-но.
Какие там еще могли быть варианты, что ты так упорно уточнял?
V>>Мы это уже обсуждали. S>Не припомню такого. И вопрос про n-tree тоже пока что в силе.
Какой именно вопрос?
И почему ты задаёшь подобные бестолковые вопросы?
Нельзя ли уже по делу или не отнимать у коллег время?
V>>Есть валюты, есть даты изменений валют, тебе надо делать join по датам от таблицы операций на таблицу курсов валют, а в той содержатся, допустим, только даты изменений курса, но не курс на каждый день. S>И как же устроен индекс, который позволяет эффективно выполнять эту операцию? Или нет, давайте так: что мешает СУБД выполнять такую операцию эффективно при использовании B-tree индекса? S>Или даже так: чем отличается специализированный time series индекс для этой задачи от банального B-tree?
Отличается представлением даных.
Разумеется, на бинарном дереве эта задача решаема.
Просто само бинарное дерево не нужно.
Бинарное дерево — это ответ на задачи про удалить/добавить в произвольное место/сбалансировать.
На самом-то деле требуется обычный бинарный поиск, где бинарное сбалансированное дерево лишь занимается подготовкой данных к такому поиску.
Но есть более простые сценарии:
— значения добавляются только с монотонно увеличивающимся ключом;
— старые записи никогда не удаляются.
В итоге, дерево не нужно, заменяется в представлении на сортированный плоский список (или набор таких списков), т.е. вместо дорогой итерации в памяти по графу дерева происходит двоичный поиск по плоскому списку (или по золотому сечению, что для бухгалтерии чаще эффективней). Представление такого индекса в памяти примерно вчетверо экономнее классического b-tree индекса и работает оно в несколько раз шустрее.
И мы это уже обсуждали когда-то.
Как минимум я тебе упоминал про time series и ты соглашался, т.е. старательно делал вид, что понимаешь, о чём речь. ))
Разумеется, эта техника подходит не только для time series, оные просто сочная отсылка к примеру подобного сценария.
V>>Мы это тоже уже обсуждали — которые имеет смысл перестраивать от статистики, инфы более чем полно. S>Дайте же ссылку на примеры этой инфы, которой "полно". "Перестраивать от статистики" — это интересная идея, но таких индексов я в промышленном применении не знаю. По крайней мере для скалярных данных.
А зачем тебе оговорка про скалярный тип данных?
В чём подвох?
Чем не устраивает пара (integer, integer)?
И мало ли, чего ты там не знаешь?
Речь идёт о формировании диапазонов ключей в листах в b-tree таким образом, чтобы уменьшить вероятность перестроения дерева при добавлении элементов или свести эти перестроения к минимуму.
S>Ну, вот PGM-индекс придумали.
Нет, не придумали.
Никакого нового принципа индексирования не показали.
Вот я тебе показал сжатие информации через хранение диапазонов ключей в единичной записи листового узла (а записей в листовом узле может быть несколько).
Но это не тянет на "придумал", это и так давно известно, с самого что ни на есть начала этой предметной области.
Просто у тебя какая странная эрудиция, с хаотическими белыми пятнами.
По одному и тому же предмету то демонстрируешь глубокое владение мало кому интересными тонкостями, то плаваешь в самых базовых вещах, вызываешь недоумение.
V>>"Новостью" в плане реляционных СУБД последний примерно десяток лет является то, что реляционные СУБД повернулись лицом к хранению слабоструктурированных данных, т.е. в них вылизали достаточно примитивный сценарий работы с отдельными таблицами, у каждой из которых единственный индекс-ключ, но размер таблиц большой. S>Это как раз ничего нового. Те же пестни на новый лад.
Однако же, ускорили почти вдвое (если это не устаревшая уже информация, т.к. тщательно не слежу).
И там никакой "придумки".
Обычное вылизывание сугубо инженерного плана способно изменять характеристики в некое кол-во раз.
Но неспособно изменять в плане оценки сложности O, а интересует именно это.
Например, в time series такая же оценка сложности кол-ва операций как у бинарного дерева, но работает в несколько раз быстрее.
В зависимости от как повезет до 10-20 раз быстрее.
Вдогонку, забыл самое главное про time series.
Cамую мощь time series показывают не при отдельном поиске значения, а при join.
В этом случае реальная стоимость поиска значения приближается к O(1) вместо O(log(N)), т.к. курсор или остаётся на текущей строке курсов валют, или передвигается на одну запись к предыдущей дате, т.е. итерироваться надо от новых дат к старым.
(в теории возможен seek на сколько угодно записей при линейном поиске, но на практике средний шаг приближается к 1)
Здравствуйте, vdimas, Вы писали:
V>Мы про хранение индексов. V>А это не чисто-теоретическое B-tree.
S>>Что это за индекс, лист которого индексирует единичную запись?
V>А что ты вообще делаешь на сайте программистов? ))
Развлекаюсь. V>Лист индекса не является листом бинарного дерева, это служебная запись о координатах целевой записи или нескольких их.
Эмм. Откуда появилось слово "бинарное"? Вы где-то видели бинарное B-дерево?
V>Т.е. узел дерева — это не единичный тип данных, а сумма типов: V>
Удивительное рядом. Я так понял, что ваш RecordRangeRef должен обработать экзотический случай неуникального кластерного индекса? Нет, это работает не так.
Непонятно, почему у вас в промежуточных узлах всего по две ссылки на детей, куда из них подевались значения ключей.
V>И зачем ты повторяешь свои глупости?
Я не повторяю, я пытаюсь нащупать смысл в ваших постах. V>Мы говорили про RAM.
Пока что мы пытаемся выяснить, что вы называете "ростом дерева".
V>Выше схематично расписан тип листового узла индекса на Хаскель (на знакомом тебе C# описывать union-ы через иерархию наследников слишком многословно). V>Еще выше картинка.
V>Включи воображение и представь, что на картинке в листовом узле не список единичных узлов, а одна записись на диапазон их, когда значения ключа идут без пропусков в этом диапазоне и соотв. строки данных хранятся на одной странице.
Попробуем разобрать эту мысль. Начнём с конца.
0. Попадут ли строки данных на одну страницу или нет зависит не от наличия пропусков в диапазоне ключей, а от соотношения размера записи и страницы.
1. Ну, ок, мы, наверное, можем сыграть на том, что у нас записи с ключами 58, 60, 61, 62, 63, 65 попали на одну страницу, тогда мы типа "экономим место" в индексе, сославшись сразу на четыре из них в одной KeyEntry вида (60, <Page>, 1, 4). Но какой смысл оставлять в листовом узле только эту KeyEntry? Он размером в 8кб, туда можно ещё много KeyEntries напихать. Так что по-прежнему непонятен смысл такого листа, который индексирует единичную запись. Тем более, что записей-то тут на самом деле ажно 4.
Ну, и, повторюсь, именно так никто не делает, т.к. это неэффективно.
V>Диапазон.
Это всё про ту же картинку?
V>Вопрос в силе.
А сила — в правде.
S>>Обычно в рассуждениях про древовидные структуры оперируют двумя параметрами: размер и глубина. Вы, как обычно, вводите какую-то новую терминологию, неведомую простым смертным.
V>И расти может общее кол-во узлов дерева, ес-но. V>Какие там еще могли быть варианты, что ты так упорно уточнял?
Ну, ок. Вот только количество узлов дерева растёт как O(1) от количества индексируемых записей. Потому я и уточнял, что бред выходит.
V>Какой именно вопрос?
Что такое n-tree и благодаря чему оно эффективнее чем B-tree. V>И почему ты задаёшь подобные бестолковые вопросы?
Потому что то, что вы пишете, выглядит как бред. И либо я чего-то фундаментально не понимаю, либо вы. Я очень надеюсь на первое — потому и выясняю такие простые вещи.
V>>>Есть валюты, есть даты изменений валют, тебе надо делать join по датам от таблицы операций на таблицу курсов валют, а в той содержатся, допустим, только даты изменений курса, но не курс на каждый день. S>>И как же устроен индекс, который позволяет эффективно выполнять эту операцию? Или нет, давайте так: что мешает СУБД выполнять такую операцию эффективно при использовании B-tree индекса? S>>Или даже так: чем отличается специализированный time series индекс для этой задачи от банального B-tree?
V>Отличается представлением даных. V>Разумеется, на бинарном дереве эта задача решаема.
Откуда опять этот термин "бинарное дерево"???? В СУБД никаких бинарных деревьев не используют с 1970х.
V>Но есть более простые сценарии: V>- значения добавляются только с монотонно увеличивающимся ключом; V>- старые записи никогда не удаляются.
V>В итоге, дерево не нужно, заменяется в представлении на сортированный плоский список (или набор таких списков), т.е. вместо дорогой итерации в памяти по графу дерева происходит двоичный поиск по плоскому списку (или по золотому сечению, что для бухгалтерии чаще эффективней). Представление такого индекса в памяти примерно вчетверо экономнее классического b-tree индекса и работает оно в несколько раз шустрее.
Ну, во-первых, непонятно, с чего это вдруг "итерация по графу дерева" будет шибко дороже двоичного поиска.
Во-вторых, непонятно, влезет ли весь нужный нам список в RAM или нет — точнее, почему мы должны полагаться на его влезаемость. Если мы говорим о данных на диске, то у бинарного поиска всё будет плохо с нагрузкой на IO.
В-третьих, может по сравнению с бинарным деревом представление и будет вчетверо более эфффективным, а вот по сравнению с B-деревьями — нет. Там будут копейки разницы, которые многократно окупаются дружелюбием к кэшу.
V>А зачем тебе оговорка про скалярный тип данных? V>В чём подвох?
В том, что словосочетание "вероятностные индексы" я встречал только в применении ко всяким задачам кластеризации документов и "поискам по релевантности". V>Чем не устраивает пара (integer, integer)?
Вполне устраивает. Расскажите на примере пары (integer, integer).
V>И мало ли, чего ты там не знаешь? АV>Речь идёт о формировании диапазонов ключей в листах в b-tree таким образом, чтобы уменьшить вероятность перестроения дерева при добавлении элементов или свести эти перестроения к минимуму.
Можно подробнее? Раз это хорошо исследованная тема, то наверняка вам будет легко найти ссылку на статью по этой теме.
S>>Ну, вот PGM-индекс придумали.
V>Нет, не придумали. V>Никакого нового принципа индексирования не показали. V>Вот я тебе показал сжатие информации через хранение диапазонов ключей в единичной записи листового узла (а записей в листовом узле может быть несколько).
Ну, это вы как раз пытаетесь изобрести PGM индекс с ограничением на коэффициент линейности равный единице. Но ваш дизайн всё ещё менее эффективен, чем классический кластерный индекс в MS SQL на основе B+-дерева.
V>Но это не тянет на "придумал", это и так давно известно, с самого что ни на есть начала этой предметной области. V>По одному и тому же предмету то демонстрируешь глубокое владение мало кому интересными тонкостями, то плаваешь в самых базовых вещах, вызываешь недоумение.
Ну, никогда же ведь не поздно научиться чему-то новому.
V>Однако же, ускорили почти вдвое (если это не устаревшая уже информация, т.к. тщательно не слежу).
"Вдвое" — это какие-то несущественные вещи. Интересна асимптотика, и ускорения в разы.
Ну, вот как ребята в MemSQL — которые устали уговаривать начальство в Редмонде запилить columnStore или хотя бы bitmap indices, и в итоге получили реализацию, которая при выполнении select count(*) по предикату окучивает больше 200 записей за такт.
V>Например, в time series такая же оценка сложности кол-ва операций как у бинарного дерева, но работает в несколько раз быстрее. V>В зависимости от как повезет до 10-20 раз быстрее.
Повторюсь: зачем вы сравниваете с бинарными деревьями, которые никто в здравом уме не применяет? B-деревья работают быстрее даже чисто-в-памяти, а при работе с диском так и вообще говорить не о чем.
V>Вдогонку, забыл самое главное про time series. Да, я тоже внимание обратил. V>Cамую мощь time series показывают не при отдельном поиске значения, а при join. V>В этом случае реальная стоимость поиска значения приближается к O(1) вместо O(log(N)), т.к. курсор или остаётся на текущей строке курсов валют, или передвигается на одну запись к предыдущей дате, т.е. итерироваться надо от новых дат к старым.
Впрочем, ровно как и B+-дерево. Так что пока непонятно, что же такое time series индекс, и чем именно он отличается.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, vdimas, Вы писали:
V>Первые СУБД только появились в начале 80-х и были с нынешней колокольни убоги.
Вижу, домашнюю работу вы так и не выполнили.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
V>Например, в языках с зависимыми типами без исключений может применяться flow control, V>т.е., некий uint[0..MAX_UINT] может быть приведёт к ограниченному типу uint[0..10] через простой if: V>
V>uint array[10] = ...;
V>uint x = readX();
V>func(array[x]); // ошибка компиляции
V>if(x < 10)
V> func(array[x]); // OK, тип переменной x модифицируется контекстом предыдущих вычислений
V>
Это все конечно здорово, но не в учебных задачах, а на практике чаще нужно работать примерно так:
uint n = readNumberOfRecordsFromFile(filename); //Откуда-то извлекаем количество элементов. Если оно вообще известно.
uint array[n] = ... //Всякие malloc и new
uint x = readX();
func(array[x],n);
....
И идут все эти зависимые типы лесом в этом случае и остается просто проверка в рантайме, что x<n
Здравствуйте, Michael7, Вы писали:
M>Это все конечно здорово, но не в учебных задачах, а на практике чаще нужно работать примерно так:
M>
M>uint n = readNumberOfRecordsFromFile(filename); //Откуда-то извлекаем количество элементов. Если оно вообще известно.
M>uint array[n] = ... //Всякие malloc и new
M>uint x = readX();
M>func(array[x],n);
M>....
M>
M>И идут все эти зависимые типы лесом в этом случае и остается просто проверка в рантайме, что x<n
В современных языках с зависимыми типами неограниченный uint может быть преобразован в ограниченный двумя способами:
Этому убогому подходу уже лет 30, если не больше, я фиг его знает, почему на него до сих пор некоторые фапают.
Выразить твой пример в этой технике непросто, читабельность стремится примерно к 0-лю.
2. В случае более продвинутой поддержки ЗТ компилятор дополнительно умеет модифицировать тип переменной через flow control.
Например, в коде динамически проверяется переменная x и далее её максимальное значение статически ограничено динамическим n.
if(x < n)
func(array[x]); // OK
То бишь, компилятор языка с ЗТ не оперирует конкретными значениями x и n, он оперирует ограничениями, в данном случае для доступа к массиву требуется ограничение x<count_of(array).
if(x < n) {
x += 10;
x -= 8;
x -= 2;
func(array[x]); // опять OK
}
И до тех пор, пока компилятор способен трекать ограничение над x, дополнительные проверки индекса при доступе к массиву уже не требуются.
Например, в дотнете происходит проверка индекса при каждом обращении к массиву.
Аналогично насчёт валидности ссылочных переменных — распространяемая валидная ссылка не требует многократной проверки на валидность в каждом месте своего использования.
Флот какой? Северный или еще какой?
