Problem: vector, algorithm

[eye51]

Hi,

I have a requirement of arranging a vector in given format,

Let say, I have an vector like this:

vector<int> VEC;
VEC.resize(16);

Values are:
7 5 10 17
5 2 9 10
17 10 15 25
10 9 11 15

Now I want to get unique indixes out like this:

2 5 7 9 10 11 15 17 25

and have them indexed starting from 0 like this:

2 5 7 9 10 11 15 17 25
| | | | | | | | |
0 1 2 3 4 5 6 7 8

then corrsponding to this new index system, I want my original VEC according to new indexes.

2 1 4 7
1 0 3 4
7 4 6 8
4 3 5 6

This is just an example, but it may extend to a very large VEC size.
Can anybody please suggest any efficient way of doing it?

Awaiting reply.
Thank you very much.

--
eye51

[hamsterman]

copy, std::sort(), std::unique() and then for each element in the original, find it in the copy. To make the finding part faster, you could implement a binary search algorithm, since the copy is sorted. You could also construct a map out of the copy and let it take care of binary search.

[onur]

I'd try this it this way (not tested, may not even compile):

typedef std::map<int, std::vector<int> > MyMapType;
MyMapType MAP; // maps values to indices
for (int i = 0; i < VEC.size(); ++i)
{
  MAP[VEC[i]].push_back(i);
}  

int idx = 0;
std::map<int,int> indicesMap; // to store the old index-> new index relation

for (MyMapType::const_iterator it = MAP.begin(); it != MAP.end(); ++it, ++idx)
{
  std::vector<int>& curVec = it->second;
  for (std::vector<int>::const_iterator jt = curVec .begin(); jt != curVec.end(); ++jt)
  {
    VEC[*jt] = idx;
  }
  // store the relation 2->0, 5->1, 7->2 in a map:
 indicesMap[it->first] = idx;
}

VEC now contains the values 2 1 4 7 ...
indicesMap the pairs (2->0), (5->1), (7->2) ...

[jsmith]

Well, the least amount of code to do that would be this:

std::set<int> s( VEC.begin(), VEC.end() );
VEC.assign( s.begin(), s.end() );

but if this is for homework, that probably won't fly, because you'll be expected to
implement some of these algorithms yourself.

[pushpik]

this problem aint that hard..try it yourself first..if you find any problem then ask

[eye51]

Hi Hamsterman, Onur, Jsmith,

Thanks for your all replies.

I tried Onur's concept and it worked well for a small case I took. But when the VEC size went upto 100 000, it simply hanged because of lot of memory allocation and I had to forcibly stop it. As a result, I feel "map" is not an option for this.

Also, just to check the efficiency, I tried just sort, unique for that VEC. But it took seem to take lot of time, but less compared to "map".

This thing actually is very important part for gaining efficiency. This is mainly to be used to assign array for opengl vertex array.

Can you please further guide me in this? Any other efficient way of doing it.

Thank you and thank you very much for your replies.

--
eye51

[hamsterman]

I doubt there is a faster way to remove copies than sort() and unique(). I have doubts about the other part. Though why do you need this? Perhaps a different approach to your problem might be more efficient.

[eye51]

Hi hamsterman,

Thanks for reply.

My VEC is not from 0 to N but its an intermediate random array from which I need to find sorted unique indices and the according to this, I need to find corresponding connectivity indices.

I do not know other solutions but to use standard stl functions. And these seem slower.

Anyway, any other idea from your side is welcome.

thanks

--
eye51

[hamsterman]

To assign one value to another will require some sort of map. If you know the range of the incorrect values, you could

int map[max_incorrect] = {0};
for i = 0 to copy_size
   map[ copy[i] ] = i;

for i = 0 to original_size
   original[i] = map[ original[i] ];

If not you'll have to use std::map. Unless you're willing to implement your own binary search (not hard).

But the real question is, how did that array get so messed up in the first place?

[simeonz]

I can't address specifically your application, but this is the solution I would try for the problem you defined originally. It is very cache oblivious, so it may be seen as inferior to some cache aware strategy, but I did what I could without trying to go in such deep waters.

EDIT: Removed the comments, because it makes the source unreadable. Will paste them back if necessary.

#include <iostream>
#include <algorithm>

using namespace std;

struct Generator {

    int m_current;

    Generator(int start) : m_current(start) {}

    int operator()() {return m_current++;}
};

template <size_t N>
struct Comparator : public binary_function<int,int,bool> {

    int (& m_a)[N];

    Comparator(int (& a) [N]) : m_a(a) {}

    bool operator() (const int& i, const int& j)
    {
        return m_a[i] < m_a[j];
    }
};

template <size_t N>
inline Comparator<N> comparator(int (& a)[N])
{
    return Comparator<N>(a);
}

template <size_t N>
struct Printer {

    int (& m_a)[N];

    Printer(int (& a) [N]) : m_a(a) {}

    void operator() (const int& i)
    {
        cout << i << ' ' << m_a[i] << endl;
    }
};

template <size_t N>
inline Printer<N> printer(int (& a)[N])
{
    return Printer<N>(a);
}

#define ARRAY_SIZE(array) (sizeof((array))/sizeof((array[0])))

template <typename T, size_t N>
inline size_t array_size(T (& a)[N]) { return N; }

template <typename T, int N>
inline T* array_begin(T (& a)[N]) { return &a[0]; }

template <typename T, int N>
inline T* array_end(T (& a)[N]) { return &a[N]; }

int main()
{
    
    int u[] = {1, 5, 4, 2, 3, 4, 4, 3, 5};
    int v[ARRAY_SIZE(u)];
	
    generate_n(&v[0], array_size(v), Generator(0));
    sort(array_begin(v), array_end(v), comparator(u));
    for_each(array_begin(v), array_end(v), printer(u));
    
    int old_value = u[v[0]];
    u[v[0]] = 0;
    v[0] = old_value;
    int unique = 0;

    for (int i = 1; i < (int)array_size(v); ++i)
    {
        int &new_value = u[v[i]];

        if (new_value != old_value)
        {
            ++unique;
            v[unique] = new_value;
            old_value = new_value;
        }
        
        new_value = unique;
    }
	
    ++unique;

    cout << endl;
    for_each(array_begin(u), array_end(u), printer(v));
    cout << endl;

    cout << "Uniques: " << unique;
}

[hamsterman]

neat!

[simeonz]

glad you like it >:)

[eye51]

Hi simeonz, hamsterman, jsmith, onur,

Thanks for your all replies.

I could use both approaches, with vector/map and with simeonz's code. Both of these approaches worked well.

It was nice doing and learning these things from you guys.

Thanks once again to all.

--
eye51