rulinux.net - Форум - Talks - [спв][у кого короче]Сортировки тред http://rulinux.net/ rulinux.net - Форум - Talks - [спв][у кого короче]Сортировки тред http://rulinux.net/ http://rulinux.net/rss_icon.png Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216895 https://rulinux.net/message.php?newsid=42613&page=1#216895 Wed, 10 Aug 2016 09:56:56 +0300 Я думаю это сделано специально для того, чтобы отвлечь нас от скачивания базы данных паспартов на 100 млн. записей.

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216894 https://rulinux.net/message.php?newsid=42613&page=1#216894 Wed, 10 Aug 2016 09:34:32 +0300 Каких еще серий? Это точный эквивалент однострочника из ОП который генерирует цифры в столбик. Только вместо 39 минут делает это за 17 секунд

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216893 https://rulinux.net/message.php?newsid=42613&page=1#216893 Wed, 10 Aug 2016 09:00:07 +0300 > atoi

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

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216892 https://rulinux.net/message.php?newsid=42613&page=1#216892 Wed, 10 Aug 2016 06:58:37 +0300 >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
 

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216887 https://rulinux.net/message.php?newsid=42613&page=1#216887 Tue, 09 Aug 2016 16:00:00 +0300 Создание, сортировка по-быстрее, но тоже не мгновенная.

text

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

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216886 https://rulinux.net/message.php?newsid=42613&page=1#216886 Tue, 09 Aug 2016 15:42:11 +0300 Это как раз не адекватно. А вдруг попадётся такой сорт, что он по всему файлу пробегать будет на каждую строчку, для экономии памяти, скажем? И обязательно альтернативный сорт должен уметь все те же функции, что и оригинальный.

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

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216885 https://rulinux.net/message.php?newsid=42613&page=1#216885 Tue, 09 Aug 2016 15:10:34 +0300 Для адекватного сравнения тогда надо и sort с рам диска хотя бы делать.

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


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


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

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216884 https://rulinux.net/message.php?newsid=42613&page=1#216884 Tue, 09 Aug 2016 15:02:10 +0300 > базу данных старых паспортов на гигабайт, но дабы не качать:

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

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

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

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

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216881 https://rulinux.net/message.php?newsid=42613&page=1#216881 Tue, 09 Aug 2016 14:39:44 +0300 На таких обьемах блох ловить, не выразительно получаются отрывы.

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

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

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

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216880 https://rulinux.net/message.php?newsid=42613&page=1#216880 Tue, 09 Aug 2016 14:34:14 +0300 на 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]$

 

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216879 https://rulinux.net/message.php?newsid=42613&page=1#216879 Tue, 09 Aug 2016 14:30:16 +0300 Ну уж сказал А выкладывай и Б. Все результаты интересны.

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216878 https://rulinux.net/message.php?newsid=42613&page=1#216878 Tue, 09 Aug 2016 14:29:34 +0300 Это сортировка или создание файла ?

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

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

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216877 https://rulinux.net/message.php?newsid=42613&page=1#216877 Tue, 09 Aug 2016 14:27:09 +0300
text

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


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

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216876 https://rulinux.net/message.php?newsid=42613&page=1#216876 Tue, 09 Aug 2016 13:55:56 +0300 даже выкладывать стыдно результаты =) на сях надо эти алгоритмы преписывать...

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216875 https://rulinux.net/message.php?newsid=42613&page=1#216875 Tue, 09 Aug 2016 11:57:48 +0300 ща заценим, тут http://mech.math.msu.su/~shvetz/54/inf/perl-problems/chSorting_sIdeas.xhtml 10 алгоритмов разных сортировки

]]> Re:[спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216874 https://rulinux.net/message.php?newsid=42613&page=1#216874 Tue, 09 Aug 2016 11:47:48 +0300 Ушёл создавать базу. Буду через 5 минут.

]]> [спв][у кого короче]Сортировки тред https://rulinux.net/message.php?newsid=42613&page=1#216873 https://rulinux.net/message.php?newsid=42613&page=1#216873 Tue, 09 Aug 2016 11:16:23 +0300 В обсуждениях новости опеннета 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 значными числами в баше.

]]>