0

In my application I solve a geometric problem on a given list of points.

0 x0 y0
1 x1 y1
...

The solution file should contain a specific ordering of the points which are represented as a list of their indexes.

1
0
...

After solving the problem I have a result = std::vector<Point>() vector of point objects in a certain order as well as the original list of points as an original = std::vector<Point>() vector. Both vectors naturally have the same size. To generate the output file I go through the result vector and search for the index of the point in the original vector. This is quite inefficient because it does need O(n^2) time. As a slight improvement I do the following:

std::ofstream out(filename);

std::vector<int> indices(instance.size);
std::iota(indices.begin(), indices.end(), 0);

for(auto &point : instance.result.points)
{
    for(std::size_t i=0; i<indices.size(); i++)
    {
        int id = indices[i];
        if(point == instance.points[id])
        {
            out << id << std::endl;
            indices.erase(indices.begin()+i);
            break;
        }
    }
}

out.close();

This allows me to not revisit the points that I already found before. Sadly for a 1 million point instance, this process exceeds my time limit and I don't want the export of my solution to take more time than solving the problem itself. Is there a way to efficiently get the indexes of a premutation of some vector in C++? The solution can use a lot of memory if desired.

michip96
  • 363
  • 3
  • 12
  • When solving the problem work with vector of indexes already, then you do not need to scan again. – Slava May 23 '19 at 17:04
  • Sadly this is not possible because I am using an external library which only accepts a given list of points. – michip96 May 23 '19 at 17:05
  • 2
    Then fill `std::unordered_map` and do lookup there. – Slava May 23 '19 at 17:06
  • Sadly the point object is not hashable. – michip96 May 23 '19 at 17:13
  • Why it is not hashable? If that is the point (which I hardly doubt), use `std::map` instead. Don't say they are not comparable – Slava May 23 '19 at 17:14
  • @Slava I get a static_assert failed due to requirement __check_hash_requirements. I know I can somehow provide my ohn hash function and I will try that if there is no better solution – michip96 May 23 '19 at 17:19
  • @Riddick I don't quite understand how to obtain the right indices, can you be more precise? – michip96 May 23 '19 at 17:19
  • Is your input list sorted? – Jarod42 May 23 '19 at 17:21
  • "and I will try that if there is no better solution" that's already a better and pretty simple solution. – Slava May 23 '19 at 17:22
  • Is it possible at all to know how the indices are transformed? Does your algorithm force you to lose all information about how the points are permuted, because if I understand correctly, you can carry a list of indices through the algorithm, then sort the original list based on that. – Riddick May 23 '19 at 17:27

2 Answers2

2

One of the simple to implement and quite efficient solution is to create a temporary std::unordered_map<Point,size_t> where key is the point and value is position inside original, then do lookup in that map. Details on how to use your (or library provided) data type as a key in std::unordered_map provided here

Slava
  • 43,454
  • 1
  • 47
  • 90
  • Yes, it does work indeed with an `std::map` as well as with an `std::unordered_map` when I implement the hash function myself. Both options fulfill my needs. Thank you! – michip96 May 23 '19 at 17:25
1

You can extend the Point structure to contain the original id, besides the position.

Paul92
  • 8,827
  • 1
  • 23
  • 37
  • For my specific task I dont have control over the point structure, because it is provided by an external library. – michip96 May 23 '19 at 17:07
  • But when I pass my custom structure to the external library it will automatically cut off the additional `size_t` or am I mistaken? – michip96 May 23 '19 at 17:20
  • Not necessarily. Can you share more details about the library you use/methods you call, if it's open source? Also, what is the Point type and what does it contain? It might be possible to extend it to add the index. – Paul92 May 23 '19 at 17:22
  • I'm using CGAL to perform some geometric operations. Therefore I'm using `Kernel::Point_2` for some (user-defined) kernel. The `std::map` solution does work good enough for me. Thank you anyways! – michip96 May 23 '19 at 17:27