Сообщение Re[11]: Java vs C# vs C++ от 29.09.2015 23:56
Изменено 30.09.2015 0:00 Evgeny.Panasyuk
Здравствуйте, T4r4sB, Вы писали:
EP>>А у меня тот код который быстрый обычно оперирует обобщёнными абстракциями — это более высокий уровень — because I can. И в таком коде я спокойно могу использовать например ФВП и замыкания, а не расписывать вручную каждую комбинацию алгоритма, контейнера и предиката — because I can.
TB>А как написать сортировку, не расписав вручную для каждого контейнера?
Абстрагировав интерфейс доступа к элементам последовательности в отдельную концепцию, например в итераторы. Один вариант итератора соответствует множеству контейнеров.
TB>Хотя я задавался таким вопросом помню, и таки да, такая сортировка существует, но от оптимальной она далека.
С сортировкой много разных моментов связанно. Выбор оптимальной зависит не только от типа контейнера/элемента.
Например тот же связный список можно отсортировать слияниями через жонглирование связями (никак не перемещая сами элементы), а можно сначала переместить данные в массив, отсортировать, и переместить обратно. Оптимальный выбор зависит от ситуации, к примеру перелинковка может быть крайне нежелательна, так как может сильно нарушить последовательность узлов в памяти.
TB>Так что обобщённость тоже имеет свой предел.
Естественно имеет. В подобных случаях кстати отлично работает перегрузка/специализация. Каноничный пример std::advance — для RandomAccess он Θ(1), для остальных Θ(n).
EP>>А у меня тот код который быстрый обычно оперирует обобщёнными абстракциями — это более высокий уровень — because I can. И в таком коде я спокойно могу использовать например ФВП и замыкания, а не расписывать вручную каждую комбинацию алгоритма, контейнера и предиката — because I can.
TB>А как написать сортировку, не расписав вручную для каждого контейнера?
Абстрагировав интерфейс доступа к элементам последовательности в отдельную концепцию, например в итераторы. Один вариант итератора соответствует множеству контейнеров.
TB>Хотя я задавался таким вопросом помню, и таки да, такая сортировка существует, но от оптимальной она далека.
С сортировкой много разных моментов связанно. Выбор оптимальной зависит не только от типа контейнера/элемента.
Например тот же связный список можно отсортировать слияниями через жонглирование связями (никак не перемещая сами элементы), а можно сначала переместить данные в массив, отсортировать, и переместить обратно. Оптимальный выбор зависит от ситуации, к примеру перелинковка может быть крайне нежелательна, так как может сильно нарушить последовательность узлов в памяти.
TB>Так что обобщённость тоже имеет свой предел.
Естественно имеет. В подобных случаях кстати отлично работает перегрузка/специализация. Каноничный пример std::advance — для RandomAccess он Θ(1), для остальных Θ(n).
Re[11]: Java vs C# vs C++
Здравствуйте, T4r4sB, Вы писали:
EP>>А у меня тот код который быстрый обычно оперирует обобщёнными абстракциями — это более высокий уровень — because I can. И в таком коде я спокойно могу использовать например ФВП и замыкания, а не расписывать вручную каждую комбинацию алгоритма, контейнера и предиката — because I can.
TB>А как написать сортировку, не расписав вручную для каждого контейнера?
Абстрагировав интерфейс доступа к элементам последовательности в отдельную концепцию, например в итераторы. Один вариант итератора соответствует множеству контейнеров.
TB>Хотя я задавался таким вопросом помню, и таки да, такая сортировка существует, но от оптимальной она далека.
С сортировкой много разных моментов связанно. Выбор оптимальной зависит не только от типа контейнера/элемента.
Например тот же связный список можно отсортировать слияниями через жонглирование связями (никак не перемещая сами элементы), а можно сначала переместить данные в массив, отсортировать интроспективной сортировкой, и переместить обратно. Оптимальный выбор зависит от ситуации, к примеру перелинковка может быть крайне нежелательна, так как может сильно нарушить последовательность узлов в памяти. Тем не менее, оба из этих вариантов сортировок могут быть реализованы обобщённо.
TB>Так что обобщённость тоже имеет свой предел.
Естественно имеет. В подобных случаях кстати отлично работает перегрузка/специализация. Каноничный пример std::advance — для RandomAccess он Θ(1), для остальных Θ(n).
EP>>А у меня тот код который быстрый обычно оперирует обобщёнными абстракциями — это более высокий уровень — because I can. И в таком коде я спокойно могу использовать например ФВП и замыкания, а не расписывать вручную каждую комбинацию алгоритма, контейнера и предиката — because I can.
TB>А как написать сортировку, не расписав вручную для каждого контейнера?
Абстрагировав интерфейс доступа к элементам последовательности в отдельную концепцию, например в итераторы. Один вариант итератора соответствует множеству контейнеров.
TB>Хотя я задавался таким вопросом помню, и таки да, такая сортировка существует, но от оптимальной она далека.
С сортировкой много разных моментов связанно. Выбор оптимальной зависит не только от типа контейнера/элемента.
Например тот же связный список можно отсортировать слияниями через жонглирование связями (никак не перемещая сами элементы), а можно сначала переместить данные в массив, отсортировать интроспективной сортировкой, и переместить обратно. Оптимальный выбор зависит от ситуации, к примеру перелинковка может быть крайне нежелательна, так как может сильно нарушить последовательность узлов в памяти. Тем не менее, оба из этих вариантов сортировок могут быть реализованы обобщённо.
TB>Так что обобщённость тоже имеет свой предел.
Естественно имеет. В подобных случаях кстати отлично работает перегрузка/специализация. Каноничный пример std::advance — для RandomAccess он Θ(1), для остальных Θ(n).