ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Изучение трудов Кнута (Как изучать)
25 сообщений из 107, страница 4 из 5
  4  все
Изучение трудов Кнута (Как изучать)
    #35734186
Программист 1с
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Программист 1с
Участник
regom Например, о его втором томе "Поиск и сортировка" хочу сказать вот что. Не знаю как насчет поиска, но по поводу сортировки практика посмеялась над теорией следующим образом. Было изобретено много видов сортировок, которые подвергались математическому исследованию и выводилась аппроксимационная формула скорости работы каждого вида. В течение ряда лет было написано много трудов на эту тему. Я так понимаю, была надежда на то, что глубокое изучение этих формул приведет к новым открытиям. Однако в один прекрасный момент был чисто случайно создан алгоритм быстрой сортировки, который работает несравнимо быстрее всех ранее изобретенных, но не поддается математическому анализу, т.е. математически нельзя доказать, что он работает быстрее других. Работает, и все.Несомненно необходимо хорошее математическое образование чтобы понять книгу. А еще лучше если вы участвовали в математических олимпиадах. Во вторых знать ассемблер не столько обязательно, но ПОНИМАТЬ КАК выполняются дествия - нужно.
А все что вы понаписали про быструю сортировку - какой-то бред. Во первых не быстрее. Во вторых для ЛЮБОГО метода есть свои доказательства. А доказать что этот метод быстрее всех и всегда - нельзя. Потому что это не так. В третьих к вашему сведенью практически все открытия, сделаны "случайно".
...
Рейтинг: 0 / 0
25.12.2008, 10:23:25
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734201
regom
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
regom
Участник
[quot Программист 1сА все что вы понаписали про быструю сортировку - какой-то бред.[/quot]
Написал не я - написано в Википедии. Или там тоже бред?
...
Рейтинг: 0 / 0
25.12.2008, 10:26:25
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734240
Фотография XDiaBLo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
XDiaBLo
Участник
regomПрограммист 1сА все что вы понаписали про быструю сортировку - какой-то бред.
Написал не я - написано в Википедии. Или там тоже бред?
Типа "моветон" наверное
...
Рейтинг: 0 / 0
25.12.2008, 10:40:05
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734264
Vladimir Kozlov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vladimir Kozlov
Участник
maytonМне пока хватает электронного варианта Кнута. Некуда ставить энти три кирпича!

Во-во, Asus EEE занимает намного меньше места - а книжек в нем больше :) У меня из бумажных кирпичей самый толстый - это второй том Хорстмана (ну и пользы от него в повседневной практике побольше чем от Кнута)
...
Рейтинг: 0 / 0
25.12.2008, 10:49:18
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734269
Vladimir Kozlov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vladimir Kozlov
Участник
SQL_Lamer
Это ви мне?

А вот так тоже неплохо...
...
Рейтинг: 0 / 0
25.12.2008, 10:50:34
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734276
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Замечу, что полезны оба "Кнута" .
...
Рейтинг: 0 / 0
25.12.2008, 10:54:21
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734332
VovkaMorkovka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VovkaMorkovka
Участник
SQL_Lamer

От себя добавлю, что там в предисловии было что - то типа "математика на уровне средней школы".
И буквально через пару страниц пошли такие математические выкладки, что у меня челюсть свело :)


Это смотря на уровне КАКОЙ школы. у Кнута таки нет ничего сложного с т. зрения математика, для хорошего выпускника
...
Рейтинг: 0 / 0
25.12.2008, 11:14:56
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734359
regom
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
regom
Участник
VovkaMorkovkaSQL_Lamer

От себя добавлю, что там в предисловии было что - то типа "математика на уровне средней школы".
И буквально через пару страниц пошли такие математические выкладки, что у меня челюсть свело :)


Это смотря на уровне КАКОЙ школы. у Кнута таки нет ничего сложного с т. зрения математика, для хорошего выпускника
Особенно если ее закончил лет эдак пять назад.
...
Рейтинг: 0 / 0
25.12.2008, 11:24:53
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734410
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
regom пишет:
> быстрый из известных универсальных алгоритмов сортировки массивов (в
> среднем O(n log n) обменов при упорядочении n элементов).

O - ВЕРХНЯЯ оценка, а не средняя.

> И еще вопрос: как на форуме перед ответом на какой нибудь вопрос
> поместить в прямоугольнике ранее заданный вопрос?

Код: plaintext
[quot]так вот[/quot]

Вверху формы нового сообщения есть кнопки. Понажимайте, посмотрите
что получается, потом научитесь сами их вставлять.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
25.12.2008, 11:40:13
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734488
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
regomОсобенно если ее закончил лет эдак пять назад.
Полноте-с, батенька. Открыли справочник. Полистати-с. Освежили тык скыть голову. А учится ради сдачи экзамена это.. знаетели как-то.
...
Рейтинг: 0 / 0
25.12.2008, 12:01:54
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35734734
Ой_2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ой_2
Гость
Вспоминается случай. Был у нас мужик один, все рассказывал, что в университете заставил весь трехтомник прочитать, мол даже на том выдуманном "ассемблере" программы писать приходилось.
И что в итоге - поработал человек программистом, архитектором, да и прошел продавать в той же сфере. Теперь наверное заказчикам мозги парит. Доход тогда отличался на порядок, то есть в 10 раз (архитектор vs торгаш), не думаю, что сейчас сильно поменялось.

Резюме - само по себе изучение это хорошо, конечно, а как жизнь вывернет ... и себя знать еще важнее...
...
Рейтинг: 0 / 0
25.12.2008, 13:25:53
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35736912
Фотография retty_jj_007
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty_jj_007
Участник
Вот-вот . O(n log n) - это у сортировки слиянием
у квик O(n^2). На практике квик быстрее, в принципе они одинаково шустрые.
Но мердж намного "надежнее", этот зверь сортирует как надо и в сроки.
Квику с легкостью можно подсунуть бяку, но и там спасает random выбор медианы
...
Рейтинг: 0 / 0
26.12.2008, 12:46:51
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35737282
LK4D4
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LK4D4
Участник
Ну раз уж зашла речь о сортировках, следует отметить radix-sort, который имеет линейную сложность, но требует дополнительных входных данных.
...
Рейтинг: 0 / 0
26.12.2008, 15:06:27
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35737505
Фотография retty_jj_007
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
retty_jj_007
Участник
LK4D4Ну раз уж зашла речь о сортировках, следует отметить radix-sort, который имеет линейную сложность, но требует дополнительных входных данных.

ну здрасьте; приплыли;
...
Рейтинг: 0 / 0
26.12.2008, 16:25:15
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35737867
CodeVoyager
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
CodeVoyager
Гость
Книги Кнута следует изучать с листком в одной руке и карандашом в другой.Там можно всё понять.И польза от книг Кнута действительно есть,я лично читал её с удовольствием.Правда она у меня в эл.варианте,и поэтому сидя перед монитором и при этом осмысливать всё это сложновато.Намереваюсь купить третий том в ближайшие месяцы.
...
Рейтинг: 0 / 0
26.12.2008, 19:50:05
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35737904
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
LK4D4Ну раз уж зашла речь о сортировках, следует отметить radix-sort, который имеет линейную сложность, но требует дополнительных входных данных.
За что его отмечать? Что, он чем-то существенным отличился? Его даже не рассматривают в разделах, посвящённых сортировкам.
...
Рейтинг: 0 / 0
26.12.2008, 20:38:41
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35737943
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SQL_Lamer
Участник
VovkaMorkovkaSQL_Lamer

От себя добавлю, что там в предисловии было что - то типа "математика на уровне средней школы".
И буквально через пару страниц пошли такие математические выкладки, что у меня челюсть свело :)


Это смотря на уровне КАКОЙ школы. у Кнута таки нет ничего сложного с т. зрения математика, для хорошего выпускника

Я, к примеру, в классе с историческим уклоном учился :))
Лет сто назад.
...
Рейтинг: 0 / 0
26.12.2008, 22:16:51
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35738121
Программист 1с
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Программист 1с
Участник
regomПрограммист 1сА все что вы понаписали про быструю сортировку - какой-то бред.
Написал не я - написано в Википедии. Или там тоже бред?Вы читаете невнимательно. Еще раз прочтите статью - даже там написано что он не является "быстрейшим":
Самый быстродействующий из всех существующих алгоритмов обменной сортировки — быстрее него только специализированные алгоритмы, использующие специфику сортируемых данных
Во вторых - при объемах списка сортировки более чем объем памяти - (что в принципе нормальное явление для больших баз) очень сильно влияеет и другой недостаток этого метода:
При классической реализации требует в худшем случае много дополнительной памяти. Правда, вероятность возникновения худшего случая ничтожна.Что позволяет методам не так интенсивно работающим с памятью обойти его.

В третьих - покажите ОТКУДА в вкипедии вы звяли слова что этот метод был открыт случайно, а не являлся плодом долгих поисков.
...
Рейтинг: 0 / 0
27.12.2008, 10:32:34
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35738254
Maykie
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Maykie
Участник
retty_jj_007Вот-вот . O(n log n) - это у сортировки слиянием
у квик O(n^2). На практике квик быстрее, в принципе они одинаково шустрые.
Но мердж намного "надежнее", этот зверь сортирует как надо и в сроки.
Квику с легкостью можно подсунуть бяку, но и там спасает random выбор медианы
introsort вполне может распознать бяку и отказаться от квика.

глянул в /usr/include/c++ - g++ юзает именно интро.
...
Рейтинг: 0 / 0
27.12.2008, 16:03:08
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35738442
jsXYZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
jsXYZ
Гость
algo_searcherкакое количество лет надо, например, чтобы
изучить последовательно?

до гроба, это наша участь!
...
Рейтинг: 0 / 0
27.12.2008, 23:52:50
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35739153
Фотография Gluk (Kazan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gluk (Kazan)
Участник
Программист 1сПравда, вероятность возникновения худшего случая ничтожна.

Живо вспоминается анекдот про роту солдат и вероятность встретить на улицк 10 мужчин подряд
...
Рейтинг: 0 / 0
29.12.2008, 09:41:22
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35739479
алчность
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алчность
Участник
Как я понимаю, здесь все - большие знатоки по части алгоритмов.

Позвольте вам задачку подкинуть:

Имеется множество одномерных отрезков вида: (x_left,x_right).
Требуется так организовать это множество (список), чтобы для заданного x
временная сложность поиска отрезка, удовлетворяющего условию x_left<x< x_right
в большинстве случаев была меньше O(n),
где n- количество отрезков.

PS:
фраза "в большинстве случаев" означает: количество нужных отрезков обычно намного меньше n
...
Рейтинг: 0 / 0
29.12.2008, 12:24:07
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35739710
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
алчность
Имеется множество одномерных отрезков вида: (x_left,x_right).
Требуется так организовать это множество (список), чтобы для заданного x
временная сложность поиска отрезка, удовлетворяющего условию x_left<x< x_right
в большинстве случаев была меньше O(n),

Что значит "организовать"? Отсортировать? Или что-то другое?
...
Рейтинг: 0 / 0
29.12.2008, 13:37:00
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35739892
алчность
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
алчность
Участник
mayton
Что значит "организовать"? Отсортировать? Или что-то другое?

- Организовать структуры данных(иерархию классов).
Разумеется для быстрого поиска понадобится предобработка(скорее всего сортировка данных по какому-либо признаку(тоже непонятно по какому)).
...
Рейтинг: 0 / 0
29.12.2008, 14:47:02
| Ответить | Цитировать | Написать  
Изучение трудов Кнута (Как изучать)
    #35739895
regom
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
regom
Участник
По вопросу о поиске подходящего отрезка будем считать, что системе небходимо максимально быстро найти первый подходящий отрезок и неважно за счет чего: то ли упорядочивания, то ли какого либо поиска - тут отражена реальная ситуация, когда необходимо решить поставленную задачу, но не сразу ясно, за счет какого алгоритма. Я бы интуитивно поступил так. Все отрезки рассматривал как лес деревьев, в каждом из которых отрезки не пересекаются и упорядочены не по координатам левого и правого конца, а по координатам середины. Тогда в процессе поиска по дереву мы быстро найдем левого и правого соседа точки Х, затем проверим принадлежит ли правый, или левый, или вообще X между двумя отрезками. В последнем случае переходим к другому дереву и т.д. При добавлении нового отрезка пробуем его разместить в ранее существующих деревьях между отрезками без пересечений, а если не получается - заводим новое дерево. В общем такие туманные предположения.
...
Рейтинг: 0 / 0
29.12.2008, 14:47:44
| Ответить | Цитировать | Написать  
25 сообщений из 107, страница 4 из 5
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Изучение трудов Кнута (Как изучать)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=35734488&tid=1344725]:
 0ms
get settings:
 7ms
get forum list:
 14ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 180ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 59ms
get tp. blocked users:
 1ms
others: 212ms
total:  488ms
созд. / загр.: 488ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]