Хочется попробовать использовать библиотеку шаблонов и вот какой возник вопрос.
Есть что-то типа вот такого:
typedef struct
{
int cmd;
float var;
}DATA;
typedef struct
{
FILETIME ft;
DATA data;
}DATA_FROM;
DATA_FROM df[1000];
Вот теперь хотелось бы отсортировать такой массив по FILETIME. Не подскажите, как это лучше сделать средствами STL? Пошукав, обнаружил такой инструмент, как map<string, int> M; <ключ, значение>. Но применительно к моей задачи никак не соображу. Есть еще элемент list, посоветуйте пожалуйста решение?
Здравствуйте, Anton_Savickiy, Вы писали:
A_S>Хочется попробовать использовать библиотеку шаблонов и вот какой возник вопрос.
A_S>Есть что-то типа вот такого:
A_S>typedef struct A_S>{ A_S> FILETIME ft; A_S> DATA data; A_S>}DATA_FROM;
A_S>DATA_FROM df[1000];
A_S>Вот теперь хотелось бы отсортировать такой массив по FILETIME. Не подскажите, как это лучше сделать средствами STL? Пошукав, обнаружил такой инструмент, как map<string, int> M; <ключ, значение>. Но применительно к моей задачи никак не соображу. Есть еще элемент list, посоветуйте пожалуйста решение?
std::map это контейнер, а не средство сортировки (да, в нем элементы лежат упорядоченно).
Для сортировки есть std::sort.
Чтобы его применить можно:
1. Определить operator< для DATA_FROM.
Тогда вызов будет таким:
Здравствуйте, Anton_Savickiy, Вы писали:
A_S>2) А теперь отсортируем структуры.
A_S>a) STL A_S>
A_S>struct sort_rule
A_S>{
A_S> bool operator() (DATA_C i, DATA_C j)// <-- Замени передачу по значению на ссылкиbool operator() (const DATA_C& i, const DATA_C& j) const// <-- Вот так
{
return (CompareFileTime(&i.ft,&j.ft) < 0);
}
A_S>} sort_object;
A_S>
A_S>А вот тут уже результат совсем другой. Да, сортируются всегда одинаковые массивы.
A_S>STL time = 1209ms A_S>selectSortS time = 911ms
A_S>Конечно можно усреднить и посмотреть детальнее, но тенденция понятна.
A_S>Существуют ли какие-нибудь методы оптимизации? Или это плата за абстракцию?
Просто неправильно готовишь.
_____________________
С уважением,
Stanislav V. Zudin
Re[3]: Re[3]: std::map Вопрос по сортировки элементов
Здравствуйте, Anton_Savickiy, Вы писали: A_S>Я еще на курсах только... Все так плохо?
Да, нет. Вроде все на лету схватываете. Просто сразу видно, что Вы последовательно C++ еще не изучали. Поэтому почти каждый и посоветовал почитать учебник. Желательно с начала. Если изучаете самостоятельно, то попробуйте хотя бы какой-либо онлайн курс. На Coursera вроде был курс типа "C++ для программистов С".
Здравствуйте, Anton_Savickiy, Вы писали:
A_S>Хочется попробовать использовать библиотеку шаблонов и вот какой возник вопрос.
A_S>Вот теперь хотелось бы отсортировать такой массив по FILETIME. Не подскажите, как это лучше сделать средствами STL? Пошукав, обнаружил такой инструмент, как map<string, int> M; <ключ, значение>. Но применительно к моей задачи никак не соображу. Есть еще элемент list, посоветуйте пожалуйста решение?
для сортировки есть sort.
also попробуйте прочитать учебник по программированию.
Здравствуйте, Abyx, Вы писали:
A>Здравствуйте, Anton_Savickiy, Вы писали:
A_S>>Хочется попробовать использовать библиотеку шаблонов и вот какой возник вопрос.
A_S>>Вот теперь хотелось бы отсортировать такой массив по FILETIME. Не подскажите, как это лучше сделать средствами STL? Пошукав, обнаружил такой инструмент, как map<string, int> M; <ключ, значение>. Но применительно к моей задачи никак не соображу. Есть еще элемент list, посоветуйте пожалуйста решение?
A>для сортировки есть sort. A>also попробуйте прочитать учебник по программированию.
Я согласен с тоном Вашего ответа, попробую еще раз.
#define NUM 100000
int A[NUM];
for(int i=0;i<NUM;i++) A[i]=(int)rand();
vector<int> v(A,A+NUM);
sort(v.begin(),v.end());
Вот так мне понятно, т е в случае вектора, а если вместо вектора будет массив структур и мне нужно отсортировать по определенному элементу?
Как накормить STL? Чтобы сортировать FILETIME я бы использовал CompareFileTime? Как внутри шаблона это можно реализовать?
Здравствуйте, Anton_Savickiy, Вы писали:
A_S>Здравствуйте, Abyx, Вы писали:
A>>Здравствуйте, Anton_Savickiy, Вы писали:
A_S>>>Хочется попробовать использовать библиотеку шаблонов и вот какой возник вопрос.
A_S>>>Вот теперь хотелось бы отсортировать такой массив по FILETIME. Не подскажите, как это лучше сделать средствами STL? Пошукав, обнаружил такой инструмент, как map<string, int> M; <ключ, значение>. Но применительно к моей задачи никак не соображу. Есть еще элемент list, посоветуйте пожалуйста решение?
A>>для сортировки есть sort. A>>also попробуйте прочитать учебник по программированию.
A_S>Я согласен с тоном Вашего ответа, попробую еще раз.
A_S>#define NUM 100000
A_S>int A[NUM]; A_S>for(int i=0;i<NUM;i++) A[i]=(int)rand();
A_S>vector<int> v(A,A+NUM); A_S>sort(v.begin(),v.end());
A_S>Вот так мне понятно, т е в случае вектора, а если вместо вектора будет массив структур и мне нужно отсортировать по определенному элементу? A_S>Как накормить STL? Чтобы сортировать FILETIME я бы использовал CompareFileTime? Как внутри шаблона это можно реализовать?
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Здравствуйте, Anton_Savickiy, Вы писали:
A_S>>Хочется попробовать использовать библиотеку шаблонов и вот какой возник вопрос.
A_S>>Есть что-то типа вот такого:
A_S>>typedef struct A_S>>{ A_S>> FILETIME ft; A_S>> DATA data; A_S>>}DATA_FROM;
A_S>>DATA_FROM df[1000];
A_S>>Вот теперь хотелось бы отсортировать такой массив по FILETIME. Не подскажите, как это лучше сделать средствами STL? Пошукав, обнаружил такой инструмент, как map<string, int> M; <ключ, значение>. Но применительно к моей задачи никак не соображу. Есть еще элемент list, посоветуйте пожалуйста решение?
SVZ>std::map это контейнер, а не средство сортировки (да, в нем элементы лежат упорядоченно).
SVZ>Для сортировки есть std::sort. SVZ>Чтобы его применить можно: SVZ>1. Определить operator< для DATA_FROM. SVZ>Тогда вызов будет таким:
SVZ>
On 10.03.2014 14:32, Anton_Savickiy wrote:
> Я согласен с тоном Вашего ответа, попробую еще раз. > > #define NUM 100000 > > int A[NUM]; > for(int i=0;i<NUM;i++) A[i]=(int)rand(); > > vector<int> v(A,A+NUM); > sort(v.begin(),v.end()); > > Вот так мне понятно, т е в случае вектора, а если вместо вектора будет > массив структур и мне нужно отсортировать по определенному элементу? > Как накормить STL?
Здравствуйте, Serg27, Вы писали:
S>Здравствуйте, Anton_Savickiy, Вы писали: A_S>>Я еще на курсах только... Все так плохо? S>Да, нет. Вроде все на лету схватываете. Просто сразу видно, что Вы последовательно C++ еще не изучали. Поэтому почти каждый и посоветовал почитать учебник. Желательно с начала. Если изучаете самостоятельно, то попробуйте хотя бы какой-либо онлайн курс. На Coursera вроде был курс типа "C++ для программистов С".
Спасибо большое за рекомендации, посмотрю какой-нибудь онлайн курс. С++ для меня в мере, которой заложил его Страуструпп, неизведан.
Да и запутал я, как вижу по ответам, да и сам запутался. Поэтому, собственно и создал тему.
Заметил, наверное, ожидаемую плату за абстракцию.
1)Попробовал отсортировать массив базового типа int.
#define NUM 10000
vector<int> vecX(arr,arr+NUM);
sort(vecX.begin(), vecX.end());
и отсортировал обычной сортировкой вставками, так сказать в лоб.
#define NUM 10000
void selectSort(int* ptr,int size)
{
int tmp, i, j, pos;
for(i = 0; i < size; ++i)
{
pos = i;
tmp = ptr[i];
for(j = i + 1; j < size; ++j)
{
if (ptr[j] < tmp)
{
pos = j;
tmp = ptr[j];
}
}
ptr[pos] = ptr[i];
ptr[i] = tmp;
}
}
selectSort(arr,NUM);
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Здравствуйте, Anton_Savickiy, Вы писали:
A_S>>2) А теперь отсортируем структуры.
A_S>>a) STL A_S>>
A_S>>struct sort_rule
A_S>>{
A_S>> bool operator() (DATA_C i, DATA_C j)// <-- Замени передачу по значению на ссылки
SVZ> bool operator() (const DATA_C& i, const DATA_C& j) const// <-- Вот так
SVZ> {
SVZ> return (CompareFileTime(&i.ft,&j.ft) < 0);
SVZ> }
A_S>>} sort_object;
A_S>>
A_S>>А вот тут уже результат совсем другой. Да, сортируются всегда одинаковые массивы.
A_S>>STL time = 1209ms A_S>>selectSortS time = 911ms
A_S>>Конечно можно усреднить и посмотреть детальнее, но тенденция понятна.
A_S>>Существуют ли какие-нибудь методы оптимизации? Или это плата за абстракцию? SVZ>Просто неправильно готовишь.
#1 — Функтор имеет смысл использовать тогда, когда требуется хранить состояние или какие-то данные для сортировки. Например, упорядочить надо по данным, которых нет внутри DATA_C. Тогда внутри функтора можно хранить указатель на внешние данные. В данном случае можно обойтись функцией сравнения (тупо меньше кода ).
Еще один прием: если элементы коллекции очень "тяжелые" и их копирование может быть накладным, либо требуется сортировка по разным критериям, то стоит сортировать индексы элементов. Заводится отдельный массив, в который складываются индексы от 0 до NUM:
std::vector<int> indexes(NUM);
for(int i = 0; i < NUM; ++i) // Можно использовать std::generate
indexes[i] = i;
class Comparator
{
public:
Comparator(const vector<DATA_C>* vecObj) : m_vecObj(vecObj) {}
bool operator()(int lv, int rv) const
{
return CompareFileTime(&(*m_vecObj)[lv].ft, &(*m_vecObj)[rv].ft);
}
private:
const vector<DATA_C>* m_vecObj; // <-- В принципе можно использовать ссылку, а не указатель
};
std::sort(indexes.begin(), indexes.end(), Comparator(&vecObj)); // <-- Можно обойтись временным объектом компаратора
// Обход по упорядоченным элементам:for(std::vector<int>::const_iterator it = indexes.begin(), itE = indexes.end(); it != itE; ++it)
{
DoSomething( vecObj[*it]);
}
Т.к. это С++, а не С, то нет необходимости возиться с memcpy (за исключением определенных экзотических случаев).
Копировать структуры можно как обычные переменные:
А если делать совсем правильно, то нет смысла многократно перезаписывать tmp, достаточно сохранять индекс.
void selectSortS(DATA_C* ptr,int size)
{
int idx;
for(int i=0;i<size;++i)
{
idx = i;
for(int j=i+1;j<size;++j) // Для каждого последующего элемента
{
if(CompareFileTime(&ptr[j].ft,&ptr[idx].ft) < 0) // Если найден элемент меньше текущего
{
idx = j; // Запомнить индекс
}
}
if (i != idx) // Обменять местами
std::swap(ptr[idx], ptr[i]);
}
}
_____________________
С уважением,
Stanislav V. Zudin
SVZ>#1 — Функтор имеет смысл использовать тогда, когда требуется хранить состояние или какие-то данные для сортировки. Например, упорядочить надо по данным, которых нет внутри DATA_C. Тогда внутри функтора можно хранить указатель на внешние данные. В данном случае можно обойтись функцией сравнения (тупо меньше кода ).
SVZ>Еще один прием: если элементы коллекции очень "тяжелые" и их копирование может быть накладным, либо требуется сортировка по разным критериям, то стоит сортировать индексы элементов. Заводится отдельный массив, в который складываются индексы от 0 до NUM:
SVZ>
SVZ>std::vector<int> indexes(NUM);
SVZ>for(int i = 0; i < NUM; ++i) // Можно использовать std::generate
SVZ> indexes[i] = i;
SVZ>class Comparator
SVZ>{
SVZ> public:
SVZ> Comparator(const vector<DATA_C>* vecObj) : m_vecObj(vecObj) {}
SVZ> bool operator()(int lv, int rv) const
SVZ> {
SVZ> return CompareFileTime(&(*m_vecObj)[lv].ft, &(*m_vecObj)[rv].ft);
SVZ> }
SVZ> private:
SVZ> const vector<DATA_C>* m_vecObj; // <-- В принципе можно использовать ссылку, а не указатель
SVZ>};
SVZ>std::sort(indexes.begin(), indexes.end(), Comparator(&vecObj)); // <-- Можно обойтись временным объектом компаратора
SVZ>// Обход по упорядоченным элементам:
SVZ>for(std::vector<int>::const_iterator it = indexes.begin(), itE = indexes.end(); it != itE; ++it)
SVZ>{
SVZ> DoSomething( vecObj[*it]);
SVZ>}
SVZ>
SVZ>Т.к. это С++, а не С, то нет необходимости возиться с memcpy (за исключением определенных экзотических случаев). SVZ>Копировать структуры можно как обычные переменные:
SVZ>
SVZ>А если делать совсем правильно, то нет смысла многократно перезаписывать tmp, достаточно сохранять индекс.
SVZ>
SVZ>void selectSortS(DATA_C* ptr,int size)
SVZ>{
SVZ> int idx;
SVZ> for(int i=0;i<size;++i)
SVZ> {
SVZ> idx = i;
SVZ> for(int j=i+1;j<size;++j) // Для каждого последующего элемента
SVZ> {
SVZ> if(CompareFileTime(&ptr[j].ft,&ptr[idx].ft) < 0) // Если найден элемент меньше текущего
SVZ> {
SVZ> idx = j; // Запомнить индекс
SVZ> }
SVZ> }
SVZ> if (i != idx) // Обменять местами
SVZ> std::swap(ptr[idx], ptr[i]);
SVZ> }
SVZ>}
SVZ>
Спасибо Станислав за критику и рекомендации.
Забавный пример с очень "тяжелыми" данными, но его нужно обмозговать, с ходу как то не очень.
Ваша оптимизация selectSortS дала еще 200мс выигрыша.
Re[7]: std::map Вопрос по сортировки элементов
От:
Аноним
Дата:
12.03.14 11:24
Оценка:
Здравствуйте, Anton_Savickiy, Вы писали:
A_S>Спасибо Станислав за критику и рекомендации. A_S>Забавный пример с очень "тяжелыми" данными, но его нужно обмозговать, с ходу как то не очень. A_S>Ваша оптимизация selectSortS дала еще 200мс выигрыша.
А еще есть различные инструменты для программистов. В частности, одни их них профилировщиками называются. Их используют, чтобы найти узкие места в программе и оптимизировать код.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Anton_Savickiy, Вы писали:
A_S>>Спасибо Станислав за критику и рекомендации. A_S>>Забавный пример с очень "тяжелыми" данными, но его нужно обмозговать, с ходу как то не очень. A_S>>Ваша оптимизация selectSortS дала еще 200мс выигрыша. А>А еще есть различные инструменты для программистов. В частности, одни их них профилировщиками называются. Их используют, чтобы найти узкие места в программе и оптимизировать код.
).