anonymous@RULINUX.NET~# Last login: 2024-12-25 18:35:10
Регистрация Вход Новости | Разметка | Пользователи | Галерея | Форум | Статьи | Неподтвержденное | Трекер | Правила форума | F.A.Q. | Ссылки | Поиск
Форум - Talks [RSS]
[#] [Добавить метку] [Редактировать]
Скрыть

[спв][у кого короче]Сортировки тред

В обсуждениях новости опеннета http://www.opennet.ru/opennews/art.shtml?num=44932

Возник вопрос о адекватности "старых" утилит типа сорт, и много большей эффективности "новых" (java, go, etc) ЯП и "современных" реализаций старых алгоритмов (с чего бы).
Там сортировали базу данных старых паспортов на гигабайт, но дабы не качать:
time tr -cd '[:digit:]' < /dev/urandom | fold -w10 | head -n 100000000 > /home/user/list.csv
real 39m40.707s
user 0m55.913s
sys 39m7.850s

и сортируем без -n, как на опеннете time sort list.csv > list_sort.csv
real 4m51.489s
user 12m23.947s
sys 0m2.593s

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


p.s. результаты получены на ноуте с обычным HDD
p.s.s. Предложите более эффективную реализацию создания гигового файла с 10 значными числами в баше.

Dr.uid(*) (2016-08-09 15:16:23)
Отредактировано Dr.uid по причине "не указана"
Mozilla/5.0 (Windows NT 6.1; rv:38.0) Gecko/20100101 Firefox/38.0

[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: [спв][у кого короче]Сортировки тред от Dr.uid 2016-08-09 15:16:23
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

Ушёл создавать базу. Буду через 5 минут.

anonymous(*)(2016-08-09 15:47:48)

[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: [спв][у кого короче]Сортировки тред от Dr.uid 2016-08-09 15:16:23
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

ща заценим, тут http://mech.math.msu.su/~shvetz/54/inf/perl-problems/chSorting_sIdeas.xhtml 10 алгоритмов разных сортировки

vilfred(*)(2016-08-09 15:57:48)
Отредактировано vilfred по причине "не указана"
Mozilla/5.0 (X11; Fedora; Linux x86_64; rv:47.0) Gecko/20100101 Firefox/47.0
[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от vilfred 2016-08-09 15:57:48
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

даже выкладывать стыдно результаты =) на сях надо эти алгоритмы преписывать...

vilfred(*)(2016-08-09 17:55:56)

Mozilla/5.0 (X11; Fedora; Linux x86_64; rv:47.0) Gecko/20100101 Firefox/47.0
[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: [спв][у кого короче]Сортировки тред от Dr.uid 2016-08-09 15:16:23
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

text

real    157m56.176s
user    1m27.981s
sys     140m2.310s
 


Ты издеваешься? Зачем я коптил атмосферу?

anonymous(*)(2016-08-09 18:27:09)

[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от anonymous 2016-08-09 18:27:09
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

Это сортировка или создание файла ?

Если создание файла, то я предупреждал, что метод крайне не эффективный.

А если сортировка то ты её видимо на телефоне делал :)

Dr.uid(*)(2016-08-09 18:29:34)
Отредактировано Dr.uid по причине "не указана"
Mozilla/5.0 (Windows NT 6.1; rv:38.0) Gecko/20100101 Firefox/38.0
[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от vilfred 2016-08-09 17:55:56
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

Ну уж сказал А выкладывай и Б. Все результаты интересны.

Dr.uid(*)(2016-08-09 18:30:16)

Mozilla/5.0 (Windows NT 6.1; rv:38.0) Gecko/20100101 Firefox/38.0
[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от Dr.uid 2016-08-09 18:30:16
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

на 10000 элементах, ибо на гиге завешивает комп напрочь , коды сортировок http://mech.math.msu.su/~shvetz/54/inf/perl-problems/chSorting_sReadyProgram.xhtml

text

10000 элементов

[vilfred@localhost perl]$ time sort 1list.csv > list_sort.csv

real    0m0.017s
user    0m0.013s
sys     0m0.003s
[vilfred@localhost perl]$

Пузырьковая сортировка(простая версия)


[vilfred@localhost perl]$ time perl x.pl

real    0m23.103s
user    0m23.016s
sys     0m0.050s

Пузырьковая сортировка(Улучшенная версия)

[vilfred@localhost perl]$ time perl x.pl

real    0m28.227s
user    0m28.002s
sys     0m0.224s
[vilfred@localhost perl]$

Шейкерная сортировка

[vilfred@localhost perl]$ time perl x.pl

real    0m25.788s
user    0m25.784s
sys     0m0.003s
[vilfred@localhost perl]$

Сортировка вставками

[vilfred@localhost perl]$ time perl x.pl

real    0m18.874s
user    0m18.790s
sys     0m0.044s
[vilfred@localhost perl]$

Сортировка выбором

[vilfred@localhost perl]$ time perl x.pl

real    0m5.304s
user    0m5.298s
sys     0m0.005s
[vilfred@localhost perl]$

Древесная сортировка

[vilfred@localhost perl]$ time perl x.pl

real    0m0.117s
user    0m0.114s
sys     0m0.003s
[vilfred@localhost perl]$

Быстрая сортировка

[vilfred@localhost perl]$ time perl x.pl

real    0m0.058s
user    0m0.054s
sys     0m0.003s
[vilfred@localhost perl]$

Умная сортировка

[vilfred@localhost perl]$ time perl x.pl

real    0m0.016s
user    0m0.014s
sys     0m0.002s
[vilfred@localhost perl]$

Перемешивание

[vilfred@localhost perl]$ time perl x.pl

real    0m0.045s
user    0m0.039s
sys     0m0.005s
[vilfred@localhost perl]$

Алгоритм Фишера — Йетса — Дурстенфельда

[vilfred@localhost perl]$ time perl x.pl

real    0m0.026s
user    0m0.023s
sys     0m0.002s
[vilfred@localhost perl]$

 

vilfred(*)(2016-08-09 18:34:14)
Отредактировано vilfred по причине добавка
Mozilla/5.0 (X11; Fedora; Linux x86_64; rv:47.0) Gecko/20100101 Firefox/47.0
[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от vilfred 2016-08-09 18:34:14
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

На таких обьемах блох ловить, не выразительно получаются отрывы.

Но "Умная сортировка" сравнялась с результатом sort.

real 0m0.016s user 0m0.014s sys 0m0.002s

Это что за алгоритм был ?

Dr.uid(*)(2016-08-09 18:39:44)

Mozilla/5.0 (Windows NT 6.1; rv:38.0) Gecko/20100101 Firefox/38.0
[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: [спв][у кого короче]Сортировки тред от Dr.uid 2016-08-09 15:16:23
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

> базу данных старых паспортов на гигабайт, но дабы не качать:

Я так думаю, там не просто колонка цифр, но и ещё какие-то данные, поэтому надо разбирать входную строку

> гигового файла

Т.е. набор данных заведомо помещается в памяти современного мобильного телефона.

Я думаю тут надо использовать башевую команду `sqlite3` - создать ею табличку с двумя полями 'id' типа интеджер и 'str' - типа текст или ещё какого символьного. Импортировать данные с применением встроенной команды .import и селектить оттуда всё чего надо в каком хошь порядке.

anonymous(*)(2016-08-09 19:02:10)

[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от anonymous 2016-08-09 19:02:10
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

Для адекватного сравнения тогда надо и sort с рам диска хотя бы делать.

Из tmpfs который по идее в памяти:
real 3m26.938s
user 10m49.187s
sys 0m2.187s
Те на пару минут лучше.


А с оптимизацией "-n"
real 1m41.007s
user 4m39.450s
sys 0m3.057s


Думаю это будет сопоставимо с qulite по скрости, только сильно проще в реализации.

Dr.uid(*)(2016-08-09 19:10:34)
Отредактировано Dr.uid по причине "не указана"
Mozilla/5.0 (Windows NT 6.1; rv:38.0) Gecko/20100101 Firefox/38.0
[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от Dr.uid 2016-08-09 19:10:34
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

Это как раз не адекватно. А вдруг попадётся такой сорт, что он по всему файлу пробегать будет на каждую строчку, для экономии памяти, скажем? И обязательно альтернативный сорт должен уметь все те же функции, что и оригинальный.

А то затычку-то на каждый конкретный случай слабать несложно, мне кажется сожно было бы подтянуть эти паспорта вообще в похапешный массив, он же вроде sparse, так что 10-значный индекс не должен ничего плохого сделать. А потом пройти по массиву в порядке возрастания - вот тебе и сорт.

anonymous(*)(2016-08-09 19:42:11)

[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от Dr.uid 2016-08-09 18:29:34
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

Создание, сортировка по-быстрее, но тоже не мгновенная.

text

real    26m20.908s
user    20m56.852s
sys     0m24.503s
 

anonymous(*)(2016-08-09 20:00:00)

[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: [спв][у кого короче]Сортировки тред от Dr.uid 2016-08-09 15:16:23
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

>time tr -cd '[:digit:]' < /dev/urandom | fold -w10 | head -n 100000000 > /home/user/list.csv
> real 39m40.707s


ОМГ. За 39 минут можно на С написать пару раз

c


#include <stdio.h>
#include <stdlib.h>

int
main(int argc, char *argv[])
{
        int lines, digits, i, j;

        if (argc < 3) {
                fprintf(stderr, "Usage: %s LINES DIGITS\n", argv[0]);
                return 1;
        }
        lines = atoi(argv[1]);
        digits = atoi(argv[2]);

        for (i=0; i<lines; i++) {
                for (j=0; j<digits; j++) {
                        putchar(rand() % 10 + '0');
                }
                putchar('\n');
        }
        return 0;
}
 


bash

$ time ./a.out 100000000 10 > list.csv

real    0m17.014s
user    0m16.324s
sys     0m0.700s
 

anonymous(*)(2016-08-10 10:58:37)

Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Firefox/38.0 Iceweasel/38.8.0
[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от anonymous 2016-08-10 10:58:37
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

> atoi

И как эта функция переваривает номера серий?

anonymous(*)(2016-08-10 13:00:07)

[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от anonymous 2016-08-10 13:00:07
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

Каких еще серий? Это точный эквивалент однострочника из ОП который генерирует цифры в столбик. Только вместо 39 минут делает это за 17 секунд

anonymous(*)(2016-08-10 13:34:32)

Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Firefox/38.0 Iceweasel/38.8.0
[Ответить на это сообщение]
[#] [Добавить метку] [Редактировать] Ответ на: Re:[спв][у кого короче]Сортировки тред от anonymous 2016-08-10 13:34:32
avatar
Скрыть

Re:[спв][у кого короче]Сортировки тред

Я думаю это сделано специально для того, чтобы отвлечь нас от скачивания базы данных паспартов на 100 млн. записей.

anonymous(*)(2016-08-10 13:56:56)

[Ответить на это сообщение]
Этот тред читают 2 пользователя:
Анонимных: 2
Зарегистрированных: 0


(c) 2010-2020 LOR-NG Developers Group
Powered by TimeMachine

Valid HTML 4.01 Transitional Правильный CSS!