ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная пирамида
25 сообщений из 126, страница 1 из 6
  1  все
Тяпничная пирамида
    #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
| Ответить | Цитировать | Написать  
25 сообщений из 126, страница 1 из 6
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная пирамида
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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