Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Здравствуйте, Anton_Savickiy, Вы писали:
SVZ>Не удержусь, еще немного покритикую.
A_S>>a) STL
A_S>>A_S>>struct DATA
A_S>>{
A_S>> int cmd;
A_S>> float var;
A_S>>};
A_S>>struct DATA_C
A_S>>{
A_S>> FILETIME ft;
A_S>> DATA dt[1000];
A_S>>};
A_S>>struct sort_rule
A_S>>{
A_S>> bool operator() (DATA_C i, DATA_C j)
A_S>> {return (CompareFileTime(&i.ft,&j.ft)==-1) ? true:false;}
A_S>>} sort_object;
A_S>>DATA_C d[NUM];
A_S>>SYSTEMTIME st;
A_S>>GetLocalTime(&st);
A_S>>for(int i=0;i<NUM;i++)
A_S>>{
A_S>> st.wMilliseconds = (WORD)rand()%1000;
A_S>> SystemTimeToFileTime(&st,&d[i].ft);
A_S>>}
A_S>>vector<DATA_C> vecObj(d,d+NUM);
A_S>>sort(vecObj.begin(), vecObj.end(),sort_object); // #1
A_S>>
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>
A_S>>A_S>>void selectSortS(DATA_C* ptr,int size)
A_S>>{
A_S>> DATA_C tmp;
A_S>> int idx;
A_S>> for(int i=0;i<size;++i)
A_S>> {
A_S>> idx = i;
A_S>> memcpy(&tmp,&ptr[i],sizeof(DATA_C));
A_S>> for(int j=i+1;j<size;++j)
A_S>> {
A_S>> if(CompareFileTime(&ptr[j].ft,&tmp.ft)==-1)
A_S>> {
A_S>> idx = j;
A_S>> memcpy(&tmp,&ptr[j],sizeof(DATA_C));
A_S>> }
A_S>> }
A_S>> memcpy(&ptr[idx],&ptr[i],sizeof(DATA_C));
A_S>> memcpy(&ptr[i],&tmp,sizeof(DATA_C));
A_S>> }
A_S>>}
A_S>>
SVZ>Т.к. это С++, а не С, то нет необходимости возиться с memcpy (за исключением определенных экзотических случаев).
SVZ>Копировать структуры можно как обычные переменные:
SVZ>A_S>> memcpy(&ptr[idx],&ptr[i],sizeof(DATA_C));
A_S>> memcpy(&ptr[i],&tmp,sizeof(DATA_C));
SVZ> ptr[idx] = ptr[i];
SVZ> ptr[i] = tmp;
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мс выигрыша.
