p
Eugene
для того что бы получить минимальный элемент массива, не обязательно сортировать его полностью
Минимальный элемент в массиве находится простым перебором за O(n) время как бы. При чем тут сортировка...
Size: a a a
2020 May 18
E
Минимальный элемент в массиве находится простым перебором за O(n) время как бы. При чем тут сортировка...
ну вот такой прикол у хаскеллистов — поиск минимального элемента массива путём его сортировки и взятия первого элемента
E
а, ну и да, тут скорее всё же не сортировка массива, а сортировка списков, с массивами может быть сложнее
λ
Давно доказано что сортировка массива не может иметь время меньше чем O(n*logn)
Бабл сорт может за O(n) ))))))
p
Eugene
ну вот такой прикол у хаскеллистов — поиск минимального элемента массива путём его сортировки и взятия первого элемента
Тогда время будет минимум O(n*logn) если честно сортировать а потом брать. Но мне кажется вы неправильно что-то увидели.
E
Тогда время будет минимум O(n*logn) если честно сортировать а потом брать. Но мне кажется вы неправильно что-то увидели.
речь о ленивом языке, там нет нужды делать всю работу, если используется только часть результата
M
MaxGraey
Вот кстати реализация:
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. Но я не хаскелист и поэтому трудно спределить в точности
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. Но я не хаскелист и поэтому трудно спределить в точности
И кстати в том же C++ это можно добиться через std::partial_sort
p
Eugene
речь о ленивом языке, там нет нужды делать всю работу, если используется только часть результата
Нихрена не понял, но очень интересно. Повторяю.
Если честно сортировать, потом брать первый элемент то время будет минимум O(n*logn).
Если честно сортировать, потом брать первый элемент то время будет минимум O(n*logn).
p
Покажите лучше откуда вы нашли эту фишку с сортировкой и взятием первого элемента.
E
Нихрена не понял, но очень интересно. Повторяю.
Если честно сортировать, потом брать первый элемент то время будет минимум O(n*logn).
Если честно сортировать, потом брать первый элемент то время будет минимум O(n*logn).
вы рассуждаете императивно
M
Нихрена не понял, но очень интересно. Повторяю.
Если честно сортировать, потом брать первый элемент то время будет минимум O(n*logn).
Если честно сортировать, потом брать первый элемент то время будет минимум O(n*logn).
В ленивом языке это возможно, так как все выполнение отложено, вопрос в том что там внутри если для начала нужно разобрать весь массив как в случае с merge sort а потом собрать заново, то O(N) не получиться для случая head(sort(list))
p
MaxGraey
В ленивом языке это возможно, так как все выполнение отложено, вопрос в том что там внутри если для начала нужно разобрать весь массив как в случае с merge sort а потом собрать заново, то O(N) не получиться для случая head(sort(list))
Я же написал, если там честно сортируется, то никак меньше O(n*logn) не выйдет
M
А вот то, как реализовано в Хаскеле (сортировка через minHeap со слиянием) это похоже возможно. Так жде советую взклянуть на std::partial_sort
E
Покажите лучше откуда вы нашли эту фишку с сортировкой и взятием первого элемента.
https://thesz.livejournal.com/958777.html?thread=7607353#t7607353
там Зефиров ответил:
> Было take n . sort, стало head . sort
ну типа так получилось...
там Зефиров ответил:
> Было take n . sort, стало head . sort
ну типа так получилось...
M
Я же написал, если там честно сортируется, то никак меньше O(n*logn) не выйдет
Тут кейс не просто отсортировать, а именно в комбинации head(sort(list)).
λ
p
MaxGraey
Тут кейс не просто отсортировать, а именно в комбинации head(sort(list)).
Не вижу разницы. Просто ещё один метод снаружи добавили. В том что компилятор каким-то необычным образом догадается, что здесь поиск минимального элемента и превратит это в перебор по списку сомневаюсь.
λ
Вполне обычный образ
λ
Обычная редукция
M
Не вижу разницы. Просто ещё один метод снаружи добавили. В том что компилятор каким-то необычным образом догадается, что здесь поиск минимального элемента и превратит это в перебор по списку сомневаюсь.
Как бы вам объяснить. Вы знакомы с генераторами в императивных языках?