Библиотека Generic классов - ошибки, описание, вопросы, особенности использования и предложения - страница 18
Вы упускаете торговые возможности:
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Регистрация
Вход
Вы принимаете политику сайта и условия использования
Если у вас нет учетной записи, зарегистрируйтесь
Запустил такое
и получил это
CArrayList быстрее хэш-варианта. Залез во внутренности CArrayList, а там такое сразу
Чувствую теперь себя обманутым. CArrayList оказался оберткой обычного массива. Думал, это нормальный список с указателями Prev/Next, а тут такое
Кроме собственно алгоритмов работы со структурами есть еще проблема выбора нужного контейнера исходя из специфики задачи.
Так интерфейс один и тот же может быть для разных реализаций. Некоторое разочарование испытал не от интерфейса, а именно от конкретной реализации - массив. По сравнению с хэшом - небо и земля.
Чувствую теперь себя обманутым. CArrayList оказался оберткой обычного массива. Думал, это нормальный список с указателями Prev/Next, а тут такое
Форум по трейдингу, автоматическим торговым системам и тестированию торговых стратегий
Алгоритмы, методы решений, сравнение их производительности
Sergey Dzyublik, 2017.12.10 20:52
Какие СУБД, что вы втираете человеку понимающему НОЛЬ в структурах данных.
Если нет понятия такое ArrayList (vector из С++), о чем тут речь может идти.....
Тут скорее ваша невнимательность...
Ознакомитесь со всем списком доступного - https://www.mql5.com/ru/docs/standardlibrary/generic
СArrayList - это аналог std::vector из С++
CLinkedList - это, скорее всего, аналог std::list из С++
Запустил такое
и получил это
CArrayList быстрее хэш-варианта. Залез во внутренности CArrayList, а там такое сразу
Чувствую теперь себя обманутым. CArrayList оказался оберткой обычного массива. Думал, это нормальный список с указателями Prev/Next, а тут такое
Исторически сложилось что List это вовсе не лист, а массив. Поэтому все правильно. Если в generic появится лист, то называться он будет скорее всего как LinkedList или как-то так.
Некоторое разочарование испытал не от интерфейса, а именно от конкретной реализации - массив.
Форум по трейдингу, автоматическим торговым системам и тестированию торговых стратегий
Библиотека Generic классов - ошибки, описание, вопросы, особенности использования и предложения
Sergey Dzyublik, 2017.12.09 01:12
Есть несколько предложений по возможному улучшению:
1) По скромному мнению реализация содержит не совсем корректный выбор capacity - как начальный размер 3, так и последующие при перестройке хеш-таблицы.
Да, все верно, что нужно выбирать простое число для равномерности распределения.
Однако реализация CPrimeGenerator не отвечает ожиданиям и содержит пропуски простых чисел.
Цель такого "генератора" понятна - обеспечить коэффициент прироста порядка 1.2 с автоматическим получением простых чисел.
Однако, разве это не слишком маленький коэффициент? В C++ для vectors обычно коэффициент составляет 1.5-2.0 в зависимости от библиотеки (так как сильно влияет на среднюю сложность операции).
Выходом может быть константный коэффициент с последующим округлением числа до простого через бинарный поиск в списку простых чисел.
И начальный размер capacity в 3 - это уж слишком мало, мы же не в прошлом веке живем.
2) На данный момент перестройка хеш-таблицы (Resize) выполняется исключительно при 100% заполнении capacity (заполнении всех m_entries[])
В связи с чем возможно значительное количество коллизий для ключей с не очень равномерным распределением.
Как вариант рассмотреть возможность введение коэффициента заполнения, который уменьшит 100% на необходимый лимит для выполнения перестройки хеш-таблицы.
1) Коэффициент прироста объема(capacity) не равен 1.2, для расчета нового объема в CHashMap используется метод CPrimeGenerator::ExpandPrime:
В данном методе старый размер коллекции умножается на два, далее для полученного значения находим ближайшее с верху простое число и возвращаем его, как новый объем.
Про начальное значение capacity - согласен, он очень маленький.
Но с другой стороны всегда есть конструкторы, в которых явно можно указать начальный объем:
Поэтому особого смысла здесь что-то менять не вижу.
2) Добавлением параметра коэффициента заполнения действительно в ряде случаев поможет избежать коллизий. Скорее всего будет реализовано.
1) Коэффициент прироста объема(capacity) не равен 1.2, для расчета нового объема в CHashMap используется метод CPrimeGenerator::ExpandPrime:
В данном методе старый размер коллекции умножается на два, далее для полученного значения находим ближайшее с верху простое число и возвращаем его, как новый объем.
Про начальное значение capacity - согласен, он очень маленький.
Но с другой стороны всегда есть конструкторы, в которых явно можно указать начальный объем:
Поэтому особого смысла здесь что-то менять не вижу.
2) Добавлением параметра коэффициента заполнения действительно в ряде случаев поможет избежать коллизий. Скорее всего будет реализовано.
Роман, Вы там по-моему не тем занимаетесь. Сейчас некоторые классы generic не содержат даже самых необходимых методов. Вы вообще ими пробовали пользоваться? Взять например CRedBlackTree - классическая реализация красно-черного дерева. Довольно крутой алгоритм, но без возможности итерирования. Это как вообще понимать? Есть и много других вещей которые нужны, но которые почему-то никто не озаботился реализовать. Тот же GetHashCode вообще ужасен. Извините, но это не уровень MQ!
Роман, Вы там по-моему не тем занимаетесь. Сейчас некоторые классы generic не содержат даже самых необходимых методов. Вы вообще ими пробовали пользоваться? Взять например CRedBlackTree - классическая реализация красно-черного дерева. Довольно крутой алгоритм, но без возможности итерирования. Это как вообще понимать? Есть и много других вещей которые нужны, но которые почему-то никто не озаботился реализовать. Тот же GetHashCode вообще ужасен. Извините, но это не уровень MQ!
Я прекрасно понимаю необходимость итераторов для всех шаблонных коллекций библиотеки Genric, но без возможностей создания вложенных классов и множественного наследования от интерфейсов, реализовать их правильно не получиться.
Относительно GetHashCode хотелось бы услыхать более конкретные замечания.
...
Относительно GetHashCode хотелось бы услыхать более конкретные замечания.
Проблема
Очевидно, что GetHashCode невозможно реализовать в пользовательском окружении MQL5 должным образом. Это так, потому что не ко всем объектам есть доступ. И если на примитивных членах вроде double int и т.п. реализация работает нормально, то для сложных объектов (классы, структуры и даже перечисления) хеш расчитывается по имени. Очевидно, что если у нас тысяча объектов типа CObject или даже ENUM_что-то_там, то и CHashMap и CHashSet вырождаются в обычный LinkedList:
избежать этого не получиться, потому что все что у нас есть на пользовательском уровне это имя объекта:
Следовательно, хеши у всех объектов сложных типов равны между собой и вот этот код для поиска задействует полный перебор массива:
На самом деле это настолько критично, что перечеркивает смысл использования всего Generic на корню. Дело в том, что в большинстве случаев, требуется ассоциация или хранения сложных объектов: перечислений, структур или классов. Если бы требовалось оперирование только простыми типами, можно было бы обойтись чем-нибудь по проще.
Решение
Очевидно, что MQL5 это типобезопасный пользовательский язык программирования, выполняющийся на внутренней виртуальной машине. Что-то наподобии Net. Это значит, что необходимый доступ к объектам все-таки есть, но на более системном уровне. Следовательно, возможно написать системную функцию GetHashCode со следующим прототипом:
Как она должна работать? Во-первых она должна быть всеядной и быстрой. Давать равномерное распределение. Например:
Данная функция может располагаться в разделе системных функций. Других решений я не вижу.
з.ы. Чуть позже выскажу другие предложения по поводу интерфейсов, множественного наследования и прочего прочего C++ наследия.