информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsВсе любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 TeamViewer обвинил в своем взломе... 
 Docker Hub закрыл доступ из России 
 Google заблокировала 2 с лишним... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
я имел ввиду операций сравнения, то есть 1 итерация поиска =... 13.12.07 03:00  Число просмотров: 5358
Автор: i1 Статус: Незарегистрированный пользователь
Отредактировано 13.12.07 03:09  Количество правок: 1
<"чистая" ссылка>
> Это всего лишь упорядочивание записей в таблице по заданным
> полям.
> Для таблицы с количеством записей ~2500 и "индексом",
> построенным по двум полям, максимальное количествово
> итераций поиска не привысит 12.

я имел ввиду операций сравнения, то есть 1 итерация поиска = 2 операции сравнения
но понял что так считать нельзя :)
в индексах я так понимаю используются двоичные деревья, то есть количество итераций поиска
равно логарифму по основанию 2 от числа записей (забыл как считать логарифм по основанию при
помощи других логарифмов и поэтому посчитал от е, получилось 7 с чемто,
ну я и прикинул что от 2-х будет 10 :))
от 2-х оказалось 11.28.... операций сравнения в предыдущем посте тогда получилось бы 24

но так как в процессе поиска участвуют 2 поля то на начальном этапе поиска достаточно сравнивать
1-е поле и, если нет совпадения, то второе не сравнивать, то есть на вскидку 12 сравнений 1-го поля
и 2-3 сравнения второго и то это много, если 1-е поле в таблице имеет в основном разные значения.
то есть в итоге 15 операций сравнения

хм.. только что понял что при построении индекса из 2-х полей выгоднее пихать первым полем то,
в котором значения будут больше разниться :)

тогда и для простого перебора будет максимум не 2*2500 сравнений а 2500 + 100 (чтоб не жадничать :))
тогда в среднем получается 1300 сравнений
<programming> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach