Отсортировать матрицу, представленную как одномерный массив по одной из координат
Такая задача.
Есть класс, в котором определена матрица NxM в виде одномерного массива в контейнере vector.
в каждой строки матрицы хранится n-мерные координаты некоторого объекта типа x1,x2,x3,xn,v1,v2,v3,vn
Требуется отсортировать этот одномерный массив по одной из координат, например по координате x2.
Т.е. нужно переставить строки этой матрицы таким образом, чтобы в каждой строке x2 (второй элемент строки) возрастал. Т.е. сверху матрицы были строки с меньшим вторым элементом, а снизу с большим.
Приходится обрабатывать огромные массивы данных, поэтому скорость и экономия памяти в данной задаче критична. По этому как инструмент сортировки были выбраны стандартные std:sort либо stdlib qsort.
Так же хочу обратить внимание на то что данная матрица представлена в виде ОДНОмерного массива и досуп к n-му элементу m-ой строки в матрице NxM осуществляется как не A[m][n], а вот так A[m*N+n]. Это сделано в целях упрощения задачи и экономии памяти.
Итак, требуется реализовать сортировку матрицы с помощью либо std::sort, либо stdlib qsort, с заданным параметром сортировки (по какому значению сортировать). и реализовать её надо полностью как метод класса.
Вот что сейчас получилось:
На данный момент этот код работает, но мне необходимо передавать как параметр по какому элементу производить сортировку, и сообщать каким то образом этот параметр компаратору sort_func.
через промежуточное прайват свойство класса не получится, т.к. компаратор является статическим членом класса.
Не статическим членом класса его делать не получается, а выносить из класса его не следует по условиям задачи.
Попробовал реализовать компаратор sort_func функтором, чтобы передавать параметр сортировки через свойство функтора, но qsort функторы (оно и понятно:-)) совсем не ест.
Подскажите пожалуйста уважаемые форумчани, как мне быть в этой ситуации? как все таки передавать этот параметр сортировки.
И еще. На самом деле, в контексте C++ я с большей радостью, как это и положено использовал бы для сортировки std::sort, и заодно тем самым решил бы проблему с параметром и увеличил производительность. Но я не могу придумать как применить std::sort применительно к данной задачи не распихивая строки матрицы по отдельным контейнерам.
Ведь у меня матрица представлена одномерным массивом.
В qsort я меняю местами блоки памяти заданной длинны, например sizeof(Tfloat)*dimension*2.
а в std::sort мне не указать какими блоками памяти мне оперировать, он сортирует не блоки памяти а элементы массива.
Может подскажите как мне применить std::sort к данной задачи?
Заранее всех благодарю!
Есть класс, в котором определена матрица NxM в виде одномерного массива в контейнере vector.
в каждой строки матрицы хранится n-мерные координаты некоторого объекта типа x1,x2,x3,xn,v1,v2,v3,vn
Требуется отсортировать этот одномерный массив по одной из координат, например по координате x2.
Т.е. нужно переставить строки этой матрицы таким образом, чтобы в каждой строке x2 (второй элемент строки) возрастал. Т.е. сверху матрицы были строки с меньшим вторым элементом, а снизу с большим.
Приходится обрабатывать огромные массивы данных, поэтому скорость и экономия памяти в данной задаче критична. По этому как инструмент сортировки были выбраны стандартные std:sort либо stdlib qsort.
Так же хочу обратить внимание на то что данная матрица представлена в виде ОДНОмерного массива и досуп к n-му элементу m-ой строки в матрице NxM осуществляется как не A[m][n], а вот так A[m*N+n]. Это сделано в целях упрощения задачи и экономии памяти.
Итак, требуется реализовать сортировку матрицы с помощью либо std::sort, либо stdlib qsort, с заданным параметром сортировки (по какому значению сортировать). и реализовать её надо полностью как метод класса.
Вот что сейчас получилось:
Код:
template <typename Tfloat>
class particle_beem
{
public:
vector <Tfloat> arr;
particle_beem(int dim, int count_el);
~particle_beem();
int resize(int count_el);
int set_dim(int dim);
int data_create_rand(Tfloat dXmin, Tfloat dXmax, Tfloat dVmin, Tfloat dVmax);
int data_write_to_file(const char *cFile_name);
int data_read_from_file(const char *cFile_name);
int data_sort_by_coordinate(/*тут необходимо передавать как параметр, по какому элементу сортировать*/);
protected:
private:
int dimension;
int count_eliments;
static int sort_func(const void *a, const void *b)
{
Tfloat* a1=(Tfloat*) a;
Tfloat* b1=(Tfloat*) b;
//cout<<"sort:"<<a1[2]<<" "<<b1[2]<<endl;
return a1[1] - b1[1]; //1 - это по какому элементу идет сортировка, т.е. по второму
}
};
//....всякий код....
template <typename Tfloat>
int particle_beem<Tfloat>::data_sort_by_coordinate()
{
qsort(&arr[0], count_eliments, sizeof(Tfloat)*dimension*2, sort_func);
return 0;
}
class particle_beem
{
public:
vector <Tfloat> arr;
particle_beem(int dim, int count_el);
~particle_beem();
int resize(int count_el);
int set_dim(int dim);
int data_create_rand(Tfloat dXmin, Tfloat dXmax, Tfloat dVmin, Tfloat dVmax);
int data_write_to_file(const char *cFile_name);
int data_read_from_file(const char *cFile_name);
int data_sort_by_coordinate(/*тут необходимо передавать как параметр, по какому элементу сортировать*/);
protected:
private:
int dimension;
int count_eliments;
static int sort_func(const void *a, const void *b)
{
Tfloat* a1=(Tfloat*) a;
Tfloat* b1=(Tfloat*) b;
//cout<<"sort:"<<a1[2]<<" "<<b1[2]<<endl;
return a1[1] - b1[1]; //1 - это по какому элементу идет сортировка, т.е. по второму
}
};
//....всякий код....
template <typename Tfloat>
int particle_beem<Tfloat>::data_sort_by_coordinate()
{
qsort(&arr[0], count_eliments, sizeof(Tfloat)*dimension*2, sort_func);
return 0;
}
через промежуточное прайват свойство класса не получится, т.к. компаратор является статическим членом класса.
Не статическим членом класса его делать не получается, а выносить из класса его не следует по условиям задачи.
Попробовал реализовать компаратор sort_func функтором, чтобы передавать параметр сортировки через свойство функтора, но qsort функторы (оно и понятно:-)) совсем не ест.
Подскажите пожалуйста уважаемые форумчани, как мне быть в этой ситуации? как все таки передавать этот параметр сортировки.
И еще. На самом деле, в контексте C++ я с большей радостью, как это и положено использовал бы для сортировки std::sort, и заодно тем самым решил бы проблему с параметром и увеличил производительность. Но я не могу придумать как применить std::sort применительно к данной задачи не распихивая строки матрицы по отдельным контейнерам.
Ведь у меня матрица представлена одномерным массивом.
В qsort я меняю местами блоки памяти заданной длинны, например sizeof(Tfloat)*dimension*2.
а в std::sort мне не указать какими блоками памяти мне оперировать, он сортирует не блоки памяти а элементы массива.
Может подскажите как мне применить std::sort к данной задачи?
Заранее всех благодарю!
Так же хочу обратить внимание на то что данная матрица представлена в виде ОДНОмерного массива и досуп к n-му элементу m-ой строки в матрице NxM осуществляется как не A[m][n], а вот так A[m*N+n]. Это сделано в целях упрощения задачи и экономии памяти.
В случае применения std::sort это не упрощение. Вектор векторов вам проще было-бы сортировать. А экономия памяти с чего?
Можно что-то в таком роде:
Код:
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
template <typename Tfloat>
class particle_beem {
public:
vector < vector<Tfloat> > arr;
void data_sort_by_coordinate(int nn) {
sort_obj.n = nn;
sort(arr.begin(), arr.end(), sort_obj);
}
private:
struct functor_srt {
int n;
bool operator() (vector<Tfloat> a, vector<Tfloat> b) {
return (a[n] < b[n]);
}
} sort_obj;
};
#include <functional>
#include <algorithm>
using namespace std;
template <typename Tfloat>
class particle_beem {
public:
vector < vector<Tfloat> > arr;
void data_sort_by_coordinate(int nn) {
sort_obj.n = nn;
sort(arr.begin(), arr.end(), sort_obj);
}
private:
struct functor_srt {
int n;
bool operator() (vector<Tfloat> a, vector<Tfloat> b) {
return (a[n] < b[n]);
}
} sort_obj;
};
Приходится обрабатывать огромные массивы данных, поэтому скорость и экономия памяти в данной задаче критична. По этому как инструмент сортировки были выбраны стандартные std:sort либо stdlib qsort.
На самом деле для быстродействия вы радикального ничего не делаете. Перестановки крупных блоков сожрут все. Сортировать лучше номера блоков и лишь в конце по отсортированному порядку копировать матрицу. Но тут нужна доп. память. Думайте, что вам важней.
В связи со скоростью. В моем примере лучше конечно так:
Код:
bool operator() (const vector<Tfloat>& a, const vector<Tfloat>& b){
...
}
...
}