Здравствуйте, inopressa, Вы писали:

I>Никого не хочу задеть, но очень широко распространено утверждение, что необходимо знание теоретическое тех же алгоритмов сортировки, правда применить его решительно негде.

Ну например, задача поиска первых минимальных N чисел (т.е., тех, что после сортировки будут идти первыми) в большом несортированом массиве. за O(длины массива) без N проходов по массиву. N << длины массива, массив можно модифицировать.

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

Здравствуйте, sdf, Вы писали:

sdf>Ну например, задача поиска первых минимальных N чисел (т.е., тех, что после сортировки будут идти первыми) в большом несортированом массиве. за O(длины массива) без N проходов по массиву. N << длины массива, массив можно модифицировать.

В смысле сделать из массива кучу? Сдается мне пример крайне неудачный

Здравствуйте, MTD, Вы писали:

MTD>Здравствуйте, sdf, Вы писали:

sdf>>Ну например, задача поиска первых минимальных N чисел (т.е., тех, что после сортировки будут идти первыми) в большом несортированом массиве. за O(длины массива) без N проходов по массиву. N << длины массива, массив можно модифицировать.

MTD>В смысле сделать из массива кучу?
Можно и сделать кучу, но это — перелопачивание всего массива. Модифицированный quicksort трогает только часть элментов и более эффективен с точки зрения локальности и кеша.

> Сдается мне пример крайне неудачный
Вполне удачый, вариант с хипом менее эффективный за счет того, что менее эффективно работает к кешем (менее локальный).

Здравствуйте, sdf, Вы писали:

sdf>Для решения используется тот же подоход. что и у quicksort, но с модификациями. Задача возникает при обработке больших обьемов данных довольно часто.
Ээээ, шеф, это не применение алгоритма сортировки! Это широко известный стандартный алгоритм, кажется называется quick select. Его не надо придумывать, и детали его реализации не надо помнить, он уже 100 раз написан, нужно только знать, что он есть!
А для решения используется более фундаментальный подход — divide and conquer. Именно этот подход и является базисом и именно из этого подхода все выводится, а вовсе не квиксорт!

Здравствуйте, sdf, Вы писали:

sdf>Модифицированный quicksort трогает только часть элментов и более эффективен с точки зрения локальности и кеша.

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

Здравствуйте, elmal, Вы писали:

E>Здравствуйте, sdf, Вы писали:

sdf>>Для решения используется тот же подоход. что и у quicksort, но с модификациями. Задача возникает при обработке больших обьемов данных довольно часто.
E>Ээээ, шеф, это не применение алгоритма сортировки!
Действительно, это не применение алгоритма сортировки. Это прменение идей из аглоритма сортировки.

> Это широко известный стандартный алгоритм, кажется называется quick select.
Во-первых, то, что вы имеете в вижу, называется k-order statistic, во-вторых, формулировка моей задачи отличается.

> Его не надо придумывать, и детали его реализации не надо помнить,
> он уже 100 раз написан, нужно только знать, что он есть!
Давайте, найдите мне его готовый.

E>А для решения используется более фундаментальный подход — divide and conquer. Именно этот подход и является базисом и именно из этого подхода все выводится, а вовсе не квиксорт!
А еще любой язык учить не надо — во всех языкаих используется фундаментальный подход — люди откывают и закрывают рот и произносят звуки, из этого подхода все выводится

Здравствуйте, MTD, Вы писали:

MTD>Здравствуйте, sdf, Вы писали:

sdf>>Модифицированный quicksort трогает только часть элментов и более эффективен с точки зрения локальности и кеша.

MTD>Неплохо бы на реализацию посмотреть, потому как не понятно, что там изобретено.
Мне совершенно неохота выдирать этот алгоритм из продакшен-кода под NDA и его тут показывать, чтобы что-то вам доказывать. Я привел пример в ответ на забавную просьбу. Попробуйте решить эту задачу сами твк, чтобы решение работало быстрее, чем построение хипа из массива и последовательный вызов heap-pop N раз и чтобы оно работало эффективно, когда весь массив не умещается в памяти, вы поймете, что пространство для изобретения там есть и оно очень большое.

> Кроме того не понял, что значит "трогает только часть элментов", пройти по всем элементам придется по условию задачи.
Пройтись придется по всем, но heapsort будет хуже использовать кещ и больше переставлять элементы туда-сюда в процессе работы. На больших объёмах данных он работает заметно хуже модифицированного quicksortа

Здравствуйте, sdf, Вы писали:

sdf>Во-первых, то, что вы имеете в вижу, называется k-order statistic, во-вторых, формулировка моей задачи отличается.
Далеко не уверен, что я это имел в виду.

sdf>Давайте, найдите мне его готовый.
http://dml.cs.byu.edu/~sburton/cs235/notes/view.php?file=PreviousTerms/extra%20notes/rodham/20-sorting-4/QuickSelect.java
Нашел просто гуглом, и, кстати, похоже память меня не подвела, действительно это quickselect. Стандартная институтская программа, вообще то. При этом я на бумажке без подготовки среди ночи квиксорт не напишу! И если б я помнил детали реализации квиксорт — далеко не факт, что я б сходу этот алгоритм вывел, я про него просто знал!

Здравствуйте, elmal, Вы писали:

E>http://dml.cs.byu.edu/~sburton/cs235/notes/view.php?file=PreviousTerms/extra%20notes/rodham/20-sorting-4/QuickSelect.java
E>Нашел просто гуглом, и, кстати, похоже память меня не подвела, действительно это quickselect. Стандартная институтская программа, вообще то. При этом я на бумажке без подготовки среди ночи квиксорт не напишу! И если б я помнил детали реализации квиксорт — далеко не факт, что я б сходу этот алгоритм вывел, я про него просто знал!

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

Здравствуйте, sdf, Вы писали:

MTD>>Неплохо бы на реализацию посмотреть, потому как не понятно, что там изобретено.
sdf>Мне совершенно неохота выдирать этот алгоритм из продакшен-кода под NDA и его тут показывать, чтобы что-то вам доказывать.

Спокойней, мы же просто общаемся

sdf>Я привел пример в ответ на забавную просьбу.

Просьба нормальная — ответ забавный

sdf>Попробуйте решить эту задачу сами твк, чтобы решение работало быстрее, чем построение хипа из массива и последовательный вызов heap-pop N раз и чтобы оно работало эффективно, когда весь массив не умещается в памяти, вы поймете, что пространство для изобретения там есть и оно очень большое.

Как только условие уточните, так с удовольствием попробую. Тем более, что сдается мне ни quick select, ни построение кучи для ваших целей не потребуются.

Здравствуйте, MTD, Вы писали:

MTD>Как только условие уточните, так с удовольствием попробую. Тем более, что сдается мне ни quick select, ни построение кучи для ваших целей не потребуются.

Условие то же, что и прежде. Могу уточнить, что данные лежат на диске (для простоты — это несколько терабайт double-ов одним файлом), N порядка 1000. Но вообще уточнять можно бесконечно. Например, что диск не SSD, памяти на машине 32 Гб, и т. д.

Здравствуйте, sdf, Вы писали:

sdf>Условие то же, что и прежде. Могу уточнить, что данные лежат на диске (для простоты — это несколько терабайт double-ов одним файлом), N порядка 1000. Но вообще уточнять можно бесконечно. Например, что диск не SSD, памяти на машине 32 Гб, и т. д.

Хорошо бы о данных уточнить, но пока этого достаточно:

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <vector>

#include <boost/progress.hpp>

template <typename T>
class Selector
{
public:
    explicit Selector(size_t limit)
        : Limit_(limit)
        , Data_(limit)
        , Size_(0)
    {
        assert(Limit_ > 0);
    }

    void operator()(const T& value)
    {
        if (Size_ != Limit_)
        {
            Data_[Size_] = value;
            ++Size_;
            Sort();
        }
        else if (value < Data_[Size_ - 1])
        {
            Data_[Size_ - 1] = value;
            Sort();
        }
    }

    const T* Begin() const
    {
        return &*Data_.begin();
    }

    size_t Size() const
    {
        return Size_;
    }

private:
    void Sort()
    {
        for (size_t i = Size_ - 1; i != 0; --i)
        {
            if (Data_[i - 1] > Data_[i])
            {
                std::swap(Data_[i - 1], Data_[i]);
            }
            else
            {
                return;
            }
        }
    }

private:
    const size_t Limit_;
    std::vector<T> Data_;
    size_t Size_;
};

template <typename Iter>
void Print(Iter begin, size_t n)
{
    std::copy(begin, begin + n, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n\n";
}

const size_t LIMIT = 1000;
const size_t TOTAL = 200000000;

typedef unsigned ValueT;

int main()
{
    std::vector<ValueT> data(TOTAL);

    srand(time(0));
    std::generate(data.begin(), data.end(), rand);

    {
        boost::progress_timer timer;
        const Selector<ValueT>& selector = std::for_each(data.begin(), data.end(), Selector<ValueT>(LIMIT));
        //Print(selector.Begin(), selector.Size());
    }

    {
        boost::progress_timer timer;
        std::nth_element(data.begin(), data.begin() + LIMIT, data.end());
        //Print(data.begin(), LIMIT);
    }
}

В среднем nth_element (который, как правило O(n)) медленнее моего велосипеда в 3 раза. Очень интересует сравнение с вашим велосипедом.

Здравствуйте, MTD, Вы писали:

MTD>Здравствуйте, sdf, Вы писали:

sdf>>Условие то же, что и прежде. Могу уточнить, что данные лежат на диске (для простоты — это несколько терабайт double-ов одним файлом), N порядка 1000. Но вообще уточнять можно бесконечно. Например, что диск не SSD, памяти на машине 32 Гб, и т. д.

MTD>Хорошо бы о данных уточнить, но пока этого достаточно:
MTD>В среднем nth_element (который, как правило O(n)) медленнее моего велосипеда в 3 раза. Очень интересует сравнение с вашим велосипедом.
Сравнивать будет можно начать тогда, кода ваш велосипед сможет обрабатвыать пару терабайт doubleов, лежащих на диске. Я об этом явно сказал в уточнении.

Здравствуйте, sdf, Вы писали:

MTD>>В среднем nth_element (который, как правило O(n)) медленнее моего велосипеда в 3 раза. Очень интересует сравнение с вашим велосипедом.

sdf>Сравнивать будет можно начать тогда, кода ваш велосипед сможет обрабатвыать пару терабайт doubleов, лежащих на диске. Я об этом явно сказал в уточнении.

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

Здравствуйте, MTD, Вы писали:

MTD>Здравствуйте, sdf, Вы писали:

MTD>>>В среднем nth_element (который, как правило O(n)) медленнее моего велосипеда в 3 раза. Очень интересует сравнение с вашим велосипедом.

sdf>>Сравнивать будет можно начать тогда, кода ваш велосипед сможет обрабатвыать пару терабайт doubleов, лежащих на диске. Я об этом явно сказал в уточнении.

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

Здравствуйте, sdf, Вы писали:

MTD>>И в чем проблема?
sdf>Проблем на самом деле куча.
sdf>Начать надо, например с того, что ваш код будет тормозить на данных, имеющих внутри отсортированные в обратном порядке куски.

В теории. Сравнить хотите? Или согласитесь, что пример у вас крайне неудачен?

Здравствуйте, MTD, Вы писали:

MTD>В теории. Сравнить хотите? Или согласитесь, что пример у вас крайне неудачен?
Не в теории, а на практике. Замените массив стучайных чисел массивом от 200000000 до 1 и посмотрите на результат.

Здравствуйте, sdf, Вы писали:

sdf>Здравствуйте, MTD, Вы писали:

MTD>>В теории. Сравнить хотите? Или согласитесь, что пример у вас крайне неудачен?
sdf>Не в теории, а на практике. Замените массив стучайных чисел массивом от 200000000 до 1 и посмотрите на результат.

Это я сразу проверил. Ну так сравнивать будем? Надеюсь на сокрушительную победу знания деталей алгоритмов сортировки

Здравствуйте, MTD, Вы писали:

MTD>Здравствуйте, sdf, Вы писали:

sdf>>Здравствуйте, MTD, Вы писали:

MTD>>>В теории. Сравнить хотите? Или согласитесь, что пример у вас крайне неудачен?
sdf>>Не в теории, а на практике. Замените массив стучайных чисел массивом от 200000000 до 1 и посмотрите на результат.

MTD>Это я сразу проверил.
Тест и результаты в студию!

>Ну так сравнивать будем?
Понятия не имею. В таком виде не вижу смыслf — на отсортированным в обратном порядке данных ваш агоритм будет работат хуже чем реалзиация из STL.

Здравствуйте, sdf, Вы писали:

>>Ну так сравнивать будем?
sdf>Понятия не имею.

Отчего так? Изобретенного вами алгоритма не существует?

sdf>В таком виде не вижу смыслf — на отсортированным в обратном порядке данных ваш агоритм будет работат хуже чем реалзиация из STL.

Потому я и говорил, что надо уточнить, что за входные данные. Для упорядоченного массива готов изобрести алгоритм со сложностью O(1)