ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная пирамида
126 сообщений из 126, показаны все 6 страниц
  все  
Тяпничная пирамида
    #39383680
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Здарова други.

Илья. Сова. Зяма. Владимир. Саша-меркурий. Дима. Форумчане.

Сегодня я хотел поговорить о пирамиде. Или heap. Или как в некоторых переводах
ее называют - "куча".



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

Собственно сабж:

1) Интересует где и как применяется. По моим сведениям
на базе heap построены такие структуры как очереди с приоритетами
(PriorityQueue).

В С++/stl есть методы для превращения векторов в пирамиду
(пирамидизация) и получение max/min ключа std::make_heap(..),
pop_heap(..) e.t.c.

Пирамидальная сортировка использует пирамиду как 1-ю фазу
сортировки. (См. линк).

Вобщем - поделитесь инфой кто где применял.

2) Интересует сравнение с Set/TreeSet/(Black&Red tree)
особенно в части тех-же очередей. Скользящее максимальное.

Условия тестинга. Как?

3) Прочие опции . Что еще можно получить с пирамиды?
Какова будет стоимость операций update ключа. Или удаления
элемента с середины пирамиды? Алгоритмически - заявлены
только - добавление в хвост и взятие головы (min/max).
А как быть с прочими операциями search?

4) Space Utilization . Вобщем если сравнивать с красно-черным
деревом - то привлекательна экономия места. В пирамидке нет
кросс-ссылок на элементы и можно всю структуру уложить в вектор.

5) Merge, Intersect и прочие реляционные операции над
пирамидами. Как? Поддержка структуры после mass-updates. Как?

6) Сравнение heap-sort с QuickSort (by Tony Hoare). . Чуть
позже я приведу скриншот из книжки маэстро Вирта. Обсудим.




Ccылки на источники.

1) Никлаус Вирт - Алгоритмы.
2) https://en.wikipedia.org/wiki/Heap_(data_structure)
3) https://en.wikipedia.org/wiki/Heapsort

P.S. Сорян если сразу не отвечу. С планшета - неудобно. Так что - с вечера с ноута.

P.P.S. Moar хардкода - приветствуется. Прошу не кидать в меня очень умные академические
статьи. Я на них надолго зависаю и дискурс не получается.
...
Рейтинг: 0 / 0
13.01.2017, 01:58
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39383688
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
maytonВобщем - поделитесь инфой кто где применял.А фиг его знает, где я его применяю. Везде наверное.
Просто у меня подход немножко другой - есть задача, под нее подбираются средства.
В данном случае, дерево этого вида удобно применять там где дерево является (или иногда раскладывается) в линейный набор данных. Ну или в массив какой-то размерности...
В общем, вот есть у тебя массив данных. Представь этот-же массив, в виде дерева - вот у тебя и классическая куча образовалась...

mayton2) Интересует сравнение с Set/TreeSet/(Black&Red tree)
особенно в части тех-же очередей. Скользящее максимальное.А зачем их друг-другу противопоставлять? Все эти структуры могут быть друг-другом одновременно. Зависит только от того как ты рассматриваешь набор данных.
Берешь ключи нод в куче - это Set. Красишь ноды - вот твоя куча и в цветное дерево превращается. (а TreeSet это и есть куча, но в некошерном ява стиле :)

mayton3) Прочие опции . Что еще можно получить с пирамиды?
Какова будет стоимость операций update ключа. Или удаления
элемента с середины пирамиды? Алгоритмически - заявлены
только - добавление в хвост и взятие головы (min/max).
А как быть с прочими операциями search?Ну вообще-то, стоимость у кучи O(k*с) для всех операций где k это ранг этого дерева, а c - максимальное количество детей у ноды.
И кем это вдруг заявлены операции "хвоста и головы" для дерева???? Ты с кучу с очередью путаешь? Они хоть и достаточно родственные вещи и очередь обычно делается через кучу, но все-же ты же про кучу начал спрашивать?

mayton4) Space Utilization . Вобщем если сравнивать с красно-черным
деревом - то привлекательна экономия места. В пирамидке нет
кросс-ссылок на элементы и можно всю структуру уложить в вектор.эээээ.... какая-такая экономия места? Красно-черные деревья это вообще-то частный случай бинарного дерева с минимизуремым (при покраске) рангом.
А куча не ставит ограничений на сбалансированность или количество детей у ноды. Поэтому и стоимость операций у кучи не настолько красивая как у цветных деревьев.

mayton5) Merge, Intersect и прочие реляционные операции над
пирамидами. Как? Поддержка структуры после mass-updates. Как?Да элементарно!
Merge - там вообще всего две операции: находишь в первом дереве ноду которая может быть родителем у корневой ноды второго дерева - и добавляешь этот бывший корень в список детей. Все.
Intersect - сложнее. Тут уже без полного перебора одного из деревьев не обойтись. Но тоже не особо сложно - найти есть или нет конкретный ключ в куче не так уж сложно (тот-же O(k*с))

mayton6) Сравнение heap-sort с QuickSort (by Tony Hoare). . Чуть
позже я приведу скриншот из книжки маэстро Вирта. Обсудим.Такой фигней я ни разу не занимался, извините. Но по идее, qsort должен быть побыстрее слегка.
...
Рейтинг: 0 / 0
13.01.2017, 03:13
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39384236
ermak.nn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ermak.nn
Участник
White Owlmayton4) Space Utilization . Вобщем если сравнивать с красно-черным
деревом - то привлекательна экономия места. В пирамидке нет
кросс-ссылок на элементы и можно всю структуру уложить в вектор.эээээ.... какая-такая экономия места? Красно-черные деревья это вообще-то частный случай бинарного дерева с минимизуремым (при покраске) рангом.
А куча не ставит ограничений на сбалансированность или количество детей у ноды. Поэтому и стоимость операций у кучи не настолько красивая как у цветных деревьев.
Я думаю имеется ввиду, что так как куча лежит в векторе, то нам не надо хранить указатели на детей и предков.


В работе лично я не применял.
Знаю, что на практике используется в priority queues, heapsort.
Решает задачу мгновенного нахождения медианы для набора данных (использование 2ух heap: одна - MAX, другая - MIN)
...
Рейтинг: 0 / 0
13.01.2017, 15:06
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39384255
Фотография NekZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NekZ
Участник
ermak.nnЯ думаю имеется ввиду, что так как куча лежит в векторе, то нам не надо хранить указатели на детей и предков.


Не обязательно. Имея вектор/массив, можно получать доступ к элементам кучи по следующим правилам
i -- сам узел
i * 2 -- левый дочерний узел
i * 2 + 1 -- правый дочерний узел
i % 2 -- родитель

Можно просто скидать все элементы в массив, и затем хипифицировать (heapify) его.
...
Рейтинг: 0 / 0
13.01.2017, 15:18
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39384614
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
White OwlА зачем их друг-другу противопоставлять? Все эти структуры могут быть друг-другом одновременно. Зависит только от того как ты рассматриваешь набор данных.
Берешь ключи нод в куче - это Set. Красишь ноды - вот твоя куча и в цветное дерево превращается. (а TreeSet это и есть куча, но в некошерном ява стиле :)

Извини Сова. Но здесь я буду с тобой спорить. Пирамида и B&R-Tree это разные структуры данных.
Насколько я понимаю, способность пирамиды раскладываться в вектор по формуле - это основное
и важное свойство. Можно и обратно. Но для B&R Tree это - сомнительный трюк. Сам факт покраски
узлов - сообщает нам важное свойство. Стоя на узле - мы не знаем текущего индекса. А операции
т.н. разворота дерева можно провести только при условии что мы оперируем указателями.
Двигать узлы (и их потомков!) эффективно игрой указателей но никак не физическим перемещением
ключей.

White OwlНу вообще-то, стоимость у кучи O(k*с) для всех операций где k это ранг этого дерева, а c - максимальное количество детей у ноды.
И кем это вдруг заявлены операции "хвоста и головы" для дерева???? Ты с кучу с очередью путаешь? Они хоть и достаточно родственные вещи и очередь обычно делается через кучу, но все-же ты же про кучу начал спрашивать?

Здесь - смешались в кучу кони и люди. Я так чувсвтую что ты мало знаком с пирамидой.

Давай разделять.

Я сейчас попробую описать некоторые свойства пирамиды
(в том виде как я их сам понял) а ты - сообщи где несогласен или где есть какое-то противоречие.

1) Куча - вектор, элементы которого удовлетворяют формуле.



Назовем это "условие пирамидизации".

Для картинки вверху топика этот вектор будет выглядеть так:

100, 19, 36, 17, 3, 25, 1, 2, 7

Формула - соблюдена.

2) На вершине кучи (на первой позиции всегда находится элемент с наибольшим ключом).
Код: plaintext
1.
2.
(можно изменить порядок сортировки и перевернуть условие 
и мы получим наименьший элемент на вершине)



3) Наличие метода добавления элемента в пирамиду (назовем это offer()).
Это добавление в хвост вектора нового элемента. И выполнение
процедуры "просеивания" его сквозь всю цепочку родительских
элементов до тех пор пока условие "пирамидизации" не станет
выполнятся. При просеивании элементы меняются местами
как в bubble-sort.

4) Наличие метода извлечения максимального элемента (назовем это poll()).
После извлечения элемента a[0] у нас образуется дырка,
которую нужно заполнить опять-же просеиванием
элементов.

Главное свойство. Цена операции o(1).

(здесь возможна ситуация когда в хвосте пирамиды будут
null элементы которые нужно уплотнять соблюдая формулу,
и я-бы поспорил по поводу o(1), возможно тут имелся
в виду peek() а не poll()).

5) Рост и деградация пирамиды просиходит точно так-же
как и обычного вектора но с соблюдением пирамидизации.
Возможен вариант когда мы будет откладывать пирамидизацию,
и оптимизировать пакетные действия.

Деградирующая пирамида не обязана освобождать память.
Можно просто маркировать последний элемент как high watermark
(HWM) и учитывать его в алгоритмах.

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

Да элементарно!
Merge - там вообще всего две операции: находишь в первом дереве ноду которая может быть родителем у корневой ноды второго дерева - и добавляешь этот бывший корень в список детей. Все.
Intersect - сложнее. Тут уже без полного перебора одного из деревьев не обойтись. Но тоже не особо сложно - найти есть или нет конкретный ключ в куче не так уж сложно (тот-же O(k*с))

Нет. Merge скорее всего так не сработает. Впрочем будем посмотреть. Когда код будет.
...
Рейтинг: 0 / 0
14.01.2017, 02:01
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39384619
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А вот цифры. На скриншоте табличка где сравниваются алгоритмы
сортировки.

Единственное что меня смущает - это достаточно старые сведенья.
Господин Вирт собирал их на древних конфигурациях и что также
доставляет на своих Modula/Pascal - подобных языках.

Тоесть цифирки интересные но нуждаются в пере-проверке.
...
Рейтинг: 0 / 0
14.01.2017, 02:14
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39384646
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton4) Наличие метода извлечения максимального элемента (назовем это poll()).
После извлечения элемента a[0] у нас образуется дырка,
которую нужно заполнить опять-же просеиванием
элементов.

Главное свойство. Цена операции o(1).
немного подправлю, не извлечение , а нахождение имеет o(1)

при равной асимптоматике эта сортировка проигрывает QSort это да, но у неё другие полезные свойства - она нерекурсивная и выполняется практически стабильное время (ту же QSort из-за отсутствия этих свойств использовать, например, в ядре нельзя)
...
Рейтинг: 0 / 0
14.01.2017, 08:43
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39384653
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
mayton,

Асимптотики доступа есть в Вике.

Но ты неправильно подходишь - ты берешь абстрактный алгоритм, и пытаешься привязать его к реальности (проблема молотка).

А интересно наоборот.
...
Рейтинг: 0 / 0
14.01.2017, 09:22
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39384682
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SiemarglНо ты неправильно подходишь - ты берешь абстрактный алгоритм, и пытаешься привязать его к реальности (проблема молотка).
Вообще ничего не вижу неправильного. Возможно это философский спор, но КМК основные
творческие успехи разработчика заключены именно в привязке абстрактных алгоритмов к реальности.
Обратное - сомнительно по причине понятия "алгоритм" в нашем современном понимании.
Большинство алгоритмов - уже созданы в середине XX века. Мы просто их берем и применяем
как совокупность кирпичиков в Lego. Разумеется генерализируя типы.

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

Поэтому нет никакой проблемы молотка.
...
Рейтинг: 0 / 0
14.01.2017, 13:03
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385157
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вброшу децл кода.

Процедура sift и heapify были стянуты у маэстро Вирта. Еще часть кода типа округления
по двоичному логарифму и модульный тест были просто написаны мной.

Ввиду того что старый немец любил индексы которые начинаются с 1, возможны
некоторые глючки или несоответствия классическому алгоритму но я думаю что
таковых будет мало либо вообще не будет.

(Сорян за отсутствие С++ и шаблонов. Возможно чуть позже обобщу но сейчас это не суть важно.)
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* 
 * Heap demo. Ported from Niklaus Wirth's book
 *
 * mayton 16-Jan-207
 */ 

int clp2(int x){
        x = x - 1;
        x = x | (x>>1);
        x = x | (x>>2);
        x = x | (x>>4);
        x = x | (x>>8);
        x = x | (x>>16);
        return x + 1;
}

void show(int * a,int n){
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            printf("%d", a[i]);
        } else {
            printf(",%d", a[i]);
        }
    }
}

void showLikeHeap(int * a, int n) {
    printf("00000000h [ ");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
        if ((i != n - 1) && (clp2(i + 2) == (i + 2))) {
            printf("]\n");
            printf("%08Xh [ ",i);
        }
    }
    printf("]");
}



bool isCorrect(int * a, int N, int m) {
    int k = N / 2;
    for (int i = 0; i < k; i++) {
        if (m * a[i] > m * a[i * 2]) {
            return false;
        }
        if (m * a[i] > m * a[i * 2 + 1]) {
            return false;
        }
    }
    return true;
}

#define N 63
#define ORDER_ASC 1
#define ORDER_DESC -1
#define RANGE 1000

void sift(int * a, int L, int R, int m) {
    int i = L;
    int j = 2 * L;
    int x = a[L];
    if (j < R && (m * a[j + 1] < m * a[j])) {
        j++;
    }
    while (j <= R && (m * a[j] < m * x)) {
        a[i] = a[j];
        i = j;
        j *= 2;
        if (j < R && (m * a[j + 1] < m * a[j])) {
            j++;
        }
    }
    a[i] = x;
}

void heapify(int * a, int n, int m) {
    int L = n / 2 + 1;
    while (L > 0) {
        L--;
        sift(a, L, n-1, m);
    }
}

int main(int argc, char **argv, char **env) {
    srand(0);
    int *a = malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) {
        a[i] = rand() % RANGE;
    }
    printf("Original array: \n");
    show(a,N);
    int order = ORDER_ASC;
    printf("\nHipifyed array (asc): \n");
    heapify(a, N, order);
    showLikeHeap(a,N);
    printf("\nValidation: ");
    if (isCorrect(a,N,order)){
        printf("\nPyramid is OK!\n");
    } else {
        printf("\nPyramid is incorrect!\n");
    }
    free(a);
    return 0;
}

...
Рейтинг: 0 / 0
16.01.2017, 03:04
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385382
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonВброшу децл кода.

Процедура sift и heapify были стянуты у маэстро Вирта. Еще часть кода типа округления
по двоичному логарифму и модульный тест были просто написаны мной.

Ввиду того что старый немец любил индексы которые начинаются с 1, возможны
некоторые глючки или несоответствия классическому алгоритму но я думаю что
таковых будет мало либо вообще не будет.

(Сорян за отсутствие С++ и шаблонов. Возможно чуть позже обобщу но сейчас это не суть важно.)
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* 
 * Heap demo. Ported from Niklaus Wirth's book
 *
 * mayton 16-Jan-207
 */ 

int clp2(int x){
        x = x - 1;
        x = x | (x>>1);
        x = x | (x>>2);
        x = x | (x>>4);
        x = x | (x>>8);
        x = x | (x>>16);
        return x + 1;
}

void show(int * a,int n){
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            printf("%d", a[i]);
        } else {
            printf(",%d", a[i]);
        }
    }
}

void showLikeHeap(int * a, int n) {
    printf("00000000h [ ");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
        if ((i != n - 1) && (clp2(i + 2) == (i + 2))) {
            printf("]\n");
            printf("%08Xh [ ",i);
        }
    }
    printf("]");
}



bool isCorrect(int * a, int N, int m) {
    int k = N / 2;
    for (int i = 0; i < k; i++) {
        if (m * a[i] > m * a[i * 2]) {
            return false;
        }
        if (m * a[i] > m * a[i * 2 + 1]) {
            return false;
        }
    }
    return true;
}

#define N 63
#define ORDER_ASC 1
#define ORDER_DESC -1
#define RANGE 1000

void sift(int * a, int L, int R, int m) {
    int i = L;
    int j = 2 * L;
    int x = a[L];
    if (j < R && (m * a[j + 1] < m * a[j])) {
        j++;
    }
    while (j <= R && (m * a[j] < m * x)) {
        a[i] = a[j];
        i = j;
        j *= 2;
        if (j < R && (m * a[j + 1] < m * a[j])) {
            j++;
        }
    }
    a[i] = x;
}

void heapify(int * a, int n, int m) {
    int L = n / 2 + 1;
    while (L > 0) {
        L--;
        sift(a, L, n-1, m);
    }
}

int main(int argc, char **argv, char **env) {
    srand(0);
    int *a = malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) {
        a[i] = rand() % RANGE;
    }
    printf("Original array: \n");
    show(a,N);
    int order = ORDER_ASC;
    printf("\nHipifyed array (asc): \n");
    heapify(a, N, order);
    showLikeHeap(a,N);
    printf("\nValidation: ");
    if (isCorrect(a,N,order)){
        printf("\nPyramid is OK!\n");
    } else {
        printf("\nPyramid is incorrect!\n");
    }
    free(a);
    return 0;
}


mayton, скажи често на на духу :) , тебе слава стебелька покоя не дает ?
Это же стебелесипед :).

Я то думал, что речь тут идет о дешевой и оптимальной сериализации .....
...
Рейтинг: 0 / 0
16.01.2017, 13:15
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385418
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Все украдено до нас :)

1. пространсво бьется на страницы размером попадающим в линейку кеша процессора.
2. У каждой страницы есть заголовок и трейлер.
3. В загловке лежит всякая метаинформация и ссылки на соседние страницы .
4. В трейлере массив смещений элементов данных страницы в нужной сортировке.
5. Элементы вставляются в страницу как попало , трейлер раздвигается на встречу
заполняемым элемантам данных функцией memcpy c соблюдением сортировки.
6. Существует функция паковки страницы ( для операции удаления ) смещение данных к хедеру и перестройка трейлера.
7 Существует функции сплитования и объдинения страниц с перезаписью хедеров
и трейлеров по критериям значений из метаданных в хедерах.
8. Существует справочник страниц занимающий энное количество страниц по фиксированному
смещению от базового адреса или начала файла.
9. Нигде не используется прямая адресация.

В конечном итоге получается индексный rowid-сипед из любой СУБД
на который наворачивается LRU алгоритм.
...
Рейтинг: 0 / 0
16.01.2017, 14:00
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385428
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
В оракле похожий алгоритм называется Locally Managed Tablespace.
...
Рейтинг: 0 / 0
16.01.2017, 14:09
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385447
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Главная задача, гарантированно попдать всей страницей в линейку кеша процессора,
что бы при обращении к странице она целяком была зачитана в кеш,
а при изменении с минимальным количеством приседаний на шине
отмапилась в оперативную память.
...
Рейтинг: 0 / 0
16.01.2017, 14:25
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385506
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
mayton3) https://en.wikipedia.org/wiki/Heapsort



ИМХО Heapsort есть вид с боку сортировки слиянием
...
Рейтинг: 0 / 0
16.01.2017, 15:30
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385602
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
д0kХmayton3) https://en.wikipedia.org/wiki/Heapsort



ИМХО Heapsort есть вид с боку сортировки слиянием
непохоже совсем
...
Рейтинг: 0 / 0
16.01.2017, 16:58
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385633
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
делал как-то тесты по сортировкам

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
QSort
  inverse array: time=16  CompareCount=1600032  ChangeCount=115535
  sorted  array: time=0  CompareCount=1600032  ChangeCount=65535
  randomic array: time=31  CompareCount=2329764  ChangeCount=420283
QSort2
  inverse array: time=0  CompareCount=1501728  ChangeCount=50000
  sorted  array: time=16  CompareCount=1501729  ChangeCount=0
  randomic array: time=15  CompareCount=2129801  ChangeCount=366528
HeapSort
  inverse array: time=16  CompareCount=2928116  ChangeCount=1497536
  sorted  array: time=31  CompareCount=4256886  ChangeCount=2937924
  randomic array: time=31  CompareCount=3059438  ChangeCount=1628454
Shell sort
  inverse array: time=16  CompareCount=2263730  ChangeCount=763730
  sorted  array: time=15  CompareCount=1500022  ChangeCount=0
  randomic array: time=3063  CompareCount=389167707  ChangeCount=387667693

собственно такие плохие результаты у HeapSort из-за лишней абстракции свёртка-развёртка
...
Рейтинг: 0 / 0
16.01.2017, 17:32
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385636
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
пардон
...
Рейтинг: 0 / 0
16.01.2017, 17:33
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385639
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

давай следующей темой Декартовы деревья, там есть все что хочешь из того что написано
...
Рейтинг: 0 / 0
16.01.2017, 17:35
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385755
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ого тут букв.
...
Рейтинг: 0 / 0
16.01.2017, 22:29
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385756
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan)mayton,

давай следующей темой Декартовы деревья, там есть все что хочешь из того что написано
Тема любопытная. Но я щас не готов писать что-то про Декартовы деревья. Для начала надо хотя-бы
ознакомится с материалом и понять юзкейс. Но вы можете стартовать еще один пятничный дискурс
и я присоединюсь.
...
Рейтинг: 0 / 0
16.01.2017, 22:31
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385757
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kХЯ то думал, что речь тут идет о дешевой и оптимальной сериализации .....
Да расслабся Док. Во первых из контекста понимай что тема - пятничная.
Поэтому - на расслабоне. Не блокер. Не авария. Не рабочий момент а так.

Что там по поводу сериализации? Не поверишь - вообще не думал.
Думал пока об очередях с приоритетами.
...
Рейтинг: 0 / 0
16.01.2017, 22:34
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385777
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan) пардон
Ёшкин крот! Этож Паскаль. :) Мне его собрать нечем.
...
Рейтинг: 0 / 0
17.01.2017, 00:27
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385779
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
White OwlИ кем это вдруг заявлены операции "хвоста и головы" для дерева???? Ты с кучу с очередью путаешь? Они хоть и достаточно родственные вещи и очередь обычно делается через кучу, но все-же ты же про кучу начал спрашивать?

Я всё-таки поднялся с кресла и прошёлся аж до шкафа (огого!) чтобы взять с полки Роберта Седжвика.

Вот что пишет эта старая задница:
Р.Седжвик - Фундаментальные Алгоритмы - Части 1-4Глава 9

Определение 9.1. Очередь по приоритетам представляет
собой структуру элементов с ключами, которая поддерживает
две основные операции: вставку нового элемента и удаление
элемента с наибольшим значением ключа.
...
Рейтинг: 0 / 0
17.01.2017, 00:33
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385780
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
QSort2
  inverse array: time=0  CompareCount=1501728  ChangeCount=50000
  sorted  array: time=16  CompareCount=1501729  ChangeCount=0
  randomic array: time=15  CompareCount=2129801  ChangeCount=366528
HeapSort
  inverse array: time=16  CompareCount=2928116  ChangeCount=1497536
  sorted  array: time=31  CompareCount=4256886  ChangeCount=2937924
  randomic array: time=31  CompareCount=3059438  ChangeCount=1628454

По поводу сведений который представлены здесь. Я не знаю что означает параметр time.
По всей видимости это время, которое было потрачено. Но удивляет несколько "квантованный"
характер этих данных. У нас в наличии 0, 15, 16, 31. Такое ощущение будто мы ведем учет
фотонов.

И хотя было протестировано 4 алгоритма в 3х условиях - наши данные - весьма непрезентативны.

Я-бы предложил увеличить время замера хотя-бы на два порядка чтобы этот загадочный
"фотон" усреднился и больше не портил нам картину.
...
Рейтинг: 0 / 0
17.01.2017, 00:53
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385812
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

По времени - согласен, но если увеличить время то Shell sort можно не дождаться и основное что измерялось это количество сравнений и количество перестановок
...
Рейтинг: 0 / 0
17.01.2017, 07:26
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385823
ermak.nn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ermak.nn
Участник
kealon(Ruslan), а можно не использовать shellsort в сравнении, а взять какой-нибудь Introsort ?
И скажите, чем различаются qsort и qsort2?
...
Рейтинг: 0 / 0
17.01.2017, 08:15
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39385863
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ermak.nnkealon(Ruslan), а можно не использовать shellsort в сравнении, а взять какой-нибудь Introsort ?
И скажите, чем различаются qsort и qsort2?
qsort логически делит массив на 2 части "<=" и ">" что приводит при большом количестве равных элементов к значительным перестановкам
qsort2 оптимизирует эту часть и сортирует на 3 участка: "<" "=" ">"
...
Рейтинг: 0 / 0
17.01.2017, 10:00
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39386194
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
maytonд0kХЯ то думал, что речь тут идет о дешевой и оптимальной сериализации .....
Да расслабся Док. Во первых из контекста понимай что тема - пятничная.
Поэтому - на расслабоне. Не блокер. Не авария. Не рабочий момент а так.

Что там по поводу сериализации? Не поверишь - вообще не думал.
Думал пока об очередях с приоритетами.

Для меня, как программера ушедшего в сисадминство и дба,
куча ( heap) асоциируется с возможностью выгрузки в своп
или возможности использования дисковго пространства ( temp space) непосредственно
в алгоритме сортировки.
Поэтому алгоритмы с возможностью сериализации на диск ,
как пятничная, академическая тема для меня предствляет интерес.

Я на все это смотрю с двух сторон, с пятнично-академически-алгоритмической и
практической-проектно-эксплуатационной.
...
Рейтинг: 0 / 0
17.01.2017, 16:13
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39386232
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
д0kХmaytonпропущено...

Да расслабся Док. Во первых из контекста понимай что тема - пятничная.
Поэтому - на расслабоне. Не блокер. Не авария. Не рабочий момент а так.

Что там по поводу сериализации? Не поверишь - вообще не думал.
Думал пока об очередях с приоритетами.

Для меня, как программера ушедшего в сисадминство и дба,
куча ( heap) асоциируется с возможностью выгрузки в своп
или возможности использования дисковго пространства ( temp space) непосредственно
в алгоритме сортировки.
Поэтому алгоритмы с возможностью сериализации на диск ,
как пятничная, академическая тема для меня предствляет интерес.

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

У меня есть generic external merge_sort для С++, написан самолично мною...
Интересно ? :-)
...
Рейтинг: 0 / 0
17.01.2017, 16:52
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39386266
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
MasterZiv, давай
...
Рейтинг: 0 / 0
17.01.2017, 17:24
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39386313
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
д0kХВсе украдено до нас :)

1. пространсво бьется на страницы размером попадающим в линейку кеша процессора.
2. У каждой страницы есть заголовок и трейлер.
3. В загловке лежит всякая метаинформация и ссылки на соседние страницы .
4. В трейлере массив смещений элементов данных страницы в нужной сортировке.
5. Элементы вставляются в страницу как попало , трейлер раздвигается на встречу
заполняемым элемантам данных функцией memcpy c соблюдением сортировки.
6. Существует функция паковки страницы ( для операции удаления ) смещение данных к хедеру и перестройка трейлера.
7 Существует функции сплитования и объдинения страниц с перезаписью хедеров
и трейлеров по критериям значений из метаданных в хедерах.
8. Существует справочник страниц занимающий энное количество страниц по фиксированному
смещению от базового адреса или начала файла.
9. Нигде не используется прямая адресация.

В конечном итоге получается индексный rowid-сипед из любой СУБД
на который наворачивается LRU алгоритм.
Док.

Я честно долго не знал как ответить на это сообщение. Здесь - целое техническое задание.
О чем оно? Блочная DBMS ? Возможно ты настолько лаконичен и гениален что
можешь сам по этому описанию что-то для себя прояснить или понять но мне
пока не понятна идея. Или это даже достойно отдельного топика.
...
Рейтинг: 0 / 0
17.01.2017, 18:27
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39386315
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan)mayton,

По времени - согласен, но если увеличить время то Shell sort можно не дождаться и основное что измерялось это количество сравнений и количество перестановок
Если сравнивать heap-sort и семейство quick-sort-* алгоритмов то Шелла можно выкинуть.
...
Рейтинг: 0 / 0
17.01.2017, 18:29
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39386342
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
maytonWhite OwlА зачем их друг-другу противопоставлять? Все эти структуры могут быть друг-другом одновременно. Зависит только от того как ты рассматриваешь набор данных.
Берешь ключи нод в куче - это Set. Красишь ноды - вот твоя куча и в цветное дерево превращается. (а TreeSet это и есть куча, но в некошерном ява стиле :)

Извини Сова. Но здесь я буду с тобой спорить. Пирамида и B&R-Tree это разные структуры данных.
Насколько я понимаю, способность пирамиды раскладываться в вектор по формуле - это основное
и важное свойство. Можно и обратно. Но для B&R Tree это - сомнительный трюк.Я не на этом акцент делал.
Куча (дерево с индексированными нодами в строгом порядке) может одновременно является и цветным деревом (ноды имеют дополнительный флаг цвета).
А так-то конечно, просто цветное дерево в массив отобразить может быть и невозможно вообще.

mayton1) Куча - вектор, элементы которого удовлетворяют формуле.



Назовем это "условие пирамидизации".Вот уже это неверно.
Это условие, это частный случай для бинарных пирамид, которые рассчитаны на укладывание в одномерный массив и имеют легкий алгоритм убирания корня (и замены его наиболее подходящей нодой из оставшихся) и добавления новых нод. Идеально для создания очередей, но это всего один единственный вариант пирамиды.
На самом деле, у кучи только два правила: каждая нода имеет ключ, ключ ребенка всегда меньше или равен ключа родителя. Все. У кучи нет ограничений на количество детей у ноды и нет ограничений на высоту дерева.

Из самых широко известных применений куч - индексы в СУБД. В файловых системах индексация организована тоже через кучу.

maytonНет. Merge скорее всего так не сработает. Впрочем будем посмотреть. Когда код будет.Сработает, просто пойми что очередь основанная на дереве это всего-лишь частный случай кучи. (Binary heap vs heap если возьмешься читать учебники :) )
...
Рейтинг: 0 / 0
17.01.2017, 19:19
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39386482
д0кХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0кХ
Гость
maytonд0kХВсе украдено до нас :)

1. пространсво бьется на страницы размером попадающим в линейку кеша процессора.
2. У каждой страницы есть заголовок и трейлер.
3. В загловке лежит всякая метаинформация и ссылки на соседние страницы .
4. В трейлере массив смещений элементов данных страницы в нужной сортировке.
5. Элементы вставляются в страницу как попало , трейлер раздвигается на встречу
заполняемым элемантам данных функцией memcpy c соблюдением сортировки.
6. Существует функция паковки страницы ( для операции удаления ) смещение данных к хедеру и перестройка трейлера.
7 Существует функции сплитования и объдинения страниц с перезаписью хедеров
и трейлеров по критериям значений из метаданных в хедерах.
8. Существует справочник страниц занимающий энное количество страниц по фиксированному
смещению от базового адреса или начала файла.
9. Нигде не используется прямая адресация.

В конечном итоге получается индексный rowid-сипед из любой СУБД
на который наворачивается LRU алгоритм.
Док.

Я честно долго не знал как ответить на это сообщение. Здесь - целое техническое задание.
О чем оно? Блочная DBMS ? Возможно ты настолько лаконичен и гениален что
можешь сам по этому описанию что-то для себя прояснить или понять но мне
пока не понятна идея. Или это даже достойно отдельного топика.

Да , это структура блока DBMS позволяющая создать виртуально непрырывную
rowid адресацию, не привяззаную к адресам в памяти, навернуть на нее индексный поиск
и LRU алгоритм ( буферный кеш).

Я из 90-х , в те времена каждый уважаюший себя программист
в свободное время, тогда небыло фейсбуков, вконтактов и политических срачей,
создавал нетленку , свой оконный интрефейс, СУБД или операционную систему.

.
...
Рейтинг: 0 / 0
17.01.2017, 23:19
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39386578
ermak.nn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ermak.nn
Участник
White OwlИз самых широко известных применений куч - индексы в СУБД. В файловых системах индексация организована тоже через кучу.


Вы, скорее всего, вы немного перепутали. Насколько я знаю, там куча не применяется, там используются, например, сбалансированные деревья поиска, B+ деревья, T деревья, hash таблицы. Да и непонятно, как их использовать для поиска, ведь они не для этого делались.
...
Рейтинг: 0 / 0
18.01.2017, 07:49
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39387125
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
ermak.nnWhite OwlИз самых широко известных применений куч - индексы в СУБД. В файловых системах индексация организована тоже через кучу.


Вы, скорее всего, вы немного перепутали. Насколько я знаю, там куча не применяется, там используются, например, сбалансированные деревья поиска, B+ деревья, T деревья, hash таблицы. Да и непонятно, как их использовать для поиска, ведь они не для этого делались.Еще один, за деревьями леса не видит.... Все перечисленные, это частные случаи кучи.
У них есть собственные особенности, но это все идеальные кучи/пирамиды.
...
Рейтинг: 0 / 0
18.01.2017, 19:17
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39387230
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
White Owlermak.nnпропущено...


Вы, скорее всего, вы немного перепутали. Насколько я знаю, там куча не применяется, там используются, например, сбалансированные деревья поиска, B+ деревья, T деревья, hash таблицы. Да и непонятно, как их использовать для поиска, ведь они не для этого делались.Еще один, за деревьями леса не видит.... Все перечисленные, это частные случаи кучи.
У них есть собственные особенности, но это все идеальные кучи/пирамиды.
Давайте разделим терминологию. Я не просто так назвал топик "Пирамидой".

В противоположность - heap.

B инфо-технологиях данный термин я встречал минимум дважды. "Heap"-ом в Java называют
память. В DBMS Oracle под "heap" обычно подразумевают create table ... organization by heap.
Это умолчательный способ аллокации экстентов. В противоположность другой способ - как раз
B+Tree.

То о чем говорит Сова я не очень понимаю т.к. heap с точки зрения Никлауса Вирта
это структура данных которая удовлетворяет формуле которую я описал выше.

Именно об этой heap я и говорю в топике. Heap Data Structure или HDS чтобы далее было понятно.

Впрочем я не модерирую течение мысли в топике. И если кто-то создает новые смыслы
- то я не против. Просто прошу разделить терминологию.
...
Рейтинг: 0 / 0
18.01.2017, 22:43
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39387305
ermak.nn
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ermak.nn
Участник
maytonWhite Owlпропущено...
Еще один, за деревьями леса не видит.... Все перечисленные, это частные случаи кучи.
У них есть собственные особенности, но это все идеальные кучи/пирамиды.
Давайте разделим терминологию. Я не просто так назвал топик "Пирамидой".

В противоположность - heap.

B инфо-технологиях данный термин я встречал минимум дважды. "Heap"-ом в Java называют
память. В DBMS Oracle под "heap" обычно подразумевают create table ... organization by heap.
Это умолчательный способ аллокации экстентов. В противоположность другой способ - как раз
B+Tree.

То о чем говорит Сова я не очень понимаю т.к. heap с точки зрения Никлауса Вирта
это структура данных которая удовлетворяет формуле которую я описал выше.

Именно об этой heap я и говорю в топике. Heap Data Structure или HDS чтобы далее было понятно.

Впрочем я не модерирую течение мысли в топике. И если кто-то создает новые смыслы
- то я не против. Просто прошу разделить терминологию.

Более понятного определения, как на wiki ( Heap ) не нашел. Может мы пользуемся разными терминами и из-за этого случилось недопонимание?
...
Рейтинг: 0 / 0
19.01.2017, 07:25
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39387355
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мой первоисточник. Стр. 89. Сортировка с помощью дерева.

http://snilit.tspu.ru/uploads/files/default/virt.pdf
...
Рейтинг: 0 / 0
19.01.2017, 09:18
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39387927
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
maytonТо о чем говорит Сова я не очень понимаю т.к. heap с точки зрения Никлауса Вирта
это структура данных которая удовлетворяет формуле которую я описал выше.Увы, но со времен Вирта прошло достаточно много времени. То что он описывал на 89-ой странице, ныне считается "balanced binary heap". Это тоже-самое что и "нормальная" куча, но с ограничениями "не более двух детей на ноду" и "дерево сбалансировано".


maytonИменно об этой heap я и говорю в топике. Heap Data Structure или HDS чтобы далее было понятно.А вот как раз Heap Data Structure может иметь столько детей на ноду, сколько захочется и баланс в Heap Data Structure не обязателен.

Вирт это конечно хорошо и классика, но увы... С тех пор было написано много других учебников, и сделано много разных дополнений и обобщений. На Вирте наука не остановилась :)
...
Рейтинг: 0 / 0
19.01.2017, 19:29
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39392529
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
mayton
1) Интересует где и как применяется. По моим сведениям
на базе heap построены такие структуры как очереди с приоритетами
(PriorityQueue).


В С++/stl есть методы для превращения векторов в пирамиду
(пирамидизация) и получение max/min ключа std::make_heap(..),
pop_heap(..) e.t.c.

Пирамидальная сортировка использует пирамиду как 1-ю фазу
сортировки. (См. линк).

Вобщем - поделитесь инфой кто где применял.


Данная структура используется для сортировки за и для реализации priority queue. Применяется, например, в жадных алгоритмах, в задачах планирования(возможно даже в банальном tfs, но в этом я не уверен).

mayton2) Интересует сравнение с Set/TreeSet/(Black&Red tree)
особенно в части тех-же очередей. Скользящее максимальное.

Условия тестинга. Как?

Что такое скользящее максимальное?
mayton3) Прочие опции . Что еще можно получить с пирамиды?
Какова будет стоимость операций update ключа. Или удаления
элемента с середины пирамиды? Алгоритмически - заявлены
только - добавление в хвост и взятие головы (min/max).
А как быть с прочими операциями search?


При создании пирамиды элементы двигаются пузырьком, т.к. высота двоичной пирамиды , то и двигаться пузырек может не больше этого расстояния, потому асимптотика вставки
Search? Данная структура данных, по крайней мере двоичная пирамида не предназначена для поиска, поскольку мы можем наблюдать только слабую упорядоченность - min heap или max heap. Потому поиск элемента занимает линейное время


mayton4) Space Utilization . Вобщем если сравнивать с красно-черным
деревом - то привлекательна экономия места. В пирамидке нет
кросс-ссылок на элементы и можно всю структуру уложить в вектор.

Можно, это одна из особенностей пирамиды)


mayton6) Сравнение heap-sort с QuickSort (by Tony Hoare). . Чуть
позже я приведу скриншот из книжки маэстро Вирта. Обсудим.

Худшее время сортировки с использованием пирамиды , qsort - . Мне кажется, это самое важное различие. Скорее всего в каких либо ОСРВ используются именно такие алгоритмы, но это только мое предположение))
...
Рейтинг: 0 / 0
26.01.2017, 21:53
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39392534
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
д0kХДля меня, как программера ушедшего в сисадминство и дба,
куча ( heap) асоциируется с возможностью выгрузки в своп
или возможности использования дисковго пространства ( temp space) непосредственно
в алгоритме сортировки.


Вы имеете ввиду отсутствие дополнительных затрат по памяти при сортировке кучей?
...
Рейтинг: 0 / 0
26.01.2017, 22:02
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39392603
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryЧто такое скользящее максимальное?

На ходу придумал. Есть скользящее среднее. Это что-то вроде ФНЧ. Есть выборка измерений с привязкой ко времени.
И есть окно в этой выборке (например в 1 минуту) где ты меряешь арифметическое среднее.

А почему нельзя максимальное? ХЗ. Я подумал - пускай будет.
...
Рейтинг: 0 / 0
27.01.2017, 01:01
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39392663
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Не в тему, но про сортировку :)

Столкнулся с проблемой что сортировка сортированного достаточно долго происходит. Никогда не задумывался, а тут просто задача попалась что на входе обычно сортированный массив, но иногда ему в конец немного дописывается, поэтому надо отсортировать. Воткнул сортировку и тормоза полезли. Ради любопытства закодил Шэлла и квиксорт - не быстрее штатной.

В итоге добавил проверку на отсортированность. Проход в цикле и сравнение соседних элементов. Проверка сортированного по времени работает в 10 раз быстрее чем его сортировка.

Интересно есть ли какие-то алгоритмы сортировки заточенные на почти отсортированные массивы?
...
Рейтинг: 0 / 0
27.01.2017, 08:44
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39392732
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima TНе в тему, но про сортировку :)

Столкнулся с проблемой что сортировка сортированного достаточно долго происходит. Никогда не задумывался, а тут просто задача попалась что на входе обычно сортированный массив, но иногда ему в конец немного дописывается, поэтому надо отсортировать. Воткнул сортировку и тормоза полезли. Ради любопытства закодил Шэлла и квиксорт - не быстрее штатной.

В итоге добавил проверку на отсортированность. Проход в цикле и сравнение соседних элементов. Проверка сортированного по времени работает в 10 раз быстрее чем его сортировка.

Интересно есть ли какие-то алгоритмы сортировки заточенные на почти отсортированные массивы?
да есть наверное, тот же HeapSort если как -то соединить с сортировкой слиянием наверное можно добиться ускорения
вопрос насколько быстро можно объединять две кучи
...
Рейтинг: 0 / 0
27.01.2017, 10:03
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39392752
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

в чём плюсы heapsort 20105057
...
Рейтинг: 0 / 0
27.01.2017, 10:16
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393294
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)да есть наверное, тот же HeapSort если как -то соединить с сортировкой слиянием наверное можно добиться ускорения
вопрос насколько быстро можно объединять две кучи
У меня массивы, там уже нахождение O(1). В принципе при объединении сортированных можно переливать в третий, если оба сортированные, то это в один проход сделается. Потестить надо.

Но проблема первичной сортировки остается, т.к. на входе массивы извне, обычно сортированные, но не всегда.

Посмотрел табличку 20104939 ShakerSort затестил, быстро сортирует сортированное, но если несортированое попадет то O(n^2), т.е. вся экономия времени съедена.

Думаю в случаях подобных моему надо просто проверять перед сортировкой
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
bool is_sort(std::string *a, size_t size) {
	if (size <= 1) return true;
	for (size_t i = 1; i < size; i++) {
		if (a[i - 1] > a[i]) {
			return false;
		}
	}
	return true;
}


В худшем случае проверка занимает 10% от времени сортировки, т.е. даже если 1 массив из 10 окажется сортированный, то проверка уже окупилась.
В среднем 5% на несортированных, тоже не большая потеря если сортированных нет.
...
Рейтинг: 0 / 0
27.01.2017, 16:55
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393430
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,
если покажешь количество основных операций как здесь 20111337 (сравнения, перестановки) то будет хотя бы понятно какие есть проблемы у метода
...
Рейтинг: 0 / 0
27.01.2017, 19:19
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393449
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Dima T,
если покажешь количество основных операций как здесь 20111337 (сравнения, перестановки) то будет хотя бы понятно какие есть проблемы у метода
Я время меряю std::sort() и своего цикла. На сортированном массиве.
...
Рейтинг: 0 / 0
27.01.2017, 20:20
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393498
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
ДмитрийИнтересно есть ли какие-то алгоритмы сортировки заточенные на почти отсортированные массивы?

В том случае, если число неотсортированных элементов значительно меньше размера исходного массива, то подойдет сортировка вставками. Попробуй её на своих данных, если у тебя будет время)
...
Рейтинг: 0 / 0
27.01.2017, 21:07
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393502
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
При этом в качестве структуры данных вероятно стоит организовать дерево, вставка будет за
...
Рейтинг: 0 / 0
27.01.2017, 21:09
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393551
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima TЯ время меряю std::sort() и своего цикла. На сортированном массиве.
этого мало, иногда сравнение дорого, иногда перемещение
...
Рейтинг: 0 / 0
27.01.2017, 22:15
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393587
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
bool is_sort(std::string *a, size_t size) {
	if (size <= 1) return true;
	for (size_t i = 1; i < size; i++) {
		if (a[i - 1] > a[i]) {
			return false;
		}
	}
	return true;
}


Может быть эта проверка... кхм... слишком пессимистична?
...
Рейтинг: 0 / 0
28.01.2017, 00:45
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393612
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
maytonMasterZiv, давай

Чего вам давать?
...
Рейтинг: 0 / 0
28.01.2017, 05:58
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393625
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Dima TЯ время меряю std::sort() и своего цикла. На сортированном массиве.
этого мало, иногда сравнение дорого, иногда перемещение
Согласен, надо поискать реализации QuickSort и счетчики туда вставить.
...
Рейтинг: 0 / 0
28.01.2017, 08:50
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393626
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonМожет быть эта проверка... кхм... слишком пессимистична?
Проверка корректна, постановка задачи слишком строгой оказалась.
Не учел что есть такая хрень как Unicode Collation Algorithm где 5 видов сравнения и все правильные.
Поэтому получив отсортированное извне, моя проверка считает его несортированным. Например сортировка от MSSQL не совпадает с сортировкой в ASCII
MSSQLASCIIa/ba+ba+ba-baaaa/ba-baaaabcabc
Думаю надо подход менять:
Первый проход запоминание элементов стоящих не на своих местах, при количестве >N считаем массив несортированным и сортируем алгоритмом со стабильной сложностью O(n log(n)) (std::sort() и т.п.).
При <N облегченная сортировка, например вставками, как Саша предлагает, можно свой велосипед поизобретать с использованием запомненного на первом проходе.

Тут надо с размером N определиться. Тупо в процентах не вариант, т.к. исходим из того что выбираем между алгоритмом стабильно дающим O(n log(n)) и нестабильным где от O(n) в случае сортированного до O(n 2 ) в случае обратноотсортированного.

С первым проходом тоже неясно как быть, например последовательность
Код: plaintext
1.
1,9,2,3,4,5,6,7,8


тут можно посчитать что 9 не на месте, а можно 2,3,4,5,6,7,8

Как вариант сразу начинать сортировать вставками и останавливаться при каком-то количестве перестановок и/или сравнений.

Немного конкретики: я этим в C# занимаюсь, в массиве ссылка на объект хранится, сравниваются строки до 100 символов, совпадение начал соседних строк до 30 символов частое явление. Думаю тут сравнение значительно тяжелее чем перестановка. Думаю можно перестановки не учитывать для упрощения.
...
Рейтинг: 0 / 0
28.01.2017, 09:00
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393670
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Тест на реальных данных со встроенным алгоритмом сортировки. Вставил счетчик в функцию сравнения.
Сортировал реальные, почти сортированные данные. Сортировка - вызовов при сортировке, Повтор - сортировка сортированного.
ЭлементовСортировкаПовтор812569456265526579885491862476695563590633866454630181456117681816065114757181573161943
Сравнений в 10-12 раз больше чем элементов. Если сортировать в обратную сторону до 15 раз доходит.
...
Рейтинг: 0 / 0
28.01.2017, 11:13
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393917
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
maytonMasterZiv, давай
Up. Есть новости?
...
Рейтинг: 0 / 0
29.01.2017, 00:43
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39393942
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Сортировка вставками почти отсортированного массива ускорила сортировку в 10 раз. Как и предполагалось.
Я туда двоичный поиск добавил для поиска места вставки. Без него особого ускорения не было.

Стоимость сравнения и перестановки в моем случае оказались примерно одинаковы, поэтому повесил все на общий счетчик и ограничил количество операций сортировки вставками 3-мя размерами массива, т.е. если не хватило 2N операций, то запуск стандартной сортировки. Цифра выбрана методом научного тыка :)

Итого: получилась сортировка сложностью от O(n) до O(n (log(n) + 3))

А ту задачу 20151862 (добавление в сортированный массив) вообще по другому решил, в один проход.
 
Исходники
Писал на C#, но если кому надо на С переписать не сложно
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
		// Сортировка почти отсортированного массива
		public static void SortOrdered<T>(this List<T> a) where T : IComparable<T> {
			if(a.Count <= 1) return;
			Int32 cnt = a.Count * 2; // Количество дополнительных операций, после которого считаем несортированным
			for(Int32 i = 1; i < a.Count; i++) {
				if(a[i-1].CompareTo(a[i]) > 0) { // a[i-1] > a[i], a[i] надо сдвинуть назад
					if(cnt < 0) { // несортированно
						a.Sort(); // полноценная сортировка
						return;
					}
					// Поиск места вставки
					T x = a[i];
					Int32 r = 0, l = i - 1; 
					while (r < l) {
						cnt--;
						Int32 c = (r + l) / 2;
						Int32 cmp = x.CompareTo(a[c]);
						if(cmp <= 0) { // x <= a[c]
							l = c;
							if (cmp == 0) break;
						} else { // x > a[c]
							r = c + 1;
						}
					}
					// Сдвиг влево [l,i-1]
					cnt -= i - l;
					for(Int32 j = i; j > l; j--) {
						a[j] = a[j-1];
					}
					a[l] = x;
				}
			}
		}

		//Объединение сортированных массивов
		public static List<T> ClueOrdered<T>(List<T> a1, List<T> a2) where T : IComparable<T> {
			Int32 cnt1 = a1.Count, cnt2 = a2.Count, i1 = 0, i2 = 0;
			var ret = new List<T>(cnt1 + cnt2);
			while(i2 < cnt2 || i1 < cnt1) {
				if(i2 == cnt2 || (i1 < cnt1 && a1[i1].CompareTo(a2[i2]) < 0)) {
					ret.Add(a1[i1]);
					i1++;
				} else if(i2 < cnt2) {
					ret.Add(a2[i2]);
					i2++;
				}
			}
			return ret;
		}

...
Рейтинг: 0 / 0
29.01.2017, 09:08
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39394112
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, для "почти сортированного" хорошо подходит merge-sort. В первую фазу
мы детектируем границы суб-последовательностей а во вторую - действуем
согласно каноническому слиянию.

Но возможно для тебя "почти отсортированный" определяется как-то иначе... и
возможно стоит уточнить или даже привести пример генератора почти-* последовательностей.
...
Рейтинг: 0 / 0
29.01.2017, 18:13
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39394126
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНо возможно для тебя "почти отсортированный" определяется как-то иначе... и
возможно стоит уточнить или даже привести пример генератора почти-* последовательностей.
Вот писал 20156048 , почти сортированный, это сортированный с другим пониманием юникода. Как-то поднимал топик про эти грабли .
Т.е. из-за этих нюансов строка немного не на своем месте оказывается. Так-то пофиг, но есть второй вариант - вообще не сортированный, его надо сортировать.

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

Началось все с того что у меня разбор XML в 200 Мб занимает 3.5 сек вместе с записью обратно на диск, а промежуточная сортировка сожрала 5+ сек., я ее запараллелил, но все равно она тормозит. Сейчас 0.5 сек.
...
Рейтинг: 0 / 0
29.01.2017, 18:31
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39394233
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, про Unicode я не очень понял. Мне кажется это - должно конфигурироваться извне
или подключаться как плагин к сортировке. Ну... я-бы забил болт и сортировал байты.

Далее. По поводу последовательности

Код: plaintext
1.
1,9,2,3,4,5,6,7,8



Я-бы выделил в ней две под-последовательности
Код: plaintext
1.
[1,9] , [2,3,4,5,6,7,8]



Они - монотонные. Неубывающие. И хорошо проходят через merge-sort.

В противоположность. Если на вход пойдет белый шум длиной N элементов - то нужно эвристически
принять решение о его НЕПРИГОДНОСТИ к частичным методам даже если случайно
в нем будут меньше чем N подпоследовательностей. Ну в общем надо исходить из
какой-то разумной пропорции.
...
Рейтинг: 0 / 0
29.01.2017, 21:57
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39394386
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonDima T, про Unicode я не очень понял. Мне кажется это - должно конфигурироваться извне
или подключаться как плагин к сортировке. Ну... я-бы забил болт и сортировал байты.
Данные из разных источников, разным софтом генерятся. Например тот софт сортирует {aaa, a-b, abc} а мой считает что "a-b" < "aaa", т.е. должно быть так {a-b, aaa, abc}.
В C# вообще отличились с дефолтной сортировкой, например это отсортировано по их мнению {ИГРА, Й ОГА, ИРА}.

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

Но иногда данные приходят вообще не сортированные и тут возникла проблема как отличить первое от второго, т.к. в первом случае для сортировки надо сдвинуть 5-10 элементов на 1-10 позиций, во втором - полноценная сортировка. Всегда делать полноценную сортировку оказалось медленно. Отсюда вопрос и родился. Сортировка вставками очень даже к месту пришлась для первого случая.
...
Рейтинг: 0 / 0
30.01.2017, 09:52
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39394390
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А ну ОК.

Вообще я смотрю тема сортировок не на шутку возбудила сообщество. Думаю поднять тяпничный
топик на тему merge. И, помнится Илья хвастался дескыть есть у него в тайные рукописи... чего-то
там дженерик и на сях.

У меня тоже есть мысли по поводу внешних сортировок.
...
Рейтинг: 0 / 0
30.01.2017, 10:00
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39394712
д0kХ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
д0kХ
Гость
Dima TmaytonНо возможно для тебя "почти отсортированный" определяется как-то иначе... и
возможно стоит уточнить или даже привести пример генератора почти-* последовательностей.
Вот писал 20156048 , почти сортированный, это сортированный с другим пониманием юникода. Как-то поднимал топик про эти грабли .
Т.е. из-за этих нюансов строка немного не на своем месте оказывается. Так-то пофиг, но есть второй вариант - вообще не сортированный, его надо сортировать.

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

Началось все с того что у меня разбор XML в 200 Мб занимает 3.5 сек вместе с записью обратно на диск, а промежуточная сортировка сожрала 5+ сек., я ее запараллелил, но все равно она тормозит. Сейчас 0.5 сек.

Сочуствую , но сортировки в разных кодировках везде аццкий треш.
Особенно когда кодировка в БД одна , а на клиентах другие и разные
обязательно где то вылаят какие то бока.

Я каждый раз когда сталкиваюсь всегда вспоминаю и перечитаваю http://utf8everywhere.org/
...
Рейтинг: 0 / 0
30.01.2017, 14:48
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39394772
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
maytonА ну ОК.

Вообще я смотрю тема сортировок не на шутку возбудила сообщество. Думаю поднять тяпничный
топик на тему merge. И, помнится Илья хвастался дескыть есть у него в тайные рукописи... чего-то
там дженерик и на сях.

У меня тоже есть мысли по поводу внешних сортировок.
Это естественно, мы так привыкли пользоваться библами, которые в реализации довольно сложны, что многие и не могут адекватную сортировку написать. Вот затыки на казалось бы вполне понятных местах и вызывают желание разобраться.
...
Рейтинг: 0 / 0
30.01.2017, 15:23
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395008
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
А я подумал что ты не будешь пробовать inserting sort. Дмитрий, а почему на C#, тут какое-то преимущество для данного конкретного случая? По коду вроде бы не очевидно.


maytonDima T, для "почти сортированного" хорошо подходит merge-sort. В первую фазу
мы детектируем границы суб-последовательностей а во вторую - действуем
согласно каноническому слиянию.

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

Честно говоря я не очень понимаю, каковы все-таки преимущества merge sort в данном случае. Insertion sort выглядит прозрачным и логичным решением. А в качестве метрики неупорядоченности массива можно использовать, например, количество элементов местоположение которых нужно изменить для того, чтобы массив стал упорядоченным. Где-то об этом читал, но уже не помню где
...
Рейтинг: 0 / 0
30.01.2017, 20:48
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395010
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryА я подумал что ты не будешь пробовать inserting sort. Дмитрий, а почему на C#, тут какое-то преимущество для данного конкретного случая? По коду вроде бы не очевидно.
Задача у меня реальная, написана на C#, поэтому C#. Переписать на С/С++ не сложно.
Я тоже не думал что буду пробовать :) читал вскользь вики - не понял, но ты упомянул, я перечитал - понял что это то что надо.
...
Рейтинг: 0 / 0
30.01.2017, 21:08
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395011
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryЧестно говоря я не очень понимаю, каковы все-таки преимущества merge sort в данном случае. Insertion sort выглядит прозрачным и логичным решением. А в качестве метрики неупорядоченности массива можно использовать, например, количество элементов местоположение которых нужно изменить для того, чтобы массив стал упорядоченным. Где-то об этом читал, но уже не помню где
Сложность O(n) - O(n log(n)) против O(n) - O(n 2 ) вот и вся разница.
...
Рейтинг: 0 / 0
30.01.2017, 21:13
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395182
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

довольно примечательная сортировка J-сортировка
её можно ещё немного оптимизировать
...
Рейтинг: 0 / 0
31.01.2017, 10:15
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395822
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Dima T,

довольно примечательная сортировка J-сортировка
её можно ещё немного оптимизировать
Сомневаюсь что на больших массивах будет работать. Автор честно сознался
авторЧем длиннее массив, тем чаще такие вырожденные узлы будет возникать. А значит, в средней полосе длинных массивов сортировке вставками придётся изрядно потрудиться.
...
Рейтинг: 0 / 0
31.01.2017, 19:12
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395845
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
 
Запилил тест
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
#include <windows.h>
#include <stdio.h>

#include <string>
#include <vector>
#include <algorithm>
#include <time.h>

// -------------------------------------------------------
#ifdef _DEBUG
#define TEST_SIZE 20
#else
#define TEST_SIZE 10000000
#endif
// -------------------------------------------------------
int32_t compare_cnt; // Счетчик сравнений
int32_t copy_cnt; // Счетчик копирований
clock_t start;

class item_t {
public:
	char data[10];

	item_t() {}

	item_t(const item_t& b) { *this = b; }

	static int compare(item_t const &a, item_t const &b) {
		compare_cnt++;
		return memcmp(a.data, b.data, sizeof(item_t));
	}

	int compare(item_t const &b) {
		compare_cnt++;
		return memcmp(data, b.data, sizeof(item_t));
	}

	bool operator > (item_t const &b) { return compare(b) > 0; }
	bool operator >= (item_t const &b) { return compare(b) >= 0; }
	bool operator < (item_t const &b) { return compare(b) < 0; }
	bool operator <= (item_t const &b) { return compare(b) <= 0; }
	bool operator == (item_t const &b) { return compare(b) == 0; }
	item_t& operator = (item_t const &b) {
		copy_cnt++;
		memcpy(data, b.data, sizeof(item_t));
		return *this;
	}

	item_t& operator = (int x) {
		_itoa(x, data, 10);
		return *this;
	}

	void swap(item_t &b) {
		item_t t = *this;
		*this = b;
		b = t;
	}

	static void swap(item_t &a, item_t &b) {
		item_t t = a;
		a = b;
		b = t;
	}
};

// -------------------------------------------------------
std::vector<item_t> a(TEST_SIZE); // Тестовый массив

// старт замера
void reset() {
	compare_cnt = 0;
	copy_cnt = 0;
	start = clock();
}

// Вывод текущего состояния
void print() {
	size_t max = a.size() < 20 ? a.size() : 20;
	for (size_t i = 0; i < max; i++) {
		printf("'%s',", a[i].data);
	}
	if (max < a.size()) printf("...");
	printf("\n");
}

// вывод результата
void result(const char* title, std::vector<item_t>* res = NULL) {
	clock_t t = clock() - start;
	printf("%s %d ms %d copies %d compares\n", title, t, copy_cnt, compare_cnt);
	if(res == NULL) {
		if(!std::is_sorted(a.begin(), a.end())) printf("!!! Not sorted\n");
	} else {
		if (!std::is_sorted(res->begin(), res->end())) printf("!!! Not sorted\n");
	}
	static FILE* f = NULL;
	if (f == NULL) {
		f = fopen("result.txt", "w");
	}
	if (f != NULL) {
		fprintf(f, "%s,%d,%d,%d\n", title, t, copy_cnt, compare_cnt);
		fflush(f);
	}
}

// Заполнение тестового массива
void fill() {
	uint32_t k = 1234567;
	for (size_t i = 0; i < a.size(); i++) {
		_itoa(k % (TEST_SIZE * 2), a[i].data, 10);
		k = (k * 65537 + 2017);
	}
	printf("Fill %d OK\n", a.size());
}

// -------------------------------------------------------
// тест qsort()
int compare(const void * a, const void * b) {
	return item_t::compare(*(item_t*)a, *(item_t*)b);
}

__declspec(noinline) void test1() {
	reset();
	qsort(&a[0], a.size(), sizeof(item_t), compare);
	result("qsort()");
}

// -------------------------------------------------------
// тест std::sort()
__declspec(noinline) void test2() {
	reset();
	std::sort(a.begin(), a.end());
	result("std::sort()");
}

// -------------------------------------------------------
// тест quick sort https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F
void quick_sort(item_t* s_arr, int first, int last)
{
	int i = first, j = last;
	item_t x = s_arr[(first + last) / 2];

	do {
		while (s_arr[i] < x) i++;
		while (s_arr[j] > x) j--;

		if (i <= j) {
			if (s_arr[i] > s_arr[j]) item_t::swap(s_arr[i], s_arr[j]);
			i++;
			j--;
		}
	} while (i <= j);

	if (i < last)
		quick_sort(s_arr, i, last);
	if (first < j)
		quick_sort(s_arr, first, j);
}

__declspec(noinline) void test3() {
	reset();
	quick_sort(&a[0], 0, a.size() - 1);
	result("quick_sort()");
}

// -------------------------------------------------------
// тест merge sort https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC

/**
* Сортирует массив, используя рекурсивную сортировку слиянием
* up - указатель на массив, который нужно сортировать
* down - указатель на массив с, как минимум, таким же размером как у 'up', используется как буфер
* left - левая граница массива, передайте 0, чтобы сортировать массив с начала
* right - правая граница массива, передайте длину массива - 1, чтобы сортировать массив до последнего элемента
* возвращает: указатель на отсортированный массив. Из-за особенностей работы данной реализации
* отсортированная версия массива может оказаться либо в 'up', либо в 'down'
**/
item_t* merge_sort(item_t* up, item_t* down, unsigned int left, unsigned int right)
{
	if (left == right)
	{
		down[left] = up[left];
		return down;
	}

	unsigned int middle = (unsigned int)((left + right) * 0.5);

	// разделяй и сортируй
	item_t *l_buff = merge_sort(up, down, left, middle);
	item_t *r_buff = merge_sort(up, down, middle + 1, right);

	// слияние двух отсортированных половин
	item_t *target = l_buff == up ? down : up;

	unsigned int width = right - left, l_cur = left, r_cur = middle + 1;
	for (unsigned int i = left; i <= right; i++)
	{
		if (l_cur <= middle && r_cur <= right)
		{
			if (l_buff[l_cur] < r_buff[r_cur])
			{
				target[i] = l_buff[l_cur];
				l_cur++;
			}
			else
			{
				target[i] = r_buff[r_cur];
				r_cur++;
			}
		}
		else if (l_cur <= middle)
		{
			target[i] = l_buff[l_cur];
			l_cur++;
		}
		else
		{
			target[i] = r_buff[r_cur];
			r_cur++;
		}
	}
	return target;
}

__declspec(noinline) void test4() {
	reset();
	std::vector<item_t> b(TEST_SIZE);
	item_t* r = merge_sort(&a[0], &b[0], 0, a.size() - 1);
	if(r == &a[0]) {
		result("merge_sort()");
	} else {
		result("merge_sort()", &b);
	}
}

//----------------------------------------------------------------------------------
// Моя самодельная Insert sort+

void insert_sort(std::vector<item_t>& a) {
	// Сортировка почти отсортированного массива
	int size = a.size();
	if (size <= 1) return;
	int cnt = size * 2; // Количество дополнительных операций, после которого считаем несортированным
	for (int i = 1; i < size; i++) {
		if (a[i - 1] > a[i]) { // a[i] надо сдвинуть назад
			if (cnt < 0) { // несортированно
				std::sort(a.begin(), a.end()); // полноценная сортировка
				return;
			}
			// Поиск места вставки
			item_t x = a[i];
			int r = 0, l = i - 1;
			while (r < l) {
				cnt--;
				int c = (r + l) / 2;
				int cmp = item_t::compare(x, a[c]);
				if (cmp <= 0) { // x <= a[c]
					l = c;
					if (cmp == 0) break;
				}
				else { // x > a[c]
					r = c + 1;
				}
			}
			// Сдвиг влево [l,i-1]
			cnt -= i - l;
			for (int j = i; j > l; j--) {
				a[j] = a[j - 1];
			}
			a[l] = x;
		}
	}
}

__declspec(noinline) void test5() {
	reset();
	insert_sort(a);
	result("insert_sort()");
}


int main()
{
	printf("Test unordered\n");
	fill();
	print();
	test1();
	fill();
	test2();
	fill();
	test3();
	fill();
	test4();
	fill();
	test5();
	printf("\nTest ordered\n");
	test1();
	test2();
	test3();
	test4();
	test5();

	return 0;
}


Результат 5-ти видов сортировки на массиве в 10 млн. элементов. Места ставил по времени.
Несортированный
АлгоритмВремя мсКопированийСравненийПримечаниеmerge_sort()1 990243 222 784230 068 109из инетаstd::sort()2 035338 720 497375 556 538MSVC2015insert_sort()2 049363 169 751376 875 415моя поделкаquick_sort()2 510168 421 944389 659 279из инетаqsort()3 045н/д277 090 450MSVC2015
Сортированный
АлгоритмВремя мсКопированийСравненийinsert_sort()520 19 999 998std::sort()48017 415 788220 483 043quick_sort()5526 465 373243 606 228merge_sort()827243 222 784129 428 083qsort()1 054н/д237 187 025
Выводы:
1. qsort() тормозит из-за того что функция сравнения не инлайнится, в остальном относительно неплохо. Количество копирований неизвестно, т.к. замерить можно только вызовы сравнений.
2. merge_sort() (скопипащено из вики ) показала неплохой результат на несортированном массиве, но заявленные O(n) на сортированном не айс, копирует много и рекурсия. Может реализация не лучшая, но пробовал несколько, остальные еще тормознее.
3. insert_sort() моя поделка комбинация сортировки вставками и std::sort()

ИМХО надо merge_sort() скрещивать с сортировкой вставками, как mayton предложил 20159478 . Должно взлететь. Есть мысли в этом направлении.

PS Не довелось тему сортировок изучить, образование не программистское, в фокспро все на таблицах, т.е. SQL, т.е. order by и готово. "Удивило" что log 2 (15000) = 14, просто никогда не задумывался об этом, поэтому интересно побыть студентом :)
...
Рейтинг: 0 / 0
31.01.2017, 19:48
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395887
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima TСомневаюсь что на больших массивах будет работать. Автор честно сознался
авторЧем длиннее массив, тем чаще такие вырожденные узлы будет возникать. А значит, в средней полосе длинных массивов сортировке вставками придётся изрядно потрудиться.
ага, фигня получилась:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
JSort с небольшой оптимизацией 
  inverse array: time=2250  CompareCount=272457260  ChangeCount=272590534
  sorted  array: time=0  CompareCount=0  ChangeCount=0
  randomic array: time=1031  CompareCount=127509157  ChangeCount=126205133
HeapSort
  inverse array: time=16  CompareCount=2928116  ChangeCount=1497536
  sorted  array: time=31  CompareCount=4256886  ChangeCount=2937924
  randomic array: time=32  CompareCount=3059438  ChangeCount=1628454

но где проблемы с HeapSort он правильно подметил
...
Рейтинг: 0 / 0
31.01.2017, 22:22
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395914
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kealon(Ruslan)Dima T,

довольно примечательная сортировка J-сортировка
её можно ещё немного оптимизировать
Спасибо. Интересная статья. Жаль что автор не расчитал среднюю оценку O(n).
...
Рейтинг: 0 / 0
31.01.2017, 23:51
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395917
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TРезультат 5-ти видов сортировки на массиве в 10 млн. элементов. Места ставил по времени.
Несортированный
АлгоритмВремя мсКопированийСравненийПримечаниеmerge_sort()1 990243 222 784230 068 109из инетаstd::sort()2 035338 720 497375 556 538MSVC2015insert_sort()2 049363 169 751376 875 415моя поделкаquick_sort()2 510168 421 944389 659 279из инетаqsort()3 045н/д277 090 450MSVC2015
Сортированный
АлгоритмВремя мсКопированийСравненийinsert_sort()520 19 999 998std::sort()48017 415 788220 483 043quick_sort()5526 465 373243 606 228merge_sort()827243 222 784129 428 083qsort()1 054н/д237 187 025
Респект за проделанную работу. Я-бы еще предложил-бы дать на вход варианты данных (N штук):
1) Белый шум из N элементов.
2) Белый шум с низкой кардинальностью (всего 3-10 уникальных элементов из N)
3) Серии монотонных под-последовательностей 3-5 штук из N. Монотонные возрастающие-убывающие ("пила", синусоида).
4) Прочие краевые случаи. Например - неблагоприятные наборы на которых q-sort
"переключается" в обычный алгоритм или валится со stackoverflow (depends on implementation)
...
Рейтинг: 0 / 0
01.02.2017, 00:02
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39395967
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonРеспект за проделанную работу. Я-бы еще предложил-бы дать на вход варианты данных (N штук):
1) Белый шум из N элементов.
2) Белый шум с низкой кардинальностью (всего 3-10 уникальных элементов из N)
3) Серии монотонных под-последовательностей 3-5 штук из N. Монотонные возрастающие-убывающие ("пила", синусоида).
4) Прочие краевые случаи. Например - неблагоприятные наборы на которых q-sort
"переключается" в обычный алгоритм или валится со stackoverflow (depends on implementation)
У меня 1й вариант реализован. Надо функцию fill() допилить: на вход параметр давать какого типа последовательность нужна.
По п.4 не знаю как сгенерить, предлагай алгоритм.
...
Рейтинг: 0 / 0
01.02.2017, 07:08
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396052
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Друзья. Как вы заметили в последнее время я редко пишу посты. Чортова
работа + курсы придавили меня к земле и не дают продохнуть. :)

Но я читаю все посты где я участник так что - мысленно с вами :)
...
Рейтинг: 0 / 0
01.02.2017, 10:03
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396356
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton4) Прочие краевые случаи. Например - неблагоприятные наборы на которых q-sort
"переключается" в обычный алгоритм или валится со stackoverflow (depends on implementation)
при правильной реализации QSort stackoverflow невозможен
...
Рейтинг: 0 / 0
01.02.2017, 14:17
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396559
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Добавил разные исходные заполнения
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
#define FILL_ORDERED		2 // Отсортированный
#define FILL_RANDOM		3 // Случайные (диапазон 0...TEST_SIZE*2)
#define FILL_RANDOM_DOUBLES	4 // Случайные с повторами (диапазон 0...100)
#define FILL_STAIRS		5 // Лесенка по 10 (1,2,3,...8,9,1,2,3...)
#define FILL_SINUS		6 // "Синусоида" по 10 (1,2,3,...8,9,8,7,6...)
#define FILL_NEARLY		7 // Почти сортированный (20 значений смещено на 20 позиций)
#define FILL_REVERSE		8 // Обратно сортированный

 
Исходник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
// Заполнение тестового массива
void fill(int type) {
	uint32_t k = 1234567;
	bool up = true;
	switch(type) {
	case FILL_NONE:
		break;

	case FILL_ORDERED:
		k = 0;
		for (auto it = a.begin(); it != a.end(); it++, k++) {
			*it = k;
		}
		printf("ordered  ");
		break;

	case FILL_RANDOM:
		for (auto it = a.begin(); it != a.end(); it++) {
			*it = k % (TEST_SIZE * 2);
			k = (k * 65537 + 2017);
		}
		printf("random  ");
		break;

	case FILL_RANDOM_DOUBLES:
		for(auto it = a.begin(); it != a.end(); it++) {
			*it = k % 100;
			k = (k * 65537 + 2017);
		}
		printf("random (max 100)  ");
		break;

	case FILL_STAIRS:
		k = 0;
		for (auto it = a.begin(); it != a.end(); it++) {
			k++;
			if (k == 10) k = 0;
			*it = k;
		}
		printf("stairs  ");
		break;

	case FILL_SINUS:
		k = 0;
		for (auto it = a.begin(); it != a.end(); it++) {
			if(up) {
				k++;
				if (k == 10) up = false;
			} else {
				k--;
				if (k == 0) up = true;
			}
			*it = k;
		}
		printf("sinus  ");
		break;

	case FILL_NEARLY:
		k = 0;
		for (auto it = a.begin(); it != a.end(); it++, k++) {
			*it = k;
			if (k % (TEST_SIZE / 20) == 0) {
				if(up) {
					*it = k + 20;
				} else {
					*it = k - 20;
				}
				up = !up;
			}
		}
		printf("nearly ordered  ");
		break;

	case FILL_REVERSE:
		k = TEST_SIZE;
		for (auto it = a.begin(); it != a.end(); it++, k--) {
			*it = k;
		}
		printf("reverse  ");
		break;

	default:
		printf("!!! Unknown fill type %d  ", type);
	}
	if(a.size() != TEST_SIZE) printf("!!! Wrong size  ");
}


Убрал qsort() добавил std::stable_sort()

Время мс
АлгоритмNEARLYORDEREDRANDOMRANDOM_DOUBLESREVERSESINUSSTAIRSinsert_sort()13131311369319128138merge_sort()64363817711164652835836quick_sort()1631621119579176415418std::sort()2712681255344305115127std::stable_sort()4254301238818502601608

Операций (копирований + сравнений)
АлгоритмNEARLYORDEREDRANDOMRANDOM_DOUBLESREVERSESINUSSTAIRSinsert_sort()10 004 6959 999 999738 371 870199 030 889302 776 605131 526 867142 030 677merge_sort()362 011 134362 010 944463 267 963462 644 325357 657 408453 386 928453 368 256quick_sort()236 447 825236 445 593541 750 828403 557 861256 445 617387 576 172382 637 354std::sort()228 952 229228 951 438737 463 387186 343 940282 625 386111 500 018122 000 152std::stable_sort()325 963 938325 963 568565 121 728563 475 795468 497 124547 301 462542 329 730
 
Подробнее
Копирования
АлгоритмNEARLYORDEREDRANDOMRANDOM_DOUBLESREVERSESINUSSTAIRSinsert_sort()7900369 072 660102 318 66272 827 95476 243 23879 998 904merge_sort()243 222 784243 222 784243 222 784243 222 784243 222 784243 222 784243 222 784quick_sort()5 807 0165 805 696169 379 23263 116 09720 805 69737 944 05239 390 073std::sort()17 903 42017 902 850363 987 48889 248 99552 799 54856 249 95860 000 051std::stable_sort()209 375 190209 375 000291 879 725291 127 627369 375 000286 375 000280 500 000


Сравнения
АлгоритмNEARLYORDEREDRANDOMRANDOM_DOUBLESREVERSESINUSSTAIRSinsert_sort()10 003 9059 999 999369 299 21096 712 227229 948 65155 283 62962 031 773merge_sort()118 788 350118 788 160220 045 179219 421 541114 434 624210 164 144210 145 472quick_sort()230 640 809230 639 897372 371 596340 441 764235 639 920349 632 120343 247 281std::sort()211 048 809211 048 588373 475 89997 094 945229 825 83855 250 06062 000 101std::stable_sort()116 588 748116 588 568273 242 003272 348 16899 122 124260 926 462261 829 730

В предыдущий замер сравнения неккоректно считались, т.к. перед записью был std::is_sorted(), который тоже счетчик менял.


PS C предыдущими замерами не сравнивать, т.к. элемент массива с char[10] поменял на int64_t, чтобы порядок удобнее было задавать.
...
Рейтинг: 0 / 0
01.02.2017, 17:08
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396733
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДалее. По поводу последовательности

Код: plaintext
1.
1,9,2,3,4,5,6,7,8



Я-бы выделил в ней две под-последовательности
Код: plaintext
1.
[1,9] , [2,3,4,5,6,7,8]



Они - монотонные. Неубывающие. И хорошо проходят через merge-sort.

В противоположность. Если на вход пойдет белый шум длиной N элементов - то нужно эвристически
принять решение о его НЕПРИГОДНОСТИ к частичным методам даже если случайно
в нем будут меньше чем N подпоследовательностей. Ну в общем надо исходить из
какой-то разумной пропорции.
Зацепил ты меня этим постом, писать некогда, пока просто размышляю.

Про белый шум не согласен, см. тест выше - отлично сортируется, т.е. можно сортировать что угодно.

Идея как эффективно смержить две соседних возрастающих последовательности уже есть. Непонятки дальше.

Последовательностей может быть много, очень много. Размеры у них разные. Тупо мержить в цикле первую с последующими не эффективно. Надо какой-то алгоритм какие мержить в каком порядке. Как интуитивно подозреваю: эффективнее всего мержить последовательности примерно равного размера.

Например есть последовательности [4][2][55][48][2][12] число в скобках это количество элементов в каждой последовательности. В каком порядке их мержить?

Может ты что предложишь? У меня мысли есть по этому поводу, но не нравятся они мне.
...
Рейтинг: 0 / 0
01.02.2017, 20:08
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396748
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, вопрос интересный. Приду домой - по думаю. Но сразу скажу что я не такой уж теоретик и знания у меня
Весьма осколочные. Но гонять бенчмаркинг на разных данных - очень важно.
...
Рейтинг: 0 / 0
01.02.2017, 20:43
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396789
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
[quot Dima T]maytonДалее. По поводу последовательности



Например есть последовательности [4][2][55][48][2][12] число в скобках это количество элементов в каждой последовательности. В каком порядке их мержить?

Может ты что предложишь? У меня мысли есть по этому поводу, но не нравятся они мне.

Судя по всему, асимптотика merge двух массивов составляет . В твоем случае, такой порядок будет оптимальным: 2 merge 2, 4 merge 4,8 merge 12, 20 merge 48, 55 merge 68. Итого 2+4+12+48+68 операций. Возможно лучшим алгоритмом будет выбор двух минимальных по размеру массивов перед каждым merge(в этом я до конца не уверен). Но перед последней итерацией, идеальным будет merge двух равных по размеру массивов
...
Рейтинг: 0 / 0
01.02.2017, 22:04
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396794
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
А, да это же задача о рюкзаке с определенными ограничениями)) Не зря я сомневался в выборе двух минимальных на каждой итерации
...
Рейтинг: 0 / 0
01.02.2017, 22:07
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396800
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
ДмитрийМожет ты что предложишь? У меня мысли есть по этому поводу, но не нравятся они мне.

Потому не зря они тебе не нравились))
...
Рейтинг: 0 / 0
01.02.2017, 22:17
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396857
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если каналов доступа к памяти два. И "удачно лягут карты" - то можно попробовать в 2 потока запустить merge sort.

+Если мы храним min/max для каждой серии то возможно стоит изучить вариант просто тривиальной конкатенации
серий (опять-же если мы имеем дело с неким синтетическим источником данных).
...
Рейтинг: 0 / 0
02.02.2017, 01:12
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396868
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Dima T...
Например есть последовательности [4][2][55][48][2][12] число в скобках это количество элементов в каждой последовательности. В каком порядке их мержить?
...

Есть такой алгоритм - "естественная двусторонняя сортировка слиянием" (nature merge sort
или nature 2-way merge sort)
(у которой есть "неестественные" вариации - вроде двоичной двусторонней бла-бла-бла, и далее - многоветочные истории, которые, правда, вроде как скисают на большом числе веток и больших сортируемых объемах - я в них не разбирался детально.)
не поленись, погугли.

Идею алгоритма приписывают Кнуту.
Смысл в том, чтобы сливать с двух краев в середину (свеча слияния горит с двух концов).
То есть на первом шаге алгоритма слияние идет в таком порядке:

[4][2][55][48][2][12] || x||x xx||xx
при этом на фазе самого слияния используют двоичный поиск.

То есть
Сортированный_результат = ГоримСДвухСторон(Разбиение_на_Сортированные_диапазоны(Сортируемый_Список))

В принципе, алгоритму не требует наличия сколь-нибудь протяженных предварительно сортированных поддиапазонов.
Но, если сортируемый список представляет чистый белый шум,
то у некоторых имплементаторов есть мнение, что разумно натравить на БелыйШум
сортировку вставкой, с размером итоговых сортированных поддиапазонов на 8 - 16 элементов, что и создаст стартовую точку для горения с двух сторон.

Еще есть изобретения in-place слияния.
имхо, годное к разглядыванию обсуждение:
http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm
...
Рейтинг: 0 / 0
02.02.2017, 02:16
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39396873
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
booby,

существенная деталь - в свечном производстве
с головы ищут неубывающую подпоследовательность, а с хвоста - невозрастающую.
т.е. в исходной идее, в голове - [4][2][55] - это возрастающие поддиапазоны (asc),
а [48][2][12] - убывающие (desc) поддиапазоны
...
Рейтинг: 0 / 0
02.02.2017, 02:29
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397027
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
booby,

очень заманчиво выглядит по сравнению с наивной квадратичной реализацией,
...
Рейтинг: 0 / 0
02.02.2017, 10:37
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397064
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
У меня мысль минимизировать копирования, т.к. из-за них тормоза на почти сортированной последовательности.

Поэтому видится вариант работы внутри исходного массива. Т.е. ограничится только слиянием соседних подмассивов.
 
Слияние двух соседних сортированных подмассивов
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
// start1,start2 индекс начала каждого, end индекс начала следующего
void merge_near(std::vector<item_t>& a, size_t start1, size_t start2, size_t end) {
	// Поиск места вставки
	item_t x = a[start2];
	int r = start1, l = start2 - 1;
	while (r < l) {
		int c = (r + l) / 2;
		int cmp = item_t::compare(x, a[c]);
		if (cmp <= 0) { // x <= a[c]
			l = c;
			if (cmp == 0) break;
		}
		else { // x > a[c]
			r = c + 1;
		}
	}
	// Слияние начиная с a[l]
	size_t i1 = l, i2 = start2;
	std::queue<item_t> queue;
	for (size_t write = l; write < end; write++) {
		if(write == i1) { // место записи занято
			if(i1 < start2) {
				queue.push(a[i1]);
				i1++;
			}
		}
		if (queue.empty()) break;

		if(i2 == end || queue.front() < a[i2]) {
			a[write] = queue.front();
			queue.pop();
		} else {
			a[write] = a[i2];
			i2++;
		}
	}
}


Из-за очереди тормозит, надо ее на массив менять, но для замера количества операций сойдет

Затестил последовательное слияние, т.е. первый со вторым, результат с третьим и т.д.
Итого на 1000 элементах в 50 раз больше операций чем у std::sort() на обратносортированной, т.е. алгоритм выродился в сортировку вставками. На "белом шуме" больше "всего" в 14 раз.
booby, тоже самое будет со свечой, разве что вдвое быстрее, т.е. вместо O(n 2 ) получим O(n 2 /2).

Затестил вариант слияния попарно, т.е.
Код: plaintext
1.
2.
3.
результат1 = список1 + список2
результат2 = список3 + список4
итого = результат1 + результат2


тут результаты получше
Заполнениеstd::sort()merge_ordered()СоотношениеRANDOM737 463 387592 349 26880%RANDOM_DOUBLES186 343 940588 526 298316%ORDERED228 951 4389 999 9994%STAIRS122 000 152488 230 344400%SINUS111 500 018552 390 781495%NEARLY228 952 22910 001 4324%REVERSE282 625 386613 296 588217%Максимум737 463 387613 296 58883%
Цифры это всего операций (сравнений + копирований). Размер массива 10 млн.

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

Надо придумать алгоритм типа такого:
перебираем в цикле массив подмассивов. Каждый subarr[i] сравниваем с соседними subarr[i-1] и subarr[i+1], затем принимаем решение с каким из них смержить или оставить как есть на данном проходе. И так по кругу в цикле пока все не смержатся.

Осталось придумать как сравнивать подмассивы. По ним есть размер и минимальный/максимальный элемент.
 
Склеивание парами
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
void merge_ordered(std::vector<item_t>& a) {
	size_t min_size = 16; // минимальный размер интервала, ниже которого сразу объединять
	// начала монотонных подмассивов
	std::vector<size_t> idx; 
	idx.push_back(0);
	for (size_t i = 1; i != a.size(); i++) {
		if (a[i - 1] > a[i]) {
			if(idx.size() == 1 || i - idx[idx.size() - 2] > min_size) {
				idx.push_back(i);
			} else { // Интервал слишком мал, объединяем с предыдущим
				merge_near(a, idx[idx.size() - 2], idx[idx.size() - 1], i);
				idx[idx.size() - 1] = i;
			}
		}
	}
	idx.push_back(a.size());
	// объединение парами
	size_t end = idx.size() - 1;
	while(end > 1) {
		size_t i = 0, w = 0;
		for (; i < end; i += 2, w++) {
			if(i + 1 != end) { // не последний без пары
				merge_near(a, idx[i], idx[i+1], idx[i+2]);
			}
			idx[w] = idx[i];
		}
		idx[w] = idx[end];
		end = w;
	}
}

...
Рейтинг: 0 / 0
02.02.2017, 11:12
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397112
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Dima T,
код внимательно разглядывать не могу, но,
кажется, ты не обратил внимание на то, что свечка при слиянии подмассивов
заведомо рассчитывает на то, что имеет дело с уже отсортированными диапазонами.
Поэтому не боится использовать двоичный поиск на фазе слияния.

Пусть сливаются отрезки с длинами а)[4](левый) и б)[12] (правый)


/*текущая позиция в а */ и = старт_а
голова_цикла:
номер_позиции_а(и)_в_б = двоичным поиском ищем позицию(б)
от текущего начала не перелитой части б до найденной и вываливаем все б(ж) в область слияния
вываливаем в область слияния элементы а, пока они не больше а(и)
устанавливаемся в новую позицию и в а
Если диапазоны не кончились, то ГОУ ТУ голова_цикла

Тут надо обратить внимание на то, что, с одной стороны,
в принципе всегда хотелось бы иметь ведущий диапазон меньшего размера,
а тот, в котором будем искать двоичным поиском - большего.
Но, если их переставлять не глядя, то нарушится стабильность, присущая исходному merge sort.
Поэтому фига из трех пальцев - либо плюнуть на стабильность, либо плюнуть на разборки - кто из них длиннее,
либо озаботиться устабилизацией обмена диапазонов.
...
Рейтинг: 0 / 0
02.02.2017, 12:03
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397179
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
boobyDima T,
код внимательно разглядывать не могу, но,
кажется, ты не обратил внимание на то, что свечка при слиянии подмассивов
заведомо рассчитывает на то, что имеет дело с уже отсортированными диапазонами.
Поэтому не боится использовать двоичный поиск на фазе слияния.
Двочный поиск у меня есть. В merge_near() им ищется место откуда слияние начинать. Все подмассивы считаются сортированными.

Может я неправильно понял описание твоего алгоритма. Пишу как понял, например массив:
Код: plaintext
1.
[4][2][55][48][2][12]


где то что в [] это уже сортированные подмассивы, цифры - количество элементов
далее смерживаем
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
//Возрастающая половина
[4][2] => [6]
[6][55] => [61]
//Убывающая половина
[12][2] => [14]
[14][48] => [62]
// Итого
[61][62] => [123]



Если так то, я почти так и делал, только полсвечи, т.е.
Код: plaintext
1.
2.
3.
4.
5.
[4][2] => [6]
[6][55] => [61]
[61][48] => [109]
[109][2] => [111]
[111][12] => [123]


Такой подход тормозит на обратносортированном, твоя свеча тоже будет тормозить, т.к. добавление будет всегда по одному элементу в начало, т.е. сортировка вставками, а двоичный поиск только лишние тормоза даст, т.к. достаточно сравнения первого с первым элемента.
...
Рейтинг: 0 / 0
02.02.2017, 13:03
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397201
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

сортировка слияниями базируется на том что слияние двух сортированных массивов имеет сложность не больше O(a+b), где a и b размеры сливаемых массивов

собственно на каждом уровне итерации - k необходимо произвести 2^k слияний мощностью (N/2^k), в сумме для уровня <= O(N)
всего уровней log2(N) - общая сложность - O(N* Ln(N))

если процедура слияния не удовлетворяет крайней оценке O(a+b), то ни о каких O(N* Ln(N)) для сортировки речи идти не может

в сабже от booby предлагается сделать с внешним массивом, тогда можно добиться O(a+b), но в крайнем случае размер временного массива должен быть равен N

с другой стороны если использовать дополнительный массив, то тот же heapsort легко избавляется от своего главного недостатка - построение обратной кучи на первом этапе
...
Рейтинг: 0 / 0
02.02.2017, 13:35
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397253
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Dima T,

сортировка слияниями базируется на том что слияние двух сортированных массивов имеет сложность не больше O(a+b), где a и b размеры сливаемых массивов

собственно на каждом уровне итерации - k необходимо произвести 2^k слияний мощностью (N/2^k), в сумме для уровня <= O(N)
всего уровней log2(N) - общая сложность - O(N* Ln(N))
При слиянии парами у меня так и получилось, например
Код: plaintext
1.
[4][2][55][48][2][12] => [6][103][14] => [109][14] => [123]


Но это O(N* Ln(N)) на уровне слияний, но сами слияния тоже отличаются например [48][2][12] можно слить
Код: plaintext
1.
[48][2][12] => [50][12]

а можно
Код: plaintext
1.
[48][2][12] => [48][14]


ИМХО второй вариант предпочтительней, т.е. предпочтение надо как-то отдать слиянию меньших подмассивов.

Есть одна мысль, вечером потестю, выложу результаты.
...
Рейтинг: 0 / 0
02.02.2017, 14:15
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397470
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
 
Сделал склеивание только тех подмассивов, которые дадут итого меньше двух средних размеров
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
void merge_ordered(std::vector<item_t>& a) {
	size_t min_size = 16; // минимальный размер интервала, ниже которого сразу объединять
	// начала монотонных подмассивов
	std::vector<size_t> idx; 
	idx.push_back(0);
	for (size_t i = 1; i != a.size(); i++) {
		if (a[i - 1] > a[i]) {
			if(idx.size() == 1 || i - idx[idx.size() - 2] > min_size) {
				idx.push_back(i);
			} else { // Интервал слишком мал, объединяем с предыдущим
				merge_near(a, idx[idx.size() - 2], idx[idx.size() - 1], i);
				idx[idx.size() - 1] = i;
			}
		}
	}
	idx.push_back(a.size());
	// объединение парами
	size_t end = idx.size() - 1;
	while(end > 1) {
		size_t i = 0, w = 0;
		size_t avg = 2 * (idx[end] / (end - 1));

		for (; i < end; i++, w++) {
			if(i + 1 != end && (idx[i + 2] - idx[i]) <= avg) { // есть пара и результат будет размером менее 2х средних
				merge_near(a, idx[i], idx[i+1], idx[i+2]);
				idx[w] = idx[i];
				i++;
			} else {
				idx[w] = idx[i];
			}
		}
		if(w == end) { // Ничего не смержилось, защита от зацикливания
			printf("circle %d\n", w);
			merge_near(a, idx[w - 2], idx[w - 1], idx[w]);
			w--;
		}
		idx[w] = idx[end];
		end = w;
	}
}


Особых изменений нет, чуть-чуть получше местами. Думаю в разы этот алгоритм не улучшить.

std::sort()insert_sort()%merge_ordered()%Заполнение737 463 387738 371 870100%600 849 36181%Случайные (диапазон 0...TEST_SIZE*2)186 343 940199 030 889107%596 760 728320%Случайные с повторами (диапазон 0...100)228 951 4389 999 9994%9 999 9994%Отсортированный122 000 152142 030 677116%488 230 344400%Лесенка по 10 (1 2 3 ...8 9 0 1 ...)111 500 018131 526 867118%549 117 750492%Синусоида по 10 (1 2 3...8 9 8 7 ...)228 952 22910 004 6954%10 001 4324%Почти сортированный (20 значений смещено на 20 позиций)282 625 386302 776 605107%613 296 588217%Обратно сортированный730 224 311711 355 83597%80 000 07811%4 одинаковых подмассива
Посчитаны операции (сравнения + копирования) Проценты по отношению к std::sort()

ИМХО insert_sort() (сортировка вставками + двоичный поиск + std::sort()) в общем случае быстрее. Исключение последний тест, где массив это 4 сортированных подмассива. Но это редкий случай и его можно заменить на слияние во время объединения подмассивов. Еще Белый шум получше сортирует, но по времени в 7 раз медленнее, есть что оптимизировать (std::queue на массив заменить), но сомневаюсь что оптимизаторством такой разрыв времени можно компенсировать. Да и памяти дополнительной надо прилично.

 
insert_sort() победил
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
void insert_sort(std::vector<item_t>& a) {
	// Сортировка почти отсортированного массива
	int size = a.size();
	if (size <= 1) return;
	int cnt = size * 2; // Количество дополнительных операций, после которого считаем несортированным
	for (int i = 1; i < size; i++) {
		if (a[i - 1] > a[i]) { // a[i] надо сдвинуть назад
			if (cnt < 0) { // несортированно
				std::sort(a.begin(), a.end()); // полноценная сортировка
				return;
			}
			//assert(a[i].data != 30);
			// Поиск места вставки
			item_t x = a[i];
			int r = 0, l = i - 1;
			while (r < l) {
				cnt--;
				int c = (r + l) / 2;
				int cmp = item_t::compare(x, a[c]);
				if (cmp <= 0) { // x <= a[c]
					l = c;
					if (cmp == 0) break;
				}
				else { // x > a[c]
					r = c + 1;
				}
			}
			// Сдвиг влево [l,i-1]
			cnt -= i - l;
			for (int j = i; j > l; j--) {
				a[j] = a[j - 1];
			}
			a[l] = x;
		}
	}
}

...
Рейтинг: 0 / 0
02.02.2017, 17:29
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397691
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

"Поиск места вставки" можно чуток оптимизировать не сразу задавая int r = 0
а
расширять диапазон в нужную сторону от прошлого места вставки с помощью бинарного расширения в нужную сторону
и к этому диапазону потом применить бинарный поиск

худшую асимптотику поиска это не увеличит, а вот на частично-отсортированных массивах ускорит основательно
...
Рейтинг: 0 / 0
02.02.2017, 23:18
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397700
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
boobyDima T,
код внимательно разглядывать не могу, но,
кажется, ты не обратил внимание на то, что свечка при слиянии подмассивов
заведомо рассчитывает на то, что имеет дело с уже отсортированными диапазонами.
Поэтому не боится использовать двоичный поиск на фазе слияния.

Пусть сливаются отрезки с длинами а)[4](левый) и б)[12] (правый)


/*текущая позиция в а */ и = старт_а
голова_цикла:
номер_позиции_а(и)_в_б = двоичным поиском ищем позицию(б)
от текущего начала не перелитой части б до найденной и вываливаем все б(ж) в область слияния
вываливаем в область слияния элементы а, пока они не больше а(и)
устанавливаемся в новую позицию и в а
Если диапазоны не кончились, то ГОУ ТУ голова_цикла

Тут надо обратить внимание на то, что, с одной стороны,
в принципе всегда хотелось бы иметь ведущий диапазон меньшего размера,
а тот, в котором будем искать двоичным поиском - большего.
Но, если их переставлять не глядя, то нарушится стабильность, присущая исходному merge sort.
Поэтому фига из трех пальцев - либо плюнуть на стабильность, либо плюнуть на разборки - кто из них длиннее,
либо озаботиться устабилизацией обмена диапазонов.

А что будет с вашим алгоритмом, если массивы будут стыковаться как две расчески?

Асимптотика слияния О(max(a_s,b_s)), не понятно о чем дискуссия. Оптимальный способ порядка сливания множества массивов - NP полная задача. Свечка возможно даст хорошее решение, но не оптимальное. Да и то, судя по всему необходимо будет проводите действия по переупорядочиванию элементов свечи, что также накладно.
...
Рейтинг: 0 / 0
03.02.2017, 00:19
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397709
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
SashaMercuryА что будет с вашим алгоритмом, если массивы будут стыковаться как две расчески?


(Кнута это алгоритм, Дональда Эрвина,
который русский выучил только за то, что им разговаривал Андрей Петрович Ершов.
Чтобы книжки его читать в оригинале.
)

Вопрос правильный.
Остановится при перехлесте.
Так как слежение за перехлестом встроено в (реальный) алгоритм.

Без опасности перехлеста работает 2-way.
Который не смотрит на то, есть ли естественным образом сортированные куски, а вменяет сливаемым диапазонам быть сортированными путем слияния диапазонов, начиная 1.

А так как первые пять шагов слияния в 2way, стартующего с единичных крайних элементов занимаются слиянием слишком коротких массивов, сам Кнут настаивает - не надо так делать.
Надо натравить сортировку вставками для разбиения массива на сортированные диапазоны
размером в 16 в качестве первого шага, а потом можно включать 2way
...
Рейтинг: 0 / 0
03.02.2017, 01:40
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397725
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Dima TМожет я неправильно понял описание твоего алгоритм

Сейчас покопался еще раз в началах и концах.
Нашел следующее - в варианте, описанном у Кнута (5.2.4), действительно, слева ищутся
возрастающие, справа убывающие диапазоны.
При этом само слияние совмещено с просмотром.
Такая версия подачи затрудняет общее понимание идеи.

Стартуя с приведенной мной ссылки можно добраться до книжки "Элементарные алгоритмы",
в которой изложена упрощенная версия, не ждущая убывающего диапазона с правой стороны.

Имхо этот вариант проще для понимания и после него легче будет смотреть в книжку Кнута.

Пусть дан для сортировки массив
M[8, 12, 14 , 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6, 15, 7]

И известно, что элементов в нем 16

N=16;
merge_step = 0

0) Выделим память размером в полученный массив (N)
M[8, 12, 14 , 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6, 15, 7]
-- доп. память N=16
P[x, xx, xx , x, x, x, xx, x, x, x, x, xx, xx, xx, xx, x]

<<ДЕЛАЙ ВСЕГДА>>
ileft_start = 1; //начало левого диапазона
ileft_stop = 1; //конец левого диапазона
iright_start = N; // начало правого диапазона
iright_stop = N; // конец правого диапазона

merge_leftpos_start = 1; // позиция, начиная с которой будем дописывать в массив промежуточного результата
// мы считаем с 1, хоть форум и по C++

merge_rightpos_start = N; // 16 - позиция, в которую будем дописывать справа

//шаг слияния, первый рабочий шаг будет 1 (нечетный шаг)
(на нечетных шагах будем дописывать в левую часть выделенной памяти, на четной - в правую
)
merge_step = 1;
<<ЦИКЛ ПОКА ПРОБЕГА ПОКА НЕ ПРОСМОТРИМ M ЦЕЛИКОМ (ileft_stop < iright_start)>>

//ищем позицию в которой завершается первый неубывающий диапазон слева
ileft_stop = поиск_слева(ileft_start ); // здесь получим 3 на первом шаге для конкретного массива

ЕСЛИ ileft_stop >= N то алгоритм завершен, т.к. массив полностью сортирован.

// вот что мы нашли
M[ 8, 12, 14 | , 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6, 15, 7]
//
//ищем позицию упорядоченного убывающего диапазона справа
iright_start = поиск_справа(iright_stop)// получим 15 на первом просмотре

ЕСЛИ ileft_stop >=iright_start то случился перехлест, любим левый край: iright_start = ileft_stop + 1
//
//вот что мы нашли
M[ 8, 12, 14 |, 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6,| 15, 7 ]
// здесь мы уже знаем какой размер займет результат
// - 5 элементов = (ileft_stop - ileft_start +1) + (iright_stop - iright_start+1)
// но, т.к. у нас две позиции вставки - левая и правая, то пусть их формирует процедура
//слияния, которой мы будет рассказывать, в какую сторону - левую или правую ей надо доливать, а она нам за это вернет новую позицию после долива

Если Нечетно(merge_step)
Сливаем_в_M(ileft_start, ileft_stop, iright_start, iright_stop,merge_leftpos_start,Слева_Если_Нечетно(merge_step));
Иначе
Сливаем_в_M(ileft_start, ileft_stop, iright_start, iright_stop,merge_rightpos_start, Слева_Если_Нечетно(merge_step));

// результат
M[ 8, 12, 14 | , 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6, 15, 7]
P[7, 8, 12, 14, 15, x, xx, x, x, x, x, xx, xx, xx, xx, x]

merge_step = NOT merge_step
ileft_start = ileft_stop + 1; // 4 после первого прохода
iright_stop = iright_start - 1; //14 после первого прохода
<<КОНЕЦ ЦИКЛА ПОКА>>
// завершен один полный пробег по M
// меняем местами M и P - swap
ОБМЕНЯТЬ(M,P);
<<КОНЕЦ ДЕЛАЙ ВСЕГДА>>
---------- ------------------------------------
//т.к. у нас не программа а лог ее выполнения - пишем дальше.
//сейчас мы на втором проходе внутри цикла <<ЦИКЛ ПОКА ПРОБЕГА ПОКА НЕ ПРОСМОТРИМ M ЦЕЛИКОМ (ileft_stop < iright_start)>>
// продолжаем...
//ищем позицию в которой завершается первый неубывающий диапазон слева
// начало у нас сейчас в 4
ileft_stop = поиск_слева(ileft_start ); // здесь получим 7 на втором шаге для конкретного массива
// вот что мы нашли
M[8, 12, 14, 0, 1, 4, 11 |, 2, 3, 5, 9, 13, 10, 6, 15, 7]

//ищем позицию упорядоченного убывающего диапазона справа
//стоп у нас в 14
iright_start = поиск_справа(iright_stop)// получим 12 на втором просмотре
// вот что мы нашли
M[8, 12, 14, 0, 1, 4, 11 |, 2, 3, 5, 9,| 13, 10, 6 |, 15, 7]
// шаг четиный, потому сливаем вправо
//!! В правый угол пишем в обратной последовательности
Если нечетно
Сливаем_в_M(ileft_start, ileft_stop, iright_start, iright_stop,merge_leftpos_start, Слева_Если_Нечетно(merge_step));
Иначе
Сливаем_в_M(ileft_start, ileft_stop, iright_start, iright_stop,merge_rightpos_start, Слева_Если_Нечетно(merge_step));
// резултьтат
M[8, 12, 14, 0, 1, 4, 11 |, 2, 3, 5, 9,| 13, 10, 6 |, 15, 7]
P[7, 8, 12, 14, 15, x, xx, x, x, 13, 11, 10, 6, 4, 1, 0]

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

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

Кнут оценивает ее как в среднем уступающую быстрой сортировке, но выигрывающей на почти сортированном массиве.
А на таком специальном почти сортированном, который за одно слияние становится сортированным, ее трудно обогнать.
В записи Кнута просмотры осуществляются с обоих концов разом и совмещены с копированием в результат (слиянием).
Главный недостаток - в этой версии алгоритму всегда неизвестно, где расположены сейчас границы диапазонов.
Хотя по мере заполнения P все размеры получающихся диапазонов известны, и после первого swap их можно было бы поддерживать.
Но, такую версию, вроде как, выписывать не принято.

Считается, что если входной массив сортированный, но не настолько, чтобы обойтись одним-двумя проходами
главного цикла, то дешевле и умнее сразу вооружиться 2way версией
(подкрученной до стартовой insertion sort), которая путем применения вмененной арифметики
всегда знает границы своих сортированных частей для четного случая.

А нечетный сводится к четному путем определения места для нечетного элемента
двоичным поиском на последнем шаге сортировки.
...
Рейтинг: 0 / 0
03.02.2017, 04:25
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397726
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
не ждущая убывающего диапазона с правой стороны.
это дефект - считать не написанным
...
Рейтинг: 0 / 0
03.02.2017, 04:28
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397765
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
booby, спасибо за разъяснения, теперь понял.
Не вижу принципиальной разницы с моим способом попарного слияния. У свечи за один раз берутся два крайних подмассива и сливаются в один, затем следующая пара и т.д., у меня берутся два смежных, затем следующие два и т.д. В итоге количество слияний одинаково в обоих алгоритмах.

В моем случае будет так
Код: plaintext
1.
2.
3.
4.
5.
M[8, 12, 14|, 0, 1, 4, 11|, 2, 3, 5, 9, 13, 10, 6, 15, 7]
P[0, 1, 4, 8, 11, 12, 14, x, x, x, x, x, x, x, x, x]

M[x, x, x, x,  x,  x,  x,|2, 3, 5, 9, 13|, 10|, 6, 15, 7]
P[0, 1, 4, 8, 11, 12, 14, 2, 3, 5, 9, 10, 13, x, x, x]
и т.д.
...
Рейтинг: 0 / 0
03.02.2017, 08:43
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39397949
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Dima T,

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

В качестве разницы (между свечкой в Кнутовой записи и в показанном варианте):
У Кнута свеча беспощадна к кэшу и чихать хотела на все представления о локальности разом.
Она смотрит одновременно на обе стороны и копирует рассматриваемый элемент в нужную сторону немедленно и сразу,
как только понимает, что условие сохранения непрерывности последовательностивыполняется.
Слияние совмещено с выявлением последовательности.

Писателю показанного варианта, очевидно поклоннику Вирта и Дейкстры,
кто-то сказал, что это Содом и Гоморра - читать массив с двух концов одновременно .
Поэтому он, на голубом глазу, предпочитает Ад и Израиль двойного касания к каждому элементу - первый раз а выявлении
непрерывной цепочки, а второй - на фазе самого мерджа.
...
Рейтинг: 0 / 0
03.02.2017, 11:28
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398494
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
booby.....
Но, если их переставлять не глядя, то нарушится стабильность, присущая исходному merge sort.
Поэтому фига из трех пальцев - либо плюнуть на стабильность, либо плюнуть на разборки - кто из них длиннее,
либо озаботиться устабилизацией обмена диапазонов.
Если честно - опция стабильности мне всегда казалась очень странным требованием.
Есть собственно KEY сортировки. И есть VALUE. Если очень важна стабильность
ключей на выходе алгоритма (а именно - сохранение ПОРЯДКА) то можно
сразу предложить добавить к ключу суррогат вида sequence (SEQ-KEY)
и сортировать как обычно уже уникальный набор tuples вида {KEY, SEQ-KEY}
любым нестабильным алгоритмом.
...
Рейтинг: 0 / 0
03.02.2017, 23:11
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398522
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Могу обоснованно предположить, что стабильная сортировка эффективнее, т.к.:
1. Не требует памяти для добавления суррогатных ключей;
2. Не требует времени на генерацию и вставку суррогатных ключей;
3. Не требует времени на удаление суррогатных ключей;
...
Рейтинг: 0 / 0
04.02.2017, 07:55
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398581
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
2 Basil A. Sidorov,

требование стабильности более строгое. Нечто, что должно быть доказанным или специально
отслеженным. Поэтому, не глядя за кулисы - можно сразу сказать, что при прочих равных нестабильный алгоритм в среднем быстрее.
И, тем самым, если под эффективностью понимать скорость сортировки - эффективнее.

2 mayton
сортировка - просто один из алгоритмов, который может использоваться сам по себе, а
может использоваться как фрагмент в цепочке алгоритмов, несущий вспомогательную функцию. Во втором случае стабильность может быть желательна или строго необходима.

Пусть например, у тебя есть массив записей, хранящий страну происхождения, товар - яблоки или груши и цена товара. Массив уже сортирован по стране происхождения и цене товара.
Пусть задается вопрос а какая максимальная цена среди всех яблок
Логика ответа такова - надо сгруппировать по товару, отбирая только яблоки, а потом
среди отобранных яблок найти максимальную цену.
Для реализации группировки часто используют сортирующий алгоритм.
И, если этот алгоритм стабильный, то вторая сортировка по цене на отобранном наборе не потребуется.
В некоторых историях стабильность может оказаться ключевым свойством
...
Рейтинг: 0 / 0
04.02.2017, 13:38
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398586
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
boobyтребование стабильности более строгое. Нечто, что должно быть доказанным или специально отслеженным.Только предлагается немного другое: "Давайте забъём на стабильность, а если понадобится - сгородим огород, чтобы продолжать использовать нестабильную сортировку".Поэтому, не глядя за кулисы - можно сразу сказать, что при прочих равных нестабильный алгоритм в среднем быстрее.Стабильная сортировка "следит", чтобы ключи с одинаковыми значениями никак не переставлялись.
Теоретически, наверное, возможно, но практически, всё-таки, маловероятно, что пред- и постобработка массива ключей для обеспечения стабильной сортировки нестабильным алгоритмом будет дешевле. Тем более - существенно дешевле.
Поэтому надо использовать бритву Оккама, чтобы отсекать ненужные фантазии.
...
Рейтинг: 0 / 0
04.02.2017, 13:49
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398595
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Замер выше 20170548
std::stable_sort() делает в разы больше копирований чем std::sort(). ИМХО выгоднее в условие сравнения добавить доп. параметры, чем стабильную сортировку использовать.
...
Рейтинг: 0 / 0
04.02.2017, 14:14
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398600
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima TЗамер выше 20170548
std::stable_sort() делает в разы больше копирований чем std::sort(). ИМХО выгоднее в условие сравнения добавить доп. параметры, чем стабильную сортировку использовать.
чудес не бывает, сравнение по доппараметрам
1. увеличит сложность операции сравнения
2. потребует больше действий (сравнений и перестановок)
...
Рейтинг: 0 / 0
04.02.2017, 14:33
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398602
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Basil A. SidorovПоэтому, не глядя за кулисы - можно сразу сказать, что при прочих равных нестабильный алгоритм в среднем быстрее.Стабильная сортировка "следит", чтобы ключи с одинаковыми значениями никак не переставлялись.
Теоретически, наверное, возможно, но практически, всё-таки, маловероятно, что пред- и постобработка массива ключей для обеспечения стабильной сортировки нестабильным алгоритмом будет дешевле. Тем более - существенно дешевле.
Поэтому надо использовать бритву Оккама, чтобы отсекать ненужные фантазии.
Простой пример
2 1 , 5 2 , 2 3 , 5 4 , 2 5
нестабильной сортируется в 1 перестановку 5 2 <=> 2 5
2 1 , 2 5 , 2 3 , 5 4 , 5 2
а стабильной минимум 3 перестановки
...
Рейтинг: 0 / 0
04.02.2017, 14:34
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398621
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Dima T2 1 , 5 2 , 2 3 , 5 4 , 2 5
нестабильной сортируется в 1 перестановку 5 2 <=> 2 5
2 1 , 2 5 , 2 3 , 5 4 , 5 2
а стабильной минимум 3 перестановкиЭто всё замечательно и демонстрирует, что стабильная сортировка медленнее нестабильной.
Где демонстрация того, что "нестабильная сортировка с наворотами для стабилизации" быстрее "изначально стабильной"? Даже не "существенно быстрее", а просто "быстрее"?
...
Рейтинг: 0 / 0
04.02.2017, 15:12
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398632
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
Basil A. Sidorov,

что за чепуха?
Из какой ноздри взято взято утверждение, что нестабильная сортировка после стабилизации должна оказаться быстрее изначально стабильной?
...
Рейтинг: 0 / 0
04.02.2017, 15:45
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398639
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
boobyИз какой ноздри взято взято утверждение, что нестабильная сортировка после стабилизации должна оказаться быстрее изначально стабильной?А теперь задайте этот вопрос mayton, который предложил стабилизировать нестабильный алгоритм путём предобработки массива ключей.
...
Рейтинг: 0 / 0
04.02.2017, 16:10
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398642
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Basil A. SidorovDima T2 1 , 5 2 , 2 3 , 5 4 , 2 5
нестабильной сортируется в 1 перестановку 5 2 <=> 2 5
2 1 , 2 5 , 2 3 , 5 4 , 5 2
а стабильной минимум 3 перестановкиЭто всё замечательно и демонстрирует, что стабильная сортировка медленнее нестабильной.
Где демонстрация того, что "нестабильная сортировка с наворотами для стабилизации" быстрее "изначально стабильной"? Даже не "существенно быстрее", а просто "быстрее"?
Что туть доказывать?
Давай возьмем любой запрос к БД.
Код: plaintext
1.
select f1,f2,f3,f4,f5 from table order by f1,f2,f3


Т.е. сортировка обычно требуется далеко не по всем полям. Как по твоему: повлияет сохранение исходного порядка f4,f5 на скорость сортировки?
Чудес не бывает, дополнительные условия всегда усложняют алгоритм, поэтому замедляют.
...
Рейтинг: 0 / 0
04.02.2017, 16:18
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398655
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИМХО спор ни о чем. Хочешь порядок сохранить, замени компаратор с
Код: plaintext
1.
bool operator < (item_t const &b) const { compare_cnt++; return data < b.data; }


на
Код: plaintext
1.
bool operator < (item_t const &b) const { compare_cnt++; if (data == b.data) return this < &b; else return data < b.data; }


Итоги: первый вариант
АлгоритмЗаполнениеВремяКопированийСравненийstd::sort()31243041388831497425std::sort()43381177819576052std::sort()222186893017163848std::sort()51054000365900094std::sort()62082499706275071std::sort()723186939017164149std::sort()826518676419651458std::sort()9802945359733074653std::sort()101082604439427351506
второй
АлгоритмЗаполнениеВремяКопированийСравненийstd::sort()31843053368031651345std::sort()41377662564248232380std::sort()220186893017163848std::sort()51198029388549573530std::sort()61268202191750400898std::sort()722186941017164162std::sort()825518676419651458std::sort()9693162457434261072std::sort()101283188979631212294

std::stable_sort() с первым компаратором
АлгоритмЗаполнениеВремяКопированийСравненийstd::stable_sort()31432518690223635522std::stable_sort()4702511565123568259std::stable_sort()234169375009533052std::stable_sort()5482405000022654542std::stable_sort()6492463750022486292std::stable_sort()735169378509533222std::stable_sort()842329375008353742std::stable_sort()9361743807010629112std::stable_sort()10982518468123644316

Извиняюсь, красоту лень наводить, заполнение:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
#define FILL_NONE			0 // Не заполнять
#define FILL_ORDERED		2 // Отсортированный
#define FILL_RANDOM			3 // Случайные (диапазон 0...TEST_SIZE*2)
#define FILL_RANDOM_DOUBLES 4 // Случайные с повторами (диапазон 0...100)
#define FILL_STAIRS			5 // Лесенка по 10 (1,2,3,...8,9,1,2,3...)
#define FILL_SINUS			6 // Синусоида по 10 (1,2,3,...8,9,8,7,6...)
#define FILL_NEARLY			7 // Почти сортированный (20 значений смещено на 20 позиций)
#define FILL_REVERSE		8 // Обратно сортированный
#define FILL_STAIRS_BIG		9 // Лесенка по TEST_SIZE / 4
#define FILL_RANDOM_2		10 // Случайные с повторами (диапазон 0...TEST_SIZE/10)
...
Рейтинг: 0 / 0
04.02.2017, 16:47
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398669
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Basil A. SidorovboobyИз какой ноздри взято взято утверждение, что нестабильная сортировка после стабилизации должна оказаться быстрее изначально стабильной?А теперь задайте этот вопрос mayton, который предложил стабилизировать нестабильный алгоритм путём предобработки массива ключей.
Бог с вами друзья. Я просто добавил что не вижу смысла стабилизировать ключи. Сами посудите.
В реляционной алгебре нет вообще такого понятия. Если нужны доп-критерии порядка то добавляют
синтетический уникальный ключ к неуникальному.

А в не-реляционных юзкейсах (csv, Streams) - очень трудно придумать полезный и такой чтобы был серъезно
аргументирован.
...
Рейтинг: 0 / 0
04.02.2017, 18:17
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398680
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
maytonА в не-реляционных юзкейсах (csv, Streams) - очень трудно придумать полезный и такой чтобы был серъезно аргументирован.Ограниченность используемого инструмента, например.
Если всё, что у меня есть, это "sort /+номер", то отсортировать сначала по колонке +50, а уже потом - колонке +20 можно только двумя последовательными сортировками.

P.S. "Есть много, друг Горацио ..."
P.P.S. Если бы чистая реляционная алгебра была практичной - хинтов и прочей магии не существовало бы.
...
Рейтинг: 0 / 0
04.02.2017, 19:27
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398743
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,
(Хоть я тебя и понял правильно)
Что ты говоришь?
Если в реляционной алгебре нет такого понятия ( а в ней нет такого понятия),
как это обстоятельство может быть изменено путем добавления чего-то к кому-то.

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

Уникальный ключ - он в огороде реляционной алгебры,
а порядок - в Киеве, на стороне клиентского приложения, привносящего порядок в последовательность поступающих с огорода уникальных ключей.

Так вот если на стороне того клиента используется набор последовательно выполняемых
алгоритмов, как-то фильтрующих группирующих поступающие ключи и ставящих
поступившие ключи в различные очереди для последующей обработки, и ставится задача сохранения историчности формирующихся очередей в том смысле, что ключ поступивший на обработку в такую систему в результирующей очереди должен оказаться перед ключём,
пришедшим в систему позже, то необходимо использовать стабильную сортировку на
промежуточных этапах.
Утверждение сорта я добавлю второй ключ в сортировку и она станет стабильной эквивалентно тому, что промежуточный сортирующий алгоритм уже точно знает окончательную судьбу обрабатываемого ключа.
Кроме разбора ключей в Киеве, стабильная сортировка часто считается желательной при работе с визуальными интерфейсами.
Логическая организация системы, в которой эффект двухключевой сортировки достигается методом применения стабильной сортировки по второму ключу к набору данных, про который
достоверно известно, что по первому ключу он уже сортирован, много проще в общем случае.
Да и в смысле физического времени отклика у нее есть хорошие шансы против пересортировки заново по всему набору ключей.
...
Рейтинг: 0 / 0
05.02.2017, 01:19
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398870
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
booby,

у меня нет с вами предмета спора. Я просто хотел акцентировать на том
что никогда не видел смысла в стабилизации и не было у меня задач
где сама постановка "порядка поступления на вход" данных была
бы ключевой.
...
Рейтинг: 0 / 0
05.02.2017, 15:52
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398877
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,

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

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

С тем, чтобы при случае, может быть, иметь возможность выбрать из готовых стабильных, вместо того, чтобы заниматься стабилизацией нестабильного.
...
Рейтинг: 0 / 0
05.02.2017, 16:28
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398887
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,

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

Вот пирамидальная сортировка, которой ты формально посвятил тему:
- неустойчива, так же как и быстрая
- для "среднего случая" оценивается как несколько хуже быстрой при той же асимптотике.

Но.
У этой сортировки есть еще одно собственное свойство, кроме нестабильности
- это сортировка с использованием специальной сортирующей структуры.

Хуже быстрой в среднем она оказывается в динамическом случае, когда сортирующую пирамиду приходится строить по мере поступления сортируемых данных.
Однако, если представить себе статический случай, когда состав пирамиды (сортирующей структуры) известен до начала процедуры сортировки, то пирамидальная сортировка
может волшебным образом превращаться из алгоритма, работающего за O(n*log(n))
в алгоритм, работающий за O(n).

Т.е. для специальных "статических" случаев сортировка с использованием полной сортирующей структуры
(в качестве которой, в простейшем случае,
может быть использован даже сам однажды сортированный массив в комбинации с разумно подкрученным бинарным поиском, если известно, что состав сортируемых данных всегда один и тот же)
может достаточно далеко обгонять любые
лидирующие для динамического случаи алгоритмы
...
Рейтинг: 0 / 0
05.02.2017, 17:14
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398946
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Basil A. SidorovP.P.S. Если бы чистая реляционная алгебра была практичной - хинтов и прочей магии не существовало бы.
Индексы это уже магия, в теории РСУБД они не упоминаются.
...
Рейтинг: 0 / 0
05.02.2017, 20:43
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398973
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
boobymayton,

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

Вот пирамидальная сортировка, которой ты формально посвятил тему:
неустойчива, так же как и быстрая
- для "среднего случая" оценивается как несколько хуже быстрой при той же асимптотике.

Но.
У этой сортировки есть еще одно собственное свойство, кроме нестабильности
- это сортировка с использованием специальной сортирующей структуры.

Хуже быстрой в среднем она оказывается в динамическом случае, когда сортирующую пирамиду приходится строить по мере поступления сортируемых данных.
Однако, если представить себе статический случай, когда состав пирамиды (сортирующей структуры) известен до начала процедуры сортировки, то пирамидальная сортировка
может волшебным образом превращаться из алгоритма, работающего за O(n*log(n))
в алгоритм, работающий за O(n).

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

Не могли бы вы пожалуйста привести пример так называемых вами специальных статических случаев?)
...
Рейтинг: 0 / 0
05.02.2017, 22:13
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39398991
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
SashaMercury
...
Не могли бы вы пожалуйста привести пример так называемых вами специальных статических случаев?)

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

Возможно, самый распространенный пример "статического случая" - индексы в базе данных.
Чем компактнее индексируемый набор данных и чаще поступают запросы на выборку
упорядоченного подмножества данных или поиск минимального/максимального или
предшествующих им элементов, тем больше смысла в создании такой сортирующей структуры
(она же выбирающая), как индекс.
...
Рейтинг: 0 / 0
05.02.2017, 23:46
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39399686
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
boobymayton,


Вот пирамидальная сортировка, которой ты формально посвятил тему:
- неустойчива, так же как и быстрая
- для "среднего случая" оценивается как несколько хуже быстрой при той же асимптотике.

Но.
У этой сортировки есть еще одно собственное свойство, кроме нестабильности
- это сортировка с использованием специальной сортирующей структуры.


Это скорее не сортировка с использование структуры данных, в сортировка основанная на использование удачной структуры данных. В данном конкретном случае, исторически есть смысл ссылаться на сортировку выбором и оптимизацию выбора нового минимального элемента не за счет поиска по всему массиву за O(n) итераций, использование удачной структуры данных и дает нам в итоге(это ключевые слова) O(lgn) на поиск нового элемента. Потому это сортировка появившаяся только благодаря удачной и красивейшей структуре данных - пирамиды.

boobyо статическом случае можно рассуждать всякий раз, когда известно, что на времени обработки полное множество данных не меняется, а число поступающих для сортировки серий,
каждая из которых представляет собой подмножество полного множества данных, достаточно велико, чтобы оправдать создание сортирующей структуры на полном множестве, которую потом можно использовать для сортировки набора поступающих подмножеств.

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


Я понимаю то, о чем говорил White Owl - действительно, существуют различные вариации пирамидальной сортировки и т.д. и т.п. Но то, о чем говорите вы, мне не очень понятно. Если вас это не слишком затруднит, приведите пожалуйста конкретный набор данных, конкретную серию и какая именно сортировка выполняется. Возможно вы имеете что-то другое, и я вас просто не понимаю, поскольку у пирамидальной сортировки в классическом понимании есть хорошая оценка асимптотики независимо от каких либо случаев: "худший", "лучший","средний".
...
Рейтинг: 0 / 0
06.02.2017, 22:33
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39399774
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
SashaMercury Возможно вы имеете что-то другое, и я вас просто не понимаю, поскольку у пирамидальной сортировки в классическом понимании есть хорошая оценка асимптотики независимо от каких либо случаев: "худший", "лучший","средний".
booby,
тоже удивило, хоть упрись но у классической реализации "составление кучи O(N), вычленение O(N ln(n))" практически стабильное время - это один из её плюсов
...
Рейтинг: 0 / 0
07.02.2017, 08:06
| Ответить | Цитировать | Написать  
Тяпничная пирамида
    #39421002
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
 
Затестил сортировку деревом триплетов
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
// triplet-three

#define TRIPLET_MAX 4096 // Максимальное количество триплетов которые можно использовать

// Интерфейс источника последовательности
class source_t {
	item_t* first = { 0 };		// Первый элемент в последовательности
	bool is_init = { NULL };
public:
	int num = { 0 };

	virtual ~source_t() {}

	void clear() {
		first = NULL;
		is_init = false;
	}

	// Первый элемент в очереди, NULL если пусто
	item_t* front() {
		if (first == NULL && !is_init) {
			is_init = true;
			pop();
		}
		return first;
	}

	// Извлечение следующего элемента
	void pop() {
		first = next();
	}

	// Считывание следующего элемента последовательности, NULL если читать нечего
	virtual item_t* next() {
		assert(false); // должно быть прописано в дочернем классе
		return NULL;
	}
};

// Возрастающая последовательность
class enumerable_t : public source_t {
	item_t* begin = { 0 }; // Первый элемент в последовательности
	item_t* end = { 0 };   // За последним

public:
	// Инициализация
	void init(item_t* begin, item_t* end) {
		assert(begin < end);
		clear();
		this->begin = begin;
		this->end = end;
	}

	// Считывание следующего элемента последовательности, NULL если читать нечего
	item_t* next() override {
		if (begin < end) {
			return begin++; 
		} else {
			return NULL;
		}
	}
};

// Триплет. Слияние двух последовательностей, выдает общую на выходе
class triplet_t : public source_t {
	source_t* src_1 = { 0 };	// Источник 1 вход
	source_t* src_2 = { 0 };	// Источник 2 вход
	source_t* next_pop = { 0 };// Следующий на pop

public:
	// Подключение дочерних источников
	void init(source_t* src1, source_t* src2) {
		src_1 = src1;
		src_2 = src2;
	}

	item_t* next() override {
		// Извлечение следующего
		if (next_pop != NULL) {
			next_pop->pop();
			next_pop = NULL;
		}
		// Выбор следующего
		if (src_2->front() == NULL) {
			next_pop = src_1;
		} else if (src_1->front() == NULL) {
			next_pop = src_2;
		} else if (*src_1->front() < *src_2->front()) {
			next_pop = src_1;
		} else {
			next_pop = src_2;
		}
		return next_pop->front();
	}
};
// Слияние массива src в dest деревом триплетов, возвращает указатель на следующий за последним item_t* triplet_store(source_t** src, size_t src_size, item_t* dest) { assert(src_size != 0); source_t* head; triplet_t trp[TRIPLET_MAX]; if (src_size == 1) { head = src[0]; } else { for (size_t i = 0; i < TRIPLET_MAX; i++) trp[i].num = i + 1000; assert(src_size != 0 || src_size >= TRIPLET_MAX); // Инициализация первых триплетов на src_size входов source_t* alone = NULL; // Не привязанный size_t cnt = 0; for (size_t i = 0; ; i += 2) { if (i == src_size) break; if (i == src_size - 1) { alone = src[i]; break; } trp[cnt].init(src[i], src[i + 1]); cnt++; } // Инициализация остального дерева size_t first = 0, last = cnt; while (last - first > 1) { for (size_t i = first; ; i += 2) { if (i == last) break; if (i == last - 1) { if (alone == NULL) { alone = &trp[i]; } else { trp[cnt].init(&trp[i], alone); cnt++; alone = NULL; } break; } trp[cnt].init(&trp[i], &trp[i + 1]); cnt++; assert(cnt < TRIPLET_MAX); } first = last; last = cnt; } if (alone != NULL) { trp[cnt].init(&trp[first], alone); first = cnt; } head = &trp[first]; } // Сохранение const item_t* i; while (i = head->front()) { *dest = *i; dest++; head->pop(); } return dest; } // Подготовка сортировки. Сортирует a. Возвращает указатель на результат std::vector<item_t>* triplet_three(std::vector<item_t>* a, std::vector<item_t>* b) { enumerable_t enm[TRIPLET_MAX]; source_t* src[TRIPLET_MAX]; size_t repeat = 0; while(repeat != 1) { repeat = 0; item_t* cur = &(*a)[0]; item_t* finish = cur + a->size(); item_t* write = &(*b)[0]; item_t* write_finish = write + b->size(); while(cur < finish) { repeat++; // Поиск последовательностей item_t* first = cur; size_t cnt = 0; while(cnt < TRIPLET_MAX) { item_t* start = cur; item_t* prev = NULL; while(cur < finish && (prev == NULL || !((*cur) < (*prev)))) { prev = cur; cur++; } enm[cnt].init(start, cur); src[cnt] = &enm[cnt]; cnt++; if (cur == finish) { break; } } if (cnt == 1) return a; // Сортировка item_t* write_new = triplet_store(src, cnt, write); write = write_new; } assert(write == write_finish); std::vector<item_t>* t = a; a = b; b = t; } return a; }

[/spoiler]
Алгоритм такой: исходный массив разбивается на последовательности, последовательности даются на вход дереву триплетов.

Код: plaintext
1.
2.
3.
1234
\/\/
 \/
Выход

1234 это источники последовательностей, т.е. 4 упорядоченные последовательности выдающие элементы по возрастанию.

У каждой последовательности есть два метода:
Код: plaintext
1.
2.
3.
4.
5.
// Интерфейс источника последовательности
class source_t {
	virtual const item_t* front() {// Первый элемент в очереди, NULL если пусто
	
	virtual void pop() { // Извлечение следующего элемента


Приемник просто вычитывет инфу пока последовательность не опустеет.

\/ это триплет. На входе две последовательности, на выходе одна. Он проверяет front() входов, и отдает тот что меньше и делает для того входа pop()

Плюс переливание сортированного в другой массив до тех пор пока за 1 перелив не перельется.

Остальные результаты отсюда 20170548

Исходные заполнения
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
#define FILL_ORDERED		2 // Отсортированный
#define FILL_RANDOM		3 // Случайные (диапазон 0...TEST_SIZE*2)
#define FILL_RANDOM_DOUBLES	4 // Случайные с повторами (диапазон 0...100)
#define FILL_STAIRS		5 // Лесенка по 10 (1,2,3,...8,9,1,2,3...)
#define FILL_SINUS		6 // "Синусоида" по 10 (1,2,3,...8,9,8,7,6...)
#define FILL_NEARLY		7 // Почти сортированный (20 значений смещено на 20 позиций)
#define FILL_REVERSE		8 // Обратно сортированный


Время мс
АлгоритмNEARLYORDEREDRANDOMRANDOM_DOUBLESREVERSESINUSSTAIRSinsert_sort()13131311369319128138merge_sort()64363817711164652835836quick_sort()1631621119579176415418std::sort()2712681255344305115127std::stable_sort()4254301238818502601608triplet_tree219829532129169018511540

 
Копирования и сравнения
Копирования
АлгоритмNEARLYORDEREDRANDOMRANDOM_DOUBLESREVERSESINUSSTAIRSinsert_sort()7900369 072 660102 318 66272 827 95476 243 23879 998 904merge_sort()243 222 784243 222 784243 222 784243 222 784243 222 784243 222 784243 222 784quick_sort()5 807 0165 805 696169 379 23263 116 09720 805 69737 944 05239 390 073std::sort()17 903 42017 902 850363 987 48889 248 99552 799 54856 249 95860 000 051std::stable_sort()209 375 190209 375 000291 879 725291 127 627369 375 000286 375 000280 500 000triplet_tree10 000 000020 000 00020 000 00020 000 00020 000 00020 000 000


Сравнения
АлгоритмNEARLYORDEREDRANDOMRANDOM_DOUBLESREVERSESINUSSTAIRSinsert_sort()10 003 9059 999 999369 299 21096 712 227229 948 65155 283 62962 031 773merge_sort()118 788 350118 788 160220 045 179219 421 541114 434 624210 164 144210 145 472quick_sort()230 640 809230 639 897372 371 596340 441 764235 639 920349 632 120343 247 281std::sort()211 048 809211 048 588373 475 89997 094 945229 825 83855 250 06062 000 101std::stable_sort()116 588 748116 588 568273 242 003272 348 16899 122 124260 926 462261 829 730triplet_tree35 500 2199 999 999238 997 171238 337 713134 434 622249 662 526209 709 873
Так себе по времени, но копирований очень мало: 1-2 переливания всего массива.
...
Рейтинг: 0 / 0
16.03.2017, 17:40
| Ответить | Цитировать | Написать  
126 сообщений из 126, показаны все 6 страниц
  все  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная пирамида
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]