Efficiency Question
I'm working with what is essentially an excel file, in the sense that it has rows and a defined number of columns. I am currently holding each column in separate vectors. The columns are of different data types. The principle task I do with this data is a multilevel sort, e.g. I sort on column 1 first and then on column 2, etc. I sort in place with an adapted quick sort algorithm I wrote, which works fine.
Alternatively, I could hold each row as a struct and just sort pointers to the structs. I could use the STL sort function, for this, by passing it appropriate compare objects. However, I am concerned about efficiency. I know I save a lot 'copy and paste' operations while sorting in place because I'll be moving a pointer around instead of the whole row, but I will also be going through a pointer to accesses fields for comparisons as opposed to accessing the value directly through an index.
Consider that I will have 500k to millions of rows and each row has 11 fields, 4 integers, 6 strings of basically const length and one char. I would be sorting based on three columns.
I want to make this change because the code will me much more simple and will probably scale better. Can you tell if it would be any less efficient based on how I described it?
Alternatively, I could hold each row as a struct and just sort pointers to the structs. I could use the STL sort function, for this, by passing it appropriate compare objects. However, I am concerned about efficiency. I know I save a lot 'copy and paste' operations while sorting in place because I'll be moving a pointer around instead of the whole row, but I will also be going through a pointer to accesses fields for comparisons as opposed to accessing the value directly through an index.
Consider that I will have 500k to millions of rows and each row has 11 fields, 4 integers, 6 strings of basically const length and one char. I would be sorting based on three columns.
I want to make this change because the code will me much more simple and will probably scale better. Can you tell if it would be any less efficient based on how I described it?
| I will also be going through a pointer to accesses fields for comparisons as opposed to accessing the value directly through an index. |
You will probably find the difference indistingusihable, although the pointer case is slightly faster.
To find the next element:
Index case:
@next_element = @array_base + (indx * sizeof(struct)) + offsetof(element)
pointer case:
@next_element = @pointer_to_struct + sizeof(struct) + offsetof(element)
Topic archived. No new replies allowed.