Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Поиск ближних соседей

Поиск:
Мы провели массированное исследование эффективности программы 5; ограничения на объем статьи позволяют кратко изложить результаты только одного из экспериментов. Таблица описывает его реализацию на двух похожих множествах данных:

D

Словарь

Мин Среднее Макс

Случайное

Мин Среднее Макс

0 9 17.0 22 9 17.1 22
1 228 403.5 558 188 239.5 279
2 1374 2455.5 3352

1690

1958.7 2155
3 6116 8553.7 10829 7991 8751.3 9255
4 15389 18268.3 21603 20751 21537.1 21998
Первая строка представляет цены выполнения поиска на расстоянии 0 для каждого слова в множестве. Рабочий 'словарь' представлял собой 10451 8-буквенных слов, в представляющем его дереве было 55870 узлов. Поиск на расстоянии 0 был проведен для всех слов в словаре. При поиске с наименьшей ценой было пройдено 9 узлов, а при поиске с наибольшей - 22 узла, в то время как средняя цена поиска была равна 17.0. 'Случайные' данные представляют 10000 8-буквенных слов, случайным образом сгенерированных по 10-символьному алфавиту и представленных в виде дерева с 56886 узлами. Последующие строки таблицы описывают поиски для расстояний от 1 до 4. Этот простой эксперимент показывает, что поиск ближайших соседей относительно эффективен, поиск более дальних становится более дорогим, и что простая вероятностная модель хорошо предсказывает время для реальных данных.






Просмотров: 2322

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную