2 года руковожу небольшой группой. Ремарки:
— «покажите», «заразите», «объясните»… — это работает только для поддающихся внушению и готовых изменятся, некоторых вы просто сотрясанием воздуха с места не сдвините
— не нужно учить паттернам (читай — фактам), человек должен ДУМАТЬ САМ, и он в процессе переизобретёт ваши паттерны
— не нужно сидеть и ревьювить код (против стилевого анализатора ничего против не имею) — нужно правильно давать правильные задания и следить за их реализацией по ходу работы. И вообще зачем нужен такой программист, после которого нужно потратить тонну времени на ревью, исправление, переревью… — так лучше пусть уж руководитель пишет, сэкономиться время/деньги. По сути это проблема — следствие невыполнения следующего пункта.
— нужно разделять кодера и разработчика. Архитектурой должно заниматься ограниченное количество профессионалов. Кодеру должно быть дано достаточно детальное задание, желательно со структурой классов, диаграммой состояний и т.д. Тогда и результат будет предсказуем. У нас вообще не любят планировать и разрабатывать, у нас принято сразу реализовывать, а потом героически бороться с результатом.
— человек — существо ленивое и хитрое и всегда будет использовать возможность работать по-меньше и по-хуже если это допустимо. В конце концов это бизнес, а людей способных работать на идею немного. Поэтому организация и мотивация труда должна быть на высоте. И не требуйте от людей того, чего сами не делаете!
Расчитывать на распределение входных данных нельзя, для этого как раз счиатем хеш. Дальше, если по List|Array[0xFFFFFF] (затраты 67 Мб) мы имеем быстрый переход в область где начинаются коды с такими же первыми 3-мя байтами (возьмём этот случай, без вложенности), то теперь нам нужно найти такой же код обходя элементы. Т.е. либо это связанный список (400 Мб только на ссылках), либо просто список на каждый элемент масива (201 Мб), либо это один сплошной (разбитый на части), но отсортированный, а после проиндексированный сплошным проходом… По сути, в моей реализации, я могу заказать хешсегмент размером 0xFFFFFF и это будет подобная вещь, цепочка обхода будет в районе 100 / 16 = 6.
А можно поподробнее по поводу «Маппинг «N байт ключа»- «список указателей»»?
Спасибо за идею ужатия строки, действительно если использовать только латиницу, то мы умещаемся в половину байта и всю строку мы упаовываем в 8 байт! Надо уточнить у заказчика по поводу ограничения латиницей.
Разбивать на простые типы идея правильная, но у нас 16 — это максимальная длина, внутри этого буфера хранится ключ фиксированной длины и дальше довесок с нуль-терминатором. Короче, задача универсальнее чем то что я описал в статье. Поэтому искал способ работы масивом.
Вопрос по поводу нескольких хештаблиц: получается что для поиска нужно обойти все таблицы, и каждая будет вычислять хеш? Т.е. мне интерессно сколько было таблиц и сколько при такой организации займет поиск. Если так прикинуть, что там хешсегмент 1:1 (400 Мб), что и дает такую скорость + избыток 8 Б на вхождение (800 Мб) = 1200 Мб. Я так понимаю вы заранее заказывали ёмкость словаря, чем обошли проблему двукратного роста. Вот и вышло 2,4 + 1,2 = 3,6.
Мы не знаем сколько будет данных, может 1 тыс., может 100 млн., поэтому память заранее выделяем лишь с небольшим запасом (параметр линейного роста листов в статье). Если памяти много, можем этим параметром выделить очень большой запас, в результате ( в идеале) каждая цепочка выделится 1 раз и затем свернётся по факту в конце. Т.е. проблем со вставкой я здесь не вижу.
А вот с поиском даже спорить не буду. Тут сделано очень просто в угоду экономии памяти. Я понимаю, что есть более выгодные поисковые структуры. Можно вас попросит, если вы имеете такой опыт, прикинуть сколько будет занимать памяти организация инфраструктуры пирамиды? И как вы предполагали делать поиск после сортировки, бинарно или как?
Вспомнил, когда-то работая в Terrasoft CRM, видел тонны кода для де/сериализации нативных объектов и потом когда уже перешел на C# увидел, что это занимает 3 строчки просто обалдел. Такая же история была со связыванием данных в памяти с визуальными компонентами.
Пример 1. Гибкость. Я пишу форму, которая умеет редактировать любой(!) объект, основываясь на типовой информация в рантайме (RTTI или рефлексия), например используя PropertyGrid. Можно сделать проверку обязательных полей и любую каcтомную валидацию основываясь на атрибутах. Атрибутами же упраляем доступностью полей для редактора, можно назначить свой редактор для поля и т.д. Редактируются вложенные объекты, включая коллекции. Кода немного, используются родные возможности. Вот например DevExpress FilterControl умеет на основе RTTI строить сложные фильтрационные выражения по свойствам любого объекта, которые потом можно использовать в where SQL. Пользу от этого просто сложно перееоценить. У нас одна форма используется для редактирования: конфигурационных файлов, настроек пользователя и системы (классы в БД), параметров отчетов.
Пример 2. Мощные фреймворки для бизнес задач. Я могу поднять трехзвенку (включая веб с рич клиентом) просто за отрицательное время практически без кода и поработав немного дизайнерами, используя: EntityFramework, WCF, RIAService, Silverlight. Классический веб можно через ASP Dynamic Data.
— Только МС и всем тем, кто может в студии галочку выставить, чтобы ASM показывало
Есть реальный опыт, чем можете поделитсья?
— WinForms — летает
Жутко тормозит даже на современном железе, многие жалуются. Поставьте бекграунд на форме, гриду с парой десятком колонок, якоря и увидите. Возьмите VCL Delphi 7 и вы увидите что такое «не тормозит».
— WPF на железе 2005 года — летает
В базовом функционале возможно. Пробовал один заокругленный прямоугольник с анимированным внешним глоу — уже ощутил тормоза. Но в чистом WPF у меня опыта мало.
SL — тоже все летает, если руки правильно заточены
У нас до сих пор один проект на эксплуатации. В целом неплохо, но проскоки кадров наблюдаются. Плюс глюков там просто тьма. Пока реализовали нормальные окна не глючащие при изменении масштаба все волосы на себе повыдергивали.
— Это проблема всех проектов, где работает больше 1 человека
Мне не интерессно сколько там человек работает. Если в структурах нет ООП, то я не должен уметь перегружать GetHashCode, Equals и ToString, а если могу, то не только их.
— О каких коллекциях конкретно идет речь?
Скажите чем отличаются ArrayList, List и Collection и почему они так названы? Ну и помогите разгребсти следующую кашу: OrderedDictionary, StringDictionary, NameValueCollection, ListDictionary, SortedList, SortedDictionary, Dictionary, Hashtable…
— Скорость разработки или скорость выполнения конкретных методов?
Скорость выполнения конечно.
Попробую без купюр указать плюсы и минусы С#:
— вуаль вирутальной машины — что там происходит, только Майкрософту изветсно
— тормознутые визуальные библиотеки
— местами вознакают сомнения в лаконичности архитектуры — не поймешь чего больше, то ли правил, то ли исключений из правил
— создает кашу из старых и новых библиотек, где уже ноги можно поломать тут тебе Generic версии и не Generic и что использовать не всегда понятно. Чего стоит разобраться в надцати коллекций.
— скорость меньше чем у нативного кода
…
+ кроссплатформенность — если оно собралось и работает, скорее всего оно будет работать везде где есть эта версия .Net — остальное проблема Майкрософт (я не учитываю инфоки платформы и прочие не кроссплатформенные вещи)
+ у вас не будет проблем с утечкой памяти на таком уровне как это возможно на нейтиве
+ RTTI — рефлексия, это кул и позволяет очень много. Декларативное програмирование.
+ возможность использовать для десктопных, мобильных и веб приложений (включая клиентские)
+ большое количество библиотек
+ развитие семимильными шагами
…
Да я из гугла не вылезал. Нам нужна была своя реализация, которую можно поддерживать. Хотя очень интересно, как поведет себя готовое универсальное решение типа memcached на данных объемах. На х64 нет предела в 2 Гб и память очень весело выделяется даже после окончания физичечкой. На машине, указанной в примерах с 4 Гб я умудрялся выделять около 8 Гб. Всё тормозило, но работало. Так вот вам и ответ- всё будет тормозить. Но это не проблема, у нас свои сервера с экслюзивным доступом, так что 8 Гб физики нам должно хватить на долго.
Честно говоря не сталкивался с пирамидальной сортировкой, но бегло прбежав описание засомневался. Если только там нужны перемещения между массивами, то это затраты на копирование памяти, я к тому, что в .Net вставка нового элемента в массив — это создание нового массива на 1 больше, копирование туда старого и только тога вставка (не важно в какую часть — в конец или середину). Не совсем понял сколько тянет инфраструктура самого дерева. Да и фразы «на почти отсортированных массивах работает столь же долго, как и на хаотических данных» не вдохновляют, тем более, что вы собираетесь сортировать после каждой вставки. Не понял фразы «скорость работы хэшей, особенно, если под каждый элемент выделять память, может быть существенно меньше» — память под занчение нужно выделять в любом случае, а хешсегмент фиксирован. «Поэтому, если поиск осуществляется чаще...» — в нашем случае нужно расчитывать на 1-разовую вставку 100 млн. и одноразовый поиск среди других 100 млн., поэтому поиск не чаще и даже наоборот — вставляться как правило будет на половину меньше, а сравниваемая сторона всегда окло 100 млн. и все время растет.
Какой например? Я так для себя понял, что можно сделать так:
— загружаем равными блоками (считаем одним массивом со сквозным индексом)
— сортируем
— умеем превращать ключ в индекс массива
Оракл решал задачу сравнения двух таблиц (100 млн. vs 50 млн.) на сортированных данных — несколько часов, на несортированных — не дожидались. Выборка шла по ключам. В памяти это происходит за 15 минут.
— «покажите», «заразите», «объясните»… — это работает только для поддающихся внушению и готовых изменятся, некоторых вы просто сотрясанием воздуха с места не сдвините
— не нужно учить паттернам (читай — фактам), человек должен ДУМАТЬ САМ, и он в процессе переизобретёт ваши паттерны
— не нужно сидеть и ревьювить код (против стилевого анализатора ничего против не имею) — нужно правильно давать правильные задания и следить за их реализацией по ходу работы. И вообще зачем нужен такой программист, после которого нужно потратить тонну времени на ревью, исправление, переревью… — так лучше пусть уж руководитель пишет, сэкономиться время/деньги. По сути это проблема — следствие невыполнения следующего пункта.
— нужно разделять кодера и разработчика. Архитектурой должно заниматься ограниченное количество профессионалов. Кодеру должно быть дано достаточно детальное задание, желательно со структурой классов, диаграммой состояний и т.д. Тогда и результат будет предсказуем. У нас вообще не любят планировать и разрабатывать, у нас принято сразу реализовывать, а потом героически бороться с результатом.
— человек — существо ленивое и хитрое и всегда будет использовать возможность работать по-меньше и по-хуже если это допустимо. В конце концов это бизнес, а людей способных работать на идею немного. Поэтому организация и мотивация труда должна быть на высоте. И не требуйте от людей того, чего сами не делаете!
Спасибо за идею ужатия строки, действительно если использовать только латиницу, то мы умещаемся в половину байта и всю строку мы упаовываем в 8 байт! Надо уточнить у заказчика по поводу ограничения латиницей.
Вопрос по поводу нескольких хештаблиц: получается что для поиска нужно обойти все таблицы, и каждая будет вычислять хеш? Т.е. мне интерессно сколько было таблиц и сколько при такой организации займет поиск. Если так прикинуть, что там хешсегмент 1:1 (400 Мб), что и дает такую скорость + избыток 8 Б на вхождение (800 Мб) = 1200 Мб. Я так понимаю вы заранее заказывали ёмкость словаря, чем обошли проблему двукратного роста. Вот и вышло 2,4 + 1,2 = 3,6.
А вот с поиском даже спорить не буду. Тут сделано очень просто в угоду экономии памяти. Я понимаю, что есть более выгодные поисковые структуры. Можно вас попросит, если вы имеете такой опыт, прикинуть сколько будет занимать памяти организация инфраструктуры пирамиды? И как вы предполагали делать поиск после сортировки, бинарно или как?
Пример 1. Гибкость. Я пишу форму, которая умеет редактировать любой(!) объект, основываясь на типовой информация в рантайме (RTTI или рефлексия), например используя PropertyGrid. Можно сделать проверку обязательных полей и любую каcтомную валидацию основываясь на атрибутах. Атрибутами же упраляем доступностью полей для редактора, можно назначить свой редактор для поля и т.д. Редактируются вложенные объекты, включая коллекции. Кода немного, используются родные возможности. Вот например DevExpress FilterControl умеет на основе RTTI строить сложные фильтрационные выражения по свойствам любого объекта, которые потом можно использовать в where SQL. Пользу от этого просто сложно перееоценить. У нас одна форма используется для редактирования: конфигурационных файлов, настроек пользователя и системы (классы в БД), параметров отчетов.
Пример 2. Мощные фреймворки для бизнес задач. Я могу поднять трехзвенку (включая веб с рич клиентом) просто за отрицательное время практически без кода и поработав немного дизайнерами, используя: EntityFramework, WCF, RIAService, Silverlight. Классический веб можно через ASP Dynamic Data.
Есть реальный опыт, чем можете поделитсья?
— WinForms — летает
Жутко тормозит даже на современном железе, многие жалуются. Поставьте бекграунд на форме, гриду с парой десятком колонок, якоря и увидите. Возьмите VCL Delphi 7 и вы увидите что такое «не тормозит».
— WPF на железе 2005 года — летает
В базовом функционале возможно. Пробовал один заокругленный прямоугольник с анимированным внешним глоу — уже ощутил тормоза. Но в чистом WPF у меня опыта мало.
SL — тоже все летает, если руки правильно заточены
У нас до сих пор один проект на эксплуатации. В целом неплохо, но проскоки кадров наблюдаются. Плюс глюков там просто тьма. Пока реализовали нормальные окна не глючащие при изменении масштаба все волосы на себе повыдергивали.
— Это проблема всех проектов, где работает больше 1 человека
Мне не интерессно сколько там человек работает. Если в структурах нет ООП, то я не должен уметь перегружать GetHashCode, Equals и ToString, а если могу, то не только их.
— О каких коллекциях конкретно идет речь?
Скажите чем отличаются ArrayList, List и Collection и почему они так названы? Ну и помогите разгребсти следующую кашу: OrderedDictionary, StringDictionary, NameValueCollection, ListDictionary, SortedList, SortedDictionary, Dictionary, Hashtable…
— Скорость разработки или скорость выполнения конкретных методов?
Скорость выполнения конечно.
По поводу SQL здесь в отзывах я описываю, что эту задачу мы как раз с Oracle 11 перенесли.
— вуаль вирутальной машины — что там происходит, только Майкрософту изветсно
— тормознутые визуальные библиотеки
— местами вознакают сомнения в лаконичности архитектуры — не поймешь чего больше, то ли правил, то ли исключений из правил
— создает кашу из старых и новых библиотек, где уже ноги можно поломать тут тебе Generic версии и не Generic и что использовать не всегда понятно. Чего стоит разобраться в надцати коллекций.
— скорость меньше чем у нативного кода
…
+ кроссплатформенность — если оно собралось и работает, скорее всего оно будет работать везде где есть эта версия .Net — остальное проблема Майкрософт (я не учитываю инфоки платформы и прочие не кроссплатформенные вещи)
+ у вас не будет проблем с утечкой памяти на таком уровне как это возможно на нейтиве
+ RTTI — рефлексия, это кул и позволяет очень много. Декларативное програмирование.
+ возможность использовать для десктопных, мобильных и веб приложений (включая клиентские)
+ большое количество библиотек
+ развитие семимильными шагами
…
— загружаем равными блоками (считаем одним массивом со сквозным индексом)
— сортируем
— умеем превращать ключ в индекс массива