В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

Compiler Development

845 membersпожаловаться на группу
2020 May 18

МБ

Михаил Бахтерев... in Compiler Development
Peter Sovietov
Так это же классический вариант представления n-арного дерева массивом. С формулами для доступа от родителя к детям. Есть в любом учебнике по алгоритмам :)
Вот. Вот... Есть такая проблема. Забуриваясь в теории типов или категорий, престаёшь уделять внимание алгоритмам. Крутые хаскеллисты зачастую (не все, но часто) не владеют простейшими алгоритмами. Как найти балланс?
источник
07:43пожаловаться#1

СЛ

Сергей Лапынин... in Compiler Development
Михаил Бахтерев
Вот. Вот... Есть такая проблема. Забуриваясь в теории типов или категорий, престаёшь уделять внимание алгоритмам. Крутые хаскеллисты зачастую (не все, но часто) не владеют простейшими алгоритмами. Как найти балланс?
Когда силы с левой стороны уравновешивают с правой.
источник
08:03пожаловаться#2

M

MaxGraey in Compiler Development
Кто то мне доказывал в этом чате что в хаскеле сортировка происходит за O(N) так как она ленивая)
источник
08:03пожаловаться#3

M

MaxGraey in Compiler Development
Так что не стоит удивляться, что кто-то не хочет учить алгоритмы, при ленивом то хаскеле)
источник
08:04пожаловаться#4

СЛ

Сергей Лапынин... in Compiler Development
MaxGraey
Кто то мне доказывал в этом чате что в хаскеле сортировка происходит за O(N) так как она ленивая)
Каким образом сортировка в хаскеле может быть ленивой? И главное каким образом можно сделать сортировку за O(N)?
источник
08:04пожаловаться#5

СЛ

Сергей Лапынин... in Compiler Development
Если мне не изменяет память, лучшее - O(NlogN).
Или это был стеб над хаскелистами?
источник
08:05пожаловаться#6

M

MaxGraey in Compiler Development
Сергей Лапынин
Каким образом сортировка в хаскеле может быть ленивой? И главное каким образом можно сделать сортировку за O(N)?
https://t.me/CompilerDev/42010
Telegram
Eugene in Compiler Development
в хаскелле тоже  O(N)
источник
08:05пожаловаться#7

СЛ

Сергей Лапынин... in Compiler Development
sticker.webp
(39.65 Кб)
источник
08:06пожаловаться#8

МБ

Михаил Бахтерев... in Compiler Development
Сергей Лапынин
Когда силы с левой стороны уравновешивают с правой.
Ага. Осталось написать лагранжиан действия программиста :)
источник
08:14пожаловаться#9

KR

K R in Compiler Development
Peter Sovietov
Так это же классический вариант представления n-арного дерева массивом. С формулами для доступа от родителя к детям. Есть в любом учебнике по алгоритмам :)
Ну я когда про это читал много лет назад о связи с кешами не задумывался. Кстати, и реализовывал неоднократно. А в данный момент мне показалось очень интересной именно эта оптимальность для иерархии кешей.

Там есть интересное ключевое слово cache oblivious algorithms.
источник
08:19пожаловаться#10

E

Eugene in Compiler Development
MaxGraey
Кто то мне доказывал в этом чате что в хаскеле сортировка происходит за O(N) так как она ленивая)
наверное, имелось в виду, что поиск минимального элемента массива с помощью сортировки и взятия первого элемента происходит за O(n), я как-то давно тестировал — это действительно так, (head.sort) работает линейно, хотя и в три раза медленнее, чем minimum
источник
08:23пожаловаться#11

E

Eugene in Compiler Development
MaxGraey
Вот так O(N) преврящается в O(N log N) в лучшем случае =)
нет, не превращается, по крайней мере в ленивом языке, просто константа увеличивается
источник
08:25пожаловаться#12

M

MaxGraey in Compiler Development
Eugene
наверное, имелось в виду, что поиск минимального элемента массива с помощью сортировки и взятия первого элемента происходит за O(n), я как-то давно тестировал — это действительно так, (head.sort) работает линейно, хотя и в три раза медленнее, чем minimum
Это очень сильно быдет зависить от алгоритма сортировки, например с merge sort этого не будет, и с selection / insertion sort да, допускаю может быть
источник
08:26пожаловаться#13

E

Eugene in Compiler Development
со стандартной сортировкой в хаскле работает линейно, а там сортировка достаточно быстрая по моим тестам
источник
08:27пожаловаться#14

E

Eugene in Compiler Development
ну, кстати, превращение квадратичного алгоритма в линейный — зависит от алгоритма, например, те же числа фибоначчи можно вычислять экспоненциальным алгоритмом, а можно и логарифмическим
источник
08:32пожаловаться#15

M

MaxGraey in Compiler Development
Eugene
со стандартной сортировкой в хаскле работает линейно, а там сортировка достаточно быстрая по моим тестам
Я не знаю как в Хаскеле реализована сортировка, но в большинстве реализаций для выборки до 100-200 елементов обычно используют insertion sort, все что выше уже идет introsort, merge sort или Timsort. Так вот для insertion sort ленивый поиск минимального элемента через сортировку да, может быть за O(N). Для merge sort уже нет и я кажется там доказывал почему
источник
08:34пожаловаться#16

E

Eugene in Compiler Development
MaxGraey
Я не знаю как в Хаскеле реализована сортировка, но в большинстве реализаций для выборки до 100-200 елементов обычно используют insertion sort, все что выше уже идет introsort, merge sort или Timsort. Так вот для insertion sort ленивый поиск минимального элемента через сортировку да, может быть за O(N). Для merge sort уже нет и я кажется там доказывал почему
на 100-200 элементах тестировать смысла нет, на миллиардах элементов стандартная сортировка хаскелла в этом тесте работает линейно
источник
08:36пожаловаться#17

M

MaxGraey in Compiler Development
Eugene
на 100-200 элементах тестировать смысла нет, на миллиардах элементов стандартная сортировка хаскелла в этом тесте работает линейно
Вот кстати реализация:
https://hackage.haskell.org/package/containers-0.6.2.1/docs/src/Data.Sequence.Internal.Sorting.html#sortBy

Там используется popMinIQ (Pop the smallest element from the queue, using the supplied comparator). И там похоже не merge sort а что то вроде merge K sorted queues via min-heap. Но я не хаскелист и поэтому трудно спределить в точности
источник
08:59пожаловаться#18

p

polunin.ai in Compiler Development
Eugene
наверное, имелось в виду, что поиск минимального элемента массива с помощью сортировки и взятия первого элемента происходит за O(n), я как-то давно тестировал — это действительно так, (head.sort) работает линейно, хотя и в три раза медленнее, чем minimum
Давно доказано что сортировка массива не может иметь время меньше чем O(n*logn)
источник
09:10пожаловаться#19

E

Eugene in Compiler Development
polunin.ai
Давно доказано что сортировка массива не может иметь время меньше чем O(n*logn)
для того что бы получить минимальный элемент массива, не обязательно сортировать его полностью
источник
09:10пожаловаться#20