Re[6]: Быстрая сортировка массива на Nemerle
От: WolfHound  
Дата: 28.01.08 10:42
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Ну, так выложил бы. Может включили бы его в стандартную библиотеку.
Так я уже выложил
Автор: WolfHound
Дата: 25.01.08
.

VD>Или ты это про сортировку через массив?
Она вобще все рвет просто как тузик грелку.

Кстати мою сортировку в случае длинных списков можно ускорить через небольшой массив для маленьких последовательностей.
Ибо я не бью весь список пополам, а откусываю от его начала по кусочку.
Сейчас откусываю по одному элементу но можно и больше.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[7]: Быстрая сортировка массива на Nemerle
От: VladD2 Российская Империя www.nemerle.org
Дата: 30.01.08 15:17
Оценка:
Здравствуйте, WolfHound, Вы писали:

VD>>Ну, так выложил бы. Может включили бы его в стандартную библиотеку.
WH>Так я уже выложил
Автор: WolfHound
Дата: 25.01.08
.

VD>>Или ты это про сортировку через массив?
WH>Она вобще все рвет просто как тузик грелку.

Тесты делал? На разных входящих последовательностях тоже? На отсортированных списках (в прямом и обратном напрвлении) пробовал?

Если, сортировка на базе массива самая быстрая в любом случае, то стоит выкинуть ту реализацию, что есть сейчас и вставить сортировку с промежуточным массивом. За одно можно сделать фунцию типа SortToArray().
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Быстрая сортировка массива на Nemerle
От: VladD2 Российская Империя www.nemerle.org
Дата: 30.01.08 15:36
Оценка:
Здравствуйте, RomulS, Вы писали:

RS>У меня такая штука получилась:

RS>
RS>  public qsort(arr: list[int], distinct: bool): list[int]
RS>  {
RS>    | ([], _) => [];
RS>    | (x::[], _) => [x];
RS>    | (x::xs, true) => qsort($[y | y in xs, y<x], distinct) + [x] + qsort($[y | y in xs, y>x], distinct);
RS>    | (x::xs, false) => qsort($[y | y in xs, y<=x], distinct) + [x] + qsort($[y | y in xs, y>x], distinct);
RS>  }
RS>


Одна проблема. Функцию нужно переименовать во что-то вроде SlowSort, так как при этом получается огромное количество копирований подсписков.

Так что подобные примеры — это не более чем демоверсия.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Быстрая сортировка массива на Nemerle
От: WolfHound  
Дата: 30.01.08 15:49
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Тесты делал? На разных входящих последовательностях тоже? На отсортированных списках (в прямом и обратном напрвлении) пробовал?
случайные числа
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3906225, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4687470, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4843719, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3437478, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.5156217, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3124980, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4218723, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0937494, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4687470, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4374972, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4687470, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4531221, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4999968, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4062474, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4374972, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3906225, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.5156217, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4062474, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.4843719, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

Отсортировано в прямом порядке
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2187486, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3124980, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2499984, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.1874988, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3906225, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2187486, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3437478, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2812482, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3437478, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2031237, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0156249, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.1874988, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3593727, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2187486, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3437478, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0468747, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2031237, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3437478, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

Отсортировано в обратном порядке
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2656233, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2812482, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2656233, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2968731, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.1874988, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.1562490, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3281229, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.1718739, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2187486, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2656233, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2031237, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0624996, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.1718739, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.2968731, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.1874988, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3749976, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort

True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.1562490, my mergesort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.3437478, List.MergeSort
True 100000 (-6502787664072455845, -9132673546309142552) 00:00:00.0312498, arrsort


VD>Если, сортировка на базе массива самая быстрая в любом случае, то стоит выкинуть ту реализацию, что есть сейчас и вставить сортировку с промежуточным массивом. За одно можно сделать фунцию типа SortToArray().
Там нужно добавить еще много функций...
Например:
        public static MapFilteredRev[T, U](this lst : list[T], fn : T -> option[U]) : list[U]
        {
            def loop(lst, res)
            {
                match (lst)
                {
                | head :: tail =>
                    match (fn(head))
                    {
                    | Some(elem) =>
                        loop(tail, elem :: res);
                    | None =>
                        loop(tail, res);
                    }
                | [] => res;
                }
            }
            loop(lst, []);
        }

        public static MapFiltered[T, U](this lst : list[T], fn : T -> option[U]) : list[U]
        {
            lst.MapFilteredRev(fn).Rev()
        }
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.