LINUX.ORG.RU
ФорумTalks

Принципиально новый алгоритм сортировки

 


0

0

Не в development потому что тупняк и баян.

package main

import (
    "fmt"
    "time"
)

func main() {
    unsorted := []int{4, 6, 9, 21, 11, 2, 8, 19, 5, 100, 99, 1, 98, 95, 97, 96}
    sorted := make(chan int)

    for _, x := range(unsorted) {
        go func(a int) {
            time.Sleep(time.Millisecond * time.Duration(a))
            sorted <- a
        }(x)
    }

    for i := 0; i < len(unsorted); i++ {
        fmt.Printf("%d ", <-sorted)
    }
    fmt.Println()
}

1 2 4 5 6 8 9 11 19 21 95 96 97 98 99 100

Автор идея не я, а анонимус на форчане.

★★★★★

Креативное использование ожидан паров клея.

Deleted ()

Если не считать того, что бесполезна, она ещё и неустойчива, а на реальном железе под нагрузкой, возможно, будет сортировать неверно.

Sadler ★★★ ()
Ответ на: комментарий от Sadler

Зато на квантовом компьютере выходит вполне себе О(1).

PolarFox ★★★★★ ()

А ещё можно завести временный массив [0..100] и за тот же один проход отсортировать, просто прибавляя единицу в i-ой ячейке, когда встречается i. Только нафиг не надо такое счастье.

Sadler ★★★ ()
Ответ на: комментарий от Cancellor

Да, кстати, интересно. А то начал читать...
package, import... ага, почти ява...
main() уже ближе к C...
:= без комментариев...
<- это парсеру не понравилось.

Sadler ★★★ ()
Ответ на: комментарий от Sadler

:= без комментариев...

Это не присваивание, это присваивание с объявлением. Правая часть имеет тип, известный на этапе компиляции. Можно было бы написать

var unsorted []int
unsorted = []int{4, 6, 9, 21, 11, 2, 8, 19, 5, 100, 99, 1, 98, 95, 97, 96}

Но это немного более длинно, зачем компьютеру писать о том, что он и так знает?

<- это парсеру не понравилось.

Сущность — канал, что-то типа именованного типизированного пайпа. В одном месте записали (канал <- что-нибудь), в другом месте прочитали (что-нибудь <- канал), при этом по умолчанию каналы небуферизованные и блокируют поток.

PolarFox ★★★★★ ()
Ответ на: комментарий от cdshines

Каг это работает?

Создаёт по горутине (местный вариант лёгкого потока) на каждый элемент массива. Каждая горутина спит число миллисекунд равное величине элемента и отправляет данные в канал, из которого их считывает основной поток и выводит на экран.

PolarFox ★★★★★ ()
Ответ на: комментарий от PolarFox

жаль только, что работает лишь для множеств, которые можно изоморфно отобразить на натуральные числа.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от PolarFox

Зато на квантовом компьютере выходит вполне себе О(1).

это почему?

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dikiy

это почему?

Я просто предположил, я не знаю как они функционируют (и функционируют ли вообще). Но если не брать в расчёт затраты на шедулер, то у этого алгоритма сложность О(1).

PolarFox ★★★★★ ()
Ответ на: комментарий от PolarFox

Ы а круто тоесть она гарантированно отсортирует за число милисекунд наибольшего числа? вопрос что будет если в массиве все числа одинаковы и велики и как себя поведёт канал когда в него в одну милисекунду попрёт 100 одинаковых элементов?

хм а ещё очень вероятны ошибки ибо стартуют все эти потоки не одновременно а по мере прохождения цикла ЕЯП и последние элементы могут не успеть попасть в первую милисекунду.

Thero ★★★★★ ()
Последнее исправление: Thero (всего исправлений: 1)

time.Sleep гарантирует точность меньше миллисекунды? Если нет, то алгоритм не работает в общем случае, причем дает такие глюки, которые просто нереально отловить.

Кроме того, если функции go func(a int) для элементов массива начинают выполняться не в абсолютно одинаковый момент времени, то опять же существует вероятность, что сортировка будет некорректной. Например, массив {2, <100500 элементов>, 1}, запуская в начале таймер на 2 мс, а пооооотооооом таймер на 1 мс, очень вероятно, что первый таймер отработает раньше.

grondek ()
Ответ на: комментарий от Thero

гарантированно

Нет. Шедулер в некоторых странных обстоятельствах может вообще решить выполнить все горутины по очереди и тогда плакал весь алгоритм. Но при текущей реализации оно в принципе работает и действительно тратит max(unsorted) миллисекунд (что в общем-то очень очень очень очень много даже по сравнению с пузырьком).

и как себя поведёт канал когда в него в одну милисекунду попрёт 100 одинаковых элементов?

Ну какой поток успеет первый, тот и запишет туда число и будет висеть, пока число не прочтут. Остальные потоки будут висеть, пока канал не освободится. В Go это средство как синхронизации потоков, так и обмена данными между ними.

PolarFox ★★★★★ ()
Ответ на: комментарий от PolarFox

Но если не брать в расчёт затраты на шедулер

Ы :)

то у этого алгоритма сложность О(1).

введи последовательность 1,2,2^1024 и жди окончания :)

dikiy ★★☆☆☆ ()
Ответ на: комментарий от grondek

Код не рассчитан на использование в реальном мире. Просто забавное извращение.

PolarFox ★★★★★ ()
Ответ на: комментарий от PolarFox

оно в принципе работает

Оно работает только в идеальных условиях на бумажке. В реальных условиях будет работать в зависимости от погоды на Марсе.

grondek ()
Ответ на: комментарий от dikiy

введи последовательность 1,2,2^1024 и жди окончания :)

Можно прикрутить какую-нибудь функцию нормализации.

PolarFox ★★★★★ ()
Ответ на: комментарий от PolarFox

введи последовательность 1,2,2^1024 и жди окончания :)

Можно прикрутить какую-нибудь функцию нормализации.

В общем случае для функции нормальзации надо будет считать все числа и разбросать их равномерно по «шкале» времени с учетом разрешения таймера. А для этого их надо будет _уже_ отсортировать.

dikiy ★★☆☆☆ ()

есть кстати веселее идея которая за 2 прохода массивов сортирует их.

чтото типа

foreach in a[] b[a[]]++

а потом пробегаемся по массиву b и печатаем i b раз..

\\как видите тут есть очевидная проблема с большими числами и весьма ограниченной длинной массива b

что возможно вариант со списком из книжки кнута будет куда эффективнее.

Thero ★★★★★ ()
Последнее исправление: Thero (всего исправлений: 1)
Ответ на: комментарий от Thero

А то ж, компилируемый статически типизированный язык, писать на котором не сильно напряжнее, чем на каком-нибудь скриптовом.

PolarFox ★★★★★ ()
Ответ на: комментарий от Thero

Да, это самая обыкновенная сортировка подсчетом. Улучшенная идея того же подхода используется в цифровой сортировке, которая при некоторых ограничениях на элементы массива может дать выигрыш по времени в некоторых случаях.

FuriousBean ()
Ответ на: комментарий от buddhist

Поздравляю, вы и Sadler изобрели сортировку подсчетом.

Изобрели? Чего-то вы гоните.

Sadler ★★★ ()
Ответ на: комментарий от buddhist

Поясню: я мягко намекнул человеку. 3 том Кнута расскажет вам ещё много интересного.

Sadler ★★★ ()
Ответ на: комментарий от buddhist

я прям теперь горд. не часто что-то изобретаю. особенно до чаепития.

Thero ★★★★★ ()
Ответ на: комментарий от Sadler

блин а я ведь вроде читал кнута.. тоесть я может и не изобрёл? ну ладно выучу яваскрипт изобрету пакетный манагер.

Thero ★★★★★ ()
Ответ на: комментарий от Thero

блин а я ведь вроде читал кнута.. тоесть я может и не изобрёл? ну ладно выучу яваскрипт изобрету пакетный манагер.

Ты только ОС свою не изобретай из убунты.

Sadler ★★★ ()
Ответ на: комментарий от Thero

А вообще расслабься, у меня масса проектов было, которые изобрели раньше меня. Иногда с отрывом в год, иногда - в столетие. Это нормально.

Sadler ★★★ ()
Ответ на: комментарий от Sadler

не мне дробинс уже мозги промыл такчто только метро только генту базед.

Thero ★★★★★ ()
Ответ на: комментарий от Sadler

да я и не парюсь просто юмор у меня такой.

Thero ★★★★★ ()

Забавно.

Вот так получше, следует учитывать время, потраченное на обход массива.

package main

import (
    "fmt"
    "time"
)

func main() {
    unsorted := []int{4, 6, 9, 21, 11, 2, 8, 19, 5, 100, 99, 1, 98, 95, 97, 96}
    sorted := make(chan int)

    length := len(unsorted)
    factor := length / 10000
    if factor == 0 {
       factor = 1
    }

    for _, x := range(unsorted) {
        go func(a int) {
            time.Sleep(time.Millisecond * time.Duration(a) * factor)
            sorted <- a
        }(x)
    }

    for i := 0; i < length; i++ {
        fmt.Printf("%d ", <- sorted)
    }
    fmt.Println()
}
gatsu ()
Ответ на: комментарий от Sadler

Вообще-то в определённых ситуациях (когда у нас много ненужной памяти, а вот время исполнения алгоритма очень критично) это может оказаться достаточно хорошим решением.

KivApple ★★★★★ ()
Ответ на: комментарий от theNamelessOne

Ты про это?

factor := length / 10000

Это целочисленное деление.

gatsu ()
Ответ на: комментарий от theNamelessOne

Я про такие тонкости не в курсе :) Вот так правильно будет.

time.Sleep(time.Millisecond * time.Duration(factor * a))
gatsu ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.