Продолжение и, скорее всего, окончание моего исследования про графы из текстов.
Мне подсказали страницу, где есть реализация одного алгоритма (QuickSort) на разных языках программирования, а значит есть отличная возможность сравнить графы этих «одинаковых» программ.
Под катом полученные графы для языков: C, C++, Java, Visual Basic, Delphi, Python, Php, Prolog, Fortran, Ruby, Haskell, Algol, Mathematica, Asm.
Попробуйте не заглядывая под кат угадать, какой граф будет наиболее красивым и какой самым страшным
Самым страшным языком программированияграфом я провозглашаю Фортрановский (сама программа, надо признать, была еще страшнее графа):
Здравствуйте, Mamut, Вы писали:
M>Как вы думаете, кто победитель?
По производительности? Думаю, фортран. Для него приведена единственная приближенная к real world реализация сортировки. В реальной библиотеке C++, кстати тоже будет insertion sort для маленького количества элементов и даже может heap sort, если глубина рекурсии слишком большая.
Не в языке дело, а в том что на них реализованы разные алгоритмы.
Здравствуйте, Mamut, Вы писали:
M>Как вы думаете, кто победитель?
Ага. Круто. Это был для односвязных списков qsort, я верно понял? Ну тех которые в Haskell built-in и для которых там сахара насыпано мама-не-горюй. А теперь пожалуйста сортировку двусвязного списка. И очень хочется поглядеть на граф на Haskell. Ну вот очень-очень. Спасибо
M>>Как вы думаете, кто победитель? T>Ага. Круто. Это был для односвязных списков qsort, я верно понял? Ну тех которые в Haskell built-in и для которых там сахара насыпано мама-не-горюй. А теперь пожалуйста сортировку двусвязного списка. И очень хочется поглядеть на граф на Haskell. Ну вот очень-очень. Спасибо
Вопрос с подвохом: можно ли преобразовать двусвязный список в односвязный, отсортировать и преобразовать обратно?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, thesz, Вы писали:
T>Вопрос с подвохом: можно ли преобразовать двусвязный список в односвязный, отсортировать и преобразовать обратно?
Какая потеря времени. А если там большой список? Я понимаю асимптотика от этого не меняется, но константу при ней мы сильно ухудшаем. Но ведь быстродействие в таких случаях тоже играет свою роль, а оно у Haskell и так не особо при таком графе мягко скажем. Я не спорю на Haskell можно и быстро, я даже знаю как... Но тогда перестанет быть красиво и станет чуть более похоже на фортран по моему личному опыту. Так что уж давайте честную сортировку двусвязного списка без дополнительных двух преобразований. Граф на C от этого кстати даже не пошевелится особо.
T>>Вопрос с подвохом: можно ли преобразовать двусвязный список в односвязный, отсортировать и преобразовать обратно? T>Какая потеря времени. А если там большой список? Я понимаю асимптотика от этого не меняется, но константу при ней мы сильно ухудшаем.
Это надо показать, как минимум. Доказывать не прошу, поскольку на RSDN принято ловко от этого уходить, загромождая дискуссию.
Показать обратное очень просто.
У нас получится сложность вида O(A*NlogN+B*N). B значительно меньше A, поскольку сравнение не используется. В результате мы придём к O(NlogN+(B/A)*N), где (B/A)<<1. Иными словами, мы получим O(NlogN).
Для вырожденного случая, где O(N^2) вообще не стоит учитывать B*N.
T>Так что уж давайте честную сортировку двусвязного списка без дополнительных двух преобразований. Граф на C от этого кстати даже не пошевелится особо.
Сперва я бы хотел увидеть сортировку на Си двусвязного списка.
Если там будет перестроение двусвязного списка на каждой итерации, то я сниму шляпу и прекращу дискуссию. Поскольку я не могу позволить себе спорить с человеком, настаивающем на бесполезных действиях.
Если же там будет нормальное решение сортировкой односвязного списка с последующим построением двусвязного, то я снова сниму шляпу и прекращу дискуссию. Но уже по другой причине.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, Mamut, Вы писали:
M>Как вы думаете, кто победитель?
Лично мне кажется, что картинки еще не совершены. Мы же тут инжинеры, мы можем лучше! Нужно это все представить в более живых формах и в цвете. Тогда получившаяся картинка будет намного яркой и индивидуальной. Тогда и выбор языка станет намного более осознаным и волевым действием. Почти как тест Роршаха.
Здравствуйте, Tilir, Вы писали:
T>Ага. Круто. Это был для односвязных списков qsort, я верно понял? Ну тех которые в Haskell built-in и для которых там сахара насыпано мама-не-горюй. А теперь пожалуйста сортировку двусвязного списка. И очень хочется поглядеть на
граф на Haskell. Ну вот очень-очень. Спасибо
Тут в выигрыше или язык или стиль написания при котором как можно меньше используются ключевые слова и как можно больше закорючек, вот например оптимизированная под это дело программка на питоне:
qsort = lambda l : qsort([y for y in l[1:] if y< l[0]])+[l[0]]+qsort([y for y in l[1:] if y>= l[0]]) if l else []
Здравствуйте, FR, Вы писали: FR>Тут в выигрыше или язык или стиль написания при котором как можно меньше используются ключевые слова и как можно больше закорючек
Ага. вот J:
