Nano Hash - криптовалюты, майнинг, программирование

Как лучше всего сравнить эффективность раскидистых деревьев?

Я реализовал несколько алгоритмов splay tree.

Как лучше их сравнить?

Это хорошее начало для сравнения времени выполнения при добавлении случайных узлов?

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

algorithm binary-search-tree splay-tree
19.10.2013

Ответы:


1

Мне нравится эмпирический подход.

В этом подходе:

  1. Создайте набор случайных типовых наборов данных разной длины.
  2. Запустите каждую реализацию и узнайте, каково время выполнения каждой из них.
  3. Используйте методы проверки гипотез, чтобы выяснить, лучше ли одна реализация, чем другая. разное. Здесь нулевая гипотеза (H0) — это "две реализации должны выполняться в среднем одинаковое время.
  4. На основании шага 3 сделайте вывод, что одна реализация лучше другой с вероятностью 1-p (где p — это ваше p_value< /а>).

PS критерий Уилкоксона считается хорошим и широко используется в литературе и исследованиях для сравнить два алгоритма.

19.10.2013
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..