Версия - алгоритм
Cтраница 3
 |
Двоичный поиск элемента со значением 44. [31] |
Несмотря на то что такое изменение незначительно, проверка top nil содержится в часто выполняемом цикле. Для больших списков этот цикл повторяется много раз, поэтому подобная экономия становится значительной. В Delphi такой перебор связанного списка осуществляется приблизительно на 10 % быстрее, чем предыдущая версия. Программа Search демонстрирует обе версии алгоритмов перебора связанных списков, поэтому можно легко сравнить их друг с другом. [32]
Алгоритм ID3 хорошо зарекомендовал себя в широком спектре приложений. Он обеспечивает высокое качество классификации, а учет статистических закономерностей позволяет ему работать с за-шумленными данными. После того, как алгоритм был впервые опубликован, ряд исследователей предложили различные усовершенствования алгоритма. Так, в статье Утгоффа предложена инкрементная версия алгоритма, которая позволяет не создавать дерево заново при добавлении одного примера, а перестроить его. Это свойство важно для того, чтобы учесть изменения в базах данных. В работе Нуньеса предложена версия алгоритма, позволяющего использовать дополнительную информацию о предметной области. Наконец, в статье Мингера рассмотрены различные методики упрощения решающих деревьев и проведено их экспериментальное сравнение. [33]
Алгоритм ID3 хорошо зарекомендовал себя в широком спектре приложений. Он обеспечивает высокое качество классификации, а учет статистических закономерностей позволяет ему работать с за-шумленными данными. После того, как алгоритм был впервые опубликован, ряд исследователей предложили различные усовершенствования алгоритма. Так, в статье Утгоффа предложена инкрементная версия алгоритма, которая позволяет не создавать дерево заново при добавлении одного примера, а перестроить его. Это свойство важно для того, чтобы учесть изменения в базах данных. В работе Нуньеса предложена версия алгоритма, позволяющего использовать дополнительную информацию о предметной области. Наконец, в статье Мингера рассмотрены различные методики упрощения решающих деревьев и проведено их экспериментальное сравнение. [34]
При двоичном поиске прежде, чем добраться до некоторых элементов списка, мы должны с необходимостью совершить несколько неудачных проверок. Шервудский вариант двоичного поиска выбирает случайный элемент между началом и концом списка и сравнивает его с искомым. Иногда оставшийся кусок оказывается меньше, чем тот, что мы бы получили при настоящем двоичном поиске, а иногда - больше. Так, например, не исключено, что в списке из 400 элементов мы выберем для пробного сравнения не 200-ый, а сотый. Если искомый элемент находится среди первых ста, то наша шервудская версия алгоритма поиска позволяет отбросить 75 % списка вместо 50 % в стандартном алгоритме. Однако если интересующий нас элемент больше сотого, то отброшенными окажутся лишь 25 % списка. Вновь в некоторых случаях мы получаем выигрыш, а иногда проигрываем. [35]
Страницы: 1 2 3