p
Size: a a a
2020 May 18
M
Ну вот, представьте что весь алгоритм сортировки и взятия первого элемента постоен на генераторах а не циклах и рекурсии. То есть внешняя функция-генератор может всегда сказать, так, стоп мы уже получили то, что хотели и прерываем дальнейшую работу по цепочке
p
MaxGraey
Ну вот, представьте что весь алгоритм сортировки и взятия первого элемента постоен на генераторах а не циклах и рекурсии. То есть внешняя функция-генератор может всегда сказать, так, стоп мы уже получили то, что хотели и прерываем дальнейшую работу по цепочке
Для этого нужно чтобы компилятор соптимизировал код вот так. А я повторюсь, сомневаюсь что это произойдет. Нужно будет как-то вечерком посмотреть какой там асм сгенерирует компилятор
λ
Для этого нужно чтобы компилятор соптимизировал код вот так. А я повторюсь, сомневаюсь что это произойдет. Нужно будет как-то вечерком посмотреть какой там асм сгенерирует компилятор
Я дал вам ссылку на книгу
λ
Компилятор вполне все это делает
E
Я же написал, если там честно сортируется, то никак меньше O(n*logn) не выйдет
не нужно полностью сортировать коллекцию, если она не нужна полностью отсортированная
E
Я же написал, если там честно сортируется, то никак меньше O(n*logn) не выйдет
M
Eugene
не нужно полностью сортировать коллекцию, если она не нужна полностью отсортированная
В хаскеле есть maximum/minimum и как я понял использовагние max = head . sort вместо них - это такой панегирик в честь ленивости и исключительности хаскеля)
E
MaxGraey
В хаскеле есть maximum/minimum и как я понял использовагние max = head . sort вместо них - это такой панегирик в честь ленивости и исключительности хаскеля)
EM
Для этого нужно чтобы компилятор соптимизировал код вот так. А я повторюсь, сомневаюсь что это произойдет. Нужно будет как-то вечерком посмотреть какой там асм сгенерирует компилятор
Хаскель ленивый язык, там подобные фишки из коробки работают, никакой особой компиляторной магии нет. Можно и в императивном языке этого добиться, используя генераторы или thunk-и.
M
Мне кажется вам хаскелистам пора вводить термин lazy-friendly алгоритмов по аналогии с cache-friendly) Потому что не скаждым алгоритмом сортировки такое можно провернуть.
АУ
Нихрена не понял, но очень интересно. Повторяю.
Если честно сортировать, потом брать первый элемент то время будет минимум O(n*logn).
Если честно сортировать, потом брать первый элемент то время будет минимум O(n*logn).
Есть классная книжка - Окасаки "Чисто функциональные структуры данных"... Там про оценку сложности алгоритмов из параллельной вселенной 🙃
AT
Не вижу разницы. Просто ещё один метод снаружи добавили. В том что компилятор каким-то необычным образом догадается, что здесь поиск минимального элемента и превратит это в перебор по списку сомневаюсь.
О! Сейчас у Вас вообще крышу сорвёт! https://medium.com/@maiavictor/some-functions-may-have-negative-complexity-im-worried-for-my-crypto-c53f6e7343d3 😂
DP
Как думаете, для студентов в курсе реализации игрушечного языка какой фреймворк больше подходит — LLVM или Graal?
не спецкурс, желательна минимальная сложность, но при этом хотелось бы на выходе иметь хоть и калькулятор но полноценный
не спецкурс, желательна минимальная сложность, но при этом хотелось бы на выходе иметь хоть и калькулятор но полноценный
AT
Dmitry Ponyatov
Как думаете, для студентов в курсе реализации игрушечного языка какой фреймворк больше подходит — LLVM или Graal?
не спецкурс, желательна минимальная сложность, но при этом хотелось бы на выходе иметь хоть и калькулятор но полноценный
не спецкурс, желательна минимальная сложность, но при этом хотелось бы на выходе иметь хоть и калькулятор но полноценный
Тогда уж не Graal VM, а Truffle — тупо пишем интерпретатор (tree-walking), получаем компилятор бесплатно.
AD
Давно доказано что сортировка массива не может иметь время меньше чем O(n*logn)
Radix sort же
IJ
Radix sort же
*Сортировка массива про элементы которого ничего не известно
AD
*Сортировка массива про элементы которого ничего не известно
Важное уточнение)
DS
Давно доказано что сортировка массива не может иметь время меньше чем O(n*logn)
Radix sort с его O(n) к вашим услугам, хотя, это конечно, не алгоритм сортировки общего плана.
DS
А, тут уже без меня упомянули